显示正整数个位数的所有唯一数字组合,其总和等于使用C中的递归的另一个正整数

问题描述 投票:1回答:1

我需要用C语言编写一个程序,以从用户读取两个正整数,数字NS。程序应显示所有唯一编号使用递归将N个位数的总和等于S的组合。例如。对于N = 3S = 10,程序应显示:

8+1+1=10
7+2+1=10
6+3+1=10
5+4+1=10
6+2+2=10
5+3+2=10
4+4+2=10
4+3+3=10

如果数字超出范围,它将显示“ Wrong input”。

这是我到目前为止编写的代码:

void check(int n,int s)
{
    int arr[n];
    for (int i=1;i<=n;i++)
    {
        arr[i]=1;
    }
    if (n==s)
    {
        int j=1;
        while (j<n)
        {
            printf("%d+",arr[j]);
            j++;
            if (j==n)
            {
                printf("%d=%d",arr[j],s);
                break;
            }
        }
    }
    else if (n<s)
    {
        printf("Wrong input");
        exit(0);
    }
    else
    {

    }
}

int main()
{
    int N,S;
    scanf("%d %d",&N,&S);
    if (N<=0 || S<=0)
    {
        printf("Wrong input");
        exit(0);
    }
    check(N,S);

}

我不知道如何解决此问题,我必须对该项目使用递归。任何人都可以帮助我吗?

c recursion
1个回答
0
投票
我们可以直接使用计数为partitions with a restricted number of parts的数学递归。我不精通C语言,因此这里有一些JavaScript代码,希望对您有所帮助:

function f(N, S){ if (N == 0 && S == 0) return [[]] if (N <= 0 || S <= 0) return [] let result = [] // Add 1 to all partitions // (N-1, S-1) to guarantee // the smallest part is 1 for (let p of f(N - 1, S - 1)) result.push(p.concat(1)) // Add 1 to each part of the // partitions (N, S - N) to guarantee // the smallest part is not 1 for (let p of f(N, S - N)){ result.push(p.map(x => x + 1)) } return result } let str = "" for (let p of f(3, 10)) str += JSON.stringify(p) + "\n" console.log(str)
© www.soinside.com 2019 - 2024. All rights reserved.