Tìm số hoạt động tối thiểu cần thiết để tính toán số sử dụng phạm vi số được chỉ định

Question

Hãy để tôi bắt đầu bằng ví dụ - Tôi có một số các số từ 1 đến 9. Và giả sử số mục tiêu mà tôi muốn là 29 Trong trường hợp này, số hoạt động tối thiểu được yêu cầu sẽ là (9 * 3) +2 = 2 hoạt động. Tương tự cho 18 số hoạt động tối thiểu là 1 (9 * 2 = 18). Tôi có thể sử dụng bất kỳ toán tử số học nào trong số 4 toán tử số học - +, -,/và *.

Làm cách nào tôi có thể tìm hiểu về số lượng hoạt động tối thiểu cần thiết? Cảm ơn trước vì đã được trợ giúp.

làm rõ: chỉ số nguyên, không có số thập phân nào được phép tính giữa. tức là những điều sau đây không hợp lệ (từ các bình luận dưới đây): ((9/2) + 1) * 4 == 22 Tôi phải thừa nhận rằng tôi không nghĩ kỹ về điều này, nhưng vì mục đích của tôi, vấn đề nếu số thập phân xuất hiện giữa tính toán. ((9/2) + 1) * 4 == 22 là hợp lệ. Xin lỗi vì sự nhầm lẫn.

Answer 1

Đối với trường hợp đặc biệt mà bộ Y = [1..9] và n> 0:

• n < = 9: 0 hoạt động
• n < = 18: 1 hoạt động (+)
• nếu không: Xóa bất kỳ ước số nào được tìm thấy trong Y. Nếu điều này là không đủ, hãy thực hiện đệ quy trên phần còn lại cho tất cả các dời gốc -9 .. +9. Offset 0 có thể được bỏ qua vì nó đã được thử.

Lưu ý cách phân chia không cần thiết trong trường hợp này. Đối với Y khác, điều này không giữ.

Thuật toán này là số mũ trong nhật ký (n). Các phân tích chính xác là một công việc cho ai đó với nhiều kiến ​​thức về đại số hơn I.

Để biết thêm tốc độ, hãy thêm cắt xén để loại bỏ một số tìm kiếm cho số lớn hơn.

Mẫu mã:

def findop(n, maxlen=9999): 
    # Return a short postfix list of numbers and operations 

    # Simple solution to small numbers 
    if n<=9: return [n] 
    if n<=18: return [9,n-9,'+'] 

    # Find direct multiply 
    x = divlist(n) 
    if len(x) > 1: 
     mults = len(x)-1 
     x[-1:] = findop(x[-1], maxlen-2*mults) 
     x.extend(['*'] * mults) 
     return x 

    shortest = 0 

    for o in range(1,10) + range(-1,-10,-1): 
     x = divlist(n-o) 
     if len(x) == 1: continue 
     mults = len(x)-1 

     # We spent len(divlist) + mults + 2 fields for offset. 
     # The last number is expanded by the recursion, so it doesn't count. 
     recursion_maxlen = maxlen - len(x) - mults - 2 + 1 

     if recursion_maxlen < 1: continue 
     x[-1:] = findop(x[-1], recursion_maxlen) 
     x.extend(['*'] * mults) 
     if o > 0: 
      x.extend([o, '+']) 
     else: 
      x.extend([-o, '-']) 
     if shortest == 0 or len(x) < shortest: 
      shortest = len(x) 
      maxlen = shortest - 1 
      solution = x[:] 

    if shortest == 0: 
     # Fake solution, it will be discarded 
     return '#' * (maxlen+1) 
    return solution 

def divlist(n): 
    l = [] 
    for d in range(9,1,-1): 
     while n%d == 0: 
      l.append(d) 
      n = n/d 
    if n>1: l.append(n) 
    return l 

Answer 2

Ý tưởng cơ bản là kiểm tra tất cả các khả năng với hoạt động k, cho k bắt đầu từ 0. Hãy tưởng tượng bạn tạo một cây có chiều cao k rằng các nhánh cho mọi hoạt động mới có thể có với toán hạng (4 * 9 nhánh trên mỗi cấp). Bạn cần phải đi qua và đánh giá lá của cây cho mỗi k trước khi di chuyển đến k tiếp theo.

tôi đã không kiểm tra này pseudo-code:

for every k from 0 to infinity 
    for every n from 1 to 9 
    if compute(n,0,k): 
     return k 


boolean compute(n,j,k): 
    if (j == k): 
    return (n == target) 
    else: 
    for each operator in {+,-,*,/}: 
     for every i from 1 to 9: 
     if compute((n operator i),j+1,k): 
      return true 
    return false 

Nó không đưa vào tài khoản số học khai thác được ưu tiên và niềng răng, mà sẽ đòi hỏi một số rework.

Answer 3

Câu hỏi thực sự thú vị :)

Lưu ý rằng bạn có thể bắt đầu từ cuối! Từ ví dụ của bạn (9 * 3) +2 = 29 tương đương với câu nói (29-2)/3 = 9. Bằng cách đó chúng ta có thể tránh được vòng lặp kép trong câu trả lời của cyborg. Điều này cho thấy các thuật toán sau đây để thiết lập Y và kết quả r:

nextleaves = {r} 
nops = 0 
while(true): 
    nops = nops+1 
    leaves = nextleaves 
    nextleaves = {} 
    for leaf in leaves: 
     for y in Y: 
     if (leaf+y) or (leaf-y) or (leaf*y) or (leaf/y) is in X: 
      return(nops) 
     else: 
      add (leaf+y) and (leaf-y) and (leaf*y) and (leaf/y) to nextleaves 

Đây là ý tưởng cơ bản, hiệu suất có thể được chắc chắn sẽ được cải thiện, ví dụ bằng cách tránh "backtracks", chẳng hạn như r+a-a hoặc r*a*b/a.

Answer 4

Tôi đoán ý tưởng của tôi cũng tương tự như một trong Peer Sommerlund:

Đối với số lượng lớn, bạn tiến nhanh, bởi nhân với thuật toán mã hóa lớn.

Có phải Y = 29 nguyên tố không? Nếu không, hãy chia nó bằng bộ chia tối đa (từ 2 đến 9). Khác bạn có thể trừ một số để đạt được số có thể chia. 27 là tốt, vì nó là dividable 9, vì vậy

(29-2)/9=3 => 
3*9+2 = 29 

Vì vậy, có lẽ - Tôi không nghĩ về điều này đến cùng: Tìm kiếm trên chia hết cho tới 9 số dưới đây Y. Nếu bạn không đạt được một số đó là một chữ số, lặp lại.

Công thức là các bước được đảo ngược.

(Tôi sẽ thử nó cho một số con số. :))

Tôi đã thử với 2551, đó là

echo $((((3*9+4)*9+4)*9+4)) 

Nhưng tôi đã không kiểm tra tất cả các kết quả trung gian cho dù đó là số nguyên tố. Nhưng

echo $((8*8*8*5-9)) 

là 2 hoạt động ít hơn. Có lẽ tôi có thể điều tra điều này sau.