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

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

そこで、パスカルの三角形を描くプログラムを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);
    }
}

実行イメージはこんな感じ。

ちなみに、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');
    }
}

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

#define P_RN 2
#define P_CN 2

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

として、出力したものと同じだ。

基本情報 平成28年春 C言語 昨日の続き

おはよう。

天気が悪い。

気象庁によると、こんな感じなのだそうだ。

大雨と雷及び突風に関する全般気象情報　第２号

平成２８年９月１８日０５時３５分　気象庁予報部発表

（見出し）
西日本や東日本では１８日夕方にかけて雷を伴った非常に激しい雨が降り、
大雨となる見込みです。土砂災害に厳重に警戒し、低い土地の浸水、河川の
増水やはん濫に警戒してください。落雷や竜巻などの激しい突風に注意して
ください。

（本文）
［気圧配置など］
　前線が西日本から東日本にのびており、１９日にかけて停滞する見込みで
す。山陰沖に前線上の低気圧があって、１８日夜には日本の東海上に進むで
しょう。低気圧や前線に向かって南から暖かく湿った空気が流れ込むため、
西日本や東日本では、１９日にかけて大気の状態が非常に不安定となる見込
みです。

［防災事項］
＜大雨＞
　西日本や東日本では、１８日夕方にかけて雷を伴った非常に激しい雨が降
り、大雨となるでしょう。
　１９日６時までの２４時間に予想される雨量は、いずれも多い所で、
　　　　九州北部地方、近畿地方　　　　　１５０ミリ
　　　　四国地方、北陸地方、東海地方　　１２０ミリ
　　　　関東甲信地方　　　　　　　　　　１００ミリ
　　　　中国地方　　　　　　　　　　　　　８０ミリ　　
です。

　土砂災害に厳重に警戒し、低い土地の浸水、河川の増水やはん濫に警戒し
てください。

　また、落雷や竜巻などの激しい突風に注意してください。発達した積乱雲
の近づく兆しがある場合には、建物内に移動するなど、安全確保に努めてく
ださい。

［補足事項］
　地元気象台の発表する警報や注意報、気象情報等に留意してください。
　次の「大雨と雷及び突風に関する全般気象情報」は、１８日１７時ころに
発表する予定です。

さて、一夜明けてアルコールが抜けると、頭も少し回復する。

とりあえず、昨日私が書いたコードはアルゴリズムが全然間違っていることが分かった。

アルゴリズムは問題の通りで、全くよろしい。

再帰的な条件判定という技巧が分かりづらく、直せないものかと思ったけど、改めて考えるとわかりやすい気がする。

実行時動作が止まる(segmentation fault)する理由もわかった。

scanfで、&をつけ忘れていた。

再帰的な処理のところに問題があると思うじゃない…。

というわけで、ちゃんと動くソースコードはこちら。

#include <stdio.h>

#define P_RN 2
#define P_CN 2

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

void print_frac(int);
int exists_at(int, int, int);

int main()
{
    int d;
    printf("深さ? : ");
    scanf("%d", &d);
    print_frac(d);
	
    return 0;
}

void print_frac(int d)
{
    int i, j, rn, cn;
    rn = cn = 1;
    
    for (i=0; i<d; i++) {
        rn *= P_RN;
        cn *= P_CN;
    }
    
    for (i=0; i<rn; i++) {
        for (j=0; j<cn; j++) {
            putchar(exists_at(i, j, d)? '*' : ' ');
        }
        putchar('\n');
    }
}

int exists_at(int i, int j, int d)
{
    if (!d) {
        return 1;
    } else if (!exists_at(i/P_RN, j/P_CN, d-1)) {
        return 0;
    } else {
        return pat[i%P_RN][j%P_CN];
    }
}

定数の取り扱いを修正している。
ソースコード全体を通じて値が変わらない変数は、#define か const指定をして定数であることを示すべきだと思う。
これだけで、だいぶ読みやすくなる。
問題の都合上、というところもあるのでしょうが。

基本情報 平成28年春 C言語

十六夜の月というビールを飲んでいた。

風雅な名前にたがわず、とても美味しい。

ほろ酔いで、この問題を解いていた。

基本情報技術者過去問題 平成28年春期 午後問9｜基本情報技術者試験.com

ジュリア集合とか高木関数とか、興味深いフラクタル図形を、ちょっと書いてみましょう、という問題。

もちろん、ジュリア集合とかを書くわけではなく、パターンを与えて、深さdの図形を描くだけである（ほんとうのフラクタルとは、コッホ曲線のように、d→∞としたものである）。

とりあえず問題には正解した。

でもソースコードに不満がある。

お世辞にもわかりやすいコード、安全なコードとは言えない（と思う）。

なので、書き直していた。

コンパイルは通るけど、なぜか止まる。

なぜだ。

今日はもう疲れた（酔ってるだけだが）ので、明日考えることにする。

ちなみに書き直したコードは、以下の通り。

何か気づいた人がいたら教えてください。

#include <stdio.h>

#define P_RN 2
#define P_CN 2

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

void print_frac(int);
int exists_at(int, int, int);

int main()
{
    int d;
    printf("深さ? : ");
    scanf("%d", d);
    print_frac(d);
    return 0;
}

void print_frac(int d)
{
    int i, j, rn, cn;
    rn = cn = 1;
    
    for(i=0; i<d; i++){
        rn *=P_RN;
        cn *=P_CN;
    }
    
    for(i=0; i<rn; i++){
        for(j=0; j<cn; j++){
            putchar(exists_at(i, j, d)? '*' : ' ');
        }
        putchar('\n');
    }
}

int exists_at(int i, int j, int d)
{
    if(d==0) {
        return 1;
    } else if(d==1) {
        return pat[i][j];
    } else {
        return exists_at(i/P_RN, j/P_CN, d-1);
    }
}

excelでちょっと複雑なソート

今日は金曜日である。

来る休日に向けて心も軽やかになる素晴らしい曜日である。

さて、今日は少しだけ複雑なソートをexcelで行った。

どんなソートをしたかを説明してみよう。

とりあえず、例としてデータを作ってみたので、見てほしい。

A列に市区町村、B列にその市区町村が所属する都道府県が入っている。

これを、次の条件でソートするのが本日の課題であった。

　１．基本的な順番は変えない。

　２．同じ都道府県どうしをまとめる。

たとえば、上の例のデータでいえば、次のようにソートすることになる。

　１．第4行まではすべて異なる都道府県なので、とりあえずここまでは何もしない。

　２．第1行で京都府京都市がでてきたあと、第5行で京都府宮津市が出てくる。同じ都道府県同士をまとめるので、第1行と第2行との間に、この第5行目のデータを挿入する。

　３．そのあとさらに下を見ていくと、長野県諏訪市が出てくる。このデータを長野県松本市のすぐ下に移動する。

　・・・以下略。

賢いやり方もあるのだろうが、時間もないので、簡単に対応することにした。

次のような対応である。

C1 に次の式を書く。

　=match($b1, $b$1:$b1, 0)

これを一番下までオートフィルする。

（たぶん固めなくてもできるけど）いちおうC列を値で固めてから、C列をキーにして、「並び替え」をする。

上の式の意味は、つまりこういうことである。

　今見てるレコードより上(自分自身も含めて)を見て、都道府県に同じ値を持つレコードがないかを先頭から順に探す。最初に見つかったレコードの優先度（＝そのレコードの番号＝先頭行からの位置）を、今見てるレコードの優先度とする。

そして、「並び替え」によって、この式によって設定した優先度でソートする。

というわけである。

結果はこんな風になる。

ちなみに、この手順では次の事実を使っている。

　１．match関数は、検索範囲の先頭から順にレコードを探し、最初にヒットしたレコードの位置を返す。

　２．excelの「並び替え」は安定ソートである。

match関数が重く、何万行もあるデータのソートにはそれなりのストレスがあった。

面白い問題だと思うので、効率的なアルゴリズムがないかとか、C言語での書き方だとか、今後考えてみたい。

BitBakeについて

今日は仕事でBitBakeというものを使った。

ゴロが非常に良い。

ググればすぐにいろいろ出てくる。

BitBake 概要

BitBake - Wikipedia, the free encyclopedia

Yocto Project を使用して組み込み用のカスタム Linux ディストリビューションを作成する

とりあえず、ウィキペディアの日本語版がないので、軽く翻訳しておこう。

私のフィーリングによると次のようなことが書かれている。

BitBakeはmakeライクなビルドツールである。
特に組み込みLinuxでクロスコンパイルするのに向いている。
もちろん、そういう目的に限定されるわけではないけど。

BitBakeはPortageにインスパイアされて作られた。
Portageはパッケージ管理ツールの一つでGentoo Linuxで使われている。

BitBakeはOpenEmbeddedプロジェクトの中の一つとして生まれたが、ディストリビューションとは独立したツールとなっている。
YoctoプロジェクトとOpenEmbeddedプロジェクトによって共同管理されている。

BitBakeの「レシピ」はある特定のパッケージのビルド方法を規定する。
ソースコードの配置や設定、コンパイル、ビルド、インストール、削除方法などすべてを含んでいる。
標準的な変数として、パッケージのメタデータを保存している。

BitBakeの「レシピ」はパッケージや依存関係、コンパイルオプション、インストールオプションのURLから構成されている。
ビルドが走っている間、このURLは依存関係を追跡するのに使われる。
ターゲットデバイスにインストールするのに適した形にコンパイルして、パッケージにしてくれる。
ルートファイルシステムやカーネルから構成される完全なイメージを作ることもできる。
BitBakeのフレームワークはクロスビルドをセットアップする第一歩として、ターゲットのプラットフォームに適したクロスコンパイラのツールチェインを作ろうとしているわけである。

途中から怪しくなってきた。

とりあえずフィーリングで理解しておく。

そのうちBitBakeのレシピを書くことにもなるかもしれない。

というか、今日先輩と一緒に少しだけいじった。

何をやっているか1mmも理解していなかったけれど。

BitBakeについて書かれた本というのは、日本語では見当たらない。

英語で書かれている本では、その名も"BitBake"という本を見つけたけど、Amazonのレビューで"What a waste"と書かれている。

良い本はないらしい。

www.amazon.co.jp

とりあえず、BitBakeとか細かいことよりも、組み込みLinuxとかYoctoプロジェクトとか、?だらけなので、そこらへんの概要をつかむことが先決だろう。

ゆっくり歩け、たくさん水を飲め

中秋の名月である。

あいにく、雲は晴れず、美しからん月を見ることは叶わない。

しかし、仲秋という暦が、夏の終わりを教えてくれる。

読書の秋、食欲の秋、スポーツの秋。

なんとでも言われる秋である。

勉強にもちょうどよいに違いない。

というわけで、意識を高めるためにブログを開設してみた。

三日坊主の予感満載である。

私は今年の春に、IT系の会社に就職した。

いちおうプロのプログラマということなのだが、就職前はまったく関係のない勉強をしていた。

なので、学ぶことの必要性を日々実感している。

そんな私の学習を記録してみようと思う。

公開の場で進めることで、さらに意識が高まるに違いない。

たぶん。

内容は低レベル極まれる感じになると予想されるので、ちゃんとしたものを見たい人はちゃんとした文献などを当たってくださいね。

おそらく、IT系に限らず、なんでも書くブログになる。

もともと、私はいろいろなことに興味を持つ性分である。