このディレクトリの索引
http://pc12.2ch.net/test/read.cgi/tech/1269438098/775
#  [1] プログラミング応用1 
#  [2] 問題文(含コード&リンク):http://ime.nu/water.eit.hirosaki-u.ac.jp/~slmizu/pa2010/ 
#   
#  ハノイの塔を解くプログラムの時間計算量と空間計算量を調べる 
#   
#      * 時間計算量、空間計算量をそれぞれ、while ループの実行回数、プログラムが実際に使用するスタックのサイズとして求める。 
#      * 上記二つの量を円盤の枚数毎に求め、横軸に円盤枚数(1-30)をとって図にプロットする。  
#  

%
% AZ-Prologの作者 稲葉輝氏 がこの解答のために書かれたコードです。
%


/* 1〜N までのハノイの塔のスタック使用量、時間量をグラフ化する */
/* 
Inter Pritive
| ?- [-'hanoi_check.pl'].
| ?- main.

Bytecode
| ?- [-'hanoi_check.pl'].
| ?- compile_all.
| ?- main.

Full Compile
> azpc -p hanoi_check.pl /i /e hanoi_check
> hanoi_check
| ?-main.

*/


main:- main(30).
make_graph:- make_graph(30).

main(End):-
	make_data(End),      /* 計測する */
	make_graph(End).     /* graph 作成 */

make_graph(End):-           /* graph 作成のみのときはこちら */
	make_prot(time,End),    /* 時間量グラフ */
	make_prot(stack,End).   /* Stack の使用量グラフ */

/* データの生成 */
make_data(End) :-
	abolish(data,2),
    repeat(N),
    N>0,
    volume(N,X),
    write(N=X),nl,
    assertz(data(N,X)),
    N=End.

volume(N,[A,B]) :-
    X is cputime,
    h(N,a,b,c,0,A),
    B is cputime-X.

/* hanoi */
h(0,_0,_1,_2,X,X) :-!.
h(N,A,B,C,StackIn,StackOut) :-
    NN is N-1,
    StackNext is StackIn+1,
    h(NN,A,C,B,StackNext,So1),
    h(NN,B,A,C,StackNext,So2),
    (So1>So2->StackOut=So1;StackOut=So2).

/* グラフの作成 */

get_data(time,N,T):-  data(N,[_,T]),!.
get_data(stack,N,S):- data(N,[S,_]),!.

write_tabs(T,0):-!.
write_tabs(T,N):- write(T),NN is N-1,write_tabs(T,NN).

make_prot(Type,End):-
	nl,
	get_data(Type,End,W),Base is (80-4)/W,TT is integer(W),
	name(Type,TypeL),length(TypeL,TypeLL),name(TT,TTL),length(TTL,TTLL),
	A is integer(Base*W-TypeLL-TTLL-4),B is integer(Base*W-1),
	write('N | '),write(Type),write(' ->'),write_tabs(' ',A),write(TT),nl,
	write('--+'),write_tabs('-',B),write('+'),nl,
	make_prot(Type,End,1,Base),nl.

make_prot(_,End,N,_):- N>End,!.
make_prot(Type,End,N,B):-
	(N<10 -> write('0');true),write(N),write('|'),
	get_data(Type,N,W),
	SP is W*B,tab(SP),write('*'),nl,
	NN is N+1,
	make_prot(Type,End,NN,B).


% data(N,[Stack,Time])
:- dynamic data/2.
data(1,[1,0.000000000000000]).
data(2,[2,0.000000000000000]).
data(3,[3,0.000000000000000]).
data(4,[4,0.000000000000000]).
data(5,[5,0.000000000000000]).
data(6,[6,0.000000000000000]).
data(7,[7,0.000000000000000]).
data(8,[8,0.000000000000000]).
data(9,[9,0.000000000000000]).
data(10,[10,0.000000000000000]).
data(11,[11,0.000000000000000]).
data(12,[12,0.0150001049041748]).
data(13,[13,0.000000000000000]).
data(14,[14,0.0149998664855957]).
data(15,[15,0.0629999637603760]).
data(16,[16,0.125000000000000]).
data(17,[17,0.156000137329102]).
data(18,[18,0.279999971389771]).
data(19,[19,0.530999898910522]).
data(20,[20,1.06100010871887]).
data(21,[21,2.13700008392334]).
data(22,[22,4.24299979209900]).
data(23,[23,8.50200009346008]).
data(24,[24,16.9730000495911]).
data(25,[25,34.1640000343323]).
data(1,[1,0.000000000000000]).
data(2,[2,0.000000000000000]).
data(3,[3,0.000000000000000]).
data(4,[4,0.000000000000000]).
data(5,[5,0.000000000000000]).
data(6,[6,0.000000000000000]).
data(7,[7,0.000000000000000]).
data(8,[8,0.000000000000000]).
data(9,[9,0.000000000000000]).
data(10,[10,0.000000000000000]).
data(11,[11,0.000000000000000]).
data(12,[12,0.000000000000000]).
data(13,[13,0.0159997940063477]).
data(14,[14,0.0310001373291016]).
data(15,[15,0.0469999313354492]).
data(16,[16,0.0620000362396240]).
data(17,[17,0.125000000000000]).
data(18,[18,0.266000032424927]).
data(19,[19,0.546000003814697]).
data(20,[20,1.07599997520447]).
data(21,[21,2.13700008392334]).
data(22,[22,4.25900006294250]).
data(23,[23,8.51699995994568]).
data(24,[24,17.0669999122620]).
data(25,[25,35.7170000076294]).
data(26,[26,70.9749999046326]).
data(27,[27,139.519000053406]).
data(28,[28,279.661000013351]).
data(29,[29,560.915999889374]).
data(30,[30,1117.21300005913]).