Skip to content

dongli96/MoneySplit

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 

Repository files navigation

AlgorithmExercise

让用户先输入一个大钱数(整型数,如100);接着输入几个小钱数(也是整型,如20,30,50等),小钱的种类不能超过5,超过了要报错。将大钱拆成小钱后,可能会有数种拆法,比如100=50x2,也可以100=50+30+20,等等。最后要求找到那个拆数最小的那一种拆法。
这道题首先要对输入函数(cin)>>熟练运用,因为大钱和小钱都是让用户自行输入。
核心算法部分有一定的难度。我的思路是,让大钱先和小钱当中最大的那个作商,1)如果能除尽,那这种就是拆数最少的。比如上面的100=50x2。显然你如果让任何小于50的数去拼成100,份数肯定>=2,因为它们都比50小,毕竟两个50才是刚好。2)如果不能除尽,那就拿它的余数和次大的小钱数作商,如果能除尽,那最小的就是这种,原因和上面的一样。如果不能除尽,那就拿再小的小钱数进行操作,一直到所有的小钱全部操作完为止。
以上操作完成以后,把上面的商减去1,余数加上除数的值,再进行相同的操作。举个例子,假设大钱100,小钱是(20,30,40),那么100和40首先作商,结果是2余20,先拿20和剩下的(20,30)进行上述操作,全部完成后,把商减去1得1,余数变成20+1x40=60,再拿这个60去和(20,30)作商。就这样,重复操作,一直到商变成0为止。这么做的原因是最少拆数,未必需要最大的小钱的参与。举个例子,大钱90,小钱(24,20,10,4),然而90=24+24+24+10+4+4,90=20+20+20+20+10,用20和10拼出来反而少一份。所以,为了得到最后结果,必须遍历,除非最大小钱能够除尽大钱,就像100分成2个50这种。
再举个例子总结一下:假设大钱100,小钱(20,30,40)。首先100/40=2(+20),20/30=0(+20),20/20=1,所以40+40+20,就是它,两个40的所有情况里面就是它份数最少,因为剩下的数字都比20小;然后余数20+40=60,继续操作。这是考察所有一个40的分法。显然,30就除尽了,60/30=2,所以不用怀疑,一个40分法里面就是它份数最少,剩下的不管了。接着0个40,100/30=3(+10),10和剩下20除不尽,这是条死路。所以把余数加上30变成40。然后40和20除尽,所以不用怀疑,0个40,2个30里面,就是它份数最少(当然也只有这一种);接着把余数再加上30变成70,和20一取模变成10,死路。接着考察0个30的情况,很显然就是20x5了。所以考察到的分法:40+40+20,40+30+30,30+30+30+10(死路),30+30+20+20,30+20+20+20+10(死路),20+20+20+20+20。所以,最少的份数就是3种,分法就是前两种。
具体到程序,就是一个递归的过程。100除以40,等于2。然后0-2迭代,对于每一个,再用相应的余数去除以30,得出一个数,再从0-这个数迭代,对于每一个,再用相应的余数去除以20。总之,一直除到小钱的数组里所有项到头。简单说,就是一个迭代套递归的“森林”。
根结点(40) 一级子结点(30) 二级子结点(20)
2 0 1
1 2 0
0 2 2
... ... ...

如果觉的有帮助的话,请帮我加星,谢谢

About

难度中等的一个C++算法小项目

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages