14

説明： 処刑されるのを待っている人々が輪になって立っています。カウントアウトは、円のあるポイントで始まり、円の周りを固定方向に進みます。各ステップで、一定数の人がスキップされ、次の人が実行されます。排除は、自由を与えられた最後の人だけが残るまで、円の周りを進みます（処刑された人が取り除かれるにつれてますます小さくなります）。

私はこの「ヨセフスの問題」をグーグルで検索しました。ウィキペディアのヒットにより、動的計画法の解決策f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1が得られました。しかし、これは最後の生存者しか得られません。どうすれば人々のシーケンスを実行させることができますか？たとえば、p（5、3）={3,1,5,2,4}。

また、O(nlogn)解決策の代わりに解決策はありO(nk)ますか？

4

5 に答える 5

8

処刑された人物と最後の生存者のシーケンスを取得するには、プロセス全体を最初からシミュレートするだけです。手順の説明を考えると、これは非常に簡単な作業です。あなたが提示する式は、誰が生き残るかを確認し、答えをすばやく得るための近道にすぎません。

レンジ ツリーを使用して O(n log n) でこれを行う方法の説明は次のとおりです: http://pl.scribd.com/doc/3567390/Rank-Trees

より詳細な分析については、http: //www.imt.ro/romjit/Volum12/Number12_1/pdf/02-MCosulschi.pdfを参照してください。

于 2013-03-09T13:20:01.220 に答える
2

人を表す最も自然なデータ構造は、循環バッファーです。私のソリューションは、リンクされたリストを作成し、リストの末尾を先頭に結び付けてから、実行する次の人までバッファを繰り返しカウントし、バッファからその人を削除し、バッファの末尾がそれ自体を指すまで続行します.

(define (cycle xs)
  (set-cdr! (last-pair xs) xs) xs)

(define (josephus n m)
  (let loop ((k (- m 1)) (alive (cycle (range 0 n))) (dead '()))
    (cond ((= (car alive) (cadr alive))
            (reverse (cons (car alive) dead)))
          ((= k 1)
            (let ((dead (cons (cadr alive) dead)))
              (set-cdr! alive (cddr alive))
              (loop (- m 1) (cdr alive) dead)))

例えば：

> (josephus 41 3)
(2 5 8 11 14 17 20 23 26 29 32 35 38 0 4 9 13 18 22 27 31 36
40 6 12 19 25 33 39 7 16 28 37 10 24 1 21 3 34 15 30)

私のブログでより完全な説明を読むことができ、3 つの異なる解決策が示されています。または、 http://programmingpraxis.codepad.org/RMwrace2でプログラムを実行できます。

于 2013-03-09T13:56:42.717 に答える
1

人々はサイズnの配列に格納されます。インデックスの人iが今実行された場合、次は次のようになります(i+k)%m。ここで、mは残りの人の数です。反復ごとに、配列サイズは1ずつ減少し、残りの要素はそれに応じてシフトされます。

入力：People [0..n-1]、n、k、i（=実行された最初の人のインデックス）

擬似コードは次のようになります。

Print People[i]

While (n > 1)
do
  n = n - 1
  for j = i to n-1
    People[j] = People[j+1]
  i = (i+k) % n
  print People[i]
done
于 2013-03-09T13:25:18.123 に答える
1

プログラムを刺激するために、プレーヤーの名前を含む構造体と、プレーヤーがアクティブかどうかを追跡するタグを使用できます。新しいラウンドで特定の数のプレーヤーをスキップするたびに、ループと条件文を使用して、ゲームに参加していないすべてのプレーヤーを無視し、ゲームに参加しているプレーヤーのみをカウントします。もちろん、printf ステートメントを追加して、現在のステータスを出力します。

于 2013-03-09T13:32:31.930 に答える
1

この実行シーケンスを出力するという質問に答えるには、シミュレーションが必要です。これは、O(nk) の複雑さを意味します。同時に O(nlogn) 時間の複雑さを求めながら、[O(n) である] 実行シーケンスを取得することは不可能です。処刑されるすべての人を出力する必要があるため、O(n) です。

kkonrad の Range Trees への言及は、優れた O(nlogn) ソリューションをもたらします。他の人が指摘しているように、循環リンクリストはこの問題の効率的なデータ構造です。Code Review の 200_success の Java ソリューションは、非常に洗練されていて読みやすいと思います。

public class CircularGunmenIterator<T> implements Iterator<T> {

  private List<T> list;
  private Iterator<T> iter;

  public CircularGunmenIterator(List<T> list) {
    this.list = list;
    this.iter = list.iterator();
  }

  @Override
  public boolean hasNext() {
    // Continue as long as there is a shooter and a victim
    return this.list.size() >= 2;
  }

  @Override
  public T next() {
    if (!this.iter.hasNext()) {
      // Wrap around, creating the illusion of a circular buffer
      this.iter = this.list.iterator();
    }
    return this.iter.next();
  }

  @Override
  public void remove() {
    this.iter.remove();
  }

  public static void main(String[] args) {
    // Create the gunmen
    List<Integer> gunmen = new LinkedList<Integer>();
    for (int i = 1; i <= 100; i++) {
      gunmen.add(i);
    }

    // Shootout!
    Iterator<Integer> ringIter = new CircularGunmenIterator<Integer>(gunmen);
    while (ringIter.hasNext()) {
        Integer shooter = ringIter.next();
        Integer victim  = ringIter.next();
        System.out.printf("%2d shoots %2d\n", shooter, victim);
        ringIter.remove();  // Bang!
    }
    System.out.println("Last one alive: " + gunmen.get(0));
  }
}

このヨセフスの問題 (k = 2) については、ウィキペディアに詳細がいくつかあります。

http://en.wikipedia.org/wiki/Josephus_problem

于 2014-07-31T01:27:52.310 に答える