python - 如何找到最小的正整数以使数字单调？-6ren

python - 如何找到最小的正整数以使数字单调？

转载作者：太空狗更新时间：2023-10-30 01:25:55

我发现了一个我无法解决的编程问题。我得到了一组 A 整数。对于A中的所有数字x，找到最小的正整数y使得x*y的数字是增加或减少，乘积 x*y 是可能的最小值。例如，如果 A=(363, 726, 1089) 那么 n=(184573, 137588, 9182736455463728191) 给出数字 (66999999, 99888888, 9999999999999999999999) 。

但是有一些我的程序没有解决的硬数字。所有情况都给出为

363 726 1089 1313 1452 1717 1798 1815 1919 2121 2156 2178 2189 2541 2626 2805
2904 2997 3131 3267 3297 3434 3630 3838 3993 4037 4092 4107 4191 4242 4257 4312
4334 4343 4356 4378 4407 4532 4646 4719 4747 4807 4949 5011 5055 5071 5082 5151
5214 5353 5423 5445 5454 5495 5610 5665 5731 5808 5819 5858 5951 5989 5994 6171
6248 6281 6429 6446 6468 6523 6534 6565 6567 6594 6721 6767 6868 6897 6919 7051
7077 7128 7139 7171 7227 7260 7381 7424 7474 7513 7623 7678 7831 7858 7878 7881
7909 7986 8041 8063 8074 8088 8107 8129 8162 8173 8184 8195 8214 8283 8316 8349
8382 8415 8453 8484 8514 8624 8649 8712 8756 8778 8814 8932 8987 8989 8990 8991
9053 9064 9075 9099 9101 9119 9141 9156 9191 9213 9251 9292 9309 9328 9361 9393
9438 9493 9515 9546 9595 9597 9603 9614 9667 9678 9757 9797 9801 9802 9834 9890
9898 9909

这是我的慢程序:

def find_smallest_increasing(number, length):
    ehd = -1
    num = "0"
    length += 1
    for one in range(0,length):
        for two in range(0,length-one):
            for three in range(0,length-one-two):
                for four in range(0,length-one-two-three):
                    for five in range(0,length-one-two-three-four):
                        for six in range(0,length-one-two-three-four-five):
                            for seven in range(0,length-one-two-three-four-five-six):
                                for eight in range(0,length-one-two-three-four-five-six-seven):
                                    for nine in range(0,length-one-two-three-four-five-six-seven-eight):
                                        if max(one,two,three,four,five,six,seven,eight,nine) > 0:
                                            num = "1"*one+"2"*two+"3"*three+"4"*four+"5"*five+"6"*six+"7"*seven+"8"*eight+"9"*nine
                                            if int(num) % number == 0:
                                                if ehd == -1:
                                                    ehd = int(num)
                                                if int(num) < ehd:
                                                    ehd = int(num)
    return(ehd)

def find_smallest_decreasing(number, length):
    ehd = -1
    num = "0"
    length += 1
    for one in range(0,length):
        for two in range(0,length-one):
            for three in range(0,length-one-two):
                for four in range(0,length-one-two-three):
                    for five in range(0,length-one-two-three-four):
                        for six in range(0,length-one-two-three-four-five):
                            for seven in range(0,length-one-two-three-four-five-six):
                                for eight in range(0,length-one-two-three-four-five-six-seven):
                                    for nine in range(0,length-one-two-three-four-five-six-seven-eight):
                                        for zero in range(0,length-one-two-three-four-five-six-seven-eight-nine):
                                            if max(one,two,three,four,five,six,seven,eight,nine) > 0:
                                                num = "9"*one+"8"*two+"7"*three+"6"*four+"5"*five+"4"*six+"3"*seven+"2"*eight+"1"*nine+"0"*zero
                                                if int(num) % number == 0:
                                                    if ehd == -1:
                                                        ehd = int(num)
                                                    if int(num) < ehd:
                                                        ehd = int(num)
    return(ehd)

numbers = [363,726,1089, 1313, 1452, 1717, 1798, 1815, 1919, 2121, 2156, 2178, 2189, 2541, 2626, 2805,
2904, 2997, 3131, 3267, 3297, 3434, 3630, 3838, 3993, 4037, 4092, 4107, 4191, 4242, 4257, 4312,
4334, 4343, 4356, 4378, 4407, 4532, 4646, 4719, 4747, 4807, 4949, 5011, 5055, 5071, 5082, 5151,
5214, 5353, 5423, 5445, 5454, 5495, 5610, 5665, 5731, 5808, 5819, 5858, 5951, 5989, 5994, 6171,
6248, 6281, 6429, 6446, 6468, 6523, 6534, 6565, 6567, 6594, 6721, 6767, 6868, 6897, 6919, 7051,
7077, 7128, 7139, 7171, 7227, 7260, 7381, 7424, 7474, 7513, 7623, 7678, 7831, 7858, 7878, 7881,
7909, 7986, 8041, 8063, 8074, 8088, 8107, 8129, 8162, 8173, 8184, 8195, 8214, 8283, 8316, 8349,
8382, 8415, 8453, 8484, 8514, 8624, 8649, 8712, 8756, 8778, 8814, 8932, 8987, 8989, 8990, 8991,
9053, 9064, 9075, 9099, 9101, 9119, 9141, 9156, 9191, 9213, 9251, 9292, 9309, 9328, 9361, 9393,
9438, 9493, 9515, 9546, 9595, 9597, 9603, 9614, 9667, 9678, 9757, 9797, 9801, 9802, 9834, 9890,
9898, 9909]

for k in range(0,len(numbers)):
    number = numbers[k]
    a = -1
    b = -1
    i= 1
    j= 1
    while a == -1:
        if a % 10 != 0:
            a = find_smallest_increasing(number,i)
        else:
            a = -1
        i = i + 1
    while b == -1:
        b = find_smallest_decreasing(number,max(i,j))
        j = j + 1
    print(str(number)+" "+str(min(a,b)/number)+" " + str(min(a,b)))

它可以在合理的时间内解决一些情况:

363 184573 66999999
726 137588 99888888
1089 9182736455463728191 9999999999999999999999
1313 16929 22227777
1452 68794 99888888
1717 12947 22229999
1798 12978 23334444
1815 550352 998888880
1919 11583 22227777
2121 15719 33339999
2156 30973 66777788
2178 45913682277318640955 99999999999999999999990
2189 507591 1111116699
2541 454939 1155999999
2626 12694 33334444
2805 35571 99776655
2904 34397 99888888
2997 333667 999999999
3131 10648 33338888
3267 69727578818487909397 227799999999999999999999
3297 20153 66444441
3434 22649 77776666

第二次尝试:

def generate_all_numbers(length):
    l = list()
    for one in range(0,length):
        for two in range(0,length-one):
            for three in range(0,length-one-two):
                for four in range(0,length-one-two-three):
                    for five in range(0,length-one-two-three-four):
                        for six in range(0,length-one-two-three-four-five):
                            for seven in range(0,length-one-two-three-four-five-six):
                                for eight in range(0,length-one-two-three-four-five-six-seven):
                                    for nine in range(0,length-one-two-three-four-five-six-seven-eight):
                                        for ten in range(0,length-one-two-three-four-five-six-seven-eight-nine):
                                            if max(one,two,three,four,five,six,seven,eight,nine) > 0:
                                                num1 = "1"*one+"2"*two+"3"*three+"4"*four+"5"*five+"6"*six+"7"*seven+"8"*eight+"9"*nine
                                                num2 = "9"*one+"8"*two+"7"*three+"6"*four+"5"*five+"4"*six+"3"*seven+"2"*eight+"1"*nine+"0"*ten
                                                l.append(int(num1)) 
                                                l.append(int(num2))
    return(list(set(l)))

numbers = [363,726,1089, 1313, 1452, 1717, 1798, 1815, 1919, 2121, 2156, 2178, 2189, 2541, 2626, 2805,
2904, 2997, 3131, 3267, 3297, 3434, 3630, 3838, 3993, 4037, 4092, 4107, 4191, 4242, 4257, 4312,
4334, 4343, 4356, 4378, 4407, 4532, 4646, 4719, 4747, 4807, 4949, 5011, 5055, 5071, 5082, 5151,
5214, 5353, 5423, 5445, 5454, 5495, 5610, 5665, 5731, 5808, 5819, 5858, 5951, 5989, 5994, 6171,
6248, 6281, 6429, 6446, 6468, 6523, 6534, 6565, 6567, 6594, 6721, 6767, 6868, 6897, 6919, 7051,
7077, 7128, 7139, 7171, 7227, 7260, 7381, 7424, 7474, 7513, 7623, 7678, 7831, 7858, 7878, 7881,
7909, 7986, 8041, 8063, 8074, 8088, 8107, 8129, 8162, 8173, 8184, 8195, 8214, 8283, 8316, 8349,
8382, 8415, 8453, 8484, 8514, 8624, 8649, 8712, 8756, 8778, 8814, 8932, 8987, 8989, 8990, 8991,
9053, 9064, 9075, 9099, 9101, 9119, 9141, 9156, 9191, 9213, 9251, 9292, 9309, 9328, 9361, 9393,
9438, 9493, 9515, 9546, 9595, 9597, 9603, 9614, 9667, 9678, 9757, 9797, 9801, 9802, 9834, 9890,
9898, 9909]

l = generate_all_numbers(20)
A = list()
for i in range(len(l)):
    for j in range(len(numbers)):
        if l[i] % numbers[j] == 0:
             A.append(l[i])
B = list()
for j in range(len(numbers)):
 best = int("9" * 20)
 for i in range(len(A)):
    if A[i] % numbers[j] == 0:
        if A[i] < best:
            best = A[i]
 print(str(numbers[j])+" "+str(best/numbers[j])+ " " + str(best))

这给出了更正确的值，但仍然有一些没有意义的结果，比如

5445 18365472910927456382001836547291092745638200183654729109274563820018365472910927456382001836547291092745638200183654729109274563820018365472910927456382001836547291092745638200183654729109274563820 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

第三次尝试:我发现如果我将简单和困难的案例分开，我可以解决更多的案例:

def generate_all_numbers(length):
    l = list()
    for one in range(0,length):
        for two in range(0,length-one):
            for three in range(0,length-one-two):
                for four in range(0,length-one-two-three):
                    for five in range(0,length-one-two-three-four):
                        for six in range(0,length-one-two-three-four-five):
                            for seven in range(0,length-one-two-three-four-five-six):
                                for eight in range(0,length-one-two-three-four-five-six-seven):
                                    for nine in range(0,length-one-two-three-four-five-six-seven-eight):
                                        for ten in range(0,length-one-two-three-four-five-six-seven-eight-nine):
                                            if max(one,two,three,four,five,six,seven,eight,nine) > 0:
                                                num1 = "1"*one+"2"*two+"3"*three+"4"*four+"5"*five+"6"*six+"7"*seven+"8"*eight+"9"*nine
                                                num2 = "9"*one+"8"*two+"7"*three+"6"*four+"5"*five+"4"*six+"3"*seven+"2"*eight+"1"*nine+"0"*ten
                                                l.append(int(num1)) 
                                                l.append(int(num2))
    return(list(set(l)))

def find_smallest_increasing(number, length):
    ehd = -1
    num = "0"
    length += 1
    for one in range(0,length):
        for two in range(0,length-one):
            for three in range(0,length-one-two):
                for four in range(0,length-one-two-three):
                    for five in range(0,length-one-two-three-four):
                        for six in range(0,length-one-two-three-four-five):
                            for seven in range(0,length-one-two-three-four-five-six):
                                for eight in range(0,length-one-two-three-four-five-six-seven):
                                    for nine in range(0,length-one-two-three-four-five-six-seven-eight):
                                        if max(one,two,three,four,five,six,seven,eight,nine) > 0:
                                            num = "1"*one+"2"*two+"3"*three+"4"*four+"5"*five+"6"*six+"7"*seven+"8"*eight+"9"*nine
                                            if int(num) % number == 0:
                                                if ehd == -1:
                                                    ehd = int(num)
                                                if int(num) < ehd:
                                                    ehd = int(num)
    return(ehd)

def find_smallest_decreasing(number, length):
    ehd = -1
    num = "0"
    length += 1
    for one in range(0,length):
        for two in range(0,length-one):
            for three in range(0,length-one-two):
                for four in range(0,length-one-two-three):
                    for five in range(0,length-one-two-three-four):
                        for six in range(0,length-one-two-three-four-five):
                            for seven in range(0,length-one-two-three-four-five-six):
                                for eight in range(0,length-one-two-three-four-five-six-seven):
                                    for nine in range(0,length-one-two-three-four-five-six-seven-eight):
                                        for zero in range(0,length-one-two-three-four-five-six-seven-eight-nine):
                                            if max(one,two,three,four,five,six,seven,eight,nine) > 0:
                                                num = "9"*one+"8"*two+"7"*three+"6"*four+"5"*five+"4"*six+"3"*seven+"2"*eight+"1"*nine+"0"*zero
                                                if int(num) % number == 0:
                                                    if ehd == -1:
                                                        ehd = int(num)
                                                    if int(num) < ehd:
                                                        ehd = int(num)
    return(ehd)

numbers = [363,726, 1313, 1452, 1717, 1798, 1815, 1919, 2121, 2156, 2189, 2541, 2626, 2805,
2904, 2997, 3131, 3297, 3434, 3630, 3838, 3993, 4037, 4092, 4107, 4191, 4242, 4257, 4312,
4334, 4343, 4378, 4407, 4532, 4646, 4719, 4747, 4807, 4949, 5011, 5055, 5071, 5082, 5151,
5214, 5353, 5423, 5454, 5495, 5610, 5665, 5731, 5808, 5819, 5858, 5951, 5989, 5994, 6171,
6248, 6281, 6429, 6446, 6468, 6523, 6565, 6567, 6594, 6721, 6767, 6868, 6897, 6919, 7051,
7077, 7128, 7139, 7171, 7227, 7260, 7381, 7424, 7474, 7513, 7678, 7831, 7858, 7878, 7881,
7909, 7986, 8041, 8063, 8074, 8088, 8107, 8129, 8162, 8173, 8184, 8195, 8214, 8283, 8316, 8349,
8382, 8415, 8453, 8484, 8514, 8624, 8649, 8756, 8778, 8814, 8932, 8987, 8989, 8990, 8991,
9053, 9064, 9075, 9099, 9101, 9119, 9141, 9156, 9191, 9213, 9251, 9292, 9309, 9328, 9361, 9393,
9438, 9493, 9515, 9546, 9595, 9597, 9603, 9614, 9667, 9678, 9757, 9797, 9802, 9834, 9890,
9898, 9909]

hardnumbers = [1089, 2178, 3267, 4356, 5445, 6534, 7623, 8712, 9801]

l = generate_all_numbers(20)
A = list()
for i in range(len(l)):
    for j in range(len(numbers)):
        if l[i] % numbers[j] == 0:
             A.append(l[i])
B = list()
for j in range(len(numbers)):
 best = int("9" * 2000)
 for i in range(len(A)):
    if A[i] % numbers[j] == 0:
        if A[i] < best:
            best = A[i]
 print(str(numbers[j])+" "+str(best/numbers[j])+ " " + str(best))

for k in range(0,len(hardnumbers)):
    number = hardnumbers[k]
    a = -1
    b = -1
    i= 1
    j= 1
    while a == -1:
        if a % 5 != 0:
            a = find_smallest_increasing(number,i)
        i = i + 1
    b = -1
    j = 1
    while b == -1:
        b = find_smallest_decreasing(number,max(i,j))
        j = j + 1
    print(str(number)+" "+str(min(a,b)/number)+" " + str(min(a,b)))

一段时间后丢失的号码是:5445、6534、7623、8712、9801。

但是对于上面给出的所有输入，什么是足够快的算法来解决问题呢？

最佳答案

我们可以通过观察任何以 10 为底的整数 y 由不同的部分组成来显着缩小搜索空间，每个部分都无法影响最终倍数中其右侧的数字:

y = b_n*10^n + b_(n-1)*10^(n-1) ... + b_0*10^0

例如，以您帖子中的数字 363 为例。所选 y 中最右边的数字单独设置最终倍数中最右边的数字:

3 * 363 = 1089

我们现在为 b_0 固定了一个数字，这也固定了最后一个 x*y 中最右边的数字，并且(可能)限制了我们对 的选择b_1。如果我们希望再有 9 个跟随，我们有:

b_1 * 3 + 8 = 9 (mod 10)
b_1 * 3 = 1 (mod 10)
b_1 = (10x + 1) / 3
b_1 = 7

等等。

关于python - 如何找到最小的正整数以使数字单调？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47947473/

文章推荐： c# - Luke Lucene BooleanQuery

文章推荐： python - 在 python 中测试非导出方法

文章推荐： c# - 用枚举参数化对象

文章推荐： VSCode 中未发现 Python 单元测试

jquery - 正/负最大值输入
我有一个加号/减号按钮，希望用户不能选择超过 20 个但不知道如何让它工作。我尝试使用 min="1"max="5 属性，但它们不起作用。这是我的代码和一个 fiddle 链接。https://jsf
r - ggplot2 正/负图无法清晰呈现
我正在尝试复制顶部底部图，如示例 here但它没有正确渲染(紫色系列有 +ve 和 -ve 值，绿色为负值)留下杂乱的人工制品。我也在努力创建一个玩具示例来复制这个问题，所以我希望尽管我缺乏数据，但有
google-maps - 正/负纬度和经度值与基本方向
已关闭。此问题不符合Stack Overflow guidelines 。目前不接受答案。这个问题似乎与 help center 中定义的范围内的编程无关。 . 已关闭 6 年前。社区去年审查了是
c++在添加两个绝对(正)值时得到负值
这个问题在这里已经有了答案: Adding two positive integers gives negative answer.Why? (4 个答案) 关闭 5 年前。我遇到了一个奇怪的问题
Java将负/正字符串数字转换为负/正 double
有谁知道如何将字符串值类型 -4,5 或 5,4 转换为 double -4.5 或 5.4? 最佳答案只需使用 Double.parseDouble(Locale, String); 糟糕，我很困
python - 在数据框中的新列中返回 TextBlob 正、负或中性分类
我正在尝试根据 TextBlob 分类插入一个仅包含“正”或“负”字符串的新数据框列:对于我的 df 的第一行，结果是 ( pos , 0.75, 0.2499999999999997)我想要' 正
VBA 循环根据相邻单元格更改单元格值(正/负)和字体颜色
我对 VBA 非常陌生，无法理解如何在一个循环中完成 2 个任务。我非常感谢您的帮助。我已经能够根据第 3 列中的数据更改第 2 列中的数值，但我不明白如何将负值的字体更改为红色。表格的大小每月都
jquery - 如何发送 "+"符号(加，正)
欢迎，我正在使用 jquery 通过 POST 发送表单。这就是我获得值(value)的方式。 var mytext = $("#textareaid").val(); var dataStrin
c# - 正 System.Double 值的快速下限和上限替代方案
double d = 0; // random decimal value with it's integral part within the range of Int32 and always p
javascript - 使用 Regex 正/负前瞻替换字符？
我有这个字符串: var a='abc123#xyz123'; 我想构建 2 个正则表达式替换函数: 1) 用 '*' 替换所有确实有 future '#'的字符(不包括'#') 所以结果应该是这样的
android - 如何将 DialogFragment 正/负按钮保留在软键盘上方
我正在使用 DialogFragment。当用户从 Gmail 平板电脑应用程序的屏幕与下面示例图片中的编辑文本进行交互时，我希望正面和负面按钮保持在键盘上方。在我的尝试中不起作用，这是我的 Dia
binary - 二进制补码； 0FFFFh 正，0FFFFh 负？
从组装艺术一书中，我复制了这句话: In the two’s complement system, the H.O. bit of a number is a sign bit. If the H.O
c++ - 基于数值(正、负、零)实现条件表达式的最佳方式
是否有更好更优雅的方法来实现下面的简单代码(diffYear、A 和 B 是数字): diffYear = yearA - yearB; if (diffYear == 0) { A = B
boolean true - 正 1 还是负 1？
我正在设计一种语言，并尝试确定 true 应该是 0x01 还是 0xFF。显然，所有非零值都将转换为 true，但我正在尝试确定确切的内部表示。每种选择的优点和缺点是什么？最佳答案没关系，只要
android - alertdialog 正/负按钮与全屏对话框 fragment 中的父级不匹配
在我的 dialogfragment 类的 OnCreateDialog 中，我正在这样做: AlertDialog.Builder builder = new AlertDialog.Builder
c++ - 正 lambda : '+[]{}' - What sorcery is this?
这个问题在这里已经有了答案: Resolving ambiguous overload on function pointer and std::function for a lambda usin
ios - 正 NSDecimalNumber 返回意外的 64 位整数值
我偶然发现了一个奇怪的 NSDecimalNumber 行为:对于某些值，调用 integerValue、longValue、longLongValue 等，返回意想不到的值(value)。示例: l
c++ - 正 lambda : '+[]{}' - What sorcery is this?
这个问题在这里已经有了答案: Resolving ambiguous overload on function pointer and std::function for a lambda using
regex - 匹配负/正 float/int 正则表达式 - 这是邪恶的吗？
我有这个正则表达式来测试用户输入是否有效: value.length === 0 || value === '-' || (!isNaN(parseFloat(value)) && /^-?\d+\.
matlab - 来自 matlab "fitgmdist"函数的不合理 [正] 对数似然值
我想用高斯混合模型拟合数据集，数据集包含大约 120k 个样本，每个样本有大约 130 个维度。当我使用 matlab 执行此操作时，我运行脚本(簇号为 1000): gm = fitgmdist(d

太空狗

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

python - 如何找到最小的正整数以使数字单调？