PTA 线性表 7-1 约瑟夫环(Josephus)问题(by Yan) (100分) 按出列次序输出每个人的编号

简介: PTA 线性表 7-1 约瑟夫环(Josephus)问题(by Yan) (100分) 按出列次序输出每个人的编号

7-1 约瑟夫环(Josephus)问题(by Yan) (100分)

编号为1,2,…,n的n个人按顺时针方向围坐在一张圆桌周围,每人持有一个密码(正整数)。一开始任选一个正整数m作为报数上限值,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数,报m的那个人出列,将他的密码作为新的m值,从他顺时针方向的下一个人开始重新从1报数,数到m的那个人又出列;如此下去,直至圆桌周围的人全部出列为止。要求按出列顺序输出n个人的编号。


输入格式:

第一行输入两个整数,依次表示人数n和初始化密码m,以空格间隔。 第二行依次输入n个整数,分别表示n个人的密码,以空格间隔。

输出格式:

按出列次序输出每个人的编号,以空格间隔。

输入样例:

在这里给出一组输入。例如:

1. 7 20
2.


输出样例:

在这里给出相应的输出。例如:

6 1 4 7 2 3 5


我的认识

我对PTA的一些总结:

                               (1).PTA对输出格式要求非常高

(2).如果遇到在编译器答案能正常输出,在PTA上是答案错误,这时你要试着在scanf语句之后增加getchar语句或者检查是否是自己的代码有些地方是真的没有考虑到。

代码部分(如有那处不懂,欢迎在下方留言,我会尽早回复。若代码有问题,请指出)

代码如下:

#include <stdio.h>
#include <malloc.h>
typedef struct set{
    int password;
  int num;
    struct set * next;
}Node;
int main (void)
{   int n,m;
  int i,j = 1,k=1;
  int flag = 1;
  int a[1000];
    Node head,*phead,*p0,*p1;
  phead = NULL;
  scanf("%d %d",&n,&m);
  getchar();
  //创建链表的部分
  //创建的是一个循环链表
  for (i = 0;i<n;i++){
    if(phead == NULL){
      phead = &head;
      phead->num = j;//存编号
      p0 = phead;
      phead->next = phead;
      
    }
    else{
      p1 = (Node*)malloc(sizeof(Node));//动态创建一个结构体
      p1->next = p0;
      phead->next = p1;
      phead = p1;
      phead->num = j;
    }
    scanf("%d",&phead->password);
    j++;//更新编号
  }
  i = 0;
  //思路,循环到编号num处,则将其编号存入一个数组中
  //然后把编号的值改为0,继续进行循环
  //退出条件:数组的元素个数和链表的个数相等
  while(p0){
    if(p0->num == 0){
      p0 = p0->next;
      continue;
    }
    if(k == m && p0->num!= 0){
      a[i] = p0->num;
      m = p0->password;
      p0->num = 0;
      i++;
      k = 0;
      
    }
    k++;
    if(i == (j - 1))
      break;
    p0 = p0->next;
  }
  //输出部分
  for(j = 0;j<i;j++)
    printf("%d ",a[j]);
}

本次分享到此结束,谢谢!!!


相关文章
|
5月前
【每日一题Day287】LC24 两两交换链表中的节点 | 模拟 递归
【每日一题Day287】LC24 两两交换链表中的节点 | 模拟 递归
25 0
|
6月前
##CC10 牛牛的双链表求和
##CC10 牛牛的双链表求和
40 0
|
26天前
乘积尾零啊填空题)
乘积尾零啊填空题)
|
5月前
|
存储
【剑指offer】- 按之字形顺序打印二叉树-45/67
【剑指offer】- 按之字形顺序打印二叉树-45/67
|
5月前
|
vr&ar
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
【每日一题Day166】LC1053交换一次的先前排列 | 贪心
51 1
|
5月前
|
Java
每日一题《剑指offer》数组篇之调整数组顺序使奇数位于偶数前面
每日一题《剑指offer》数组篇之调整数组顺序使奇数位于偶数前面
36 0
每日一题《剑指offer》数组篇之调整数组顺序使奇数位于偶数前面
|
7月前
|
C++
剑指offer(C++)-JZ77:按之字形顺序打印二叉树(数据结构-树)
剑指offer(C++)-JZ77:按之字形顺序打印二叉树(数据结构-树)
|
11月前
每日一题——两两交换链表中的节点
每日一题——两两交换链表中的节点
|
11月前
|
算法
Leecode 25. K 个一组翻转链表
Leecode 25. K 个一组翻转链表
42 0
|
11月前
Leecode 24. 两两交换链表中的节点
Leecode 24. 两两交换链表中的节点
42 0