大体瑟夫问题解题记录。POJ3750: 小孩报数问题+一鸣经典约瑟夫问题(猴子选大王)

题材讲述:

大约瑟夫问题:有n只猕猴,按顺时针方向绕成一环抱选大王(编号从1顶n),从第1如泣如诉起报数,一直数到m,数到m的猴子退出圈外,剩下的猴还跟着从1开始报数。就这么,直到圈内就剩余一单单猕猴时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的编号。

而同样蹩脚以一个有点左,POJ上Wrong
Answer了多涂鸦。。。。。

输入:

每行是用空格分开的有数个整数,第一单凡是
n, 第二单凡是 m ( 0 < m,n <=300)。最后一尽是:
0 0

每当多要舍弃的时候,发现了这猥琐的非克重俗气的bug,改了了付出就AC了,简直无语。。。。

输出:

对每行输入数据(最后一履除了),输出数据吧是单排,即最后猴王的号。

主题wo采用模拟方法:

样例输入:

1 6 2
2 12 4
3 8 3
4 0 0

爱博体育app 1爱博体育app 2

样例输出:

1 5
2 1
3 7
 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 struct child{
 6     char name[16];
 7     int id;
 8     //child(string, int);
 9 }cd[100];
10 void init(int n){
11     char s[16];
12     for(int i=1;i<=n;i++){
13         scanf("%s",cd[i].name);
14         cd[i].id=0;
15     }
16 }
17 int main(){
18     int n,w,s; char c;
19     scanf("%d",&n);
20     init(n);
21     scanf("%d%c%d",&w,&c,&s);
22     cd[w].id=1;
23     int pt=w;
24     int kill=0;
25     while(true){
26         int step=s%(n-kill)-1;
27         if(step<=0) step=step+n-kill;
28         /*
29             这里的取模运算是考虑到s值可能非常大,如果这样的话,模拟报数过程1。。。。s将会非常
30             耗时间。
31             至于为什么这么取模,自己算一算就明白了。 
32         */
33         for(int i=1;i<=step;i++){
34                 int ptr=pt%n+1;
35                 while(cd[ptr].id==-1){//要跳过已经被kill的元素 
36                     ptr=ptr%n+1;
37                 }
38                 cd[ptr].id=cd[pt].id+1;
39                 pt=ptr;
40         }//这里的pt指向的就是我们要删除的元素 
41         cd[pt].id=-1;//将id赋值为-1,相当于删除动作 
42         printf("%s\n",cd[pt].name);
43         kill++;
44         if(kill==n) break; //已经清空,跳出循环 
45         int ptr=pt%n+1;
46         while(cd[ptr].id==-1){
47                     ptr=ptr%n+1;
48         }
49         cd[ptr].id=1;
50         pt=ptr;
51             
52     }
53     //system("pause");
54     return 0;
55 }

代码:

 1 #include<stdio.h>                                                                                                                                                                                           
 2 #include<stdlib.h>
 3 typedef struct monkey{
 4     int val;
 5     struct monkey *next;
 6 }mon;
 7 mon *create(int num){  //创造链表
 8     mon *head=(mon*)malloc(sizeof(mon));
 9     head->next=NULL;
10     mon *pre=head;
11     for(int i=1;i<=num;i++){
12         mon *p=(mon*)malloc(sizeof(mon));
13         p->next=NULL;
14         pre->next=p;
15         pre=p;
16         p->val=i;
17     }
18     pre->next=head->next;
19     return pre;
20 }
21 int sel(mon *head,int cur,int m){  //提猴子
22     if(head->next==head)
23         return head->val;
24     if(cur<m)
25         return sel(head->next,cur+1,m);
26     else{
27         head->next=head->next->next;
28         return sel(head,1,m);
29     }
30 }
31 int main()
32 {
33     int m,n;
34     while(1){
35         scanf("%d%d",&n,&m);
36         if(n==0)
37             break;
38         mon *head=create(n);
39         int num=sel(head,1,m);
40         printf("%d\n",num);
41     }
42     return 0;
43 }

 

View Code

还有好为此双向循环链表来模拟:

爱博体育app 3爱博体育app 4

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 using namespace std;
 5 struct node{
 6     int id;
 7     node *next,*pre;
 8     node();
 9     node(int);
10 };
11 node *head;
12 char name[101][20];
13 node::node(int value){
14     id=value;
15     next=pre=NULL;
16 }
17 void build(int n){
18     head=new node(1);
19     head->next=head->pre=head;
20     if(n==1) return;
21     node *p=head;
22     for(int i=2;i<=n;i++){
23         node *a=new node(i);
24         p->next=a;
25         a->pre=p;
26         p=a;        
27     }
28     p->next=head;
29     head->pre=p;
30 }
31 void print(){
32     node *p=head;
33     printf("%d ",p->id);
34     p=p->next;
35     while(p!=head){
36         printf("%d ",p->id);
37         p=p->next;
38     }
39     printf("\n");
40 }
41 void joseph(int s,int k){
42     node *p=head;
43     s--;
44     while(s--) p=p->next;
45     while(p->next!=p){
46         for(int i=1;i<=k-1;i++) p=p->next;
47         printf("%s\n",name[p->id]);
48         node *front=p->pre;
49         node *rear=p->next;
50         p=rear;
51         front->next=rear;
52         rear->pre=front;        
53     }
54     printf("%s\n",name[p->id]);
55 }
56 int main(){
57     int n; char c;
58     scanf("%d",&n);
59         build(n);
60         //print();
61         for(int i=1;i<=n;i++){
62             scanf("%s",name[i]);
63         }
64         int s,k;
65         scanf("%d%c%d",&s,&c,&k);
66         joseph(s,k);
67 }

View Code

 

猴子选大王问题: 

问题叙述约瑟夫问题:有n只猕猴,按顺时针方向绕成一环绕选大王(编号从1暨n),从第1声泪俱下开始报数,一直数到m,数到m的猴退出圈外,剩下的猴子还接着打1开报数。就这样,直到圈内就剩下一才猕猴时,这个猴子就是猴王,编程求输入n,m后,输出最后猴王的号码。

输入每行是为此空格分开的一定量单整数,第一单凡是
n, 第二只是 m ( 0 < m,n <=300)。最后一实行是:

0 0

输出对于每行输入数据(最后一执行除了),输出数据吧是单排,即最后猴王的编号
爱博体育app样例输入

6 2

12 4

8 3

0 0

样例输出

5

1

7

爱博体育app 5爱博体育app 6

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 struct child{
 6     int name;
 7     int id;
 8     //child(string, int);
 9 }cd[100];
10 void init(int n){
11     for(int i=1;i<=n;i++){
12         cd[i].name=i;
13         cd[i].id=0;
14     }
15 }
16 void solve(int n,int s){
17     init(n);
18     cd[1].id=1;
19     int pt=1;
20     int kill=0;
21     while(true){
22         int step=s%(n-kill)-1;
23         if(step<=0) step=step+n-kill;
24         /*
25             这里的取模运算是考虑到s值可能非常大,如果这样的话,模拟报数过程1。。。。s将会非常
26             耗时间。
27             至于为什么这么取模,自己算一算就明白了。 
28         */
29         for(int i=1;i<=step;i++){
30                 int ptr=pt%n+1;
31                 while(cd[ptr].id==-1){//要跳过已经被kill的元素 
32                     ptr=ptr%n+1;
33                 }
34                 cd[ptr].id=cd[pt].id+1;
35                 pt=ptr;
36         }//这里的pt指向的就是我们要删除的元素 
37         cd[pt].id=-1;//将id赋值为-1,相当于删除动作 
38         kill++;
39         if(kill==n){
40             printf("%d\n",cd[pt].name); break; //已经清空,跳出循环 
41         }
42         int ptr=pt%n+1;
43         while(cd[ptr].id==-1){
44                     ptr=ptr%n+1;
45         }
46         cd[ptr].id=1;
47         pt=ptr;
48             
49     }
50 }
51 int main(){
52          int n,s;
53         while(scanf("%d%d",&n,&s)!=EOF&&n&&s){
54             solve(n,s);
55         }
56         return 0;    
57 }

View Code

 

 

相关文章