《妙趣橫生的算法》（C語言實現）-第5章 數學趣題（一）

提示：這里可以添加系列文章的所有文章的目錄，目錄需要自己手動添加
例如：第一章 Python 機器學習入門之pandas的使用

---

提示：寫完文章后，目錄可以自動生成，如何生成可參考右邊的幫助文檔

---

前言

提示：這里可以添加本文要記錄的大概內容：

例如：隨著人工智能的不斷發展，機器學習這門技術也越來越重要，很多人都開啟了學習機器學習，本文就介紹了機器學習的基礎內容。

---

提示：以下是本篇文章正文內容，下面案例可供參考

5.1 舍罕王的失算

【題目要求】

舍罕是古印度的國王，據說他十分好玩，宰相達依爾為討好國王，發明了現今的國際象棋獻給國王。舍罕非常喜歡這項游戲，于是決定嘉獎達依爾，許諾可以滿足達依爾提出的任何要求。達依爾指著舍罕王前面的棋盤提出了要求：“陛下，請您按棋盤的格子賞賜我一點麥子吧，第1個小格賞我一粒麥子，第2個小格賞我兩粒，第3個小格賞我四粒，以后每一個小格都比前一個小格賞的麥粒數增加一倍，只要把棋盤上全部64個小格按這樣的方法得到的麥粒都賞賜給我，我就心滿意足了。”舍罕王聽了達依爾這個“小小”的要求，想都沒想就滿口答應下來。結果在給達依爾麥子時舍罕驚奇地發現它要給達依爾的麥子比自己想象的要多得多，于是他進行了計算，結果令他大驚失色。問題是：舍罕王的計算結果是多少粒麥子？

【實現代碼】

// 舍罕王的失算
# include <stdio.h>
int main()
{unsigned long long int s = 0, p = 1; // 變量s記錄賞賜的總的麥粒數，變量p記錄第i個小格賞的麥粒數 for (int i = 1; i <= 64; ++i) { // 共有64個格子，使用for循環 s += p; // 累加求和 p *= 2; // 每一小格都比前一個小格賞的麥粒數增加一倍 }printf("%llu", s); // 輸出結果 return 0;
} 
// 運行結果：18446744073709551615 

【總結】

數據范圍很大，使用unsigned long long int類型可滿足要求。
另外，想清楚循環了多少次。

5.2 求兩個數的最大公約數和最小公倍數

【題目要求】

編寫一個程序計算兩個正整數的最大公約數和最小公倍數。

【實現代碼】

// 計算兩個正整數的最大公約數和最小公倍數
# include <stdio.h>
int main()
{int a, b; // 聲明變量記錄兩個正整數printf("Please input two numbers:");scanf("%d%d", & a, & b); // 輸出兩個正整數for (int i = (a <= b ? a : b); i > 0; --i) { // 計算最大公約數 if (a % i == 0 && b % i == 0) {printf("the greatest common division of %d and %d is %d\n", a, b, i);break;}}for (int i = (a >= b ? a : b); ; ++i) { // 計算最小公倍數 if (i % a == 0 && i % b == 0) {printf("the least common multiple of %d and %d is %d\n", a, b, i);break;}}return 0;
}

【總結】

可直接利用for循環解決問題，不過有些費時。歐幾里得算法應該會快一些吧。

5.3 哥德巴赫猜想的近似證明

【題目要求】

所謂哥德巴赫猜想是說任何一個大于2的偶數都能表示成為兩個素數之和。應用計算機工具可以很快地在一定范圍內驗證哥德巴赫猜想的正確性。請編寫一個C程序，驗證指定范圍內哥德巴赫猜想的正確性，也就是近似證明哥德巴赫猜想（因為不可能用計算機窮舉出所有正偶數）。

【實現代碼】

// 哥德巴赫猜想的近似證明
// 驗證1-100中大于2的偶數是否都能表示為兩個素數之和
# include <stdio.h>
# include <math.h>int isprime(int n) // 判斷素數 
{int res = 1;if (n == 1) { // 1不是素數 res = 0;}for (int i = 2; n > 2 && i <= sqrt(n); ++i) { // 2是素數if (n % i == 0) { // 有除1和本身之外的因子的數也不是素數 res = 0;break;}}return res;
}int main()
{int k = 0;for (int i = 1; i <= 100; ++i) { // 遍歷1-100這100個數 if (i <= 2 || i % 2) { // 小于2或者是奇數要排除掉 continue;}for (int j = 2; j <= i - 2; ++j) {if (isprime(j) && isprime(i - j)) {printf("%2d = %2d + %2d", i, j, i - j);++k; // 變量k用來控制輸出格式 if (k == 5) {printf("\n");k = 0;} else {printf("\t");}break;}}}return 0;
} 

【總結】

復習了判斷素數的函數。

5.4 三色球問題

【題目要求】

有紅、黃、綠三種顏色的球，其中紅球3個，黃球3個，綠球6個。現將這12個球混放在一個盒子中，從中任意摸出8個球，編程計算摸出球的各種顏色搭配。

【實現代碼】

// 三色球問題
# include <stdio.h>
int main()
{for (int i = 0; i <= 3; ++i) { // 紅球有3個，那么有4種可能性被拿出來 for (int j = 0; j <= 3; ++j) { // 黃球有3個，那么有4種可能性被拿出來 for (int k = 0; k <= 6; ++k) { // 綠球有6個，那么有7種可能性被拿出來 if (i + j + k == 8) { // 約束條件：任意拿出8個球 for (int r = 0; r < i; ++r) { // 輸出結果 printf("red ");}for (int r = 0; r < j; ++r) {printf("yellow ");}for (int r = 0; r < k; ++r) {printf("green ");}printf("\n");}}}}return 0;
} 

【總結】

窮舉法解決問題。

5.5 百錢買百雞問題

【題目要求】

我國古代數學家張丘建在《算經》一書中曾提出過著名的“百錢買百雞”問題。該問題敘述如下：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，則翁、母、雛各幾何？請編寫C程序，解決“百錢買百雞”問題。

【實現代碼】

// 百錢買百雞問題
# include <stdio.h>
int main()
{int a, b, c; // 三個變量分別表示公雞、母雞、小雞的數目for (int a = 0; a <= 100 / 5; ++a) { // 100元最多買100 / 5 = 20只公雞 for (int b = 0; b <= 100 / 3; ++b) { // 100元最多買100 / 3 = 33只母雞 for (int c = 0; c <= 300; ++c) { // 100元最多買100 * 3 = 300只小雞 if (c % 3 == 0 && a + b + c == 100 && 5 * a + 3 * b + c / 3 == 100) { // 判斷是否花了100元買了100只雞，小雞的數目要是3的倍數printf("a = %d, b = %d, c = %d\n", a, b, c);}}}} return 0;
} 

【總結】

窮舉法解決問題。

5.6 判斷回文數字

【題目要求】

有這樣一類數字，它們順著看和倒著看是相同的數，例如121、656、2332等，這樣的數字叫做回文數字。編寫一個程序，判斷從鍵盤接收的數字是否為回文數字。

【實現代碼】

// 判斷回文數字
# include <stdio.h>
int main()
{int num;printf("please input a number:");scanf("%d", & num); // 輸入正整數 int tmp = num, s = 0;while (tmp) { // 計算逆序數 s = s * 10 + tmp % 10;tmp /= 10;}if (s == num) { // 逆序數等于數字本身，那就是回文數字 printf("%d is a palindrome figures\n", num);} else {printf("%d is not a palindrome figures\n", num);}return 0;
} 

【總結】

回文數字、回文字符串一類題型，清楚回文的含義。

5.7 填數字游戲求解

【題目要求】

有這樣一個算式：ABCD * E = DCBA，其中ABCDE代表的數字各不相同。編寫一個程序，計算出ABCDE各代表什么數字。

【實現代碼】

// 填數字游戲求解
# include <stdio.h>
int main()
{for (int a = 1; a < 10; ++a) {for (int b = 0; b < 10; ++b) {if (b == a) { continue;}for (int c = 0; c < 10; ++c) {if (c == b || c == a) {continue;}for (int d = 1; d < 10; ++d) {if (d == a || d == b || d == c) {continue;}for (int e = 1; e < 10; ++e) {if (e == a || e == b || e == c || e == d) {continue;}int tmp = (a*1000 + b*100 + c*10 + d) * e;if (tmp%10 == a && tmp%100/10 == b && tmp%1000/100==c && tmp/1000 == d) {printf("A = %d, B = %d, C = %d, D = %d, E = %d\n", a, b, c, d, e);printf("%d%d%d%d\n", a, b, c, d);printf("*  %d\n", e);printf("----\n");printf("%d%d%d%d", d, c, b, a);return 0;}}}}}}return 0;
}

【總結】

仔細觀察可發現DCBA是ABCD的逆序數，可以用回文解決問題。

5.8 新郎和新娘

【題目要求】

3對新婚夫婦參加婚禮，3個新郎為A、B、C，3個新娘為X、Y、Z。有人不知道誰和誰結婚，于是詢問了6位新人中的3位，但聽到的回答是這樣的：A說他將和X結婚；X說她的未婚夫是C；C說他將和Z結婚。這人聽后知道他們在開玩笑，全是假話。請編程找出誰將和誰結婚。

【實現代碼】

// 新郎和新娘
# include <stdio.h>// 根據題目的敘述篩選除符合要求的答案
int match (int i, int j, int k, char wife[])
{if (wife[i] == 'X') { // A不和X結婚 return 0;}if (wife[k] == 'X') { // X不和C結婚 return 0;}if (wife[k] == 'Z') { // C不和Z結婚 return 0;}return 1; 
} int main()
{char husband[3] = {'A', 'B', 'C'};char wife[3] = {'X', 'Y', 'Z'};for (int i = 0; i < 3; ++i) { // 新郎A for (int j = 0; j < 3; ++j) { // 新郎B if (j == i) { // 不能1個新娘與2個新郎配對 continue;}for (int k = 0; k < 3; ++k) { // 新郎C if (k == i || k == j) { // 不能1個新娘與2個新郎配對 continue; }// 三重循環，可以得到3*2*1 = 6種配對方案// 根據題目的敘述篩選除符合要求的答案if (match(i, j, k, wife)) { // 得到一種配對方式 printf("husband  wife\n");printf("A------%c\n", wife[i]);printf("B------%c\n", wife[j]);printf("C------%c\n", wife[k]);}}}}return 0;
} 

【總結】

不知道怎么把約束條件寫出來誒，如何使用約束條件用程序寫出來。

5.9 愛因斯坦的階梯問題

【題目要求】

愛因斯坦曾出過這樣一道有趣的數學題：有一個長階梯，若每步上2階，最后剩1階；若每步上3階，最后剩2階；若每步上5階，最后剩4階；若每步上6階，最后剩5階；只有每步上7階，最后剛好一階也不剩。請問該階梯至少有多少階？編寫一個C程序解決該問題。

【實現代碼】

// 愛因斯坦的階梯問題
# include <stdio.h>
int main()
{for (int i = 1; ; ++i) {if (i % 2 == 1 && i % 3 == 2 && i % 5 == 4 && i % 6 == 5 && i % 7 == 0) {printf("該階梯至少有%d階\n");break;}}return 0;
} 
// 運行結果：119

【總結】

窮舉法。

5.10 尋找水仙花數

【題目要求】

如果一個3位數等于其各位數字的立方和，則稱這個數為水仙花數。例如：407=444+000+777，因此407就是一個水仙花數。編寫一個程序，找出全部的水仙花數。

【實現代碼】

// 尋找水仙花數
# include <stdio.h>
int main()
{for (int i = 100; i < 1000; ++i) { // 三位數 int a = i / 100; // 百位 int b = i / 10 % 10; // 十位 int c = i % 10; // 個位 if (i == a*a*a + b*b*b + c*c*c) { // 是水仙花數要輸出 printf("%d\n", i);}}return 0;
} 

【總結】

窮舉法。

5.11 猴子吃桃問題

【題目要求】

有一只猴子第一天摘下若干個桃子，當即吃掉了一半，又多吃了一個；第二天又將剩下的桃子吃掉了一半，又多吃了一個；按照這樣的吃法每天都吃前一天剩下的桃子的一半又一個。到了第十天，就只剩下一個桃子了。問題：這只猴子第一天摘了多少個桃子。

【實現代碼】

// 猴子吃桃問題
# include <stdio.h>
int main()
{int s = 1; // 第十天只剩下一個桃子for (int i = 0; i < 9; ++i) { // 前九天計算桃子數量s = 2 * (s + 1);}printf("這只猴子第一天摘了%d個桃子。", s); // 輸出結果return 0;
} 
// 這只猴子第一天摘了1534個桃子。

【總結】

遞推。

5.12 兔子產仔問題

【題目要求】

13世紀意大利數學家斐波那契他的《算盤書》中提出這樣一個問題：有人想知道一年內一對兔子可繁殖成多少對，便筑了一道圍墻把一對新生的兔子關在里面。已知一對兩個月大的兔子以后每一個月都可以生一對小兔子，而一對新生的兔子出生兩個月后才可以生小兔子（例如：1月份出生，3月份才可產仔）。假如一年內沒有發生死亡，則一年內共能繁殖成多少對？

【實現代碼】

// 兔子產仔問題
# include <stdio.h>
int main()
{int a = 1, b = 1, s = 0; // 第一月和第二月只有1對兔子 for (int i = 3; i <= 12; ++i) { s = b + a; // 從第三月起，每月的兔子數量是前兩個月的兔子數量之和 a = b; // 前一個月的兔子數量 b = s; // 前兩個月的兔子數量 }printf("一年內一對兔子可繁殖成%d對。", s); // 輸出 return 0;
} 
// 144

【總結】

遞推。求第12個月的兔子數量，不是累加每個月的兔子數量哦。

5.13 分解質因數

【題目要求】

根據數論的知識可知任何一個合數都可以寫成幾個質數相乘的形式，這幾個質數都叫做這個合數的質因數。例如24=222*3。把一個合數寫成幾個質數相乘的形式表示，叫做分解質因數。對于一個質數，它的質因數可定義為它本身。編寫一個程序實現分解質因數。

【實現代碼】

// 分解質因數
# include <stdio.h>
# include <math.h>int isprime(int n)
{int res = 1;if (n <= 1) {res = 0;}for (int i = 2; n > 2 && i <= sqrt(n); ++i) {if (n % i == 0) {res = 0;break;}}return res;
}int main()
{int num;printf("Please input a number:");scanf("%d", & num);printf("%d = ", num);int k = 0;if (isprime(num)) { // 素數直接輸出 printf("%d\n", num);} else { // 合數進行分解 for (int i = 2; ; ++i) {if (isprime(i) && num % i == 0) {++k;if (k > 1) {printf("*");} printf("%d", i);num /= i;i = 1; // 下次循環依然從2開始判斷是不是質因數if (num == 1) {break;}}}}return 0;
} 

【總結】

判斷素數函數要清楚。

5.14 常勝將軍

【題目要求】

現有21根火柴，兩人輪流取，每人每次可以取走1至4根，不可多取，也不能不取，誰取最后一根火柴誰輸。請編寫一個程序進行人機對弈，要求人先取，計算機后取；計算機一方為“常勝將軍”。

【實現代碼】

// 常勝將軍
# include <stdio.h>
int main()
{int computer, people, spare = 21;printf("--------------------------------\n");printf("---- 你不能戰勝我，不信試試 ----\n");printf("Game begin:\n\n");while (1){printf("---- 目前還有火柴 %d 根 ----\n", spare);printf("People:");scanf("%d", & people);if (people < 1 || people > 4 || people > spare) {printf("你違規了，你取的火柴數有問題！\n\n");continue;}spare -= people;if (spare == 0) {printf("\nComputer win! Game Over!\n");break;}computer = 5 - people;spare -= computer;printf("Computer:%d\n", computer);if (spare == 0) {printf("\nPeople win! Game Over!\n");break;}}return 0;
} 

【總結】

沒有想法！怎么實現這個程序啊？？
21根火柴，在人先取，計算機后取，每次取1-4根的前提下，只要保證每一輪的抽取（人先取一次，計算機再取一次）人抽到的火柴數與計算機抽到的火柴數之和為5就可以實現計算機的常勝不敗。

5.15 求圓周率的近似值

【題目要求】

編寫一個C程序，用來求出圓周率的近似值。

【實現代碼】

// 計算圓周率的近似值
# include <stdio.h>
# include <math.h>double getPI(int n);int main()
{int n;double PI;printf("Please enter accuracy\n");scanf("%d", & n);PI = getPI(n);printf("The similar value of PI is \n%f\n", PI);return 0;
}double getPI(int n)
{int div, i = 4;double b = sqrt(2) / 2.0;double c = 0.0;for (div = 0; div < n; ++div) {b = sqrt(2.0 - 2.0 * sqrt(1.0 - b * b)) * 0.5;i *= 2;}c = b * i;return c;
}

【總結】

計算圓周率的方法有許多，比如正多邊形逼近、應用數值概率算法。

5.16 魔幻方陣

【題目要求】

所謂魔幻方陣是指在nn的矩陣中填寫1-nn這些數字，使得它的每一行、每一列、以及兩個對角線之和均相等。編寫程序，打印出一種三階的魔幻方陣。

【實現代碼】

// 魔幻方陣
# include <stdio.h>
int main()
{for (int a1 = 1; a1 < 10; ++a1) {for (int a2 = 1; a2 < 10; ++a2) {if (a1 == a2) {continue;}for (int a3 = 1; a3 < 10; ++a3) {if (a3 == a2 || a3 == a1) {continue;}for (int a4 = 1; a4 < 10; ++a4) {if (a4 == a3 || a4 == a2 || a4 == a1) {continue;}for (int a5 = 1; a5 < 10; ++a5) {if (a5 == a4 || a5 == a3 || a5 == a2 || a5 == a1) {continue;}for (int a6 = 1; a6 < 10; ++a6) {if (a6 == a5 || a6 == a4 || a6 == a3 || a6 == a2 || a6 == a1) {continue;}for (int a7 = 1; a7 < 10; ++a7) {if (a7 == a6 || a7 == a5 || a7 == a4 || a7 == a3 || a7 == a2 || a7 == a1) {continue;}for (int a8 = 1; a8 < 10; ++a8) {if (a8 == a7 || a8 == a6 || a8 == a5 || a8 == a4 || a8 == a3 || a8 == a2 || a8 == a1) {continue;}for (int a9 = 1; a9 < 10; ++a9) {if (a9 == a8 || a9 == a7 || a9 == a6 || a9 == a5 || a9 == a4 || a9 == a3 || a9 == a2 || a9 == a1) {continue;}int r1 = a1 + a2 + a3;int r2 = a4 + a5 + a6;if (r1 != r2) {continue;}int r3 = a7 + a8 + a9;if (r3 != r2) {continue;}int c1 = a1 + a4 + a7;if (c1 != r3) {continue;}int c2 = a2 + a5 + a8;if (c2 != c1) {continue;}int c3 = a3 + a6 + a9;if (c3 != c2) {continue;}int s1 = a1 + a5 + a9;if (s1 != c3) {continue;}int s2 = a3 + a5 + a7;if (s2 != s1) {continue;}printf("%d %d %d\n", a1, a2, a3);printf("%d %d %d\n", a4, a5, a6);printf("%d %d %d\n", a7, a8, a9);return 0;}}}}}}}}}return 0;
} 

【總結】

耐心一些，認真一些！

5.19 完全數

【題目要求】

如果一個數恰好等于它的因子之和，那么這個數就被稱為完全數。例如6的因子為1，2，3，而6 = 1+2+3，因此6是一個完全數。求出1000以內的完全數。

【實現代碼】

// 完全數
# include <stdio.h>
int main()
{for (int i = 1; i <= 1000; ++i) { // 1000以內的數字int tmp = 0;for (int j = 1; j < i; ++j) {if (i % j == 0) {tmp += j; // 對因子累加求和}}if (tmp == i) {printf("%d ", i);}}return 0;
} 

【總結】

對數字的因子累加求和。

5.20 親密數

【題目要求】

如果整數A的全部因子（包括1，不包括A本身）之和等于B，并且整數B的全部因子（包括1，不包括B本身）之和等于A，則稱整數A和B為親密數。求解3000以內的全部親密數。

【實現代碼】

// 親密數
# include <stdio.h>
int main()
{for (int a = 2; a <= 3000; ++a) {int b = 0;for (int i = 1; i < a; ++i) {if (a % i == 0) {b += i;}}int s = 0;for (int i = 1; i < b; ++i) {if (b % i == 0) {s += i;}}if (s == a && a < b) {printf("%d %d\n", a, b);}}return 0;
} 

【總結】

對數字的因子累加求和。

總結

提示：這里對文章進行總結：

例如：以上就是今天要講的內容，本文僅僅簡單介紹了pandas的使用，而pandas提供了大量能使我們快速便捷地處理數據的函數和方法。