一、題目描述

一個人趕著鴨子去每個村莊賣，每經過一個村子賣去所趕鴨子的一半又一只，這樣他經過7個村莊后還剩2只鴨子，問他出發時工趕多少只鴨子？

二、算法構造

1、遞歸算法
由題意可知，對于最后一個村子duck-(duck/2+1)=2，設此時為第0個村莊。由此，定義一個有一個變量的遞歸函數duck(v)。其中，v表示所經過的村莊數。函數的意義是到達第v個村莊所有的鴨子總數。容易得到下面的遞歸公式：
duck(v) = { duck(0) = 1 v=1
| duck(v)+duck(v-1)+duck(0) v>0 && v<=7
2、非遞歸算法
具體算法實現如圖所示。

圖2.2 趕鴨子非遞歸實現

三、算法實現

// 遞歸實現 int duck(int village){if(village == 0){return 2;}else if(village > 0){return 2 * (duck(village - 1) + 1);} } //在main()中輸出每一個村莊賣出的鴨子數for(i = 1; i <= 7; i++){temp = ducks / 2 + 1;printf("經過第 %d 個村莊賣出 %d 個鴨子。\n", i, temp);ducks = ducks / 2 - 1;} // 非遞歸實現 int duck_un(int village,int sell){int d = 2;int temp = 0;for(village; village > 0; village--){temp = (d + 1) * 2;printf("經過第 %d 個村莊賣出 %d 個鴨子。\n",village,temp-d);d = (d + 1) * 2;}return temp; }

四、調試、測試及運行

1、調試
（1）進入duck()函數，調用遞歸結束開始返回的各數據的值。


（2）duck()函數調用結束各數據的值。

（3）進入duck_un()函數，調用遞歸結束開始返回的各數據的值。

（4）duck_un()函數調用結束各數據的值。

2、測試
測試代碼：

void test(int counts){int i = 1;for (; i <= 7; i++){counts = counts / 2 - 1;}if (counts == 2){printf("測試正確，最后剩余%d只鴨子。\n", counts);}else{printf("測試結果錯誤!\n");} }

測試結果：

3、運行

五、總結

test()函數傳參錯誤。

通過調試得知此時的ducks=2，應傳入參數ducks1。

總結

以上是生活随笔為你收集整理的赶鸭子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。