【題目鏈接】

ybt 2043：【例5.11】楊輝三角形

【題目考點(diǎn)】

1. 遞推

遞推問題要從以下3個(gè)方面著手分析：

• 遞推狀態(tài)定義
• 初始狀態(tài)
• 遞推關(guān)系

【解題思路】

二維數(shù)組遞推經(jīng)典問題
我們要考察輸出時(shí)楊輝三角各位置之間數(shù)值的遞推公式。
根據(jù)示例：
1
1 1
1 2 1
1 3 3 1

假設(shè)空的位置的值都是0，將其存入二維數(shù)組，結(jié)果應(yīng)該為

通過觀察可知，第i行有i個(gè)元素，第1列的元素都是1，除了第1列的元素，根據(jù)楊輝三角的定義，每個(gè)元素(i,j)是其上方元素(i-1,j)及左上方元素(i-1,j-1)的加和。

• 遞推狀態(tài)：a[i][j]:第i行第j列的值
• 遞推初始狀態(tài)：a[i][1] = 1
• 遞推關(guān)系：a[i][j] = a[i-1][j] + a[i-1][j-1]

【題解代碼】

解法1：遞推

二維數(shù)組初始化為0，每行最后一個(gè)1通過遞推關(guān)系，即由其左上及上方元素相加得到。

#include<bits/stdc++.h> using namespace std; int main() {int n, a[25][25] = {};//注意：數(shù)組要初始化為0，這樣讓每行最后一個(gè)1也能通過遞推關(guān)系得到 cin >> n;for(int i = 1; i <= n; ++i)for(int j = 1; j <= i; ++j)//每行有i個(gè)元素 {if(j == 1)a[i][j] = 1;//遞推初始狀態(tài) elsea[i][j] = a[i-1][j] + a[i-1][j-1];//遞推關(guān)系 }for(int i = 1; i <= n; ++i){for(int j = 1; j <= i; ++j)//每行有i個(gè)元素 cout << a[i][j] << ' ';cout << endl; }return 0; }

解法2：遞推

每行最后一個(gè)1通過特殊判斷進(jìn)行賦值

#include<bits/stdc++.h> using namespace std; int main() {int n, a[25][25];cin >> n;for(int i = 1; i <= n; ++i)for(int j = 1; j <= i; ++j)//每行有i個(gè)元素 {if(j == 1 || j == i)a[i][j] = 1;//每行第1和最后1個(gè)數(shù)特殊處理 elsea[i][j] = a[i-1][j] + a[i-1][j-1];//遞推關(guān)系 }for(int i = 1; i <= n; ++i){for(int j = 1; j <= i; ++j)//每行有i個(gè)元素 cout << a[i][j] << ' ';cout << endl; }return 0; } 新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通 2043：【例5.11】杨辉三角形的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。