递归算法-解答.doc

_/*-1、运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。-*/*/#includeint F(int n, int &m)/若n天时，有金牌m枚；则前一天有金牌N * 7/6 + N-1枚, 即n-天时，m = m/6*7 + n. if(m%6 = 0)/因金牌的数量必须为整数，则m和m/6*7 + n也为整数, 则m必须为6的整数倍if(n = 1)return 1;/逆推至第一天时，返回1，结束main函数中的i循环else n-; m = m/6*7 + n; F(n, m);/当n不是第一天，调用F，依次向前，并将金牌数存放至&m中，即M中else return 0;/当m不是6的整数倍，返回0，不结束i循环void main()int N, M;for(int i = 1; i; i+)M = i;/因第N天刚好还有金牌N枚，可以将i赋给N M，判断是否可以推至第一天N = i;if(F(N,M) break;/返回1,结束循环printf(N = %dM = %dn, N, M);/*/验证printf(n分析:n);for(i = 1; i = N ; i+)printf(N = %d时,M = %dn, i, M);M = (M - i)/7*6;*/*-2、国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？-*/*/#includeint F(int &n, int m)/假设老国王共有n个儿子，财产共分成了m份，第一个儿子时，剩余财产份数(m-1) * 9/10, /第n+个儿子时，剩余财产份数m = (m-n) * 9/10； m = (m-n)应为10的整数倍。n+;m = m-n;if(m%10 = 0)/为10的整数倍时，进行下一步判断if(m = 0)return 1;/当财产剩余数为零时，返回1，结束main函数中的i循环else m = m/10*9; F(n, m);/当财产剩余数不为零时，调用Felse return 0;/当不是10的整数倍时，返回0，继续i循环void main()int n, m;for(int i = 1; i; i+)/当i=1时，存在一组取值n = 0;/对于每一个i，需对n清零m = i;/以i循环来产生财产份数if(F(n,m) break;/返回1,结束循环printf(n = %dm = %d 或nn, n, m);for(i = 2; i; i+)/当i=2时，存在一组取值n = 0;/对于每一个i，需对n清零m = i;/以i循环来产生财产份数if(F(n,m) break;/返回1,结束循环printf(n = %dm = %dn, n, m);/*/验证printf(n分析:n);for(i = 1; i = n ; i+)printf(n = %d时,财产剩余m = %dn, i, m);m = (m-i)*9/10;*/*-3、某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？-*/*/#includeint F(int n)if(n = 8) return 6;else return (F(n+1)+n-7)*2;/对下一站有F(n+1)= F(n)/2 + (7-n)，则F(n) = void main()printf(第1站发车时车上有乘客%d人n, F(1);/验证for(int i = 2; i=8; i+)printf(第%d站，有乘客%d人，在该站上车%d人n, i, F(i), 8-i);/*-4、猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？1022-*/*/#includeint F(int n)if(n = 10) return 0;else return (F(n+1)+1)*2;/对后一天有F(n+1)= F(n)/2 - 1，则F(n) = void main()printf(猴子们摘来桃子%d个n, F(1);/验证for(int i = 1; i=9; i+)printf(第%d天有%d个桃子，吃%d个n, i, F(i), F(i)/2+1);/*-5、小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此，第六天读完了最后的三页，问全书有多少钱页？220-*/*/#includeint F(int n)if(n = 6) return 3;else return (F(n+1)+2)*2;/对后一天有剩余页数F(n+1)= F(n)/2 - 2，则F(n) = void main()printf(全书有多少%d页n, F(1);/验证for(int i = 1; i=9; i+)printf(第%d天有%d页，读%d页n, i, F(i), F(i)/2+2);/*-6、题目描述：日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？-*/*/#includevoid F(int A, int n)if(n 6) F(A, n+1);An = An/(8-n)*(9-n) - An-1/(9-n);/An/(8-n)*(9-n)表示给出桔子前的桔子数目；/An/(8-n)*(9-n) - An-1/(9-n)表示得到桔子前的数目void main()int A7=0,420,420,420,420,420,420;/分配最后，六人各有420个A1 = A1 - A6/2 ;/老大的桔子中有A6/2 个来自老六 （注：给老大(1/3)后老六还有(2/3)，(1/3)/(2/3) = 1/2）/此时，老大到老六，分别为自己给出桔子前状态的7/8 6/7 5/6 4/5 3/4 2/3 ,由老六至老大可依次推出，得到桔