Problem
印出巴斯卡三角形, 使用者輸入n則輸出n層巴斯卡三角形, 不使用array.
假設(shè)使用者輸入為5, 則輸出:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
Solution
這題我還真的想不出來(lái), 但是網(wǎng)路上有神人解出來(lái)了, 在此
我理解了之後來(lái)解釋一樣, 我先將i當(dāng)作row, j當(dāng)作column且都從0開(kāi)始, 很明顯地我們知道:j==0和i==j的時(shí)候會(huì)輸出1, 難的是其他部分.
我們來(lái)討論其他部分的情況, 如果數(shù)學(xué)好一點(diǎn)的會(huì)發(fā)現(xiàn)在row=i column=j會(huì)等於iCj, 難的部分來(lái)了, 因?yàn)榘退箍ㄈ切瓮ǔＪ菑纳弦粚蛹酉聛?lái)的, 但是你不能用陣列記住上一層的值, 但是其實(shí)記住每一個(gè)row的第一個(gè)值, 然後開(kāi)始向後推出來(lái).
sol1
假設(shè)所在的位址為row=i column=j 則這個(gè)數(shù)為iCj, 那你右邊的那一個(gè)數(shù)字其實(shí)就是(i+1)Cj, 那這兩個(gè)數(shù)字的比值其實(shí)就是 (j+1)Cj / iCj等於(i-j)/j+1, 既然推出來(lái)了你可以用作左邊的數(shù)字1一直去乘以這個(gè)值就行了, 這個(gè)方法有個(gè)細(xì)節(jié), 先印出自己的值, 並且順便推出下一個(gè)值, 所以你印的值都是上一次算出來(lái)的.
for(i = 0 ; i < n ; i++){
num = 1;
for(j = 0 ; j <= i ; j++){
printf("%3d",num);
num = num * (i-j)/(j+1);
}
printf("\n");
}
sol2
剛剛探討的是跟右邊數(shù)字的關(guān)係, 其實(shí)也可以探討跟數(shù)字左邊的關(guān)係, 假設(shè)所在的位址為row=i column=j 則這個(gè)數(shù)為iCj, 左邊的數(shù)字為iC(j-1), 所以兩邊的比值為(i-j+1)/j, 這方法的細(xì)節(jié)就是, 先從上一個(gè)值算出自己的值, 在印出自己的值, 所以你自己得值是從這次算出來(lái)的.
for(i = 0 ; i < n ; i++){
for(j = 0 ; j <= i ; j++){
if(i==j || j==0)
num = 1;
else
num = num * (i-j+1)/(j);
printf("%3d", num);
}
printf("\n");
}
