5.简单问题和递推求解

简单题目和递推求解HDOJ1008电梯ProblemDescription：我们城市最高的建筑只有一部电梯。请求列表由N个正数组成，其中的正数表示按特定顺序电梯停留的层号，电梯上一层需要6秒，下一层需要4秒，每一次停留时间为5秒钟。对每一个给出的请求列表，你需要计算完成请求列表需要的总运行时间，电梯最开始停留在0层且完成所有请求后不需要回到0层。Input：输入有多个测试实例，每个实例包含一个正整数N，后面跟N个正整数，所有整数均小于100.N=0的输入表示输入结束且该行不需要处理。Output：对每个输入实例输出一行表示总的处理时间。SampleInput1232310SampleOutput1741#includestdio.hintmain(){intn,i,t,sum,cdeg,ddeg;while(scanf(%d,&n),n!=0){cdeg=0;sum=0;for(i=0;in;i++){scanf(%d,&ddeg);if(ddeg=cdeg){sum+=(ddeg-cdeg)*6+5;cdeg=ddeg;}if(ddegcdeg){sum+=(cdeg-ddeg)*4+5;cdeg=ddeg;}}printf(%d\n,sum);}return1;}模拟法问题难以找到规律或公式，只能按照一定步骤不停做下去，最终肯定能得到答案。让计算机模拟人解决此问题的行为即可。HDOJ1108最小公倍数ProblemDescription：给定两个正整数，计算这两个数的最小公倍数。Input：输入包含多组测试数据，每组只有一行，包括两个不大于1000的正整数.Output：对于每个测试用例，给出这两个数的最小公倍数，每个实例输出一行。101470欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。定理：gcd(a,b)=gcd(b,amodb)步骤一、利用辗除法或其它方法求得最大公约数；二、最小公倍数等于两数之积除以最大公约数。算法#includestdio.hintgcd(intx,inty){intt;if(xy){t=x;x=y;y=t;}while(x%y){t=x%y;x=y;y=t;}returny;}intmain(){inta,b;while(scanf(%d%d,&a,&b)!=EOF)printf(%d\n,a*b/gcd(a,b));return1;}问题：如何改成递归形式？HDOJ1061：RightmostDigitProblemDescription：GivenapositiveintegerN,youshouldoutputthemostrightdigitofN^N.Input：Theinputcontainsseveraltestcases.ThefirstlineoftheinputisasingleintegerTwhichisthenumberoftestcases.Ttestcasesfollow.EachtestcasecontainsasinglepositiveintegerN(1=N=1,000,000,000).Output：Foreachtestcase,youshouldoutputtherightmostdigitofN^N.SampleInput234SampleOutput76#includestdio.hintmain(){intrm[10][4]={0,0,0,0,1,1,1,1,2,4,8,6,3,9,7,1,4,6,4,6,5,5,5,5,6,6,6,6,7,9,3,1,8,4,2,6,9,1,9,1};intn,i,nu,nu1,nu2;scanf(%d,&n);for(i=0;in;i++){scanf(%d,&nu);nu1=nu%10;nu2=nu%4;printf(%d\n,rm[nu1][(nu2+3)%4]);}return1;}数据规模很大时，必须找出其中的规律，避免直接计算HDOJ2035:人见人爱A^BProblemDescription:求A^B的最后三位数表示的整数。说明：A^B的含义是“A的B次方”Input:输入数据包含多个测试实例，每个实例占一行，由两个正整数A和B组成（1=A,B=10000），如果A=0,B=0，则表示输入数据的结束，不做处理。Output:对于每个测试实例，请输出A^B的最后三位表示的整数，每个输出占一行。SampleInput2312667891000000SampleOutput89841#includestdio.hintmain(){longa,b,result;longi,j;while(scanf(%ld%ld,&a,&b),a!=0||b!=0){result=1;for(i=0;ib;i++)result=result*a%1000;result=result%1000;printf(%ld\n,result);}return1;}HDOJ1425sort给你n个整数，请按从大到小的顺序输出其中前m大的数。Input：每组测试数据有两行，第一行有两个数n,m(0n,m1000000)，第二行包含n个各不相同，且都处于区间[-500000,500000]的整数。Output：对每组测试数据按从大到小的顺序输出前m大的数。SampleInput533-3592213-644SampleOutput213923常规做法：排序，然后输出前m个数据耗时间更好的做法：hash，用空间换时间#includestdio.h#includememory.hinta[1000001];intmain(){intn,m,i,in;while(scanf(%d%d,&n,&m)!=EOF){memset(a,0,1000001);for(i=0;in;i++){scanf(%d,&in);a[in+500000]=1;}for(i=1000000;i=0&&m0;i--){if(a[i]==1){if(m1)printf(%d,i-500000);elseprintf(%d\n,i-500000);m--;}}}return1;}另一个空间换时间的例子问题：对于一个字节（8bit）的数据，求其中“1”的个数，要求算法的执行效率尽可能地高。#include#defineBYTEunsignedcharBYTEnumTable[256]={0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8};intmain(intargc,char*argv[]){inti,num=0;BYTEa=0;printf(\nPleaseInputaBYTE(0~255):);scanf(%d,&a);printf(\nthenumof1intheBYTEis%d,numTable[a]);return0;}这是个典型的空间换时间算法，把0~255中1的个数直接存储在数组中，字节a作为数组的下标，checknum[a]直接就是a中“1”的个数！算法的时间复杂度：O(1)，空间复杂度：O(2n)FibonacciAgainProblemDescription:ThereareanotherkindofFibonaccinumbers:F(0)=7,F(1)=11,F(n)=F(n-1)+F(n-2)(n=2).Input:Inputconsistsofasequenceoflines,eachcontaininganintegern.(n1,000,000).Output:Printthewordyesif3divideevenlyintoF(n).Printthewordnoifnot.#includestdio.hintmain(){intyu[8]={1,2,0,2,2,1,0,1};inti,n;while(scanf(%d,&n)!=EOF){i=n%8;printf(%s\n,yu[i]==0?yes:no);}return1;}NumberSequenceProblemDescriptionAnumbersequenceisdefinedasfollows:f(1)=1,f(2)=1,f(n)=(A*f(n-1)+B*f(n-2))mod7.GivenA,B,andn,youaretocalculatethevalueoff(n).InputTheinputconsistsofmultipletestcases.Eachtestcasecontains3integersA,Bandnonasingleline(1=A,B=1000,1=n=100,000,000).Threezerossignaltheendofinputandthistestcaseisnottobeprocessed.OutputForeachtestcase,printthevalueoff(n)onasingleline.第一种解法（不可行）按照题目要求，递推计算#includeiostreamusingnamespacestd;intmain(){inta,b,n;while(cinabn&&n){intf1=1,f2=1,f,t=3;while(t=n){f=(a*f2+b*f1)%7;f1=f2;f2=f;++t;}coutfendl;}return0;}同余问题一般地，两个整数a和b，除以大于1的自然数m所得的余数相同，就称a、b对于模m同余，记作：2.同余的性质（1）（每个整数都与自身同余，称为同余的反身性。）（2）若，那么（这称作同余的对称性）（3）若，，则（这称为同余的传递性）同余的性质（2）（4）若，，则（）（这称为同余的可加性、可减性），同理：（称为同余的可乘性）（5）若，则，n为正整数，同余还有一个非常有趣的现象：如果，那么（的差一定能被k整除）#includestdio.hintmain(){intfa[51];intflag=0;inta,b,n,i,j,circle,bpos;while(scanf(%d%d%d,&a,&b,&n),(a!=0||b!=0||n!=0)){flag=0;fa[1]=1;fa[2]=1;for(i=3;i=50&&(!flag);i++){fa[i]=(a%7*fa[i-1]+b%7*fa[i-2])%7;for(j=i-1;j1;j--)if(fa[i]==fa[j]&&fa[i-1]==fa[j-1]){flag=1;bpos=j-1;circle=i-j;}}if(n=bpo