问题:约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围人全部出列,通常,我们会要求输出最后一位出列的人的序号。那么这里主要研究的是最后一个出列的人的序号要怎么确定。
解决:
1.使用带头节点的链表
#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(people)
typedef struct People{
int num;
struct People *next;
}people;
people *create(int sum){
people *head=(people *)malloc(LEN),*bh,*temp;
int num=0;
bh=head;
head->next=NULL;
while(sum){
temp=(people *)malloc(LEN);
temp->num=++num;
temp->next=NULL;//好习惯,防止野指针
bh->next=temp;
bh=temp;
sum--;
}
return head;
}
people *del(int num,people *head){
people *p,*bh=head;
if(head->next==NULL){
printf("链表为空");
return;
}
p=head->next;
while(p){
if(p->num==num){
bh->next=p->next;
return bh;
}
bh=p;
p=p->next;
}
return NULL;
}
void handle(people *head,int sum,int m,int k){//删除编号为3的及节点
int i=1,j,n=sum;
people *p=head;
if(head->next==NULL){
printf("链表为空");
return;
}
if(k>sum){
printf("输入计数位置有误");
return;
}
for(j=1;j<=k;j++)
p=p->next;
printf("删除的编号:");
while(n!=1){
while(!(i%m)){
printf("%-5d",p->num);
p=del(p->num,head);
n--;
break;
}
if(p->next==NULL||p==head)
p=head->next;
else
p=p->next;
i++;
}
}
void print(people *head){//打印带头结点的链表
people *p=head;
if(head==NULL||head->next==NULL){
printf("链表为空");
return;
}
p=p->next;
while(p){
printf("%d\n",p->num);
p=p->next;
}
}
int main(){
int n,m,k;
people *head;
printf("请输入总共有多少人:");
scanf("%d",&n);
printf("请输入开始计数的位置:");
scanf("%d",&k);
printf("请输入第几个人出列:");
scanf("%d",&m);
head=create(n);
handle(head,n,m,k);
putchar('\n');
printf("最后留下的编号为:");
print(head);
return 0;
}
2.使用数组和指针(数组重组,比较复杂)
#include<stdio.h>
#define N 20
int n;
int handle(int *a,int m,int k){
int *temp=a,i=1,j,num=n,judge=k,w;
printf("删除编号有:");
while(num-1){//当到达数组最后一个位置,数组重构
if(judge>n){
w=0;
judge=1;
for(j=1;j<=n;j++){
if(a[j]!=0){
w++;
temp[w]=a[j];
}
}
n=w;
}
if(i%m==0){
printf("%-5d",temp[judge]);
temp[judge]=0;
num--;
}
judge++;
i++;
}
return judge;
}
int main(){
int i,j,m,k,a[N]={0};
printf("输入人数n:");
scanf("%d",&n);
printf("请输入开始位置:");
scanf("%d",&k);
printf("请输入第几个人出列:");
scanf("%d",&m);
for(i=1;i<=n;i++)
a[i]=i;
j=handle(a,m,k);
if(j>n)
j%=n;
printf("\n%d",a[j]);
}
3.数组指针实现(比较简单,提起定好从第一个人开始,第三个人出列)
#include<stdio.h>
int main(){
int n,a[20]={0};
printf("请输入人数:");
scanf("%d",&n);
int i,j=1,k=0;
for(i=1;i<=n;i++) {
a[i]=i;
}
i=n;
while(i-1){
if(j>n) j=1;
if(a[j]!=0) k++;
if(k==3){
a[j]=0;
k=0;
i--;
}
j++;
}
for(i=1;i<=n;i++)
if(a[i]!=0){
printf("%d\n",a[i]);
break;
}
return 0;
}