このディレクトリの索引
http://pc12.2ch.net/test/read.cgi/tech/1248012902/487
#  【 課題 】http://ime.nu/rg550.hp.infoseek.co.jp/cgi-bin/joyful/img/834.txt
# [4] 探索問題のアルゴリズムについて,以下の問いに答えよ
# (1) 大きな者から順にデータが並んでいる配列を対象とする,2 分探索のプ
# ログラムコードを示せ. プログラムインタフェース(API) は
# bsearch(int key)とする.
# 
# (2) 配列を対象とする番兵法を用いない線形探索のプログラムを書け.プロ
# グラムインタフェース(API)はlsearch(int key)とする.
# 
# (3) 配列を対象とする番兵法を用いる線形探索のプログラムを書け.ただし,
# データが満杯になることはないと仮定して良い.プログラムインタフェ
# ース(API)はssearch(int key)とする.
# 
# [5] キューを配列で表現したとき,データをキューに挿入するinsert(int i)
# とデータをキューから取り除くremove()のプログラムコードを示せ.ただし
# キューが満杯になることは考えなくても良い.つまりリングキューにする必要
# はない.
# 
# [6] 連結リストでスタックを表現したとき,データをスタックに挿入する
# push(int i)とデータをスタックから取り除くpop()のプログラムコードを示
# せ.ただしスタックが空の時にpop が呼ばれたときには,エラーメッセージを
# 出すようにすること.(連結リストを使うと,原理的にはスタックが満杯になる
# ことはないので,push におけるエラーメッセージは不要)

% [4] Prologでは言語の構成要素として配列がない。リストがこれに代わって
% 利用されるが、相対位置指定によって、高速にアクセスする方法がない。
% [4]は逐次検索では遅くて役に立たない場合に使うロジックを要求しているの
% であり、リストの先頭から逐次的に手繰っていくリスト処理では答えにならない。
% Prolog向きの問題ではないといえる。
%
% ここではロジックとしてPrologで定義してみるが、これはマスデータの検索の
% 役に立つものではない。くれぐれも。

二分検索(_検索キー,降順,L) :-
    length(L,Len),
    M is Len // 2,
    list_nth_r(M,L,L1,A,L2),
    二分検索(_検索キー,降順,L1,A,L2).

二分検索(_検索キー,降順,L1,A,L2) :-
    _検索キー @> A,
    二分検索(_検索キー,降順,L1).
二分検索(_検索キー,降順,L1,A,L2) :-
    _検索キー @< A,
    二分検索(_検索キー,降順,L2).
二分検索(_検索キー,降順,L1,A,L2) :-
    _検索キー = A.

list_nth_r(0,[A|R],[],A,R) :- !.
list_nth_r(N,[A|R1],[A|R2],X,R) :-
    N1 is N - 1,
    list_nth_r(N1,R1,R2,X,R).

% [5]

insert(E,X-[E|Y],X-Y).

remove(E,[E|X]-Y,X-Y).

new(X-X).

empty(X-Y) :- X == Y.

% remove/3は組込述語として存在する。ここでは別にユーザが登録可能とする。
% 組込述語のremove/3はリストから部分リストを切り取るもの。
% ?- remove([c,d],[a,b,c,d,e],X).
% X = [a,b,e]

% [6]

push(I,Stack,[I|Stack]).

pop(I,[I|Stack],Stack).
pop(I,[],[]) :- write('Error:stack empty!\n').