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