2017-12-22 99 views
5

Tôi đã tìm thấy một vấn đề lập trình mà tôi không thể giải quyết được. Tôi đã được đặt một số A của số nguyên. Đối với tất cả các số x trong A, hãy tìm số nguyên dương nhỏ nhất y sao cho các số của x*y đang tăng hoặc giảm và sản phẩm x*y là nhỏ nhất có thể. Ví dụ: nếu A=(363, 726, 1089) thì n=(184573, 137588, 9182736455463728191) cung cấp các số (66999999, 99888888, 9999999999999999999999).Làm thế nào để tìm số nguyên dương nhỏ nhất để làm cho chữ số đơn điệu?

Nhưng có một số con số khó mà chương trình của tôi không giải quyết được. Tất cả các trường hợp được cho là

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 

Đây là chương trình chậm của tôi:

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))) 

Nó có thể giải quyết một số trường hợp trong một thời gian hợp lý:

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 

Second try:

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)) 

Điều này cung cấp cho đúng chính xác hơn va lues nhưng vẫn có kết quả đó không có ý nghĩa, như

5445 18365472910927456382001836547291092745638200183654729109274563820018365472910927456382001836547291092745638200183654729109274563820018365472910927456382001836547291092745638200183654729109274563820 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999 

Thứ ba thử: Tôi thấy rằng nếu tôi chia các trường hợp dễ dàng và cứng riêng biệt, tôi có thể giải quyết nhiều trường hợp:

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))) 

số Thiếu sau một thời gian: 5445, 6534, 7623, 8712, 9801.

Nhưng thuật toán đủ nhanh để giải quyết vấn đề cho tất cả đầu vào được đưa ra ở trên là gì?

+0

Nhận xét không dành cho thảo luận mở rộng; cuộc hội thoại này đã được [chuyển sang trò chuyện] (http: //chat.stackoverflow.com/rooms/161858/discussion-on-question-by-user2219896-how-to-find-nhỏ-dương-số nguyên-đến). –

Trả lời

1

Chúng tôi có thể thu hẹp không gian tìm kiếm đáng kể bằng cách quan sát rằng bất kỳ cơ số 10 số nguyên, y, được làm bằng phần riêng biệt, mỗi không thể ảnh hưởng đến chữ số bên phải của họ trong nhiều thức:

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

Ví dụ: lấy số 363 trong bài đăng của bạn. Các chữ số tận cùng bên phải trong chọn y mình đặt chữ số tận cùng bên phải trong nhiều thức:

3 * 363 = 1089 

Bây giờ chúng ta đã cố định một chữ số cho b_0, mà cũng sửa chữa các chữ số tận cùng bên phải trong trận chung kết x*y, và (khả năng) giới hạn của chúng tôi lựa chọn cho b_1. Nếu chúng tôi muốn một 9 người khác theo dõi, chúng tôi có:

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

Và cứ tiếp tục như vậy.

1

Tôi không chắc chắn về đầu ra của thuật toán của bạn, bằng cách này để có được các chữ số đơn điệu tiếp theo của một số N một thuật toán possibile là sau một:

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]])) 

Hãy thử nó trong này repl

Các vấn đề liên quan