詳解C語言處理算經中著名問題百錢百雞
🌟 前言
Wassup guys,我是Edison😎
今天是C語言每日一練,第117天!
Let’s get it!
1. 問題描述
中國古代數學傢張丘健在他的 《算經》 中提出瞭一個著名的 “百錢百雞問題” 👇 一隻公雞值五錢,一隻母雞值三錢,三隻小雞值一錢,現在要用百錢買百雞,請問公雞、母雞、小雞各多少隻?
2. 問題分析
如果用百錢隻買公雞,最多可以買20隻,但題目要求買一百隻,所以公雞數量在 0~20 之間。 同理,母雞數量在 0~33 之間。 在此把公雞、母雞和小雞的數量分別設為cock、hen、chicken,則 c o c k + h e n + c h i c k e n = 100 cock+hen+chicken=100 cock+hen+chicken=100 因此百錢買百雞問題就轉換成解不定方程組的問題瞭:
3. 算法思路
對於不定方程組,我們可以利用窮舉循環的方法來解決。 公雞范圍是 0~20,可用語句for(cock=0; cock<=20; cock++)
實現。 錢的數量是固定的,要買的雞的數量也是固定的,母雞數量是受到公雞數量限制的。 同理,小雞數量受到公雞和母雞數量的限制,因此可以利用三層循環的嵌套來解決:第一層循環控制公雞數量,第二層控制母雞數量,最裡層控制小雞數量。
4. 代碼實現
📝
#include <stdio.h> int main() { int cock = 0; int hen = 0; int chicken = 0; for (cock = 0; cock <= 20; cock++) //外層循環控制公雞數量取值范圍0~20 { for (hen = 0; hen <= 33; hen++) //中層循環控制母雞數量取值范圍0~30 { for (chicken = 0; chicken <= 100; chicken++) //內層循環控制小雞數量取值范圍0~100 { //在內外層循環條件控制下小雞數量的取值限制用難一組解的合理性 if ((5*cock + 3*hen + chicken/3.0 == 100) && (cock + hen + chicken == 100)) { printf("cock=%2d, hen=%2d, chicken=%2d\n", cock, hen, chicken); } } } } return 0; }
運行結果👇
5. 算法優化
以上算法需要窮舉嘗試 21 ∗ 34 ∗ 101 = 72114 21 *34*101=72114 21∗34∗101=72114 次,算法的效率明顯太低瞭。 對於本題來說,公雞的數量確定後,小雞的數量就是固定為 100 − c o c k − h e n 100-cock-hen 100−cock−hen,無須進行窮舉瞭。 此時約束條件就隻有一個: 5 ∗ c o c k + 3 ∗ h e n + c h i c k e n / 3 = 100 5*cock+3*hen+chicken/3=100 5∗cock+3∗hen+chicken/3=100。 這樣我們利用兩重循環即可實現。
此算法隻需嘗試 21 ∗ 34 = 714 21 * 34 = 714 21∗34=714 次,實現時約束條件中限定瞭chicken必須能被3整除。 隻有chicken能被3整除時才會繼續進行約束條件 5 ∗ c o c k + 3 ∗ h e n + c h i c k e n / 3 = 100 5*cock+3*hen+chicken/3=100 5∗cock+3∗hen+chicken/3=100 的判斷。 這樣省去瞭chicken不能被3整除時需要進行的算術計算和條件判斷,進一步提高瞭算法的效率。
到此這篇關於詳解C語言處理算經中著名問題百錢百雞的文章就介紹到這瞭,更多相關C語言 百錢百雞內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- C語言char s[]和char* s的區別
- C語言深度解剖篇之關鍵字以及補充內容
- C語言函數基礎教程分類自定義參數及調用示例詳解
- C語言中#define定義的標識符和宏實例代碼
- C語言學習之函數知識總結