2016年藍橋杯C/C++B組

2016年藍橋杯C/C++B組

第一次參加藍橋杯，也是有很多感觸的，時間完全不夠寫最後一題...

最後一題沒做...還有全排序很重要...

1、

煤球數目

有一堆煤球，堆成三角稜錐形。具體：
第一層放1個，
第二層3個（排列成三角形），
第三層6個（排列成三角形），
第四層10個（排列成三角形），
….
如果一共有100層，共有多少個煤球？

請填表示煤球總數目的數字。
注意：你提交的應該是一個整數，不要填寫任何多余的內容或說明性文字。

/*答案：171700*/ 
#include 
#include 
using namespace std;
int main()
{
	int i,j;
	int sum=0;
	int num=1;
	i=2;
	for(j=1;j<=100;j++)
	{
		sum+=num;
		num+=i;
		i++;
	}
	cout<
 

2、

生日蠟燭

某君從某年開始每年都舉辦一次生日party，並且每次都要吹熄與年齡相同根數的蠟燭。

現在算起來，他一共吹熄了236根蠟燭。

請問，他從多少歲開始過生日party的？

請填寫他開始過生日party的年齡數。

注意：你提交的應該是一個整數，不要填寫任何多余的內容或說明性文字。
/*答案：26*/ 
#include 
#include 
using namespace std;
int main()
{
	int i,j,sum,flag=0;
	for(i=1;i<=100;i++)//一般只能活到不超過100歲，不放心就多加一點兒 
	{
		sum=0;
		for(j=i;j<=100;j++)
		{
			sum+=j;
			if(sum==236)
			{
				flag=1;
				break;
			}
			if(sum>236)break;
		}
		if(flag==1)
		break;
	}
	cout<
 

3、湊算式 B DEF A + — + ——- = 10 C GHI （如果顯示有問題，可以參見【圖1.jpg】） 這個算式中A~I代表1~9的數字，不同的字母代表不同的數字。 比如： 6+8/3+952/714 就是一種解法， 5+3/1+972/486 是另一種解法。 這個算式一共有多少種解法？ 注意：你提交應該是個整數，不要填寫任何多余的內容或說明性文字。

/*答案：29*/ 
#include 
#include 
#include 
#include 
using namespace std;

/*一種偷懶的辦法，next_permutation這是一個求一個排序的下一個排列的函數，可以遍歷全排列，但先要加
#include 頭文件，當存在一個排列的下一個排列，則返回true,否則返回false,
每執行一次，排列變為它的後繼。與之完全相反的函數是prev_permutation*/ 
int main()
{
	int a[11],sum=0,i;
	for(i=0;i<=8;i++)
	{
		a[i]=i+1;
	}
	while(next_permutation(a,a+9))
	{	
		
		if(fabs(a[0]+1.0*a[1]/a[2]+(1.0*100*a[3]+10*a[4]+a[5])/(100*a[6]+10*a[7]+a[8])-10)<1e-6)
		{
		sum++;
		}
	}
	cout<
 

4、

快速排序

排序在各種場合經常被用到。

快速排序是十分常用的高效率的算法。

其思想是：先選一個“標尺”，

用它把整個隊列過一遍篩子，

以保證：其左邊的元素都不大於它，其右邊的元素都不小於它。

這樣，排序問題就被分割為兩個子區間。

再分別對子區間排序就可以了。

下面的代碼是一種實現，請分析並填寫劃線部分缺少的代碼。

#include 

void swap(int a[], int i, int j)

{

int t = a[i];

a[i] = a[j];

a[j] = t;

}

int partition(int a[], int p, int r)

{

int i = p;

int j = r + 1;

int x = a[p];

while(1){

while(i
while(a[–j]>x);

if(i>=j) break;

swap(a,i,j);

}

______________________;

return j;

}

void quicksort(int a[], int p, int r)

{

if(p
int q = partition(a,p,r);

quicksort(a,p,q-1);

quicksort(a,q+1,r);

}

}

int main()

{

int i;

int a[] = {5,13,6,24,2,8,19,27,6,12,1,17};

int N = 12;

quicksort(a, 0, N-1);

for(i=0; i
printf(“\n”);

return 0;

}

注意：只填寫缺少的內容，不要書寫任何題面已有代碼或說明性文字。
 
//答案：swap(a,p,j)
#include 
void swap(int a[], int i, int j)
{
	int t = a[i];
	a[i] = a[j];
	a[j] = t;
}

int partition(int a[], int p, int r)
{
    int i = p;
    int j = r + 1;
    int x = a[p];
    while(1){
        while(ix);
        if(i>=j) break;
        swap(a,i,j);
    }
	swap(a,p,j);
    return j;
}

void quicksort(int a[], int p, int r)
{
    if(p
 

5、

抽簽

X星球要派出一個5人組成的觀察團前往W星。

其中：

A國最多可以派出4人。

B國最多可以派出2人。

C國最多可以派出2人。

….

那麼最終派往W星的觀察團會有多少種國別的不同組合呢？

下面的程序解決了這個問題。

數組a[] 中既是每個國家可以派出的最多的名額。

程序執行結果為：

DEFFF

CEFFF

CDFFF

CDEFF

CCFFF

CCEFF

CCDFF

CCDEF

BEFFF

BDFFF

BDEFF

BCFFF

BCEFF

BCDFF

BCDEF

….

(以下省略，總共101行)

#include 

#define N 6

#define M 5

#define BUF 1024

void f(int a[], int k, int m, char b[])

{

int i,j;

if(k==N){

b[M] = 0;

if(m==0) printf(“%s\n”,b);

return;

}

for(i=0; i<=a[k]; i++){

for(j=0; j
______________________; //填空位置

}

}

int main()

{

int a[N] = {4,2,2,1,1,3};

char b[BUF];

f(a,0,M,b);

return 0;

}

仔細閱讀代碼，填寫劃線部分缺少的內容。

注意：不要填寫任何已有內容或說明性文字。
//答案：f(a,k+1,m-i,b),用深搜
#include 
#define N 6
#define M 5
#define BUF 1024
void f(int a[], int k, int m, char b[])
{
	int i,j;
	
	if(k==N){ 
		b[M] = 0;
		if(m==0) printf("%s\n",b);
		return;
	}
	
	for(i=0; i<=a[k]; i++){
		for(j=0; j

6、

方格填數 如下的10個格子 +–+–+–+ | | | | +–+–+–+–+ | | | | | +–+–+–+–+ | | | | +–+–+–+ （如果顯示有問題，也可以參看【圖1.jpg】） 填入0~9的數字。要求：連續的兩個數字不能相鄰。 （左右、上下、對角都算相鄰） 一共有多少種可能的填數方案？ 請填寫表示方案數目的整數。 注意：你提交的應該是一個整數，不要填寫任何多余的內容或說明性文字。

/*答案：1580 直接搜索最後判斷就可以。*/ 
#include 
#include 
#include 
using namespace std;
int a[11];
int flag[10];
int sum;
int flag1;
void DFS(int x)
{
	int i;
	if(x==10)
	{
		flag1=1;
		for(i=0;i<9;i++)
		{
		if(a[i]==0&&!(a[i+1]!=1&&a[i+1]!=3&&a[i+1]!=4&&a[i+1]!=5))
		{
			flag1=0;
		}
		if(a[i]==1&&!(a[i+1]!=0&&a[i+1]!=2&&a[i+1]!=4&&a[i+1]!=5&&a[i+1]!=6))
		{
			flag1=0;
		}
		if(a[i]==2&&!(a[i+1]!=1&&a[i+1]!=5&&a[i+1]!=6))
		{
			flag1=0;
		}
		if(a[i]==3&&!(a[i+1]!=4&&a[i+1]!=7&&a[i+1]!=8&&a[i+1]!=0))
		{
			flag1=0;
		}
		if(a[i]==4&&!(a[i+1]!=0&&a[i+1]!=1&&a[i+1]!=3&&a[i+1]!=5&&a[i+1]!=7&&a[i+1]!=8&&a[i+1]!=9))
		{
			flag1=0;
		}
		if(a[i]==5&&!(a[i+1]!=0&&a[i+1]!=1&&a[i+1]!=2&&a[i+1]!=4&&a[i+1]!=6&&a[i+1]!=8&&a[i+1]!=9))
		{
			flag1=0;
		}
		if(a[i]==6&&!(a[i+1]!=1&&a[i+1]!=2&&a[i+1]!=5&&a[i+1]!=9))
		{
			flag1=0;
		}
		if(a[i]==7&&!(a[i+1]!=3&&a[i+1]!=4&&a[i+1]!=8))
		{
			flag1=0;
		}
		if(a[i]==8&&!(a[i+1]!=3&&a[i+1]!=4&&a[i+1]!=5&&a[i+1]!=7&&a[i+1]!=9))
		{
			flag1=0;
		}
		if(a[i]==9&&!(a[i+1]!=6&&a[i+1]!=4&&a[i+1]!=5&&a[i+1]!=8))
		{
			flag1=0;
		}
		}
		if(flag1)
		{
		sum++;
		}
		return ;
	}
	for(i=0;i<=9;i++)
	{
		if(flag[i]==0)
		{
			flag[i]=1;
			a[x]=i;
			DFS(x+1);
			flag[i]=0;
		}
	}
}
int main()
{
	memset(flag,0,sizeof(flag));
	sum=0;
	DFS(0);
	cout<

7、

剪郵票

如【圖1.jpg】, 有12張連在一起的12生肖的郵票。

現在你要從中剪下5張來，要求必須是連著的。

（僅僅連接一個角不算相連）

比如，【圖2.jpg】，【圖3.jpg】中，粉紅色所示部分就是合格的剪取。

請你計算，一共有多少種不同的剪取方法。

請填寫表示方案數目的整數。

注意：你提交的應該是一個整數，不要填寫任何多余的內容或說明性文字。

/*答案:116*/ 
#include 
#include 
#include 
#include 
using namespace std;
int a[10];
int flag[15];
int flagtwo[15];
int sum;
void DFS(int x,int pos)
{
	int num;
	int i,j;
	if(x==6)
	{
		num=0;
		memset(flagtwo,0,sizeof(flagtwo));
		for(i=1;i<=5;i++)
		{
			for(j=1;j<=5;j++)
			{
				if(i!=j)
				{
					if(abs(a[i]-a[j])==4)num++;
					else if((a[i]-1)/4==(a[j]-1)/4&&abs(a[i]-a[j])==1)num++;
				}
			}
		}
		if(num>=8)
		{
		for(i=1;i<=5;i++)
		cout<