やあ子供たち。今日はパスカルの三角形のn段目を取り出せるプログラムを作ったよ。
以下の、calc_nth_pascal_row()という関数がそれさ。
#include <iostream> #include <vector> using namespace std; void calc_nth_pascal_row( const int n, vector<int>* lv ) { vector<int>& v = *lv; v.push_back(1); for( int i=0; i<n-1; ++i ) { int tmp=1; int tmp2; for( int j=1; j<(int)v.size(); ++j ) { tmp2 =v[j]; v[j] = tmp + tmp2; tmp= tmp2; }// j v.push_back( 1 ); }// i return; } int main( void ) { int n= 10;// ←ここは任意段数を指定。 // for( int i=1; i<11; ++i) { vector< int > v; calc_nth_pascal_row( i, &v ); for( int ii=0; ii<(int)v.size(); ++ii) printf( "%d, ", v[ii] ); printf("\n"); }// i return 0; }
上記のようなコードを、codepadで入力し、LanguageとしてはC++を選んでSubmitすると、
以下のような結果が得られたよ。
1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 15, 20, 15, 6, 1, 1, 7, 21, 35, 35, 21, 7, 1, 1, 8, 28, 56, 70, 56, 28, 8, 1, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1,
vector使わずに用途に応じて固定長配列なふうに改造すればもっと高速化できそうだね。
用途に応じていろいろと「高速化の余地」があるコードになっているぞ。
そしてこれは、このページと内容一致してるからあってるんだと思う。
どうだこの絶妙さ。tmpと、さらに、tmp2を導入することに気付けたところがポイントかな。
何に使うんだって?画像処理の畳み込み枠に使える重みづけ関数の自動算出にだよ。決まってるじゃないか。
おじさんが意味もなくこんなコードを書こうと思うとでも思ったのかい?
ではまたな、チャオ!