Josephus' Problem

Josephus' Problem

description:

There are N children sitting around a round table, and they are clockwise labeled from 1 to N. The children number off clockwise. Given a number M, once a child numbers off M, he/she should leave the table, and the next child will begin to number off from 1. The process is repeated until all the children leave the table. This problem asks students to determine the order of children leaving the table.

source:

right:shenyaoxing

--------------------------------------------------------------------------------------------------

#include "stdio.h"int main(){ int n,p,m,i,j; int a[400]; //freopen("3254.txt","r",stdin); while(1) { scanf("%d%d%d",&n,&p,&m); if(n==0 && p==0 && m==0) break; for(i=1;i<=n;i++) a[i]=i; int count=0,num=0; i=p; while(num<n-1) { if(a[i]!=0) { count++; } if(count==m) { a[i]=0; printf("%d,",i); count=0; num++; } i++; if(i==n+1) i=1; } for(i=1;i<=n;i++) if(a[i]!=0) printf("%d\n",i); } return 0;}

--------------------------------------------------------------------------------------------------

wrong 1: yiyiyi

--------------------------------------------------------------------------------------------------

#include<iostream>#include<cstring>#include<cmath>using namespace std;int main(){ int child[300],i,j; int n,m,p,npr,count,nc; while(cin>>n>>p>>m) { if(n==0&&m==0&&p==0) break; nc=n; npr=p-1; for(i=0;i<n;i++) child[i]=1; count=1; while(nc!=0) { while(count<m) { while(child[npr]==0) npr=(npr+1)%n; npr=(npr+1)%n; while(child[npr]==0) npr=(npr+1)%n; count++; } child[npr]=0; nc--; cout<<npr+1; if(nc!=0) cout<<","; npr++; count=1; } cout<<endl; } return 0;}

--------------------------------------------------------------------------------------------------

wrong2: cs10107_00730013

--------------------------------------------------------------------------------------------------

#include <iostream>using namespace std;int main(){ int n, p ,m; while ( cin >> n >> p >> m ) { if ( n == 0 && p == 0 && m == 0 ) break; const int n1 = n; int a[n1]; for ( int i = 0; i < n; i++ ) a[i] = i+1; int k = p; for ( int i = n1; i > 1; i-- ) { k += m-1; k %= i; if ( k == 0 ) cout << a[i-1] << ','; else { cout << a[k-1] << ','; for ( int j = k - 1; j < i - 1; j++ ) a[j] = a[j+1]; } } cout << a[0]; cout << endl; }}

--------------------------------------------------------------------------------------------------

wrong3: ic07160

--------------------------------------------------------------------------------------------------

#include <stdio.h>#include <stdlib.h>#define max 300;int an[310];void main(){ int n,m,i ,p; while (1){ scanf("%d%d%d",&n, &p , &m); if (n==0) break; for (i=0;i<n;i++) an[i]=i+1; int nptr=p; for (i=0;i<n;i++){ int nc=0; while (nc<m){ while (an[nptr]==0) nptr=(nptr+1)%n; nc++; nptr=(nptr+1)%n; } nptr--; if(nptr<0) nptr=n-1; an[nptr]=0; if ( i != n - 1) { if ( nptr == 0) printf("%d,", nptr+ n) ; else printf("%d,", nptr); } else { if ( nptr == 0 ) printf("%d", nptr + n ); else printf("%d", nptr); } } printf("\n"); }}

--------------------------------------------------------------------------------------------------

wrong4: ccccccc

--------------------------------------------------------------------------------------------------

#include <iostream>using namespace std;int main(){ int m,n,p; cin >> n>> p >> m; while(n!=0) { int a[301]={0}; int k=0; p+=m-1; cout << p; a[p]=1; for(int i=2;i<=n;i++) { k=0; for(;a[p]!=0;p++) if(p==n+1) p=1; for(;k<m;p++) { if(p==n+1) p=1; if(a[p]==0) k++; } cout << ',' << p-1; a[p-1]=1; if(p==n+1) p=1; } cout << endl; cin >> n>> p >> m; } return 0;}

--------------------------------------------------------------------------------------------------

wrong5: xyz123

--------------------------------------------------------------------------------------------------

#include<iostream>using namespace std;int main(){ int i,j,n,m,p,k,a[301]; while(cin>>n>>p>>m) { if(!n&&!m) break; for(i=1;i<301;i++) a[i]=1; j=p; for(i=1;i<=n;i++) { k=0; while(k<m) { while(a[j]==0) j=j+1; if(j>n) j=1; k++; j=j+1; if(j>n) j=1; } j--; if(j<1) j=n; a[j]=0; if(i==n) cout<<j<<endl; else cout<<j<<','; } } return 0;}

--------------------------------------------------------------------------------------------------