本文介绍了用链表求解 Josephus的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我已经尝试了一段时间,但我不知道如何让下面的程序以 N 作为输入并生成一个 M,以便最后一个死去的士兵是第 13 个(N>13);

I've been tryin for a while but i cant figure out how to make the program below take N as input and generate an M in order that the last soldier that dies is the 13th(N>13);

 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
.", p->player_id);

   return 0;
  }

结果应该与this 一个(但我在链表中​​需要它,因为我不理解那个):>.

the result should be the same as this one(but I need it in linked lists cos i dont understand that one):>.

推荐答案

上面的代码我没看懂,我觉得它可以找到给定 NM 的最后一项

I didn't read all the code above, I think it can find the last item for given N and M

根据原题,12.所以,很可能它可以在给定的时间内简单地用蛮力解决.

According to the original problem, 12<N<100. So, probably it can be solved in the given time limit simply with brute force.

  • 你读入了N
  • 开始循环以从 1
  • 中查找 m
  • 在循环中:
    • 运行算法,使用循环变量作为m.如果最后一项是 13,则返回循环变量.
    • You read in N
    • start a loop for finding m from 1
    • in the loop:
      • run the algorithm, using the loop variable as m. If the last item is 13, return the loop variable.

      你不必工作很多.你只是简单地开始一个循环而不是阅读M.

      You don't have to work a lot. You just simply start a loop instead of reading 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
      ", M);
         break;
       }
       else
         M++;
      }
      

      如果您想对多个 N-s 执行此操作,您可以将此循环放入一个函数中.在这种打印 M 的情况下,函数应该返回它.有趣的是:链表部分是由你完成的.也许你应该先尝试更简单的练习.

      If You want to do this for multiple N-s, You can put this loop into a function. In this case insted of printing M, the function should return it.The funny thing is: The linked list part is done by You. Maybe You should try simpler exercises first.

      编辑 2:HERE 是我的最终答案,检查结构和输出,希望可以理解.

      EDIT 2:HERE is my final answer, check the structure and the output, I hope it is understandable.

      注意:我认为如果你真的想学习,你应该做这样的事情而不是跳进一个不小的问题:

      NOTE:I think if You really want to learn, You should do something like this instead of jumping in a not trivial problem:

      • 理解指针
      • 了解结构
      • 了解链表
      • 对链表的头/尾/某个位置实现插入/更新/删除
      • 自己在 10 分钟内解决约瑟夫斯问题

      这篇关于用链表求解 Josephus的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-06 06:07