天天看点

约瑟夫环C语言

问题:约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知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;
} 
           

继续阅读