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<
