c – 对于给定的整数a,找到总和为a的所有唯一正整数组合

概述不是作业问题. 我正在阅读问题 here,我遇到了这个问题. 有人回答了.我已经尝试了很多来理解使用的递归,但我无法得到它.有人可以向我解释一下吗？ Write a function, for a given number, print out all different ways to make this number, by using addition and any number equa 不是作业问题.
我正在阅读问题 here,我遇到了这个问题.
有人回答了.我已经尝试了很多来理解使用的递归,但我无法得到它.有人可以向我解释一下吗？

Write a function,for a given number,print out all different ways to make this number,by using addition and any number equal to or smaller than this number and greater than zero.

例如,给定a = 5,我们有以下七种方法来弥补5：

> 1,1,1
> 1,4
> 1,2
> 1,3
> 2,3
> 1,2,2
> 5

该网站的解决方案是在C：

voID printSeq( int num,int a[],int len,int s ){    if( num <= 0 )    {        for( int j = 0 ; j < len ; j++ )            cout << a[ j ] << "," ;        cout << endl;        return;    }    for(int i = s ; i <= num ; i++)    {        a[ len ] = i;        printSeq( num - i,a,len + 1,i );    }}int main(){    int a[5];    printSeq(5,1);    cin.get();    return 0;}

解决方法 当遇到这样的问题时,通常从编辑器/ IDE退一步并通过在白板上绘制一个简单的案例来思考问题通常是个好主意.甚至不做伪代码,只是绘制一个流程图,说明这个问题的一个简单案例(例如a = 3)将如何一直向下.此外,首先不要担心重复组合.尝试找到一个解决方案,为您提供所有需要的组合,然后改进您的解决方案,不给您重复.在这种情况下,为什么不看一下a = 3的可管理案例呢？让我为你画一幅画.绿色复选标记表示我们已达到有效组合,红叉表示组合无效.

如您所见,我们从三个空子组合开始,然后通过向每个子组合附加一个数字来构建三个新的子组合.我们想要检查所有可能的路径,因此我们选择1,2和3,最后得到[1],[2]和[3].如果组合中的数字总和等于3,我们找到了一个有效的组合,所以我们可以停下来检查这条路径.如果组合中的数字总和超过3,则组合无效,我们也可以停止.如果不是这种情况,我们只是继续构建组合,直到我们得出有效或无效的解决方案.

因为你的问题似乎主要是关于如何为这类问题制定一个递归解决方案而不是特定语法,你恰好找到了一个C解决方案我将在Python中提供一个解决方案(它几乎看起来像伪代码它就是它所知道的.

def getcombs(a,combo = None):    # initialize combo on first call of the function    if combo == None:        combo = []    combosum = sum(combo) # sum of numbers in the combo,note that sum([]) == 0    # simple case: we have a valID combination of numbers,i.e. combosum == a    if combosum == a:        yIEld combo # this simply gives us that combination,no recursion here!    # recursive case: the combination of numbers does not sum to a (yet)    else:        for number in range(1,a + 1): # try each number from 1 to a                           if combosum + number <= a:  # only proceed if we don't exceed a                extcombo = combo + [number] # append the number to the combo                # give me all valID combinations c that can be built from extcombo                for c in getcombs(a,extcombo):                    yIEld c

我们来测试代码吧！

>>> combos = getcombs(3)>>> for combo in combos: print(combo)... [1,1][1,2][2,1][3]

这似乎工作正常,a = 5的另一个测试：

>>> combos = getcombs(5)>>> for combo in combos: print(combo)... [1,2][1,3][1,3,4][2,1][2,3][3,1][3,2][4,1][5]

该解决方案包括我们正在寻找的所有七种组合,但代码仍然会产生重复.您可能已经注意到,没有必要使用小于先前所选数字的数字来生成所有组合.因此,让我们添加一些代码,这些代码只会开始为不小于组合中当前最后一个数字的数字构建extcombo.如果组合为空,我们只需将之前的数字设置为1.

def getcombs(a,combo = None):    # initialize combo on first call of the function    if combo == None:        combo = []    combosum = sum(combo) # sum of numbers in combo,no recursion here!    # recursive case: the combination of numbers does not sum to a (yet)    else:        lastnumber = combo[-1] if combo else 1 # last number appended        for number in range(lastnumber,a + 1): # try each number between lastnumber and a            if combosum + number <= a:                extcombo = combo + [number] # append the number to the combo                # give me all valID combinations that can be built from extcombo                for c in getcombs(a,extcombo):                    yIEld c

再一次,让我们测试代码吧！

>>> combo = getcombs(5)>>> for combo in combos: print(combo)... [1,3][5]

提出的解决方案可能不是最有效的解决方案,但希望它会鼓励您递归思考.逐步解决问题,为小输入绘制一个简单的案例,一次解决一个问题.

总结

以上是内存溢出为你收集整理的c – 对于给定的整数a,找到总和为a的所有唯一正整数组合全部内容，希望文章能够帮你解决c – 对于给定的整数a,找到总和为a的所有唯一正整数组合所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。