一、问题描述
约瑟夫问题是:有 n 只猴子,按顺时针方向围成一圈选大王(编号为 1~n),从第 1 号开始报数,一直数到 m,数到 m 的猴子退到圈外,剩下的猴子再接着从 1 开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王。编程求输入 n、m 后,输出最后猴王的编号。
输入数据:每行是用空格分开的两个整数,第一个是 n,第二个是 m(0<m, n<=1 000 000)。最后一行是:
0 0
输出要求:对于每行输入数据(最后一行除外),输出数据也是一行,即最后猴王的编号。
输入样例:
6 2
12 4
8 3
0 0
输出样例:
5
1
7
二、求解
1.用C++ list容器求解
#include<iostream>
#include<list>
using namespace std;
/*
约瑟夫问题是:有 n 只猴子,按顺时针方向围成一圈选大王(编号为 1~n),
从第 1 号开始报数,一直数到 m,数到 m 的猴子退到圈外,剩下的猴子再接着从 1 开始报数。
就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王。
编程求输入 n、m 后,输出最后猴王的编号
*/
int main(int argc,char **argv)
{
list<int> monkeys;
int n,m;
while(true){
cin>>n>>m;
if(n==0 && m==0){ //输入0 0退出游戏
break;
}
monkeys.clear(); //清空list容器
for(int i=1;i<=n;++i){
monkeys.push_back(i); //初始化猴子的编号
}
list<int>::iterator it=monkeys.begin();
cout<<"出局monkeys顺序:";
while(monkeys.size()>1){ //只要容器中不止一只猴子,游戏就要继续
for(int i=1;i<m;++i){
++it;
if(it==monkeys.end())
it=monkeys.begin();
}
cout<<*it<<" "; //输出出局猴子的编号
it=monkeys.erase(it);//erase成员函数返回删除元素的下一个元素的迭代器
if(it==monkeys.end())
it=monkeys.begin();
}
cout<<endl;
cout<<monkeys.front()<<endl; //输出最后选出的猴王
}
return 0;
}
运行结果分析
- 用循环链表求解(C语言实现)
#include<stdio.h>
#include<stdlib.h>
typedef struct Sqlist{
int val;
struct Sqlist *next;
}Sqlist;
//初始化循环链表
Sqlist *initList(int n)
{
Sqlist *head=(Sqlist*)malloc(sizeof(Sqlist));
head->val=1;
head->next=NULL;
Sqlist *body=head;
int i;
for(i=2;i<=n;++i){
Sqlist *tmp=(Sqlist*)malloc(sizeof(Sqlist));
tmp->val=i;
tmp->next=NULL;
body->next=tmp;
body=body->next;
}
body->next=head; //首尾相连
return head;
}
//找到编号为k的人开始报数,数到m的人出列
void findAndKillm(Sqlist *head,int m,int k)
{
Sqlist *tmp=head;
//遍历链表到第k个
while(tmp->val!=k){
tmp=tmp->next;
}
int i;
Sqlist *fro=tmp;
while(tmp->next!=tmp){ //当tmp->next=tmp时,说明链表中只剩一个人,即胜利者
for(i=1;i<m;++i){
fro=tmp;
tmp=tmp->next;
}
fro->next=tmp->next;
printf("%d ",tmp->val);
free(tmp);
tmp=fro->next;
}
printf("\n");
printf("最后胜出者:%d\n",tmp->val);
}
void solution()
{
int n,m,k;
while(1){
printf("输入总人数n:n=");
scanf("%d",&n);
printf("数到m的人出列:m=");
scanf("%d",&m);
if(n==0 || m==0){
exit(0);
}
Sqlist *head=initList(n);
printf("从第k人开始报数(k>0):k=");
scanf("%d",&k);
printf("出列人的顺序为:");
findAndKillm(head,m,k);
}
}
int main(int argc,char **argv)
{
solution();
return 0;
}
求解结果
欢迎不同求解方案探讨
欢迎点赞!
网友评论