Q:猴子选王
一堆猴子有m个,编号分别是1,2,3,,,m,这m只猴子按照编号1,2,3,,,m的顺序坐成一圈,然后从第1个开始数,每数到第n个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子就为大王。
A:典型的约瑟夫问题
1.用链表来解决:
#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
int data;
struct node *next;
}Node;
void MONKEY(int m,int n)
{
Node *head = NULL,*end = NULL, *node = NULL;
head=(Node*)malloc(sizeof(Node));
head->data = 1;
head->next = NULL;
end = head; //把head的地址给end,end中所储存的即为head的地址,换句话来说就是将end放在head上
int i ;
for(i = 2;i <= m;i++)
{
node=(Node*)malloc(sizeof(Node));
node->data = i;
node->next = NULL;
end->next = node; //尾插入法 ,next域中存储的是node的地址
end = node; //将end从head移动到node
}
end->next = head; //形成循环链表
end = head;
while(end->next != end)
{
for(i = 1;i<n;i++) //“开始报数”
{
node = end;
end = end->next;
}
printf("%d",end->data);
node->next = end->next;//删除节点
end = end->next;
}
printf("%d",end->data);
}
2.用数组的方法:
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a[50],b[50],m,n,i,x,j=1,count=0;
printf("please input m;");
scanf("%d",&m);
printf("please input n:");
scanf("%d",&n);
if(m==0||n==0) //当m或n中有一个为0,都会报错
{
printf("error");
}
else
{
x=m; //防止在编译过程中造成数据更改
for(i=1;i<=m;i++) //将数存储到数组里
{
a[i]=i;
}
while(x>=1)
{
for(i=1;i<=m;i++)
{
if(a[i]!=0)
{
count++; //报数
}
if(count==n)
{
b[j]=a[i]; //用另一个数组重新按顺序记录
a[i]=0; //已经报过数的将其值赋为0
count=0; //重新开始报数
x--; //总数在减少
j++;
}
}
}
for(i=1;i<=m;i++) //输出
{
printf("%d ",b[i]);
}
}
return 0;
}
更多推荐
约瑟夫问题(C语言)
发布评论