0

ジョセフス問題に慣れていない場合:

N 人の兵士が輪になって立っています。彼らは全員処刑され、1 から始まり M ずつ移動します。以下のコードは、N と M を要求し、最後に立っているプレイヤーを生成します。

#include <stdio.h>
#include <stdlib.h>
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 linkedl
}

printf("Last player left standing is %d\n.", p->player_id);

return 0;
}

N=17;M=7 としましょう。出力は 13 である必要があります。上記のプログラムは 2 を生成します (何が起こるでしょうか? 1 からではなく M からカウントを開始するため、1,8,15 の代わりに ...... 7 を削除します)。 ,14......) これは私があなたの助けを必要とするところです (リンクされたリストは私にとってまだ難しい概念であるため)。これを変更するにはどうすればよいですか？

4

1 に答える 1

0

ノード除去ラインを間違った場所に配置しました。

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

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

最初から M ノードをカウントするループの後にこの行を配置したため、常に (M+1) 番目のノードの削除から始まります。最初のノードから開始するように、その前に移動する必要があります。

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

}

これはあなたが探しているものですか？

于 2013-06-02T20:23:59.850 に答える