chia một số nguyên thành phần k

Question

Tôi đang lập trình bằng java và tôi cần xây dựng một thuật toán. Các yêu cầu của thuật toán là:

• Chúng tôi có 3 biến Integer n, m, k;
• Chúng tôi muốn chia n vào k phần sao cho tổng các k -parts đều bình đẳng để n và mỗi phần là một số nguyên giữa 1 và m.
• Chúng tôi muốn tất cả các kết hợp có thể có với số nguyên được phép.

Ví dụ với bộ đầu vào:

n = 7; m = 3; k = 4 

chúng ta có hai kết hợp khác nhau mà chúng ta có thể xây dựng:

7 = 2 + 2 + 2 + 1 

và

7 = 3 + 2 + 1 + 1 

cảm ơn tất cả các bạn.

Answer 1

Ý tưởng là phương pháp thuật toán backtraking (với đệ quy), Bạn có thể giảm tham số và nhận giải pháp partials và sau đó kiểm tra xem bạn có giải pháp đúng hay không.

public class Problem { 

    private static void algorithm(int n, int k, int m) { 
     algorithmRecursive(Collections.EMPTY_LIST, n, k, m, 1); 
    } 

    private static void algorithmRecursive(List<Integer> partial, int n, int k, int m, int min) { 
     if ((k > 0)) { 
      // Optimization 
      if ((n <= k * m) && (n >= k*min)){ 
       for (int i = min; i <= Math.min(m, n); i++) { 
        List<Integer> newPartial = new ArrayList<>(partial); 
        newPartial.add(i); 
        algorithmRecursive(newPartial, n - i, k - 1, m, i); 
       } 
      } 
     } else if (n == 0) { 
      // Right solution 
      System.out.println(partial); 
     } 
    } 

    public static void main(String[] args) { 
     algorithm(7,4,3); 
    } 
} 

Answer 2

Để có được đếm "số phận" bạn có thể sử dụng Dynamic Programming, mà theo công thức đệ quy:

D(0,0,j) = 1 
D(x,0,j) = 0  x > 0 
D(x,i,j) = 0  x < 0 or j<0 
D(x,i,j) = D(x-j,i-1,j) + D(x,i,j-1) 

Câu trả lời được biểu thị bởi D(n,k,m) là số phận như vậy.
phức tạp là mã O(n*k*m)

Java:

public static int numDivisions(int n, int m, int k) { 
    int[][][] D = new int[n+1][k+1][m]; 
    for (int j = 0; j < m; j++) { 
     for (int x = 0; x <= n; x++) { 
      D[x][0][j] = 0; 
     } 
     D[0][0][j] = 1; 
    } 
    for (int i = 1; i <= k; i++) { 
     for (int x = 0; x <= n; x++) { 
      for (int j = 0; j < m; j++) { 
       D[x][i][j] = 0; 
       if (j > 0) D[x][i][j] += D[x][i][j-1]; 
       if (x-j-1 >=0) D[x][i][j] += D[x-j-1][i-1][j]; 
      } 
     } 
    } 
    return D[n][k][m-1]; 
} 

Như một mặt lưu ý, điều này cũng tương tự như vấn đề stars and bars - nhưng ở đây tự không quan trọng, và ngoài ra bạn đã giới hạn trên cho số "sao" trong ô.

Answer 3

Tôi tin rằng điều này có thể được thực hiện dễ dàng với đệ quy. Trước tiên, hãy kiểm tra xem bạn có thể chia n ở tất cả, đó là khi n<=m*k && n>=k, nếu không, trả về mảng trống.

Nếu chia hết, hãy chọn m' từ dải [1..m] và chọn số đó làm số đầu tiên, sau đó nhận số còn lại đệ quy cho tham số n'=n-'m, m'=m', k'=k-1, sau đó trả về tất cả kết quả.

Đệ quy sẽ dừng thành công chỉ cho n=0 và k=0. Độ phức tạp thời gian phải giống với kích thước đầu ra.