poj-ジョセフ問題(サル選王)

1777 ワード

アナログ poj

2746:ジョセフ問題
合計時間制限:
1000ms
メモリの制限:
65536kB
説明
ヨセフ問題:n匹のサルがいて、時計回りに囲んで大王を選び(番号は1からn)、1番から数え、mまで数え、mまで数えたサルは圏外に出て、残りのサルは1から数え始めます.こうして、圏内にサルが1匹しか残っていないまで、このサルはサル王であり、n,mをプログラミングして入力した後、最後のサル王の番号を出力する.
入力
各行はスペースで区切られた2つの整数で、1つ目はnで、2つ目はm(00 0
しゅつりょく
各行の入力データ(最後の行を除く)に対して、出力データも1行、すなわち最後のサル王の番号である
サンプル入力

サンプル出力

5
1
7

問題解決レポート:
本題はシミュレーションの方法で、配列やチェーンテーブルで解決できるので、チェーンテーブルを使うともっと便利ですが、ここでは配列を使う方法だけを紹介したほうがいいです.初心者の方が分かりやすいです.houzi[MAX]で配列はn個の数を格納し、n個の数が並んだ輪に相当する.1個の数を切り落とす操作は、1つの配列要素を0にする方法で実現される.人工数の場合、切り捨てた数をスキップするには、プログラムが実行される場合、0になった配列要素をスキップする.iがhouziの最後の要素(下付きn-1)を指す場合に注意が必要であるを選択すると、最初の要素に戻ります.houziは輪のようになります.リファレンス1:

#include
#define MAX 300
int main()
{
	int houzi[MAX+10],n,m;
	int i;
	int count,sum;		//sum      ,count          

	while(scanf("%d%d",&n,&m)&&(n||m))
	{
	for(i=0;i1)	//       1     
	{	count=0;
		while(count=n)
				i%=n;	//  ， i  n-1 ，    
			if(houzi[i])	//       ，    
				count++;
			i++;
		
		}
		if(i-1<0)	//    ，    n-1    ，  i   0，i-1  0
			houzi[n-1]=0; //   n-1         i-1 ，  i-1<0
		else
			houzi[i-1]=0;
		sum--;  	//    ，       


	}
	for(i=0;i

リファレンス2:配列aloopでn個の数を格納し、変数nptrで現在の数からの配列要素を指す

#include
#define N 300
int main()
{
	int nloop[N+10],nptr,count;
	int n,m,i;
	while(1){
	scanf("%d%d",&n,&m);
	if(n==0)
		break;
	for(i=0;i

stm 8 s 103 f 3 p 6の遅延関数

【Chapter 8*プログラミングまとめ*】gdbトラッキングスタック情報と再確認標準IOとファイルIOの基本的な違い