南郵NOJ誕生日パーティーとヨセフ問題(異教徒を海に投げ込む排法)
<span style="font-family: Arial; font-size: 14px; background-color: rgb(255, 255, 255);"> </span>今日はJacmYの诞生日で、彼はみんなに食事をごちそうして、このようにして、1行のN人はレストランに来て、みんなは食べて饮んで、笑って、雰囲気はとても楽しくて、この时突然ある人はみんなに1つのゲームを游ぶことを提案して、规则を闻いてから、ゲームを始めました.
ゲームのルールはこうです.食事をしているN人がテーブルのそばに座っています.JacmYは1番で、時計回りに番号をつけ始めます.2、3......N、それからJacmYがランダムにKを数えます(1<=K<=N)、JacmYから時計回りに数えます.「1、2......」と、Kに報告されたとき、この人は彼の位置から立ち上がって、まず他のテーブルに座りました.そして次の人が再び1から報告を始める・・・こうして循環していくと、Kに報告されるたびに、この人はテーブルを離れて、最後の人が残るまで、彼はとても運が悪くてみんなの罰を受けなければならなくて、酒を1杯罰します.JacmYは少し憂鬱になって、Kは自分で言ったので、もし自分に罰を受けると言ったら、これは少し気分が悪くなって、だからJacmYはあなたにどんなKが彼に罰を受けることができることを探し出してもらいたいと思って、このようにしてから、JacmYはあまり酒を飲む心配はありません!
入力
1行目の整数Tは、サンプルのグループ数を表す
次のT行は、1行当たり整数N、1<=N<=100である.Nはタイトルの通りです.
しゅつりょく
各グループのデータについて、最初の行は1つの整数Mを出力して、M個のこのようなKがJacmYに罰を受けることを表して、次の行はM個の整数で、Kがそれぞれ取ったどの値を代表して、これらの数字の間はスペースで隔てられています.
サンプル入力
3 5 8 10
サンプル出力
1 4 2 2 6 1 8
#include <iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
int main()
{
int T,N,k,index,i;
int num;
cin >> T;
while(T--)
{
cin >> N;
int *K= new int[N+1];
for(i=0;i<=N;i++) // K[N], 0,1 ， ，
K[i]=1;
K[1]=0; //k=1 ，
num=1; // num k
for(k=2;k<=N;k++)
{
index = k-1; // 0,1,2,3,4，，，N-1， ，jacmY 0
// index
for(i=1;i<=N-2;i++)
{
index = (index+k-1)%(N-i); // k-1 ， k k-1 ， -1。 -1。
if(index == 0) // jacmY ， 1 ， 。
{
K[k] = 0;
num ++ ;
break; // ， k。
}
}
}
num = N - num; // num k
printf("%d
",num);
for(i=1;i<=N;i++)
{
if(K[i]==1) //
{
printf("%d",i);
num--;
if(num>0)
printf(" ");
if(num==0)
printf("
");
}
}
}
return 0;
}詳しくはコメントを参照...PEは间违って、私を直してとても长い时间....
その後、本でジョセフの問題がこの問題に似ているのを見て、貼った.
ヨセフ問題
30人の信者が一緒に船で航行し、クリスチャンと異教徒はそれぞれ15人だったが、危険にさらされたため、半分の人を海に投入しなければならなかった.解決策は30人が1周し、1人目が1、2人目が2というように、9人が海に投げ込まれる.その後次のラウンドを行い、次の人は1から数え始め、9人目は海に投げ込まれた.このルールに従って循環し、船に15人しか残っていないことを知るまで、どのように30人を並べてすべての異教徒を海に投入することができますか?
#include <iostream>
using namespace std;
int main()
{
int all[30];//
int yijiao[15];//
int jidu[15];//
int i,k,yijiao_count,yijiao_index,jidu_count;
for (i=0;i<30;i++)
all[i]=i+1; //
i=0; //i
k=0; //k 1，2...9
yijiao_count=0; //
yijiao_index=0; //
jidu_count=0; //
while (yijiao_count<15)// 15
{
if (all[i]!=0)//
k++;
if (k==9)
{
yijiao[yijiao_index]=all[i];
yijiao_index++;
all[i]=0;//
k=0;
yijiao_count++;
}
i++;
if (i==30)//
i=0;
}
for(i=0;i<30;i++)
{
if (all[i]!=0)
{
jidu[jidu_count]=all[i];
jidu_count++;
}
}
cout<<" ："<<endl;
for(i=0;i<15;i++)
{
cout<<yijiao[i]<<" ";
}
cout<<endl<<" ："<<endl;
for(i=0;i<15;i++)
{
cout<<jidu[i]<<" ";
}
cout<<endl;
return 0;
}all[i]=0;投入されたことを示し、排除された人はマークされただけで、座席(メモリの中の位置)は依然として保存されている.
この考え方に従って、誕生日の問題を書き直します.
/***************************
2015-5-02
1-N ， N-1 ，
***************************/
#include <iostream>
#include<string.h>
#include<stdlib.h>
using namespace std;
int main()
{
int N,index,k,i,paichu_count;
cin >> N;
int *all=new int[N];
for(index=1;index<=N;index++)
{
for(i=0;i<N;i++) // all[i]
all[i]=i+1; //all[i]=i+1; 0-N 1-N+1 ， ，
i=0;
k=0;
paichu_count=0;
while(paichu_count < N-1)
{
if(all[i]!=0)
k++;
if(k==index)
{
all[i]=0;
k=0;
paichu_count++;
}
i++;
if(i==N)
i=0;
}
for(i=0;i<N;i++)
{
if(all[i]!=0)
// if(all[i]!=0 && all[i]==1) // 1 ， 。
cout <<index <<" "<< all[i] << endl;
}
}
return 0;
}