约瑟夫斯问题
实验题目:约瑟夫斯问题的一种描述是:编号为1,2,……n的n个人按顺时针方向围坐一圈,每人持有一个密码9(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按照顺时针方向自1开始报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他在顺时针方向下一个人开始重新重新从1报数,如此下去,直至所有的人全部出列为止。试设计一个程序,按出列顺序印出各人编号。假定参数m=20,n=7; 则输出应为 6 1 4 7 2 3 5
这是我写的程序 输出前两个是对的,后面就错了,逻辑有点问题;求修改!
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
int data;
int key;
struct node *next;
} Node;
Node *circle_create(int n);
void count_off(Node *head, int m,int n);
int main()
{
int n,m;
printf("输入m n");
scanf("%d %d", &m,&n);
Node *head = circle_create(n);
count_off(head,m,n);
return 0;
}
Node *circle_create(int n)
{
Node *temp, *new_node, *head;
int i;
// 创建第一个链表节点并加数据
temp = (Node *) malloc(sizeof(Node));
head = temp;
printf("输入key");
scanf("%d",&(temp->key));
head->data = 1;
// 创建第 2 到第 n 个链表节点并加数据
for(i = 2; i <= n; i++)
{
new_node = (Node *) malloc(sizeof(Node));
new_node->data = i;
printf("输入key");
scanf("%d",&(new_node->key));
temp->next = new_node;
temp = new_node;
}
// 最后一个节点指向头部构成循环链表
temp->next = head;
return head;
}
void count_off(Node *head,int m,int n)
{
int i;
Node *temp, *t,*val;
temp = head;
t = head;
while(temp->data != (m%n))//temp指向第m%n个元素
temp = temp->next;
printf("%d\n",temp->data);//
while( t->next != temp)//删除
t = t->next;
t->next = t->next->next;
while(temp != temp->next)//当链表元素大于二时
{
for(i = 1; i < (temp->key)-1; i++)
{
temp = temp->next;
}
printf("%d\n",temp->data);
while( t->next != temp)
t = t->next;
t->next = t->next->next;
temp = temp -> next;
}
printf("%d\n",temp->next->data);
free(temp);
return;
}