文档介绍：伪造硬币问题+.【伪造硬币问题】给你一个装有n个硬币的袋子。n个硬币中有一个是伪造的。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务,将提供一台可用来比较两组硬币重量的仪器,利用这台仪器,可以知道两组硬币的重量是否相同。试用分治法的思想写出解决问题的算法,并计算其时间复杂度。(1)源程序:#include<>#include<>#include<>intfindTheCoin(intq[],inta,intb);intquantity(intq[],inta,intb);voidmain(){time_tts;srand((unsigned)time(&ts));constintMax=70;intn,k;while(true){cout<<"请输入硬币的个数"<<endl;cin>>n;intq[Max];inti;for(i=1;i<=n;i++){q[i]=2;}k=rand()%n;if(k==0)k=n;q[k]=1;cout<<"随机产生的硬币排列顺序"<<endl;for(i=1;i<=n;i++){cout<<q[i]<<"";if(i%5==0)cout<<endl;}cout<<endl;intp=findTheCoin(q,1,n);cout<<"伪造硬币的位置:"<<p<<endl;cout<<"======================="<<endl;}}intquantity(intq[],inta,intb){inttotal=0;inti;for(i=a;i<=b;i++)total+=q[i];returntotal;}intfindTheCoin(intq[],inta,intb){if(a==b)returna;intn=b-a+1;intc=n%3;intm=a+n/3-1;intd;switch(c){case0:if(quantity(q,a,m)==quantity(q,m+1,m+n/3)){d=findTheCoin(q,m+n/3+1,m+2*(n/3));returnd;}elseif(quantity(q,a,m)==quantity(q,m+n/3+1,m+2*(n/3))){d=findTheCoin(q,m+1,m+n/3);returnd;}else{d=findTheCoin(q,a,m);returnd;}//break;case1:if((quantity(q,a,m)==quantity(q,m+1,m+n/3))&&(quantity(q,m+n/3+1,m+2*(n/3))==quantity(q,m+1,m+n/3)))returnm+2*(n/3)+1;else{if(quantity(q,a,m)==quantity(q,m+1,m+n/3)){d=findTheCoin(q,m+n/3+1,m+2*(n/3));returnd;}elseif(quantity(q,a,m)==quantity(q,m+n/3+1,m+2*(n/3))){d=findTheCoin(q,m+1,m+n/3);returnd;}else{d=findTheCoin(q,a,m);returnd;}}//break;case2:if(q[m+2*(n/3)+1]==q[m+2*(n/3)+2]){if(quantity(q,a,m)==quantity(q,m+1,m+n/3)){d=findTheCoin(q,m+n/3+1,m+2*(n/3));returnd;}elseif(quantity(q,a,m)==quantity(q,m+n/3+1,m+2*(n/3))){d=findTheCoin(q,m+1,m+n/3);returnd;}else{d=findTheCoin(q,a,m);returnd;}}else{if(q[m+2*(n/3)+2]==q[1])returnm+2*(n/3)+1;//cout<<"伪造硬币的号码是"<<3*m+1<<endl;elsereturnm+2*(n/3)+2;//cout<<"伪造硬币的号码是"<<3*m+2<<endl;}}//returntrue;}(2)运行结果2.【找零钱问题】一个小孩买了价值为33美分的糖,并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目有限的面值为25美分、10美分、5美分、及1美分的硬币。给出一种找零钱的贪心算法。(1)源程序:#include<>#include<>intmakeChange(intmoney,intcoin25,intcoi