给定三个整数 a,b,c 写出寻找其中数的算法，并分析平均和最坏情况下要作多少次比较？
由于A,B,C中每一个为中数的概率均为⅓；
当A为中数时，需要比较2次。
当B或C为中数时，则需要比较3次；
由此可知，平均情况下需要比较的次数为：2⅓+3⅓+3*⅓=8/3次，最坏的情况下则需要比较3次。
#include <iostream>
#inlcude "stdlib.h"
using namespace std;
int mid(int a,int b,int c)
{
int m;
m = a; //先假设中数为m
if (m >= b)
{
if (m >= c)
{
if (b >= c) m = b; //中数为b
else m = c; //中数为c
}
}
else
{
if(m<=c)
{
if (b >= c) m = c; //中数为c
else m = b; //中数为b
}
}
return (m);
}
int main()
{
int a, b, c;
cout << "please input a,b,c=\t";
cin >> a >> b >> c;
cout << "所求的中数为：" << mid(a, b,c) << endl;
system("pause");
return 0;
}
#include <stdio.h>
#include <conio.h>
int main(){
int a,b,c,d;
printf("Input a,b,c:");
scanf("%d,%d,%d",&a,&b,&c);
if(a>=b){
if(b>=c)d=b; //a >= b >= c ，比较2次
else if(a>=c)d=c; //a >= c > b ，比较3次
else d=a; // c > a >= b ，比较3次
}else{
if(a>=c)d=a; //b > a >= c ，比较2次
else if(b>=c)d=c; //b >= c > a ，比较3次
else d=b; //c > b > a ，比较3次
} //平均比较次数：(2+3+3+2+3+3)/6=8/3次，最坏比较次数：3次
printf("Zhong Shu = %d\nFinished!\n",d);
getch();
return 0;
}
平均比较8/3次，最坏比较3次。第二个问题：
#include <stdio.h>
#include <conio.h>
int BinMax(int a[],int low,int high){//二分查找最大值，low、high为查找范围下标
if(low>high){
printf("\nBinMax Error!\n");
return -32768;//范围出错，提示，并返回整型最小值
}
if(low==high)return a[low];
if(low==high-1)return (a[low]>a[high]?a[low]:a[high]);
int mid=(low+high)/2,m1,m2;
m1=BinMax(a,low,mid);//找前半部的最大值
m2=BinMax(a,mid+1,high);//找后半部的最大值
return (m1>m2?m1:m2);
}
int main(){
int a[9]={3,6,2,5,9,1,8,7,10},max;//元素个数不一定要满足n=2^k
max=BinMax(a,0,8);
printf("max=%d\nFinished!\n",max);
getch();
return 0;
}