计算将 n 划分为正整数之和的方法数 c++

Question

我需要编写函数作为赋值的一部分..\n我需要计算将 n 划分为正整数之和的方法数，但我不能使用 while 或 goto

\n\n

/*\n * REQUIRES: n > 0\n * EFFECTS: computes the number of ways to partition n into the sum of\n *          positive integers\n * MUST be tree recursive\n * Hint: Use a helper function that computes the number of ways to\n * partition n using a bounded subset of integers. Then use logic\n * similar to count_change() from lecture to divide partitions into\n * those that use a specific item and those that do not.\n */\nint num_partitions(int n);\n

\n\n

我想出了一种打印它们的方法，但无法对其进行计数，并且我的函数还需要 for 循环。这里的功能

\n\n

void print(int n, int * a) {\n    int i ; \n    for (i = 0; i <= n; i++) {\n        printf("%d", a[i]); \n    }\n    printf("\\n"); \n}\n\nint integerPartition(int n, int * a, int level,int c){\n    int first; \n    int i; \n    if (n < 1)\n    {\n        return c;    \n    }\n    a[level] = n;\n    print(level, a);\n    c++;\n    first = (level == 0) ? 1 : a[level-1];\n    for(i = first; i <= n / 2; i++){\n        a[level] = i; \n        integerPartition(n - i, a, level + 1,c);\n    }\n}\nint num_partitions(int n){\n    int * a = (int * ) malloc(sizeof(int) * n); \n    return integerPartition (n, a, 0,0);\n\n}\n

\n\n

请帮忙...

\n\n

这是计数更改函数

\n\n

int count_change(int amount, const int coins[], int num_coins) {\n\nif (amount == 0) {\n\nreturn 1;\n\n} else if\xe2\x80\x8b (amount < 0 || num_coins < 1) {\n\nreturn 0;\n\n} else {\n\nreturn\ncount_change(amount - coins[num_coins - 1], coins, num_coins) +\n\ncount_change(amount, coins, num_coins - 1);\n}\n\n}\n

\n

Answer 1

你可以这样做：

#include <conio.h>
#include <iostream>

using namespace std;
int integerPartition(int n, int k);

int main() 
{ 
    int n;
    cin>>n;
    int k =n;
    cout<<integerPartition(n,k);

    getchar();
    return 0;                                                   
}        
int integerPartition(int n, int k)
{
    if(k==0)
        return 0;
    if(n ==0)
        return 1;
    if(n<0)
        return 0;

    return integerPartition(n,k-1) + integerPartition(n-k,k);
}

灵感来自： http: //www.programminglogic.com/integer-partition-algorithm/

或者您也可以使用：分区函数的递归公式，在
https://en.wikipedia.org/wiki/Partition_(number_theory)上给出