約瑟夫環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;
}