Chuyển đổi phương thức đệ quy đơn giản đệ quy trong vòng lặp vào phương thức lặp

Question

Một thời gian sau, tôi đang làm việc về một vấn đề lập trình (CCC). Tôi cũng đã bắt gặp những câu hỏi tương tự trong các cuộc thi vừa qua nên tôi quyết định hỏi về điều này. Vấn đề là cơ bản này.

Bạn được cung cấp n người và miếng bánh.

n mọi người đang đứng liên tiếp.

Bạn phải phân phối các miếng bánh giữa chúng. Bạn đi theo thứ tự và mỗi người phải nhận được ít nhất là nhiều mảnh như người trước họ. Mỗi người phải nhận ít nhất một miếng bánh và không còn chiếc bánh nào nữa.

Bạn phải trả lại số cách có thể để phân phối chiếc bánh.

tôi quản lý để tạo ra các giải pháp đệ quy sau nhưng phải mất quá lâu (hơn 5 giây) cho các đầu vào sau:

120 mảnh, 20 người -> 97.132.873

250 mảnh, 130 người -> 1844349560

giải pháp của tôi:

import java.io.*; 

public class Main 
{ 
    int pieces, people; 
    int combinations = 0; 

    public void calculate (int person, int piecesLeft, int prev) 
    { 
    if (person == people) 
    { 
     if (piecesLeft == 0) 
      combinations++;    
    } 
    else 
    { 
     for (int x = prev ; (x * (people - person)) <= piecesLeft ; x++) 
     { 
      calculate (person + 1, piecesLeft - x, x); 
     } 
    } 
    } 


    public static void main (String[] args) throws Exception 
    { 
    Main m = new Main(); 
    BufferedReader in = new BufferedReader (new InputStreamReader (System.in)); 
    //m.pieces = Integer.parseInt (in.readLine()); 
    //m.people = Integer.parseInt (in.readLine()); 
    m.pieces=250; 
    m.people=130; 
    if (m.people == m.pieces) 
     System.out.println (1); 
    else if (m.people == 1) 
     System.out.println (1); 
    else 
    { 
     m.calculate (0, m.pieces, 1); 
     System.out.println (m.combinations); 
    } 
    } 
} 

tôi tìm thấy giải pháp python sau đây từ các giải pháp không chính thức, từ những gì tôi under tand, về cơ bản tạo ra một mảng các giá trị đã gặp phải.

visited = [] 
def pi(n,k,min): 
if visited [n][k][min] == 0:  
    if n == k: 
     visited[n][k][min] = 1 
    elif k == 1: 
     visited[n][k][min] = 1 
    else: 
     t = 0 
     for i in range (min, (n/k)+1): 
      t = t + pi(n-i, k-1, i) 
     visited[n][k][min] = t 
return visited[n][k][min] 


file = open("j5.10.in", "r") 
n = int(file.readline()) 
k = int(file.readline()) 

for i in range(n+1): 
x = [] 
for j in range(k+1): 
    t = [] 
    for kk in range(n+1): 
     t.append (0) 
    x.append(t) 
visited.append(x) 

print pi(n,k,1) 

Điều tôi muốn làm là tạo giải pháp lặp đi lặp lại từ một trong hai cách này nhưng không chắc chắn cách thực hiện. Từ những gì tôi hiểu, có thể không có sự khác biệt về tốc độ lớn nhưng với những trường hợp lớn hơn, nó sẽ cho phép tôi tránh được tình trạng tràn ngăn xếp.

Answer 1

Giải pháp thứ hai được ghi nhớ ... các visited giá trị bản ghi mảng đã được tính toán. Một thủ thuật để chuyển đổi một đệ quy đã ghi nhớ thành một giải pháp lặp (loại) được lặp lại thông qua các trường hợp nhỏ hơn để điền vào mảng ghi nhớ. Bạn chỉ có thể vứt bỏ kết quả cho các trường hợp nhỏ hơn (chúng sẽ được lưu trữ trong mảng ghi nhớ). Sau đó, khi bạn cuối cùng tính toán một trong những bạn muốn, nó sẽ sử dụng mảng bản ghi nhớ ngay lập tức, không tính thêm.

Nếu bạn thực sự muốn xây dựng một giải pháp lặp đi lặp lại từ đầu, bạn phải tìm ra những trường hợp trước bạn cần lưu trữ để xây dựng trường hợp tiếp theo. Ví dụ, để tính toán giai thừa, với một vòng lặp, bạn chỉ cần lưu trữ một giá trị trong bộ nhớ. Trong một vấn đề thay đổi với tiền xu của mệnh giá 1, 5, và 10 cent, bạn sẽ cần phải tiết kiệm chỉ mười mục trước đó để xây dựng kế tiếp. Trong một số trường hợp, bạn cần phải biết tất cả các giá trị trước đó để xây dựng tiếp theo. Một khi bạn biết rằng, cấu trúc bộ nhớ nên rõ ràng, sau đó logic chương trình sẽ trở nên rõ ràng.