2018年北理研究所學生考試複試機試第二題

哥德巴赫猜想

任何一個大于2的偶數均可表示為兩個素數之和。輸入m, n(6<=m<=n<=50),則把[m, n]内的所有偶數表示成兩個素數之和的形式。輸出這些素數及其出線的次數，輸出次序按照素數出現的次數從多到少輸出；若出線次數相同，按照素數從大到小輸出；若偶數有多種素數相加形式，則把所有的情況都輸出，每種情況占一行。

輸入：8 9    輸出：5 1 3 1

輸入：9 10  輸出：5 2

                                 7 1 3 1

輸入：14 15 輸出：7 2

                                   11 1 3 1

輸入：8 10   輸出：5 3 3 1

                                   3 2 7 1 5 1

題目說按排序輸出，但是有一點沒有說明确，比如10可以分成{3:1,  7:1}和{5:2},這兩個是否要排序。我按照這兩個不需要排序來做的，是以沒有處理這個地方。

代碼一：（思路注釋裡寫的很詳細了）

#include<bits/stdc++.h>

using namespace std;

vector<int> prime;	//素數數組

void su()   //素篩，來選出2~50之間的素數
{
	int a[55];
	memset(a, 0, sizeof(a));
	for(int i=2; i<=50; i++)
	{
		if(a[i]==0)  //是素數
			prime.push_back(i);
		int j=2;
		while(i*j <= 50)
			a[i*j++] = -1; 	//非素數
	}
}

bool my_cmp(pair<int, int> a, pair<int, int> b)
{
	if(a.second != b.second)	return a.second>b.second;
	return a.first>b.first;
}

vector<map<int, int> > cal(vector<map<int, int> > v1, vector<map<int, int> > v2)
{
	vector<map<int, int> > res;
	map<int, int>::iterator iter;
	for(int i=0; i<v1.size(); i++)
	{
		for(int j=0; j<v2.size(); j++)
		{
			map<int, int> n1 = v1[i];
			map<int, int> n2 = v2[j];
			map<int, int> m1, m2;
			for(iter=n1.begin(); iter!=n1.end(); iter++)
				m1[iter->first] += iter->second;
			for(iter=n2.begin(); iter!=n2.end(); iter++)
				m1[iter->first] += iter->second;
			//對m1進行排序
			//vector<pair<int, int> > temp(m1.begin(); m1.end());
			//sort(temp.begin(), temp.end(); my_cmp);
			//排完序賦給m2
			//for(int k = 0;k < temp.size();k++)
			//	m2[temp[k].first] = temp[k].second;
			res.push_back(m1);
		}
	}
	return res;
}


int main()
{
	su();	//得到2~50以内的素數表
	int n,mm;
	cin>>n>>mm;
	//最外層map存放n~m之間的素數和該數的vector, 每個數的vector又存放素數清單
	//比如 10的vector為 [ {3:1, 7:1}, {5:2} ], 8的vector為[ {3:1, 5:1 } ]
	map<int, vector<map<int, int> > > m;
	for(int i=n; i<=mm; i++)
	{
		if(i%2 == 1)	continue;  //奇數，跳過
		vector<map<int, int> > v;	//暫存該數的素數清單,map的鍵和值為素數以及該素數出現的次數
		for(int j=0; prime[j]<=i/2; j++)		//周遊素數數組prime,找小于i/2的素數
		{
			//如果小于i/2的素數和 i-prime[j]的素數都有
			//例如，i=8時， 3 和  5都有
			if(find(prime.begin(), prime.end(), i-prime[j]) != prime.end() )
			{
				map<int, int> temp;   //暫存此次素數組合
				temp[prime[j]]++;
				temp[i-prime[j]]++;
				v.push_back(temp);    //存入該數的素數清單
			}
		}
		m[i] = v;
	}
	

	//進行排序輸出
	if(m.size() == 1)	//n~m之間隻有一個素數 ,則不必排列組合，直接排序輸出
	{  
		vector<map<int, int> > res = m.begin()->second;	//得到該數的素數清單
		for(int i = res.size()-1; i >= 0; i--)
		{
			//為了排序
			vector<pair<int, int> > temp(res[i].begin(), res[i].end());
			sort(temp.begin(), temp.end(), my_cmp);
			//輸出
			for(int j=0; j<temp.size(); j++)
				cout<<temp[j].first<<":"<<temp[j].second<<" ";
			cout<<endl;
		}
	}
	else	//多組需要進行排列組合
	{
		map<int, vector<map<int, int> > >::iterator it = m.begin();
		vector<map<int, int> > v1 = it->second;	//得到第一個數的素數清單
		it++;
		vector<map<int, int> > v2 = it->second;	//得到第2個數的素數清單
		it++;
		//排列組合
		vector<map<int, int> > res = cal(v1, v2);
		while(it!=m.end())
		{
			vector<map<int, int> > v3 = it->second;
			res = cal(res, v3);
			it++;
		}
		//輸出
		for(int i = res.size()-1; i>=0; i--)
		{
			//對結果的每個清單進行排序
			vector<pair<int, int> > temp(res[i].begin(), res[i].end());
			sort(temp.begin(), temp.end(), my_cmp);
			for(int j = 0;j < temp.size();j++)
				cout<<temp[j].first<<":"<<temp[j].second<<" ";
			cout<<endl;
		}
	}
	return 0;
}
           

代碼二：遞歸

#include<iostream>
#include<map>
using namespace std;
int prime[15]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
bool judge(int x)  //判斷是否是素數
{
	for(int i=0;i<15;i++)
	{
		if(prime[i]==x)return true;
	}
	return false;
}
void dfs(map<int,int> Q,int n,int m)
{
	if(n>m)    //邊界，輸出
	{
		map<int,int>::iterator it,max;
		while(Q.empty()==false)
		{
			max=Q.begin();
			for(it=Q.begin();it!=Q.end();it++)
			{
				if(max->second<it->second||max->second==it->second&&max->first>it->first)max=it;
			}
			if(max->second>0)cout<<max->first<<":"<<max->second<<" ";
			Q.erase(max);
		}
		cout<<endl;
	}
	else
	{
		for(int i=2;i<=n/2;i++)
		{
			if(judge(i)&&judge(n-i))
			{
				Q[i]++;
				Q[n-i]++;
				dfs(Q,n+2,m);
				Q[i]--;
				Q[n-i]--;
			}
		}
	}
}
int main()
{
	int n,m;
	while(cin>>n>>m)
	{
		map<int,int>Q;
		Q.clear();
		if(n%2==0)dfs(Q,n,m);
		else dfs(Q,n+1,m);
	}
	return 0;
}