本题的另外一个解法请看：一个无重复面值的找零算法的思路与实现（二）
在论坛上看到有人问了一个类似的算法题：
给出升序排列的N个数字，比如1， 2， 3， 7， 70
找出无法被这组数字组成的最小正整数。（这组数字中每个数字最多使用一次）
（1）简单描述你的算法和思路。（2）用C/C++实现
（3）分析你的代码的时间复杂度和空间复杂度
解题思路：
这个问题类似于一个硬币找零问题的升级版。现存在一堆面值为V1,V2,V3,...的硬币，每种面值的硬币只有一枚，现在需要为顾客找出总值为sum的零钱。问不能被找零的sum的最小值是多少？
方案1：
- 算法概述
最容易理解的实现方法是使用递归。
我们假定V1,... Vn是面值由小到大排列的所有币种。我们从sum等于1开始，递增的循环进行找零。
首先找出小于等于sum且最接近sum的面值Vm。然后得出sum-Vm的值，并对sum-Vm继续进行找零，找出小于等于sum-Vm且小于Vm的最接近面值。递归的找下去，如果连最小面值都被遍历到而sum仍然没被找完，则不能被找零。
若sum不能被无重复面值的找零，则sum即所求。否则，对sum+1进行递归的找零。
- 实现
如下是我用C语言实现的算法，可以直接运行。可以为values指定任意的一组升序面值。
- #include"stdio.h"
- #include"conio.h"
- staticintvalues[]={1,2,3,12};/*升序排列的所有面值*/
- voidmain()
- {
- intsum;
- /*如果最小的币值都大于1，则1必定不能被找零*/
- if(values[0]>1){
- printf("1istheminimum.\n");
- }
- else{
- for(sum=1;;sum++){
- inti,j;
- /*找出最接近sum且不大于sum的面值在values数组中的下标*/
- for(i=sizeof(values)-1;i>=0;i--){
- if(values[i]<=sum){
- j=i;
- break;
- }
- if(recursion(j,sum-values[j])==-1){/*该sum不能被找零*/
- printf("%distheminimum.\n",sum);
- break;
- };
- getchar();
- intrecursion(intj,intsum){
- if(j<1&&sum>0)
- return-1;/*不能被找零*/
- if(sum==0)
- return0;/*可以被找零*/
- /*找出最接近sum且不大于sum，小于values[j]的面值在values数组中的下标*/
- for(i=j-1;i>=0;i--){
- if(values[i]<=sum){
- k=i;
- returnrecursion(k,sum-values[k]);
- }
- 算法正确性证明
有同学
问我”首先找出小于等于sum且最接近sum的面值Vm“的这种做法是不是正确。会不会存在某些情况，sum的值大于Vm，但是并不能被包含Vm的硬币集合表示，反而可以被一组小于Vm的硬币集合表示呢？例如{ 1,5,6,7 }在判断11能否被找零的过程中会取Vm = 7，而sum - Vm = 11 - 7 = 4，4不能被找零，但实际上11可以由5,6找零。
然而实际上这种情况是不存在的。因为程序是从sum等于1开始对sum进行递增的判断，如果sum=k时不能被找零，则所求的最小值就是k，程序将不会继续往下进行。也就是说上段所说的情况是不存在的，因为4已经是所求的不能被找零的最小值，程序将跳出循环。
接下来我们来证明算法的正确性。
在sum=1或sum=2的情况下很明显，算法正确。根据数学归纳法，我们只需证明对于面值集G={ V1,...,Vn }，在sum=1,k（k>=1）都可以被正确找零的情况下，算法对sum=k+1的验证是正确的，即可证明算法正确。而要证明这点，我们只需证明递归算法是正确的，即
取不大于且最接近sum的Vm的做法是正确的。
首先我们证明一些辅助命题。如果嫌长也可以先看下面正题的证明再来查阅这两个辅助命题。
1.对于面值集G={ V1,Vn }，若G可以为1,Vm（m<=n）找零，则由G的前m个连续面值组成的子集A={ V1,...Vm}必定可以为1,Vm找零。
@H_281_403@
@H_427_404@
证明：首先能为sum=x找零的面值均小于等于x。（比如为5找零，零钱中肯定不会有6）。所以能为x找零的面值中可以不包含比x更大的面值。