第21題

將 2006 個(gè)人分成若干不相交的子集，每個(gè)子集至少有 3 個(gè)人，并且： 

（1）在每個(gè)子集中，沒(méi)有人認(rèn)識(shí)該子集的所有人。

（2）同一子集的任何 3 個(gè)人中，至少有 2 個(gè)人互不認(rèn)識(shí)。 

（3）對(duì)同一子集中任何 2 個(gè)不相識(shí)的人，在該子集中恰好只 有 1 個(gè)人認(rèn)識(shí)這兩個(gè)人。 

則滿足上述條件的子集最多能有 ___________個(gè)？

第22題

將邊長(zhǎng)為 n 的正三角形每邊 n 等分，過(guò)每個(gè)分點(diǎn)分別做另外兩邊的平行線， 得到若干個(gè)正三角形，我們稱(chēng)為小三角形。正三角形的一條通路是一條連續(xù)的折線， 起點(diǎn)是最上面的一個(gè)小三角形，終點(diǎn)是最 下面一行位于中間的小三角形。在通路中， 只允許由一個(gè)小三角形走到另一個(gè)與其有公共邊的且位于同 一行或下一行的小三 角形，并且每個(gè)小三角形不能經(jīng)過(guò)兩次或兩次以上（圖中是 n=5 時(shí)一條通路的 例 子）。設(shè) n=10，則該正三角形的不同的通路的總數(shù)為_(kāi)____________。

第23題

#include <stdio.h>
int main()
{
	int i,u[4],v[4],x,y=10;
	for(i=0;i<=3;i++)
		scanf("%d", &u[i]);
	v[0]=(u[0]+u[1]+u[2]+u[3])/7;
	v[1]=u[0]/((u[1]-u[2])/u[3]);
	v[2]=u[0]*u[1]/u[2]*u[3];
	v[3]=v[0]*v[1];
	x=(v[0]+v[1]+2)-u[(v[3]+3)%4];
	if(x>10) 由 OIFans.c 收集
		y+= (v[2]*100-v[3])/(u[u[0]%3]*5);
	else
		y+=20+(v[2]*100-v[3])/(u[v[0]%3]*5);
	printf("%d,%d\n", x,y);
	return 0;
} /* 注：本例中，給定的輸入數(shù)據(jù)可以避免分母為 0 或下標(biāo)越界。 */

輸入：9 3 9 4 

輸出：_______________

第24題

#include <stdio.h>
int main()
{
	int i,j,m[]={2,3,5,7,13};
	long t;
	for (i=0;i<=4;i++)
	{
		t=1;
		for(j=1;j<m[i];j++) t*=2;
			printf("%ld ",(t*2-1)*t);
	}
	printf("\n");
}

輸出:____________________

第25題

#include "stdio.h"
#define N 7
int fun1(char s[],char a,int n)
{
	int j;
	j=n;
	while(a<s[j] && j>0) j--;
	return j;
}
int fun2(char s[],char a,int n)
{
	int j;
	j=1;
	while(a>s[j] && j<=n) j++;
	return j;
}
void main()
{
	char s[N+1];
	int k,p;
	for(k=1;k<=N;k++)
		s[k]='A'+2*k+1;
	p=fun1(s,'M',N);
	printf( “%d\n”,p+fun2(s,'M',N));
}

輸出：_____________

第26題

#include <stdio.h>
void digit(long n,long m)
{
	if(m>0)
		printf("%2ld",n%10);
	if(m>1)
		digit(n/10,m/10);
	printf("%2ld",n%10);
}
int main()
{
	long x,x2;
	printf("Input a number:\n"); scanf("%ld",&x);
	x2=1;
	while(x2<x) x2*=10;
	x2/=10;
	digit(x,x2);
	printf("\n");
}

輸入：9734526 

輸出：______________________________

第27題

（選排列）下面程序的功能是利用遞歸方法生成從 1 到 n(n<10)的 n 個(gè)數(shù)中取 k(1<=k<=n)個(gè)數(shù)的 全部可能的排列（不一定按升序輸出）。

例如，當(dāng) n=3，k=2 時(shí)， 應(yīng)該輸出（每行輸出 5 個(gè)排列）： 

12 13 21 23 32 

31

程序：

#include <stdio.h>
int n,k,a[10]; 
long count=0;
void perm2(int j)
{
	int i,p,t;
	if( ① )
	{
		for(i=k;i<=n;i++)
	{
		count++;
		t=a[k]; a[k]=a[i]; a[i]=t;
		for( ② )
			printf("%1d",a[p]); /* "%1d" 中是數(shù)字 1，不是字母 l */
		printf(" ");
		t=a[k];a[k]=a[i];a[i]=t;
		if(count%5==0) printf("\n");
	}
	return;
	}
	for(i=j;i<=n;i++)
	{
		t=a[j];a[j]=a[i];a[i]=t;
		③ ;
		t=a[j]; ④ ;
	}
}
int main()
{
	int i;
	printf("\nEntryn,k (k<=n):\n");
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++) a[i]=i;
	⑤ ;
}

第28題

（TSP 問(wèn)題的交叉算子） TSP 問(wèn)題 (Traveling Salesman Problem) 描述如下： 給定 n 個(gè)城市， 構(gòu)成一個(gè)完全圖，任何兩城市之間都有一個(gè)代價(jià)（例如路程、旅費(fèi)等） ，現(xiàn)要構(gòu)造遍歷所有 城市的環(huán)路，每個(gè)城市恰好經(jīng)過(guò)一次，求使總代價(jià)達(dá)到最小的一條環(huán)路。 遺傳算法是求解該問(wèn)題的一個(gè)很有效的近似算法。 在該算法中， 一個(gè)個(gè)體為一條環(huán)路， 其編 碼方法之一是 1 到 n 這 n 個(gè)數(shù)字的一個(gè)排列， 每個(gè)數(shù)字為一個(gè)城市的編號(hào)。 例如當(dāng) n=5 時(shí)， “ 3 4 2 1 5 表示該方案實(shí)施的路線為 ” 3->4->2->1->5->3 。遺傳算法的核心是通過(guò)兩個(gè)個(gè)體的 交叉操作，產(chǎn)生兩個(gè)新的個(gè)體。下面的程序給出了最簡(jiǎn)單的一種交叉算法。

具體過(guò)程如下：

 (1)選定中間一段作為互換段，該段的起止下標(biāo)為 t1，t2，隨機(jī)生成 t1，t2 后，互換兩段。

 (2)互換后，在每個(gè)新的排列中可能有重復(fù)數(shù)字，因而不能作為新個(gè)體的編碼，一般再做兩 步處理： 

(2.1) 將兩個(gè)互換段中，共同的數(shù)字標(biāo)記為 0，表示已處理完。 

(2.2) 將兩個(gè)互換段中其余數(shù)字標(biāo)記為 1，按順序?qū)⒒Q段外重復(fù)的數(shù)字進(jìn)行替換。

 例如： n=12，兩個(gè)個(gè)體分別是： 

a1: 1 3 5 4 * 2 6 7 9 * 10 12 8 11 

a2: 3 2 1 12 * 6 7 10 11 * 8 5 4 9 t1=5，t2=8。

上述每一行中，兩個(gè)星號(hào)間的部分為互換段。假定數(shù)組的下標(biāo)從 1 開(kāi)始，互換 后有： 

a1: 1 3 5 4 * 6 7 10 11 * 10 12 8 11 

a2: 3 2 1 12 * 2 6 7 9 * 8 5 4 9 

然后，將數(shù)字 6,7 對(duì)應(yīng)的項(xiàng)標(biāo)記為 0，星號(hào)內(nèi)數(shù)字 2,9,10,11 對(duì)應(yīng)的項(xiàng)標(biāo)記為 1，并且按順序 對(duì)應(yīng)關(guān)系為 : 10<->2 ，11<->9。于是，將 a1[9]=10 替換為 a1[9]=2 ，將 a2[2]=2 替換為 a2[2]=10 ， 類(lèi)似再做第 2 組替換。這樣處理后，就得到了兩個(gè)新個(gè)體： 

a1: 1 3 5 4 6 7 10 11 2 12 8 9 

a2: 3 10 1 12 2 6 7 9 8 5 4 11 

（3）輸出兩個(gè)新個(gè)體的編碼。 

程序：

#include <stdio.h>
#include <stdlib.h>
#define N 20
int a1[N],a2[N],kz1[N],kz2[N],n;
int rand1(int k)
{
	int t=0;
	while(t<2|| t>k)
		t=(int)((double)rand()/RAND_MAX*k);
	return t;
}
void read1(int a[],int m)
{ 讀入數(shù)組元素 a[1]至 a[m], a[0]=0 ,略. }
void wrt1(int a[],int m)
{ 輸出數(shù)組元素 a[1]至 a[m],略. }
void cross(int a1[], int a2[],int t1, int t2, int n)
{
	int i,j,k,t,kj;
	for(i=t1; i<=t2; i++)
	{
		t=a1[i]; ①；
	}
	for(i=1;i<=n;i++)
		if(i<t1 || i>t2)
			kz1[i]=kz2[i]=-1;
		else
			②；
	for(i=t1;i<=t2;i++)
	for(j=t1;j<=t2;j++)
	if(a1[i]==a2[j])
	{
 		③ ; break;
	}
	for(i=t1;i<=t2;i++)
	if(kz1[i]==1)
	{
		for(j=t1;j<=t2;j++)
		if(kz2[j]==1)
		{
			kj=j; break;
		}
		for(j=1;j<=n;j++)
		if( ④ )
		{
			a1[j]=a2[kj];break;
		}
		for(j=1;j<=n;j++)
		if( ⑤ )
		{
			a2[j]=a1[i]; break;
		}
		kz1[i]=kz2[kj]=0;
	}
}
int main()
{
	int k,t1,t2;
	printf("input (n>5):\n"); scanf("%d",&n);
	printf("input array 1 (%d'numbers):\n",n); read1(a1,n);
	printf("input array 2 (%d'numbers):\n",n); read1(a2,n);
	t1=rand1(n-1);
	do
	{
		t2=rand1(n-1);
	}while(t1==t2);
	if(t1>t2)
	{
		k=t1; t1=t2; t2=k;
	}
	⑥
	wrt1(a1,n); wrt1(a2,n);
}