用C語言程式碼求N以內的勾股數(勾股數是正整數),這裡我們不算重複的,使用窮舉法。這篇經驗會提供程式碼及詳細說明。首先我會展示執行結果,然後給出程式碼,最後會對程式碼中初學者可能會有的疑問做一些解答。
工具/原料
任何一款C語言IDE
一、結果及程式碼展示
首先我展示一下執行結果,我這裡N設為1000
程式碼如下
#include
int main()
{
unsigned int a, b, c, N;
unsigned int n = 0;
N = 1000;
for (a = 1; a <= N; a++)
for (b = a+1; b <= N; b++)
for (c = b+1; c <= N; c++)
{
if (a*a + b*b == c*c)
{
printf("%5d%5d%5d\n", a, b, c);
n++;
/*if (n % 15 == 0)
getchar();*/
}
}
printf("\n共計%d個\n", n);
getchar();
return 0;
}
變數a,b,c就是代表三個欲求的勾股數;
N是欲求勾股數的範圍,我給的例子中是1000以內;
n是用來計數有多少個的,沒有需要可自行修改不用。
用 unsigned int定義是勾股數都是正整數,用這個能算更大範圍內的數,不是必要的。
二、可能有的疑問的解答
下面對我想到可能會有的一些問題做出解答,對這個演算法有興趣或者有疑問的往下看吧。
1、為什麼判斷是否是勾股數時只判斷了“a*a + b*b == c*c”,而不是“a*a + b*b == c*c a*a+c*c==b*b b*b+c*c==a*a”(為了便於後面說明,前者簡稱方式一,後者簡稱方式二)?
答:我們本意是找到勾股數而沒有重複的,打個比方,我們希望結果裡有個3,4,5就行了,而不希望除了它還有3,5,4、4,5,3、5,3,4等等。如果判斷是用了方式二,這些結果都會出現,在本程式碼中,使用方式二判斷做了無用功。
(在本程式碼中,只改判斷條件為後者結果並不變,不會出現重複的項,但這是程式碼中其他地方的功勞,具體往下看)。
可能有的小夥伴喜歡追尋真理,把判斷條件改成方式二執行發現並沒有像我說的那樣出現重複項,這是因為在前面for迴圈那裡初始值的設定過濾了會出現的重複項,這個具體第2個問題會說到。
結果雖然一致,但是使用方式二會多判斷,做無用功,所以不用方式二。在第三幅圖裡,我把前面初始值都改成了1,可以和第二幅圖對比一下,多出了許多重複項,它們是三者順序不一樣而已。
2、for迴圈的內層迴圈起始值為什麼是外層的起始值加1,即為什麼b=a+1,c=b+1?
答:前面已經展示了這樣寫可以過濾重複項,可能還有一些小夥伴會問到既然判斷條件是用了“a*a + b*b == c*c”,為什麼初始值還需要這樣寫。這裡糾正一個誤區,判斷條件使用方式一併不能杜絕所有的重複情況。插一句,演算法真正鑽研起來還是很有趣的,我直接解釋也許初學者不太能跟得上,有點暈。我先給出執行結果示例,然後再做解釋。看圖,程式碼中判斷語句不變,修改了for迴圈初始值。(看第二、第三幅圖)
有沒有發現什麼?總數跟之前的任何一次都不一樣,因為出現了其它情況產生的重複項。上面我們說到修改判斷條件為方式二出現了順序不一樣的重複項,這裡還是出現了重複項。
圖裡我已經圈出來了,看看這個判斷條件:“a*a + b*b == c*c”,按a,b,c的順序分別帶入3,4,5和4,3,5發現都成立,對於6,8,10和8,6,10道理也是一樣。從表現上來說,上面看起來是三者順序變換的重複項,此處看起來是前兩者順序變換的重複項,後者是前者的子集。
說到這裡可能還會有點暈,這裡簡單整理一下:
在for迴圈初始值設為1(沒過濾)的情況下,方式一“a*a + b*b == c*c”會出現前兩者順序不同的重複項。而方式二“a*a + b*b == c*c a*a + c*c == b*b b*b + c*c == a*a”包含了方式一的條件,也就是前兩者順序不同的重複項也會產生,因為還產生了其他的重複項所以看起來像是三個順序變換產生的。
說了這些,只是想說明判斷條件使用方式一併不能杜絕所有的重複情況,所以上面的for迴圈初始值的設定是有必要的。
列出不重複的勾股數,必然a
如果還有人要問為什麼b不能和a一樣從4開始,因為我們要找的勾股數是正整數(這是定義),等腰直角三角形直角邊為整數斜邊必為無理數(根號2倍直角邊長),所以直角邊長相同的情況也不用考慮,至此終於解釋完第二個問題了。
如果想弄清楚這個演算法又還是沒能理解就多執行幾次程式碼,改改看結果,然後基本上就慢慢理解了。
注意事項
如果想弄清楚這個演算法又還是沒能理解就多執行幾次程式碼,改改看結果,然後基本上就慢慢理解了。