ACM POJ 2245 Lotto解題報告
21477 ワード
http://poj.org/problem?id=2245
Lotto
ドイツゲームLottoでは集合{1,2,…,49}から6個の数を取り出す.
非常に流行している遊び方(この遊び方は勝つ機会を増やすことはできないが)は、この49の数字からkの数字(6例えば、k=8、S=1、2、3、5、8、13、21、34の場合、28種類の可能なゲームがあります.
[1,2,3,5,8,13],[1,2,3,5,8,21],[1,2,3,5,8,34],[1,2,3,5,13,21],……,[3,5,8,13,21,34].
プログラムを作成し、kの値と集合Sを読み込み、Sからのみ数を取る可能性のあるすべてのゲームを印刷します.
入力
入力ファイルには、1つ以上のテスト状況が含まれます.
各シナリオの行は、複数の整数で構成され、整数間はスペースで区切られます.行頭整数はk値(6次に、集合Sを記述するためのk個の整数が、全て昇順に配列されている.
kの位置にゼロ(0)を入力すると入力が終了します.
出力:
各テストシナリオについて、すべての可能なゲーム、各ゲームの1行を印刷します.
各ゲームの数字は昇順に並べ、2つの間にスペースで区切らなければなりません.これらのゲームは辞書の編纂に似た方法で並べ替えなければならない.つまり、最低位を先に並べ替え、それから2番目の低位を順に類推し、出力例で示したようにしなければならない.
サンプルを入力:
0
出力サンプル
本題は組合せ数を生成する方法である.
#include
#include
using namespace std;
#define MAXN 20
int p[MAXN];
void print(int *a,int m) //しゅつりょく
{
int i,cnt;
for(i=0;i cnt=a[m-1];
cout<}
//まず、1、2、3、4、5、6、7…といった組み合わせ数を生成し、さらに、下付き出力に必要な組み合わせ数を利用する
void GenComb(int*a,int n,int m)/次の組合せ数を生成
{
int i,j,t;
print(a,m);
for(j=m-1;j>=0;j--)
if(a[j] t=a[j];
for(i=0;i<=m-j-1;i++)
a[j+i]=t+i+1;
}
void GenAllComb(int *a,int n,int m)
{
int index;
for(index=0;index index=0;
while(index<=n−m)/indexは、最初の組合せ数の小さなスケールを指し、indexがn−mより大きい場合には、テールに到達したことを示す.
{
GenComb(a,n,m);
if(a[0]>index+1)index++;
}
}
int main()
{
int n,m=6,a[MAXN],i;
int first=0;//POJ上の問題は最後にスペースを生成しないことを要求するので、第1グループを除いて残りの前にスペースを生成する
while(cin>>n,n)
{
if(first) cout< first=1;
for(i=1;i<=n;i++) cin>>p[i];
GenAllComb(a,n,m);
}
return 0;
}
(このプログラムはPOJでGCC++が通じないので、C++、Acceptで...おかしい)
以下のプログラムはネット上の书き込みを勉强したので、比较的简洁で、お勧めします!!!
Lotto
ドイツゲームLottoでは集合{1,2,…,49}から6個の数を取り出す.
非常に流行している遊び方(この遊び方は勝つ機会を増やすことはできないが)は、この49の数字からkの数字(6
[1,2,3,5,8,13],[1,2,3,5,8,21],[1,2,3,5,8,34],[1,2,3,5,13,21],……,[3,5,8,13,21,34].
プログラムを作成し、kの値と集合Sを読み込み、Sからのみ数を取る可能性のあるすべてのゲームを印刷します.
入力
入力ファイルには、1つ以上のテスト状況が含まれます.
各シナリオの行は、複数の整数で構成され、整数間はスペースで区切られます.行頭整数はk値(6
kの位置にゼロ(0)を入力すると入力が終了します.
出力:
各テストシナリオについて、すべての可能なゲーム、各ゲームの1行を印刷します.
各ゲームの数字は昇順に並べ、2つの間にスペースで区切らなければなりません.これらのゲームは辞書の編纂に似た方法で並べ替えなければならない.つまり、最低位を先に並べ替え、それから2番目の低位を順に類推し、出力例で示したようにしなければならない.
サンプルを入力:
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0
出力サンプル
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34
本題は組合せ数を生成する方法である.
#include
#include
using namespace std;
#define MAXN 20
int p[MAXN];
void print(int *a,int m) //しゅつりょく
{
int i,cnt;
for(i=0;i
cout<
//まず、1、2、3、4、5、6、7…といった組み合わせ数を生成し、さらに、下付き出力に必要な組み合わせ数を利用する
void GenComb(int*a,int n,int m)/次の組合せ数を生成
{
int i,j,t;
print(a,m);
for(j=m-1;j>=0;j--)
if(a[j]
for(i=0;i<=m-j-1;i++)
a[j+i]=t+i+1;
}
void GenAllComb(int *a,int n,int m)
{
int index;
for(index=0;index
while(index<=n−m)/indexは、最初の組合せ数の小さなスケールを指し、indexがn−mより大きい場合には、テールに到達したことを示す.
{
GenComb(a,n,m);
if(a[0]>index+1)index++;
}
}
int main()
{
int n,m=6,a[MAXN],i;
int first=0;//POJ上の問題は最後にスペースを生成しないことを要求するので、第1グループを除いて残りの前にスペースを生成する
while(cin>>n,n)
{
if(first) cout<
for(i=1;i<=n;i++) cin>>p[i];
GenAllComb(a,n,m);
}
return 0;
}
(このプログラムはPOJでGCC++が通じないので、C++、Acceptで...おかしい)
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXN 20
int p[MAXN];
void print(int *a,int m) //
{
int i,cnt;
for(i=0;i<m-1;i++) {cnt=a[i];cout<<p[cnt]<<' ';}
cnt=a[m-1];
cout<<p[cnt]<<endl;
}
// 1，2，3，4，5，6，7...... ，
void GenComb(int *a,int n,int m)//
{
int i,j,t;
print(a,m);
for(j=m-1;j>=0;j--)
if(a[j]<n-m+j+1)break;
t=a[j];
for(i=0;i<=m-j-1;i++)
a[j+i]=t+i+1;
}
void GenAllComb(int *a,int n,int m)
{
int index;
for(index=0;index<m;index++)a[index]=index+1;// ， 1，2，3...
index=0;
while(index<=n-m)//index ， index n-m ， 。
{
GenComb(a,n,m);
if(a[0]>index+1)index++;
}
}
int main()
{
int n,m=6,a[MAXN],i;
int first=0;//POJ ，
while(cin>>n,n)
{
if(first) cout<<endl;
first=1;
for(i=1;i<=n;i++) cin>>p[i];
GenAllComb(a,n,m);
}
return 0;
} 以下のプログラムはネット上の书き込みを勉强したので、比较的简洁で、お勧めします!!!
#include<stdio.h>
#include<string.h>//memset
int K;//
int num[13];
int chosed[13];
void find(int st,int n)
{
int i,first;
if(n==6)
{
first=1;
for(i=0;i<K;i++)
{
if(chosed[i])
{
if(first==1) {printf("%d",num[i]);first=0;}
else printf(" %d",num[i]);
}
}
printf("
");return;
}
for(i=st;i<K;i++)
{
if(!chosed[i])
{
chosed[i]=1;
find(i+1,n+1);
chosed[i]=0;
}
}
}
int main()
{
int i,first=1;
while(scanf("%d",&K)!=EOF&&K)
{
for(i=0;i<K;i++) scanf("%d",&num[i]);
if(first==1)first=0;
else printf("
");
memset(chosed,0,sizeof(chosed));
find(0,0);
}
return 0;
}