本题的另外一个解法请看:一个无重复面值的找零算法的思路与实现(二)
在论坛上看到有人问了一个类似的算法题:
给出升序排列的N个数字,比如1, 2, 3, 7, 70
找出无法被这组数字组成的最小正整数。(这组数字中每个数字最多使用一次)
(1)简单描述你的算法和思路。(2)用C/C++实现
(3)分析你的代码的时间复杂度和空间复杂度
解题思路:
这个问题类似于一个硬币找零问题的升级版。现存在一堆面值为V1,V2,V3,...的硬币,每种面值的硬币只有一枚,现在需要为顾客找出总值为sum的零钱。问不能被找零的sum的最小值是多少?
方案1:
- 算法概述
最容易理解的@R_301_369@是使用递归。
我们假定V1,... Vn是面值由小到大排列的所有币种。我们从sum等于1开始,递增的循环进行找零。
首先找出小于等于sum且最接近sum的面值Vm。然后得出sum-Vm的值,并对sum-Vm继续进行找零,找出小于等于sum-Vm且小于Vm的最接近面值。递归的找下去,如果连最小面值都被遍历到而sum仍然没被找完,则不能被找零。
若sum不能被无重复面值的找零,则sum即所求。否则,对sum+1进行递归的找零。
- 实现
如下是我用C语言实现的算法,可以直接运行。可以为values指定任意的一组升序面值。
@H_403_101@
- #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]);
- }