Làm thế nào để có được số mục tiêu với các hoạt động +3 hoặc * 5 mà không cần đệ quy?

Question

Đây là một vấn đề phỏng vấn tôi gặp phải hôm qua, tôi có thể nghĩ ra một giải pháp đệ quy nhưng tôi muốn biết nếu có một giải pháp không đệ quy.

Với số N, bắt đầu bằng số 1, bạn chỉ có thể nhân kết quả bằng 5 hoặc thêm 3 vào kết quả. Nếu không có cách nào để lấy N thông qua phương thức này, hãy trả về "Không thể tạo nó".

Ex:

Input: 23 
Output: (1+3)*5+3 
Input: 215 
Output: ((1*5+3)*5+3)*5 
Input: 12 
Output: Can't generate it. 

Phương pháp đệ quy có thể rõ ràng và trực quan, nhưng có bất kỳ phương pháp phi đệ quy?

Answer 1

Tôi nghĩ rằng giải pháp đệ quy nhanh nhất, không là (cho N> 2):

• nếu N mod 3 == 1, nó có thể được tạo ra như 1 + 3*k.
• nếu N mod 3 == 2, nó có thể được tạo ra như 1*5 + 3*k
• nếu N mod 3 == 0, nó không thể được tạo ra

Tuyên bố cuối cùng xuất phát từ thực tế là bắt đầu với 1 (= 1 mod 3) bạn chỉ có thể đạt được con số mà là tương đương với 1 hoặc 2 mod 3:

• khi bạn thêm 3, bạn không thay đổi giá trị mod 3
• một số tương đương với 1 mod 3 nhân 5 đưa ra một số bằng t o 2 mod 3
• một số tương đương với 2 mod 3 nhân 5 đưa ra một số tương đương với 1 mod 3

Answer 2

Bạn có thể sử dụng đệ quy sau (đó là thực sự trực quan):

f(input) = f(input/5) OR f(input -3) 
base: 
f(1) = true 
f(x) = false x is not natural positive number 

Lưu ý rằng nó có thể được thực hiện bằng động Lập trình cũng như:

f[-2] = f[-1] = f[0] = false 
f[1] = true 
for i from 2 to n: 
    f[i] = f[i-3] or (i%5 == 0? f[i/5] : false) 

để có được tỷ số, bạn cần phải nhận được trên bàn sau khi xây dựng nó từ f[n] và thực hiện theo các động thái true hợp lệ.

thời gian và không gian phức tạp của các giải pháp DP là O(n) [pseudo-đa thức]

Answer 3

Tất cả các thuật toán đệ quy cũng có thể được thực hiện bằng một chồng. Vì vậy, một cái gì đó như thế này:

bool canProduce(int target){ 
Stack<int> numStack; 
int current; 

numStack.push(1); 

while(!numStack.empty){ 
    current=numStack.top(); 
    numStack.pop(); 
    if(current==target) 
    return true; 
    if(current+3 < target) 
    numStack.push(current+3); 
    if(current*5 < target) 
    numStack.push(current*5); 
} 

return false; 
} 

Answer 4

Trong Python:

Giải pháp thông minh:

def f(n): 
    if n % 3 == 1: 
     print '1' + '+3' * (n // 3) 
    elif n % 3 == 2: 
     print '1*5' + '+3' * ((n - 5) // 3) 
    else: 
     print "Can't generate it." 

Một ngây thơ nhưng vẫn O (n) phiên bản:

def f(n): 
    d={1:'1'} 
    for i in range(n): 
     if i in d: 
      d[i*5] = '(' + d[i] + ')*5' 
      d[i+3] = d[i] + '+3' 

    if n in d: 
     print d[n] 
    else: 
     print "Can't generate it." 

Và tất tất nhiên, bạn cũng có thể sử dụng ngăn xếp để tái tạo hành vi của các cuộc gọi đệ quy.

Mà cho:

>>> f(23) 
(1)*5+3+3+3+3+3+3 
>>> f(215) 
(1)*5+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3+3 
>>> f(12) 
Can't generate it. 

Answer 5

Mẫu vấn đề như một đồ thị:

• Nodes là những con số
• nút gốc của bạn là 1
• Liên kết giữa các nút là *5 hoặc +3.

Sau đó, chạy Dijkstra's algorithm để nhận đường đi ngắn nhất. Nếu bạn xả tất cả các liên kết khỏi các nút <N mà không cần đến N thì bạn không thể tạo ra N. (Ngoài ra, hãy sử dụng câu trả lời của @ obourgain để quyết định xem liệu vấn đề có thể được giải quyết hay không và chỉ cố gắng giải quyết vấn đề nếu nó có thể được giải quyết.)

Vì vậy, về cơ bản, bạn đưa vào nút (1, đường dẫn null). Bạn cần một từ điển lưu trữ {node (tức là số) => đường dẫn tốt nhất được tìm thấy cho đến nay cho nút đó}. Sau đó, miễn là hàng đợi không trống, trong mỗi đường vòng của vòng lặp, bạn

• Làm dịu đầu (nút, đường dẫn) khỏi hàng đợi.
• Nếu số lượng nút này là >N hoặc bạn đã thấy nút này trước đây với ít bước hơn trong đường dẫn, thì bạn không cần thực hiện thêm bất kỳ thao tác nào nữa trên thẻ này.
• Thêm (node ​​=> path) vào từ điển.
• Enqueue các nút truy cập từ nút này với *5 và +3 (cùng với đường dẫn giúp bạn có được những nút)

Khi vòng lặp kết thúc, nhìn lên N trong từ điển để có được những con đường, hoặc đầu ra " Không thể tạo ra nó ".

Sửa: lưu ý, đây thực sự là Breadth-first search hơn là thuật toán Dijkstra, như chi phí đi qua một liên kết được cố định ở mức 1.

Answer 6

Mấu chốt ở đây là để làm việc về phía sau. Bắt đầu với số bạn muốn đạt và nếu chia hết cho 5 thì chia cho 5 vì nhân với 5 kết quả trong giải pháp ngắn hơn so với phép cộng 3. Ngoại lệ duy nhất là nếu giá trị bằng 10, vì chia cho 5 sẽ mang lại 2 là không thể giải quyết được. Nếu số lượng là không chia hết cho 5 hoặc bằng 10, trừ 3. Điều này tạo ra chuỗi ngắn

Lặp lại cho đến khi bạn đạt 1

Đây là mã python:

def f(x): 
    if x%3 == 0 or x==2: 
     return "Can't generate it" 
    l = [] 
    while x!=1: 
     if x%5 != 0 or x==10: 
      l.append(3) 
      x -= 3 
     else: 
       l.append(5) 
       x /=5 
    l.reverse() 
    s = '1' 
    for v in l: 
     if v == 3: 
      s += ' + 3' 
     else: 
      s = '(' + s + ')*5' 
    return s 

tín dụng đến các giải pháp trước đây để xác định xem một số đã cho có thể là