a-sanの日記

 | 

2009-06-23(Tue)

不正な状態遷移を見つけるアルゴリズム

状態、'0'および、'A'〜'I'に対して、
以下の状態遷移が定義されているとする。
	'0'→'A'
	'A'→'B'
	'B'→'C'
	'C'→'B'
	'C'→'A'
	'D'→'B'
	'D'→'H'
	'H'→'D'
	'E'→'F'
	'F'→'G'
	'G'→'F'
	'G'→'E'
	'I'→'I'
この状態遷移は間違っており、遷移しない状態が存在する。
遷移しない状態を求めるプログラムを作成せよ。
ここで、'0' は開始状態である。
上記の状態遷移では'D','E','F','G','H','I'が出力されればよい(順不同)。
プログラム言語、および入出力の方法については自由でよい。

お仕事で、これと等価な問題にぶち当たりました。

お仕事のはもっとややこしいのですが、本質的にはこれと等価です。

すでにお仕事ではエレガントな解決方法が見つかってクリアしています。

プログラマとしての「力試し」にはイイ感じなので、よければどうぞ(^^;

f:id:a-san:20090627013558j:image

ardbeg1958ardbeg1958 2009/07/20 05:33 GCのアルゴリズムを開発していたのですか?(笑)

 |