第6回ブルーブリッジカップ校内選抜試合C/C++高職組解題(6)

2594 ワード

アルゴリズム

1/aの点数を単位点数と呼ぶ.
1をいくつかの互いに異なる単位点数の和に分解することができる.
例:
1 = 1/2 + 1/3 + 1/9 + 1/18
1 = 1/2 + 1/3 + 1/10 + 1/15
1 = 1/3 + 1/5 + 1/7 + 1/9 + 1/11 + 1/15 + 1/35 + 1/45 + 1/231
など、このような分解は尽きない.
最大の分母は30を超えなければならないという制約を追加しました
n項に分解したときのすべての異なる分解法を求めてください.
データフォーマットの要件:
n項に分解することを示す整数nを入力する(n<12)
分解した単位分数項を出力し、真ん中を1つのスペースで区切ります.
各分解法は1行を占有し,行間の順序は分母が小さいから大きいまで並べ替えられる.
たとえば、
入力:
4
プログラムは出力するべきです:
1/2 1/3 1/8 1/24
1/2 1/3 1/9 1/18
1/2 1/3 1/10 1/15
1/2 1/4 1/5 1/20
1/2 1/4 1/6 1/12
例えば、
入力:
5
プログラムは出力するべきです:
1/2 1/3 1/12 1/21 1/28
1/2 1/4 1/6 1/21 1/28
1/2 1/4 1/7 1/14 1/28
1/2 1/4 1/8 1/12 1/24
1/2 1/4 1/9 1/12 1/18
1/2 1/4 1/10 1/12 1/15
1/2 1/5 1/6 1/12 1/20
1/3 1/4 1/5 1/6 1/20
生産資源約定:
ピークメモリ消費量<256 M
CPU消費<2000 ms
要求通りに出力してください.ヘビを描いて印刷しないでください.「入力してください.」と入力します.
すべてのコードを同じソースファイルに配置し、デバッグに合格した後、コピーしてソースコードをコミットします.
注意:main関数は0を返す必要があります
注:ANSI C/ANSI C++標準のみを使用し、コンパイル環境やオペレーティングシステムに依存する特別な関数を呼び出さないでください.
注意:すべての依存する関数は、ソースファイル内のincludeで明確にする必要があります.通常のヘッダファイルは、エンジニアリング設定で省略することはできません.
コミットするときは、目的のコンパイラタイプを選択することに注意してください.
暴力的な検索方法を思いついただけで、次のような効率はまだよくありません.

#include 
#include 
#include 
#include 
#include 
#include 
#include  
#include  
#include 
#include 
#include 
using namespace std;
int N; 
int count=0;
int counts=0; 
double Table[31][30];//    n       m     
void coutvector(vector d)
{
	for(int i=0;i d)
{
	double ret=0;
	for(int i=0;i d)
{
	count++;
	if(count>=1000)
	{
		counts++;
		count=0;
	}
	double sum=getvectorsum(d);//          
	
	
	if((sum-(1.0/30.0))>1 )
	{
		d.pop_back();
		return;
	}
	if(d.size()==N)
	{
		if(fabs(sum-1) <1e-8) 
			coutvector(d); 
		d.pop_back();
		return;
	}
	if(d.size()>0)
	{
		if(1-sum>Table[d[d.size()-1]][N-d.size()])
		{
			d.pop_back();
			return;
		}
	}
	
	int k=2;
	if(d.size()!=0)
		k=d[d.size()-1]+1;
	for(int i=k;i<=30;i++)
	{
		d.push_back(i);
		dsf(d);
		d.pop_back();
	}
	
}
int main()
{
	//   TABLE 
	for(int i=2;i<=30;i++)
	{
		Table[i][0]=0;
		for(int j=1;j<=(30-i);j++)
			Table[i][j]=Table[i][j-1]+(1.0/(double)(i+j));
	}
	cin>>N; 
	vector  i;
	dsf(i);
	cout<

ソースに近づく:Redisがコマンドを実行する方法

Redisの一般的な操作