递推实训答案

算法作业1、一个顽猴在一座有30级台阶的小山上爬山跳跃，猴子上山一步可跳1级，或跳3级，试求上山的30级台阶有多少种不同的爬法。答案是58425.思路：假设猴子跳到30级有f（30）种跳法，而猴子跳到30级的之前位置，只可能是第29（30-1）级和第27（30-3）级两种可能，所以f（30）=f（29）+f（27）；由此得出递推式 f（k）=f(K-1)+f(k-3)不难看出，f（1）=1，f（2）=1，f（3）=2；由此写出代码代码：#includevoid main()long f400;int n=30;int i;f1=1;f2=1;f3=2;for(i=4;i=n;i+)fi=fi-1+fi-3;printf(爬法数是%ldn,f30);2、n个水手来到一个岛上，采了一堆椰子后，因为疲劳都睡着了。一段时间后，第一个水手醒来，悄悄地将椰子等分成n份，多出m个椰子，便给了旁边的猴子，然后自己藏起一份，再将剩下的椰子重新合在一起，继续睡觉。不久，第二名水手醒来，同样将椰子了等分成n份，恰好也多出m个，也给了猴子。然而自己也藏起一份，再将剩下的椰子重新合在一起。以后每个水手都如此分了一次并都藏起一份，也恰好都把多出的m个给了猴子。第二天，n个水手醒来，发现椰子少了许多，心照不宣，便把剩下的椰子分成n份，恰好又多出m个，给了猴子。对于给定的整数n,m(约定0mn9)，试求原来这堆椰子至少有多少个？请输入人数n(1n9): 7请输入每次所剩椰子数m(0mn): 3原有椰子至少为： 5764783个.第 1个水手面临椰子： 5764783=7* 823540+3个,藏 823540个.第 2个水手面临椰子： 4941240=7* 705891+3个,藏 705891个.第 3个水手面临椰子： 4235346=7* 605049+3个,藏 605049个.第 4个水手面临椰子： 3630294=7* 518613+3个,藏 518613个.第 5个水手面临椰子： 3111678=7* 444525+3个,藏 444525个.第 6个水手面临椰子： 2667150=7* 381021+3个,藏 381021个.第 7个水手面临椰子： 2286126=7* 326589+3个,藏 326589个.最后一起分时有椰子： 1959534=7* 279933+3个.每人分得 279933个.思路：假设第k个水手面临的椰子数是飞f（k）个，不难看出递推式 f（k+1）=f（k）-m*（n-1）/nf(1)的值需要用穷举法列举，必需满足f（k）%n=m（1=k=n）为了提高穷举效率，设 变量i，f（1）=n*i+m； i递增穷举求值；试验代码：#includeint main()long f10;int m=3,n=7,k=1;long i=1;dof1=n*i+m;if(fk%n=m)/如果f（k）符合条件，递推f（k+1），然后再循环验证是否符合条件fk+1=(fk-m)*(n-1)/n;k+;if(fk%n!=m)/当f（k）不符合条件时，说明f（1）取值是不正确的，让i递增继续穷举，让k=1，重新对f（k）赋值，之前的赋值就作废了。k=1;i+;while(k=n);/当k=n时 说明所有的f（k）值已经符合条件，f（1）的值既椰子总数就确定了，可以输出结果了printf(%ldn,f1);return 0;完整代码：#includeint main()long f10;int m,n,k=1;long i=1;printf(请输入人数nn);scanf(%d,&n);printf(请输入每次所剩椰子数m(0mn)n);scanf(%d,&m);dof1=n*i+m;if(fk%n=m)fk+1=(fk-m)*(n-1)/n;k+;if(fk%n!=m)k=1;i+;while(k=n);for(i=1;i=7;i+)printf(第%d个水手面临椰子:%ld=%d*%ld+%d个,藏%ld个n,i,fi,n,fi-fi+1,