このディレクトリの索引
http://hibari.2ch.net/test/read.cgi/tech/1312201995/747
#   
#   
#  [1] 授業単元:アルゴリズム  
#  [2] 問題文(含コード&リンク):  
#  双方向循環リストに関する問題 
#  詳細はリンクに貼ります。 
#  http://ime.nu/codepad.org/b1UQfaJN 
#  
#  以下の関数を作れ。
#  1) ダミーノードがある場合の,「長さ」を求める関数
#  2) 双方向循環リストに対する「直前への挿入」と「削除」(削除ノードを直接指定)(option)
#  3) Josephusの問題を解くプログラム(option)
#  4) 入力:二つの整数n, m
#  5) 出力:1からnまでの番号札をもった人が,番号順に円陣を組んでいる。最初に,1番札の人からm番目の人が退席する(円陣は1減)。
#  続いて,その次からm番目の人が退席する。これを繰り返したときの,
#  退席者の順番を求め,出力せよ。
#  6) 例:n = 9, m = 5 のとき,退席者の順番は5,1,7,4,3,6,9,2,8
#  
#  以下授業で使った関数です。
#  struct node {
#  int data;
#  struct node *next;
#  };
#  struct node *head;
#  
#  双方向リスト
#  struct dnode {
#  int data;
#  struct dnode *prev;
#  struct dnode *next;
#  };
#  struct dnode *head;
#  
#  
#  空リスト作成関数
#  struct node *newlist()
#  {
#  struct node *hd, *tl;
#  hd = (struct node *) malloc(sizeof *hd);
#  tl = (struct node *) malloc(size of *tl);
#  hd->next = tl; hd->data = NULL;
#  tl->next = tl; tl->data = NULL;
#  return hd;
#  }
#  

円陣(1,2).
円陣(2,3).
円陣(3,4).
円陣(4,1).

円陣から退席(_退席者) :-
        円陣(_前席者,_退席者),
        円陣(_退席者,_次席者),
        retract(円陣(_前席者,_退席者)),
        retract(円陣(_退席者,_次席者)),
        assertz(円陣(_前席者,_次席者)).

円陣から退席(_現在の席次者,_現在の席次者からの変位,_退席者,_新たな席次者) :-
        現在から変位によって退席者を得る(0,_現在の席次者からの変位,_現在の席次者,_退席者),
        円陣(_退席者,_新たな席次者),
        円陣からの退席(_退席者),!.

現在から変位によって退席者を得る(N,N,_退席者,_退席者) :- !.
現在から変位によって退席者を得る(N,_現在の席次者からの変位,_現在の席次者,_退陣者) :-
        円陣(_現在の席次者,_次席者),
        N2 is N + 1,
        現在から変位によって退席者を得る(N2,_現在の席次者からの変位,_次席者,_退席者).