C++ブルーブリッジカップ基礎練習の楊輝三角形

C++ブルーブリッジカップテーマ解説まとめ(継続更新)
ヤングさんかくけい
リソースの制限
時間制限:1.0 sメモリ制限:256.0 MB
問題の説明
楊輝三角形はPascal三角形とも呼ばれ、そのi+1行目は(a+b)iの展開式の係数である.
その重要な性質の一つは、三角形の各数字が肩の数字に等しいことです.
次に、楊輝三角形の最初の4行を示します.
1
1 1
1 2 1
1 3 3 1
nを与え、その前のn行を出力する.
入力フォーマット
入力にはnの数が含まれます.
出力フォーマット
楊輝三角形の前n行を出力します.各行は、この行の最初の数から順に出力され、中央にスペースで区切られます.前に余分なスペースを出力しないでください.
サンプル入力
4
サンプル出力
1 1 1 1 2 1 1 3 3 1
データ規模と約定
1 <= n <= 34
構想
シナリオ1:1次元配列+1次元補助配列
私が使っているのは長さn+2の補助配列で、0位は0で、更新配列の値を記録して、出力が終わった後、実際の配列はそれと一致して、絶えず更新して、サンプルを持って説明しましょう.
[ 0 1 0 0 0 0 0 1 1 0 0 0 0 1 2 1 0 0 0 1 3 3 1 0 ] (1)\begin{bmatrix} 0 &1 &0 &0 &0 &0\\0 &1 &1 &0 &0 &0\\0 &1 &2 &1 &0 &0\\0 &1 &3 &3 &1 &0\\\end{bmatrix}\tag{1} ⎣⎢⎢⎡​0000​1111​0123​0013​0001​0000​⎦⎥⎥⎤​(1)
上記の行列に示すように、更新毎に、前回の行列の値に基づいて、更新j=1−>j=i j=1−>j=1−>j=1−>j=i規格がf(n)=f(n)+f(n−1)f(n)=f(n)+f(n)=f(n)+f(n)=f(n)+f(n)+f(n−1)を満たすため、補助配列が用いられる.この部分の私はネット上のブロガーが余分な空間を使っていないのを見て、
j=i−>j=1 j=i−>j=1 j=1 j=i−>j=1であることにより、更新値の計算が回避され、前の値の変更による煩わしさから、補助配列が不要となる.
シナリオ2:2 D配列2 Dはいれつ
考え方は上とあまり差がありませんが、2次元配列を使うと補助配列を参照する必要はありません.2次元では前の行の行列を直接参照することができますので、上記の式で示します.
コードC++
シナリオ1:1次元配列

#include
using namespace std;

int main(){
	int n;
	cin>>n;
	int lst[n+2];
	int res[n+2];
	for (int i=0;i<=n+1;i++){
		res[i]=0;
		lst[i]=0;
	}
	lst[1]=1;
	res[1]=1;
	
	for (int i=1;i<=n;i++){
		for (int j=1;j<=i;j++){ 
			res[j]=lst[j]+lst[j-1];
				cout<<(lst[j]+lst[j-1])<<" ";
		}
		cout<<endl;
		
		for (int k=1;k<=i;k++){
			lst[k]=res[k];
		}
	}
	
	return 0;
}

最適化されたコード

#include
using namespace std;

int main(){
	int n;
	cin>>n;
	int lst[n+2];
	int res[n+2];
	for (int i=0;i<=n+1;i++){
		res[i]=0;
		lst[i]=0;
	}
	lst[1]=1;
	res[1]=1;
	
	for (int i=1;i<=n;i++){
		for(int j=i;j>0;j--){
			lst[j]+=lst[j-1];
			cout<<lst[j]<<" ";
		}
		cout<<endl;
	}
	
	return 0;
}

シナリオ2:2 D配列2 Dはいれつ

#include
#include
using namespace std;

//    
int main(){
	int n;
	cin>>n;
	int lst[n][n+2];
	memset(lst,0,sizeof lst);
	lst[0][1]=1;
	
	for (int i=1;i<n;i++){
		for (int j=1;j<=n+1;j++){
			lst[i][j] = lst [i-1][j]+lst[i-1][j-1];
		}
	}
    //    ，          ，        
    for (int i=0;i<n;i++){
        for (int j=1;j<=i+1;j++){
            cout<<lst[i][j]<<" ";
        }
        cout<<endl;
    }
			
	return 0;
} 

検討してみる
この問題は1時間近くかかって、一度自分の考えに問題があることを疑って、後発は私が配列とcin>>nを宣言するのが逆であることを発見して、nを入力して変数を宣言する前に、後の運行の多くの間違いを招いて、私がC++に接触したばかりなので、まだ何が起こっているのか分からないで、もしできるならば、みんなは伝言することができます.基礎の水の問題はやはりしなければならなくて、さもなくば私の頭の鉄のようにC++の文法はすべて熟知していないと推定して、進度を速めてできるだけいくつかの基礎の問題をして、文法を強固にして記憶するしかありません.