C言語でセルオートマトンを作成したい

最近C言語の勉強を始めた学生です。

講義中の課題で「セルオートマトン（ルール90）を作成する」というものがありました。
セルオートマトンについて・どのようなものを作るのかはわかったのですが、”次の世代を作るための計算”の部分をどのようにすれば良いのかわかりません。
ヒントとして、シフト演算を使って…と言われたのですが、なぜシフト演算が必要なのかもわからず…
昔から計算が苦手で、わからないのが歯がゆいです。

どなたか解説して頂けませんでしょうか？
ソースコードのみや、それらが載っている書籍の紹介でも構いません。

宜しくお願い致します。

No.1 ベストアンサー 回答者： osamuy 回答日時： 2012/05/20 23:11

たとえば1次元セルオートマトンの計算をするときに、セル位置0の状態計算を行ったあとで、セル位置1の計算を行うことにします。

セル位置1の計算はセル位置0の計算と同じですから、1次元セルをシフトすることで位置1のセルは位置0にくることになり、位置0について同じ計算を行えば良いことになります。同様にセル位置2の計算を行うには、さらにシフトすれば、位置2のものが位置0に来ますから、その繰り返しで1次元セル全体の計算を行うことができます。

そんなところからシフト演算を使うことをヒントとして挙げているのではないかと。

外している可能性もあるので、詳しいことは、お使いの教科書を読み返してみるか、先生の質問したほうが手っ取り早いと思います。

この回答へのお礼

なるほど、注目するセルではなくセルの中身を動かしていくんですね。
試してみようと思います！
ありがとうございます！

お礼日時：2012/05/23 22:54

No.3 回答者： jjk65536 回答日時： 2012/05/20 23:41

解説やソースをお求めとのことなので、シフト演算を使わずになるべく平易に書いてみました。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void print_data(char *data, char len)
{
　int i;
　for(i=0; i<len; i++){
　　if(data[i] == 0)
　　　printf("□");
　　else
　　　printf("■");
　}
　printf("\n");
}

void step(char *data, char len)
{
　int i;
　char rule[8][3] = {
　　{1,1,1},
　　{1,1,0},
　　{1,0,1},
　　{1,0,0},
　　{0,1,1},
　　{0,1,0},
　　{0,0,1},
　　{0,0,0}
　};
　char value[] = {0,1,0,1,1,0,1,0};
　char *result = malloc(len);
　for(i=1; i<len-1; i++){
　　int j;
　　for(j=0; j<8; j++){
　　　if(memcmp(rule[j], &data[i-1], 3) == 0)
　　　　break;
　　}
　　result[i] = value[j];
　}
　memcpy(data, result, len);
　free(result);
}

#define WIDTH 80
#define HEIGHT 40
int main(int argc, const char *argv[])
{
　char data[WIDTH] = {0};
　data[WIDTH/2] = 1;
　int len = sizeof(data);
　int i;
　for(i=0; i<HEIGHT; i++){
　　print_data(data, len);
　　step(data, len);
　}
　return 0;
}


パターン比較の処理をメモリ節約しようとしたときに、以下の様な感じで
ビットシフト使うことも考えられます。

rule[] = {7, 6, 5, 4, 3 , 2, 1, 0};
int tmp = (data[i-1] << 2) + (data[i] << 1) + data[i+1];
for(j=0; j<8; j++)
　if(rule[j] = tmp)
　　break;
result[i] = value[j];

ちょっと見当違いかもしれませんね。

この回答へのお礼

シンプルでわかりやすいソースコードをありがとうございます！
メモリ節約が目的のビットシフトとは、気付きませんでした。勉強になります。
こちらも参考にして書いてみようと思います！

お礼日時：2012/05/23 23:05

No.2 回答者： Tacosan 回答日時： 2012/05/20 23:19

うん, 確かに「シフト演算の必要性」は全くわからん... というか, シフトなぞ使わない方がシンプルじゃないかなぁ.

ま, とりあえずシフトは使わないという方向でプログラム作ってみたら?

この回答へのお礼

一応シフト演算無しのプログラムは作ってみたのですが、シフト演算を使うという考え方が一般的かと思い悩んでいました……。

「シフト演算の必要性がわからない」というご意見も非常に参考になりました！
ありがとうございます！

お礼日時：2012/05/23 22:59