关于约瑟夫问题代码的分享
本帖最后由 ByTime 于 2020-2-27 18:22 编辑用VScode写的
//用循环链表模拟约瑟夫问题
#include<stdio.h>
#include<stdlib.h>
typedef struct people
{
int number;
struct people *next;
}people;
int globoal;
//循环链表的创立 创建number个节点返回头部链表指针
people *creat_struct(int number)
{
int creat_people;
int struct_size;
people *head,*p1,*p2;
globoal = number;
struct_size = sizeof(people);
head = p1 = (people*)malloc(struct_size);
//printf("请输入:");
//scanf("%d",&head->number);
head->number = 1;
for(creat_people=1;creat_people<number;creat_people++)
{
p2 = (people*)malloc(struct_size);
p1->next = p2;
p1 = p2;
//fflush(stdin);
//printf("请输入:");
//scanf("%d",&head->number);
p1->number = creat_people+1;
p1->next = head;
}
//printf("head=%p,p1=%p,p2=%p\n",head,p1,p2->next);
return head;
}
//约瑟夫环问题
//head为传入循环链表的头结点，
//number为约瑟夫问题中的数到多少要杀掉的人数；
void joseph_problem(people *head,int number)
{
people *del;
int first_move = number-2;
int after_move = number-1;
int read;
int move = 1;
for(;move<=first_move;move++)
{
head = head->next;
}
del = head->next;
head->next = head->next->next;
printf("->%d",del->number);
free(del);
globoal--;
while (globoal > after_move)
{
head = head->next->next;
del = head->next;
head->next = head->next->next;
printf("->%d",del->number);
free(del);
globoal--;
}
read = globoal;
while(read!=0)
{
printf("\n剩下:%d号\n",head->number);
head=head->next;
read--;
}
}
int main()
{
int pwd;
people *headl;
//41为约瑟夫问题中代表的人的数量
head = creat_struct(41);
//3代表每次数到多少杀掉的人
joseph_problem(head,3);
return 0;
} 运行结果：
->3->6->9->12->15->18->21->24->27->30->33->36->39->1->5->10->14->19->23->28->32->37->41->7->13->20->26->34->40->8->17->29->38->11->25->2->22->4->35
剩下:31号
剩下:16号 虽然实现了，但是过于复杂。
页:
[1]