约瑟夫问题

╰半夏微凉° 2022-06-02 08:57 256阅读 0赞

约瑟夫问题

成绩10分折扣0.8

(本题要求用循环链表实现)

约瑟夫问题是一个经典的问题。已知n个人（不妨分别以编号1，2，3，…，n 代表）围坐在一张圆桌周围，从编号为 k 的人开始，从1开始顺时针报数1, 2, 3, ...，顺时针数到m 的那个人，出列并输出。然后从出列的下一个人开始，从1开始继续顺时针报数，数到m的那个人，出列并输出，…依此重复下去，直到圆桌周围的人全部出列。

输入：n,k,m

输出：按照出列的顺序依次输出出列人的编号，编号中间相隔一个空格,每10个编号为一行。

非法输入的对应输出如下

输入：：n、k、m任一个小于1  
输出：n,m,k must bigger than 0.

输入：k>n

输出：k should not bigger than n.

例

输入

9,3,2

输出

4 6 8 1 3 7 2 9 5

<table style="color:rgb(68,68,68)"> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th>测试输入<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" title="关于“测试输入”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“测试输入”的帮助"></a></th> 
   <th>期待的输出<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" title="关于“期待的输出”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“期待的输出”的帮助"></a></th> 
   <th>时间限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" title="关于“时间限制”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“时间限制”的帮助"></a></th> 
   <th>内存限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" title="关于“内存限制”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“内存限制”的帮助"></a></th> 
   <th>额外进程<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" title="关于“{$a} 个额外进程”的帮助" style="color:rgb(67,142,185)" rel="nofollow"><img src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1510491239/help" alt="关于“{$a} 个额外进程”的帮助"></a></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>测试用例 1</td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64752&amp;test=82417&amp;type=in&amp;download=0" style="color:rgb(67,142,185)" rel="nofollow">以文本方式显示</a> 
    <div> 
     <ol> 
      <li>9,3,2↵</li> 
     </ol> 
    </div> </td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64752&amp;test=82417&amp;type=out&amp;download=0" style="color:rgb(67,142,185)" rel="nofollow">以文本方式显示</a> 
    <div> 
     <ol> 
      <li>4&nbsp;6&nbsp;8&nbsp;1&nbsp;3&nbsp;7&nbsp;2&nbsp;9&nbsp;5↵</li> 
     </ol> 
    </div> </td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>测试用例 2</td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64752&amp;test=82414&amp;type=in&amp;download=0" style="color:rgb(67,142,185)" rel="nofollow">以文本方式显示</a> 
    <div> 
     <ol> 
      <li>10,12,3↵</li> 
     </ol> 
    </div> </td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=64752&amp;test=82414&amp;type=out&amp;download=0" style="color:rgb(67,142,185)" rel="nofollow">以文本方式显示</a> 
    <div> 
     <ol> 
      <li>k&nbsp;should&nbsp;not&nbsp;bigger&nbsp;than&nbsp;n.↵</li> 
     </ol> 
    </div> </td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

#include<stdio.h> 
    #include<stdlib.h> 
    int n, k, m; 
     
    typedef struct node 
    { 
       int data; 
      struct node*next; 
    }*ptrnode,node; 
    ptrnode creatList() 
    { 
        ptrnode head = NULL; 
       ptrnode s, r; 
      for (int i = 1; i <= n; i++) 
        { 
            s = (ptrnode)malloc(sizeof (struct node)); 
           s->data = i; 
            if (head == NULL) 
          { 
              head = s; 
          } 
          else 
           { 
              r->next = s; 
            } 
          r = s; 
     } 
      r->next = head; 
     return head; 
    } 
     
    int main() 
    { 
       //freopen("1.txt", "r", stdin); 
        scanf("%d,%d,%d", &n, &k, &m); 
     if (m < 1 || k < 1 || n < 1) 
      { 
          printf("n,m,k must bigger than 0.\n"); 
         return 0; 
      } 
      else if (k>n) 
       { 
          printf("k should not bigger than n.\n"); 
       } 
      else if (m == 1) 
       { 
          int i; 
         for ( i = 1; i <= n; i++) 
           { 
              if (i % 10 == 0) 
                   printf("%d\n", k); 
             else if (i==n) 
                 printf("%d\n", k); 
             else 
                   printf("%d ", k); 
              k++; 
               if (k > n) 
                  k = 1; 
         } 
      } 
      else 
       { 
          ptrnode head=creatList(); 
          ptrnode p = head; 
          int count = 0; 
         struct node*pp; 
            while (p->data !=k) 
             p = p->next; 
            int k = 0; 
         int mark; 
          /*while (1) 
            { 
              count++; 
               if (count == m-1) 
              { 
                  pp = p->next; 
                   p->next = pp->next; 
                  k++; 
                   if (k % 10 == 0) 
                       printf("%d\n", pp->data); 
                   else 
                       printf("%d ", pp->data); 
                    free(pp); 
                  count = 0; 
                 if (--n == 1) 
                      break; 
             } 
              p = p->next; 
            } 
          k++; 
           printf("%d\n", p->data);*/ 
          while (count < n) 
           { 
              for (int i = 1; i <m - 1; i++) 
                  p = p->next; 
                pp = p->next; 
               count++; 
               if (count % 10 == 0||count==n) 
             { 
                  printf("%d\n", pp->data); 
               } 
              else 
                   printf("%d ", pp->data); 
                p->next = pp->next; 
              free(pp); 
              p = p->next; 
            } 
      } 
      return 0; 
    }