パスカルの三角形
ループ制御と計算
アルゴリズム関連の書物でしばしば見かけるアルゴリズムです
実際にみると、さほど複雑な内容でもなく
計算も、普通の公立高校程度の知識があれば理解できる内容です
まずパスカルの三角形ですが、頂点を1として、必ず斜め上の値を加算したものが下にきます
数学的に見ると、行を i 列を j とし、行は頂点、列は左を0と考え
その関係はiCjにあることがわかります
例えば、三角形の 3 行目は、3C0 , 3C1 , 3C2 , 3C3 となるでしょう
（この計算式は、たとえば5C2であれば、5 * 4 / 2 * 1 を行う）
そこで、まずはこの計算モジュールを作成してみようと思います
モジュールでやらなければならない計算は、iCjの場合
iをj回、毎回1減算しながら乗算した和と、jが0になるまで毎回1減算しながら乗算した和を得
それを除算した結果を返せばよいですね
int getMathC(int i , int j) {
int x = 1 , tmp = 1 , cou = j;
if ( i == 0 ) return 1;
if ( i == j ) return 1;
if ( j == 1) return i;
for (; cou > 0 ; cou-- , i--) x *= i;
for (; j > 0 ; j--) tmp *= j;
x = x / tmp;
return x;
}
i が 0 だったり、i と j が同じ値であれば、必ず1になります
そのため、まず計算が必要かどうかを選択して、必要のない場合は適切な値を返しています
最初のfor文は、iをj回、繰り返すごとに1減算しながら乗算した和をxに代入しています
次のfor文は j を1減算しながら0になるまで乗算した和を tmp に代入しています
最後に x を tmp で除算することで iCj を表現しています
これができれば、あとは原理に基いて出力するだけです
問題は空白をどう表現するかですが、これには様々なアプローチがあるでしょう
今回は、比較的簡単な配列を用いた方法を採用します
まず、配列内のデータを全てスペースの空白で埋めます
そして、空白の終端に0を代入しておけば、C言語の場合はそこで文字列が終わります
0を代入する位置は頂点を最大行数 * 2の位置にするようにします
こうすれば、行ごとに最大行数 - 行 * 2 で縮まっていく空白を表現できます
#include <stdio.h>
int getMathC( int , int );
int main() {
char sp[128];
int i = 0 , j = 0 , count , n_count , height = 5;
for (count = 0 ; count < 128 ; count++) sp[count] = ' ';
for (count = 0 ; count < height ; count++ , j = 0 , i++) {
sp[(height - count) * 2] = 0;
printf("%s" , sp);
for (n_count = 0 ; n_count <= count ; n_count++ , j++ ) {
printf("%d " , getMathC( i , j ) );
}
printf("\n");
}
return 0;
}
int getMathC(int i , int j) {
int x = 1 , tmp = 1 , cou = j;
if ( i == 0 ) return 1;
if ( i == j ) return 1;
if ( j == 1) return i;
for (; cou > 0 ; cou-- , i--) x *= i;
for (; j > 0 ; j--) tmp *= j;
x = x / tmp;
return x;
}
このプログラムでは、2桁以上の数が出力されると
空白の関係でレイアウトが崩れてしまいますが、パスカルの三角形を表現しています
main()関数内の変数 height の値を変えると行数が変化します