14

最近の求人応募の一環として、この問題の解決策をコーディングするように依頼されました。

与えられた、

  • n=円の中に立っている人の数。
  • k=毎回カウントする人数

各人には、一意の（増分）IDが与えられます。最初の人（最も低いID）から始めて、1からkまで数え始めます。

次に、kの人が削除され、円が閉じます。次の残りの人（排除された人に続く）は1からカウントを再開します。このプロセスは、勝者である1人だけが残るまで繰り返されます。

ソリューションは以下を提供する必要があります。

  • サークルから削除された順序での各人のID
  • 勝者のID。

パフォーマンスの制約：

  • できるだけ少ないメモリを使用してください。
  • ソリューションを可能な限り高速に実行します。

何年も前からCSコースで同じようなことをしたことを思い出しましたが、このテストの時点では詳細を思い出せませんでした。私は今、それが複数の解決策を伴うよく知られた古典的な問題であることに気づきました。（一部の人は単に「ウィキペディア」の答えかもしれないので、まだ名前で言及しません）。

私はすでに解決策を提出しているので、私のために答えてくれる人を絶対に探していません。私は少し後でそれを提供します/他の人がいくつかの答えを提供した場合。

この質問をするための私の主な目標は、要件と制約を考慮して、私のソリューションが他のソリューションとどのように比較されるかを確認することです。

（「クラシック」ソリューションの一部が無効になる可能性があるため、要件に注意してください。）

4

8 に答える 8

12

Manuel Gonzalezは、これが有名なJosephus 問題の一般的な形式であることを正しく認識しました。

サイズ N の円とサイズ K のジャンプの生存者 f(N,K) のみに関心がある場合は、非常に単純な動的計画法ループ (線形時間と定数メモリ) でこれを解決できます。ID は 0 から始まることに注意してください。

int remaining(int n, int k) {
    int r = 0;
    for (int i = 2; i <= n; i++)
        r = (r + k) % i;

    return r;
}

これは、次の再帰関係に基づいています。

f(N,K) = (f(N-1,K) + K) mod N

この関係は、除去のプロセスをシミュレートし、各除去後に 0 から始まる新しい ID を再割り当てすることで説明できます。古いインデックスは、k 位置の循環シフトを持つ新しいインデックスです。この式の詳細については、http://blue.butler.edu/~phenders/InRoads/MathCounts8.pdfを参照してください。

OPは、削除されたアイテムのすべてのインデックスを正しい順序で要求することを知っています。しかし、上記の洞察はこれを解決するためにも使用できると思います。

于 2010-10-04T12:48:39.567 に答える
2

「k番目」の人を決定する問題は、ヨセフス問題と呼ばれます。マシュハドの Ferdowsi 大学の Armin Shams-Baragh は、ジョセフス問題の公式とその拡張版を公開しました。この論文は http://www.cs.man.ac.uk/~shamsbaa/Josephus.pdfで入手できます。

于 2010-09-28T14:09:32.397 に答える
2

boolean配列を使用してそれを行うことができます。

擬似コードは次のとおりです。

sizealiveのboolean配列としますN。もしそうなら、人alive[i]は生きていて、そうでなければ死んでいます。最初は、 生きている人の数だけです。というわけでスタート。trueithtrue1>=i<=N
numAlivenumAlive = N

i = 1 # Counting starts from 1st person.
count = 0;

# keep looping till we've more than 1 persons.
while numAlive > 1 do

 if alive[i]
  count++
 end-if

 # time to kill ?
 if count == K
   print Person i killed
   numAlive --
   alive[i] = false
   count = 0
 end-if

 i = (i%N)+1 # Counting starts from next person.

end-while

# Find the only alive person who is the winner.
while alive[i] != true do
 i = (i%N)+1
end-while
print Person i is the winner

上記の解決策はスペース効率は良いですが、死んだ人がチェックされているため、時間効率は良くありません。

時間効率を高めるために、循環リンクリストを利用できます。人を殺すたびに、リストからノードを削除します。リストに 1 つのノードが残るまで続行します。

于 2010-09-28T08:35:59.687 に答える
1

Clojureでの解決策は次のとおりです。

(ns kthperson.core
  (:use clojure.set))


(defn get-winner-and-losers [number-of-people hops]
  (loop [people (range 1 (inc number-of-people))
         losers []
         last-scan-start-index (dec hops)]
    (if (= 1 (count people))
      {:winner (first people) :losers losers}
      (let [people-to-filter (subvec (vec people) last-scan-start-index)
            additional-losers (take-nth hops people-to-filter)
            remaining-people (difference (set people)
                                         (set additional-losers))
            new-losers (concat losers additional-losers)
            index-of-last-removed-person (* hops (count additional-losers))]
        (recur remaining-people
               new-losers
               (mod last-scan-start-index (count people-to-filter)))))))

説明：

  • 人々 1..n のコレクションでループを開始します

  • 残っている人が 1 人だけの場合、その人が勝者となり、その ID と敗者の ID を (負けた順に) 返します。

  • 潜在的な勝者の残りのリストでN人ごとに取得することにより、各ループ/再帰で追加の敗者を計算します

  • 潜在的な勝者の新しい短いリストは、以前に計算された潜在的な勝者から追加の敗者を削除することによって決定されます。

  • すすぎと繰り返し（係数を使用して、残りの人のリストのどこから次回のカウントを開始するかを決定します）

于 2010-09-28T14:39:34.610 に答える
1

基本的に Ash の回答と同じですが、カスタム リンク リストを使用します。

using System;
using System.Linq;

namespace Circle
{
    class Program
    {
        static void Main(string[] args)
        {
            Circle(20, 3);
        }

        static void Circle(int k, int n)
        {
            // circle is a linked list representing the circle.
            // Each element contains the index of the next member
            // of the circle.
            int[] circle = Enumerable.Range(1, k).ToArray();
            circle[k - 1] = 0;  // Member 0 follows member k-1

            int prev = -1;  // Used for tracking the previous member so we can delete a member from the list
            int curr = 0;  // The member we're currently inspecting
            for (int i = 0; i < k; i++)  // There are k members to remove from the circle
            {
                // Skip over n members
                for (int j = 0; j < n; j++)
                {
                    prev = curr;
                    curr = circle[curr];
                }

                Console.WriteLine(curr);
                circle[prev] = circle[curr];  // Delete the nth member
                curr = prev;  // Start counting again from the previous member
            }
        }
    }
}
于 2010-09-28T09:19:58.160 に答える
1

これは私のソリューションで、C# でコーディングされています。何を改善できますか？

public class Person
{
    public Person(int n)
    {
        Number = n;
    }

    public int Number { get; private set; }
}


static void Main(string[] args)
{
    int n = 10; int k = 4;
    var circle = new List<Person>();

    for (int i = 1; i <= n; i++)
    {
        circle.Add(new Person(i));
    }

    var index = 0;
    while (circle.Count > 1)
    {
        index = (index + k - 1) % circle.Count;
        var person = circle[index];
        circle.RemoveAt(index);
        Console.WriteLine("Removed {0}", person.Number);
    }
    Console.ReadLine();
}
        Console.WriteLine("Winner is {0}", circle[0].Number);
于 2010-09-28T08:31:52.063 に答える
1

これはヨセフス問題の変種です。

ここでは、一般的な解決方法について説明します。

Perl、Ruby、および Python でのソリューションは、こちらで提供されています。環状二重連結リストを使用して人々の輪を表すC の簡単なソリューションを以下に示します。ただし、これらの解決策のいずれも、削除された各人の位置を特定するものではありません。

#include <stdio.h>
#include <stdlib.h>

/* remove every k-th soldier from a circle of n */
#define n 40
#define k 3

struct man {
    int pos;
    struct man *next;
    struct man *prev;
};

int main(int argc, char *argv[])
{
    /* initialize the circle of n soldiers */
    struct man *head = (struct man *) malloc(sizeof(struct man));
    struct man *curr;
    int i;
    curr = head;
    for (i = 1; i < n; ++i) {
        curr->pos = i;
        curr->next = (struct man *) malloc(sizeof(struct man));
        curr->next->prev = curr;
        curr = curr->next;
    }
    curr->pos = n;
    curr->next = head;
    curr->next->prev = curr;

    /* remove every k-th */
    while (curr->next != curr) {
        for (i = 0; i < k; ++i) {
            curr = curr->next;
        }
        curr->prev->next = curr->next;
        curr->next->prev = curr->prev;
    }

    /* announce last person standing */
    printf("Last person standing: #%d.\n", curr->pos);
    return 0;
}
于 2011-08-04T23:17:20.700 に答える
0

提出されたC＃での私の答えは次のとおりです。批判したり、笑ったり、嘲笑したりしてください;）

public static IEnumerable<int> Move(int n, int k)
{
    // Use an Iterator block to 'yield return' one item at a time.  

    int children = n;
    int childrenToSkip = k - 1;

    LinkedList<int> linkedList = new LinkedList<int>();

    // Set up the linked list with children IDs
    for (int i = 0; i < children; i++)
    {
        linkedList.AddLast(i);
    }

    LinkedListNode<int> currentNode = linkedList.First;

    while (true)
    {
        // Skip over children by traversing forward 
        for (int skipped = 0; skipped < childrenToSkip; skipped++)
        {
            currentNode = currentNode.Next;
            if (currentNode == null) currentNode = linkedList.First;
        }

        // Store the next node of the node to be removed.
        LinkedListNode<int> nextNode = currentNode.Next;

        // Return ID of the removed child to caller 
        yield return currentNode.Value;

        linkedList.Remove(currentNode);

        // Start again from the next node
        currentNode = nextNode;
        if (currentNode== null) currentNode = linkedList.First;

        // Only one node left, the winner
        if (linkedList.Count == 1) break;  
    }

    // Finally return the ID of the winner
    yield return currentNode.Value;
}
于 2010-09-28T09:11:06.613 に答える