studies

いろいろ勉強用備忘録的な感じ

パスカルの三角形を描くプログラム

フラクタルを描く問題に刺激されて、何か再帰的な処理を含むプログラムを書いてみたくなった。
とはいえ、定番の再帰的に階乗計算じゃつまらない。

そこで、パスカルの三角形を描くプログラムをC言語で書いてみた。
(これも定番なんだろうな…)。

choice関数が再帰的な関数になっている。

#include <stdio.h>

void print_pascal(int);
int choice(int, int);

int main()
{
    int d;
    printf("段数? : ");
    scanf("%d", &d);
    print_pascal(d);
    return 0;
}

void print_pascal(int d)
{
    int i, j;
    
    for (i=0; i<d; i++) {
        for (j=0; j<=i; j++) {
            printf("%6d", choice(i, j));
        }
        putchar('\n');
    }
}

int choice(int n, int r)
{
    if (r<0 || r>n) {
        return 0;
    } else if (r==0) {
        return 1;
    } else {
        return choice(n-1, r-1) + choice(n-1, r);
    }
}

実行イメージはこんな感じ。
f:id:developingskills1110:20160918104146p:plain


ちなみに、print_pascalを少し編集した、print_sierpinskiを使うと、シェルピンスキーのギャスケットが書ける。
パスカルの三角形の偶数のところだけくり抜くと、シェルピンスキーのギャスケットが現れる、という性質を使っている。

void print_sierpinski(int d)
{
    int i, j;
    
    for (i=0; i<d; i++) {
        for (j=0; j<=i; j++) {
            putchar(choice(i, j)%2 ? '*' : ' ');
        }
        putchar('\n');
    }
}

f:id:developingskills1110:20160918105806p:plain

これはもちろん、基本情報 平成28年春 C言語の問題のフラクタルパターンを

#define P_RN 2
#define P_CN 2

const int pat[P_RN][P_CN] = {
    {1, 0},
    {1, 1}
};

として、出力したものと同じだ。
f:id:developingskills1110:20160918110511p:plain