不是作业问题.
我正在阅读问题 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]

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

给一点背景(与这个问题无关),在C11中我注意到一个狭隘的问题：

int foo[] = { 0xFFFFFFFF };

这是无法编译(缩小转换),因为0xFFFFFFFF是一个无符号的int.不过,我看过0xFF签名的情况.

我看过整数促销规则,但这主要是在lvalues而不是rvalues / constants的上下文中.编译器如何确定常量的类型(不带字面后缀)？有没有文件或一个漂亮的小桌子/“cheat sheet”,显示这个规则？我甚至不确定这是什么,否则我本来会试图用C11标准来找到它.

提前致谢.

标准中有一张表,转载于cppreference.com： http://en.cppreference.com/w/cpp/language/integer_literal

特别地,没有后缀的十六进制或八进制整数文字被认为具有可以表示其值的以下列表中的第一个类型：

intunsigned intlong intunsigned long intlong long intunsigned long long int

如果int是32位长,0xFFFFFFFF对于int来说太大,所以选择了unsigned int.但是0xFF适合于int,所以就是这样.

给定一个整数数组,找到第一个唯一的整数.

我的解决方案：使用std :: map

将整数(数字作为键,其索引作为值)逐个放入(O(n ^ 2 lgn)),如果有重复,则在将所有数字放入之后从地图中删除条目(O(lg n))映射,迭代映射并找到索引为O(n)最小的密钥.

O(n ^ 2 lgn)因为地图需要进行排序.

效率不高.

更好的解决方案？

我相信以下将是最佳解决方案,至少基于时间/空间复杂性：

步骤1：
将整数存储在哈希映射中,该映射将整数保存为键,并将其显示为值的计数次数.这通常是O(n)操作,并且哈希表中元素的插入/更新平均应该是恒定时间.如果发现整数出现的次数超过两次,则实际上不必进一步增加使用次数(如果您不想这样做).

第2步：
对整数执行第二次传递.在哈希映射中查找每个,并且外观计数为1的第一个是您要查找的那个(即,第一个单个出现的整数).这也是O(n),使整个过程为O(n).

针对特殊情况的一些可能的优化：

优化A：可以使用简单数组而不是哈希表.即使在最坏的情况下,这也可以保证O(1)计算特定整数的出现次数以及查看其出现次数.此外,这增强了实时性能,因为不需要执行散列算法.由于可能较差的引用局部性(即,较大的稀疏表与具有合理的加载因子的哈希表实现)可能存在命中.然而,这将是针对整数排序的非常特殊的情况,并且可以通过散列表的散列函数来减轻,该散列函数基于输入的整数产生伪随机桶放置(即,开始的参考的不良位置).

数组中的每个字节表示由该字节的索引表示的整数的计数(最多255).只有当最低整数和最高值(即有效整数域的基数)之间的差足够小以使该数组适合存储器时,这才是可能的.特定整数数组中的索引将是其值减去数据集中存在的最小整数.

例如,在具有64位OS的现代硬件上,可以想象可以分配4GB阵列,其可以处理32位整数的整个域.可以想象甚至更大的阵列具有足够的存储器.

在处理之前必须知道最小和最大的整数,或者使用minmax算法通过数据进行另一次线性传递以找出该信息.

优化B：您可以进一步优化优化A,每个整数最多使用2位(一位表示存在,另一位表示多重性).这将允许每个字节表示四个整数,扩展数组实现以处理给定量的可用内存的更大的整数域.可以在这里播放更多位游戏以进一步压缩表示,但是它们仅支持特殊情况的数据进入,因此不能推荐用于仍然最常见的情况.