cách hiệu quả để tìm số tiền có thể

Question

Với ba số nguyên n, k và d, có bao nhiêu cách thể n được biểu diễn dưới dạng tổng của các số nguyên dương i<=k, chẳng hạn rằng d xảy ra ít nhất một lần trong tổng. Đó là bảo đảm rằng 0<d<=k. Cách tiếp cận của tôi là một cách đệ quy;

#include <stdio.h> 
#include <stdlib.h> 
int n,k,d,ans=0; 
void solve(int totw,int flag)//totw is the total sum till now, and flag is to keep track of the number of d's in the sum. 
{ 
    if(totw>n) 
     return; 
    if(totw==n && flag>0)//flag>0--->at least 1 d 
    { 
     ans = (ans+1)%1000000007;//answer is expected modulo 10^9+7 
     return; 
    } 
    int i=1,h=k; 
    if(h>n-totw) 
     h=n-totw; 
    while(i<=h) 
    { 
     if(i==d) 
      flag++; 
     solve(totw+i,flag); 
     i++; 
    } 
} 
int main() 
{ 
    scanf("%d %d %d",&n,&k,&d); 
    solve(0,0); 
    printf("%d",ans); 
} 

Input:
Output:
Nhưng quan tòa cho thấy Time Limit Exceeded. Có bất kỳ thuật toán hiệu quả hơn để tiến hành trong trường hợp này? 0<n,k<=100
PS: Tôi đã tự hỏi liệu có bất kỳ đối số tổ hợp nào có thể giải quyết câu hỏi này mà không cần recursion hoặc iteration. Và vâng .... thứ tự của các khoản tiềnvấn đề.

Answer 1

Đề cập đến trang Wikipedia này: Stars and Bars

Về cơ bản các số cách để tách một số n vào k nguyên dương là (n-1)C(k-1) hoặc n-1 chọn k-1. Do đó, bạn có thể lặp lại k = 1 đến n-d-1 để tìm số cách bạn có thể chia n-d-1 thành bất kỳ số nguyên dương nào.

Tham khảo here để tìm hiểu làm thế nào để có hiệu quả tính toán nCk cho lớn n và k hiệu quả

Answer 2

Bạn có thể đại diện cho các cuộc gọi đệ quy của bạn như là một đồ thị. Mỗi nút được đưa ra bởi các tham số của hàm (totw, flag) và bạn thêm một cạnh bất cứ khi nào bạn thực hiện cuộc gọi đệ quy. Có khoảng n*2 nút và các cạnh n*2*k trong biểu đồ này.

Biểu đồ này có một thuộc tính rất thú vị: đó là DAG (ví dụ: vì totw đang tăng lên nghiêm ngặt ở mỗi cuộc gọi). Do đó, khi bạn gọi solve(totw, flag), bạn có thể giữ kết quả trong một mảng, do đó bạn không tính toán hai lần. Điều này thực sự là một cách để giải thích dynamic programming: một thuật toán để tìm đường đi ngắn nhất trong một DAG (với sửa đổi nhỏ nó cũng có thể tính toán con đường dài nhất/số lượng đường dẫn, nhưng bạn có được ý tưởng). Độ phức tạp về thời gian trên biểu đồ G = (V, E) sẽ là O(|V|+|E|) (đó thực sự là một loại amortized analysis).

Do đó, việc giữ kết quả trong một mảng sẽ dẫn đến độ phức tạp về thời gian là O(nk).

Trên thực tế bạn có thể làm cho việc thực hiện thậm chí ngắn hơn bằng cách thay đổi một chút đồ thị:

enum { UNKNOWN = -1 }; 

/* not tested */ 
/* solve(num, d_seen): returns the answer to the problem with a sum 
    target, knowing whether `d` was already used */ 
int solve(int sum, int d_seen) 
{ 
    if (sum == 0) return d_seen; 
    int ans = dp[sum][d_seen]; 
    if (ans == UNKNOWN) { 
    ans = 0; 
    /* min(a, b) being what it is supposed to be */ 
    for (int i = 1; i <= min(sum, k); ++i) 
     ans = (ans + solve(sum - i, d_seen || (i == d))) % MOD; 
    } 

    return (dp[sum][d_seen] = ans); 
} 

Bằng cách này bạn không đặt flag trở về 0 sau incrementing nó.

Answer 3

Chắc chắn một số phép toán tổ hợp có thể giải quyết vấn đề này mà không cần sử dụng mã. Nhưng thử thách đệ quy trông rất thú vị khi cố gắng viết mã.

Ví dụ được kiểm tra nhẹ - không hiệu quả hơn OP nhiều.
(Bước 1, sử dụng tên biến có ý nghĩa hơn)

unsigned long solve(unsigned sum_n, unsigned max_value_k, unsigned special_d) { 
    if (sum_n == 0) return special_d == 0; 
    unsigned long solutions = 0; 

    // Improve efficiency, only loop up to min(k,n) 
    if (max_value_k > sum_n) { 
    max_value_k = sum_n; 
    } 

    // Will the loop contain d? 
    if (max_value_k >= special_d) { 
    for (unsigned i = 1; i <= max_value_k; i++) { 
     solutions += solve(sum_n - i, max_value_k, 
      i == special_d ? 0 : special_d); 
     solutions %= 1000000007; 
    } 
    } 
    return solutions; 
} 

#include <stdio.h> 
int main(void) { 
    unsigned n, k, d; 
    for (n=0; n<100; n++) { 
    printf("%u %lu\n", n, solve(n, 100, 1)); 
    fflush(stdout); 
    } 
    scanf("%u %u %u", &n, &k, &d); 
    printf("%lu\n", solve(n, k, d)); 
}