資源簡介
|
A、B、C、D、E這5個人合伙夜間捕魚，凌晨時都已經疲憊不堪，于是各自在河邊的樹叢中找地方睡著了。第二天日上三竿時，A第一個醒來，他將魚平分為5份，把多余的一條扔回河中，然后拿著自己的一份回家去了；B第二個醒來，但不知道A已經拿走了一份魚，于是他將剩下的魚平分為5份，扔掉多余的一條，然后只拿走了自己的一份；接著C、D、E依次醒來，也都按同樣的辦法分魚。問這5人至少合伙捕到多少條魚？每個人醒來后所看到的魚是多少條？ 問題分析 假設5個人合伙捕了x條魚，則“A第一個醒來，他將魚平分為5份，把多余的一條扔回河中，然后拿著自己的一份回家去了”之后，還剩下4(x-1)/5條魚。 這里實際包含了一個隱含條件：假設Xn為第n(n=1、2、3、4、5)個人分魚前魚的總數，則(Xn-1)/5必須為正整數，否則不合題意。（Xn-1)/5為正整數即(X〜l)mod5=0必須成立。 又根據題意，應該有下面等式： X4=4(X5-1)/5 X3=4(X4-1)/5 X2-4(X3-1)/5 X1=4(X2-1)/5 則一旦給定X5，就可以依次推算出X4、X3、X2和X1的值。要保證X5、X4、X3、X2和X1都滿足條件(Xn-1)mod5=0，此時的X5則為5個人合伙捕到的魚的總條數。顯然，5個人合伙可能捕到的魚的條數并不唯一，但題目中強調了 “至少”合伙捕到的魚，此時題目的答案唯一。該問題可使用遞歸的方法求解。 程序設計 在main()函數中構建一個不定次數的do-while循環。定義變量x表示5個人合伙可能捕到的魚的條數，可以取x的最小值為6，讓x值逐漸增加，x每一次取值，都增加5，直到找到一個符合問題要求的答案。由于題目中問“這5人至少合伙捕到多少條魚”，而我找到的第一個x值就是5個人至少捕到的魚的總條數。 通過這個循環，就可以對每一個的可能情況進行檢查。當然，是通過調用分魚的遞歸函數來進行檢查的。 分魚的遞歸函數如下： fish()函數中包含了兩個參數：n和x。n表示參與分魚的人數，x表示n個人分魚前魚的總條數。這兩個參數都是由main()函數中傳遞進來的。 根據前面的分析，當n=5時，(x-1)mod5==0必須成立，否則該x值不是滿足題意的值，退出fish()函數，返回到main()函數，main()函數中再傳遞新的x值到fish中進行檢驗。如果(x-1)mod5==0條件成立，則要判斷n=4時，(x-1)mod5=0條件是否成立，需要注意的是，此時的形參x是4個人分魚前魚的總條數，即f(5,x)遞歸調用f(4,(x-1)/5*4)。這樣依次進行下去，直到n=1時，(x-1)mod5==0條件仍成立，則說明開始從main()函數中傳遞進來的x值是符合題意要求的一個值，可以逐層從遞歸函數中返回，每次返回值都為1，直至返回到main()函數。 |
代碼片段和文件信息
#include
/*分魚遞歸函數*/
int?fish（int?n?int?x）
{
if（（x-1）%5?==?0）
{
if（n?==?1）
return?1;?/*遞歸出口*/
else
return?fish（n-1?（x-1）/5*4）;?/*遞歸調用*/
}
return?0;?/*x不是符合題意的解，返回0*/
}
int?main（）
{
int?i=0?flag=0評論
共有 條評論