-1

私はしばらく試してみましたが、以下のプログラムで N を入力として取り、最後に死ぬ兵士が 13 番目 (N>13) になるように M を生成する方法がわかりません。

 int main()
 {
 int N, M;
 struct node { int player_id; struct node *next; };
 struct node *p, *q;
 int i, count;

 printf("Enter N (number of players): "); scanf("%d", &N);
 printf("Enter M (every M-th payer gets eliminated): "); scanf("%d", &M);

// Create circular linked list containing all the players:

p = q = malloc(sizeof(struct node));

p->player_id = 1;

for (i = 2; i <= N; ++i) {
    p->next = malloc(sizeof(struct node));
    p = p->next;
    p->player_id = i;
}

p->next = q;//Close the circular linkedlist by having the last node point to the 1st   

// Eliminate every M-th player as long as more than one player remains:

for (count = N; count > 1; --count) {
   for (i = 0; i < M - 1; ++i)

 p = p->next;       p->next = p->next->next;

  // Remove the eiminated player from the circular linked list.
     }    printf("Last player left standing is %d\n.", p->player_id);

   return 0;
  }

結果はこれと同じになるはずです（しかし、私はそれを理解していないため、リンクされたリストでそれが必要です）:>.

4

1 に答える 1

1

上記のコードをすべて読んだわけではありませんが、指定された最後のアイテムを見つけることができると思いNますM

元の問題によると、12<N<100. というわけで、制限時間内に力ずくで解けるかもしれません。

  • あなたが読んだN
  • m1 から検索するためのループを開始します
  • ループの中：
    • ループ変数を として使用して、アルゴリズムを実行しますm。最後の項目が 13 の場合、ループ変数を返します。

編集: たくさん働く必要はありません。を読む代わりにループを開始するだけですM。

M=1;
while(1)
{
//your code goes here: 
//build up the linked list with N element
//eliminate the nodes, until only one remains
//instead of writing out the last number, you check it: if it equals 13 print M, if doesn't, increment `M` and continue the loop.
 if(p->player_id==13)
 {
   printf("The minimal M is: %d\n", M);
   break;
 }
 else
   M++;
}

複数の -s に対してこれを行いたい場合はN、このループを関数に入れることができます。この場合、印刷の代わりMに、関数はそれを返す必要があります。面白いことに、リンク リストの部分はあなたが作成します。最初はもっと簡単なエクササイズを試したほうがいいかもしれません。

編集 2: HEREは私の最終的な答えです。構造と出力を確認してください。理解できることを願っています。

注: 本当に学びたいのであれば、些細な問題に飛びつくのではなく、次のようなことを行うべきだと思います。

  • ポインターを理解する
  • 構造体を理解する
  • 連結リストを理解する
  • リンクされたリストの先頭/末尾/特定の位置に挿入/更新/削除を実装する
  • ヨセフス問題を 10 分で自力で解く
于 2013-06-01T18:01:33.007 に答える