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

问题描述 投票：5回答：2

我发现了一个无法解决的编程问题。我得到了一组整数的A。对于x中的所有数字A，找到最小的正整数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。

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

python python-3.x algorithm
2个回答
1
投票

我们可以通过观察任何基数为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

等等。

1
投票

我不确定你的算法的输出，通过获得数字N的下一个单调数字的方式，一个可能的算法是以下一个：

def nextMonotoneDigits(self, N):
        if N < 10: return N
        n, inv_index = N, -1
        num = [int(d) for d in str(n)[::-1]] 

        for i in range(1, len(num)): 
            if num[i] > num[i - 1] or (inv_index != -1 and num[inv_index] == num[i]):
                inv_index = i

        if inv_index == -1: return N

        for i in range(inv_index): num[i] = 9
        num[inv_index] -= 1

        return int(''.join([ str(i) for i in num[::-1]]))

试试这个repl

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.