}
9. 荷兰国旗问题。要求重新排列一个由字符R, W, B（R代表红色，W代表白色，B代表兰色，这都是荷兰国旗的颜色）构成的数组，使得所有的R都排在最前面，W排在其次，B排在最后。为荷兰国旗问题设计一个算法，其时间性能是O(n)。
//0代表红；1代表白；2代表蓝 #include
const int N = 20;
void swap_ab ( int *p , int *q ) {
int tmp = *p; *p = *q; *q = tmp; }
void process ( int a[], int n ) {
int *p, *q; p = q = a;
while ( p != a+n-1 ) //p向前遍历，直到便利完毕 {
if ( *(p+1) < *p ) {
q = p+1;
while ( *q < *(q-1) ) {
swap_ab ( q, q-1 ); --q; //q指针后移 } } //if ++p; } //while }
int main()
{
int a[N] = { 0, 2, 1, 2, 0, 1, 0, 2, 2, 1, 0, 1, 2, 1, 1, 0, 0, 1, 1, 2}; //待处理的数组
cout << \处理后的数组序列: \ process ( a, N );
for (int i=0; i< N; ++i ) cout << a[i] <<\
cout << endl; return 0; }
10. 设最近对问题以k维空间的形式出现，k维空间的两个点p1=(x1, x2, ?, xk)和p2=(y1, y2, ?, yk)的欧几里德距离定义为：d(p1,p2)??(y-x)iii?1k2。对k维空间的最近对问题设计
蛮力算法，并分析其时间性能。
11．设计蛮力算法求解小规模的线性规划问题。假设约束条件为：（1）x+y≤4；（2）x+3y≤6；（3）x≥0且y≥0；使目标函数3x+5y取得极大值。
#include
int main() {
int x,y,x0,y0;
int summax=0,temp=0; for(x0=0;x0<=4;++x0) {
for(y0=0;(x0+y0<=4)&&(x0+3*y0<=6);++y0)
temp=3*x0+5*y0; if(temp>=summax) { summax=temp; x=x0;//符合sum最大值的x y=y0;//符合sum最大值得y }
}//for
cout<<\
return 0; }
12．设计算法，判定一个以邻接矩阵表示的连通图是否具有欧拉回路。
算法描述：
输入：邻接矩阵(n*n)
输出：如有证明有欧拉回路，则输出该回路，否则，输出无解信息 1 对矩阵的对角线是否有>0的元素进行判断 1.1 循环变量i从1—n重复进行下述操作：
1.1.1计算矩阵i次方，如果矩阵对角线上有>0的元素，则跳转到1.2 1.1.2否则++i;
1.2 如果矩阵对角线有>0的元素，则输出该回路 2 输出无解信息；
13．找词游戏。要求游戏者从一张填满字符的正方形表中，找出包含在一个给定集合中的所有单词。这些词在正方形表中可以横着读、竖着读、或者斜着读。为这个游戏设计一个蛮力算法
14. 变位词。给定两个单词，判断这两个单词是否是变位词。如果两个单词的字母完全相同，只是位置有所不同，则这两个单词称为变位词。例如，eat和tea是变位词。
//判断qwer和rewq是否是变位词 #include
int main() {
char s[5]=\ char t[5]=\ for(int i=0;i!=4;++i) { if(s[i]!=t[3-i]) { cout<<\和rewq不是变位词\ return 0; break; } }
cout<<\和rewq是变位词\
return 0; }
15．在美国有一个连锁店叫7-11店，因为这个商店以前是早晨7点开门，晚上11点关门。有一天，一个顾客在这个店挑选了四样东西，然后到付款处去交钱。营业员拿起计算器，按了一些键，然后说：“总共是$7.11。”这个顾客开了个玩笑说：“哦？难道因为你们的店名叫7-11，所以我就要付$7.11吗？”营业员没有听出这是个玩笑，回答说：“当然不是，我已经把这四样东西的价格相乘才得出这个结果的！”顾客一听非常吃惊，“你怎么把他们相乘呢？你应该把他们相加才对！”营业员答道：“噢，对不起，我今天非常头疼，所以把键按错了。”然后，营业员将结果重算了一遍，将这四样东西的价格加在一起，然而，令他俩更为吃惊的是总和也是$7.11。设计蛮力算法找出这四样东西的价格各是多少？
该算法为：
int $7.11(float a[],float b[],float c[],float d[],int n) {
for(int i=0;i!=n;++i) for(int j=0;j!=n;++j) for(int k=0;k!=n;++k)
for(int m=0;m!=n;++m) {
if((a[i]+b[j]+c[k]+d[m])==7.11 && a [i]*b[j]*c[k]*d[m]==7.11) cout< 习题4 1. 分治法的时间性能与直接计算最小问题的时间、合并子问题解的时间以及子问题的个数有关，试说明这几个参数与分治法时间复杂性之间的关系。 2. 证明：如果分治法的合并可以在线性时间内完成，则当子问题的规模之和小于原问题的规模时，算法的时间复杂性可达到O(n)。 O(N)=2*O(N/2)+x