十、用分治法求金块问题老板有一袋金块共n块,n是2

《十、用分治法求金块问题老板有一袋金块共n块,n是2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、十、用分治法求金块问题：老板有一袋金块(共n块，n是2的幂（n>=2）)，最优秀的雇员得到其中最重的一块，最差的雇员得到其中最轻的一块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块(书P130).31#includeintn;floata[100];maxmin(inti,intj,float&fmax,float&fmin){intmid;floatlmax,lmin,rmax,rmin;if(i==j){fmax=a[i];fmin=a[i];}elseif(i==j-1){if(a[i]

2、}else{fmax=a[i];fmin=a[j];}}else{mid=(i+j)/2;maxmin(i,mid,lmax,lmin);maxmin(mid+1,j,rmax,rmin);if(lmax>rmax)fmax=lmax;elsefmax=rmax;if(lmin>rmin)fmin=rmin;elsefmin=lmin;}}voidmain(){floatfmax=0;floatfmin=0;cout<<"请输入一维数组的长度"<>n;cout<<"请初始化数组！"<>a[i];maxmin(0,

3、n-1,fmax,fmin);cout<<"fmax="<voidmain(){inta[50][50][3],i,j,n;cout<<"pleaseinputthenumberofrows:";cin>>n;cout<

4、>>a[i][j][1];a[i][j][2]=a[i][j][1];a[i][j][3]=0;}for(i=n-1;i>=1;i=i-1)for(j=1;j<=i;j=j+1)if(a[i+1][j][2]>a[i+1][j+1][2]){a[i][j][2]=a[i][j][2]+a[i+1][j][2];a[i][j][3]=0;}else{a[i][j][2]=a[i][j][2]+a[i+1][j+1][2];a[i][j][3]=1;}cout<<"max="<

5、]<<"->";j=j+a[i][j][3];}cout<intjz[8][8]={{0,1,1,1,0,1,0,0},{1,0,0,0,0,1,0,0},{1,0,0,1,1,0,0,0},{1,0,1,0,0,0,1,0},{0,0,1,0,0,0,1,1},{1,1,0,0,0,0,0

6、,1},{0,0,0,1,1,0,0,1},{0,0,0,0,1,1,1,0}};struct{intcity,pre;}sq[100];intqh,qe,i,visited[100];intn=8;voidout(){cout<

7、q[qh].city][i]==1)&&(visited[i]==0)){qe=qe+1;sq[qe].city=i;sq[qe].pre=qh;visited[i]=1;if(sq[qe].city==7){out();return;}}}cout<<"Noavaliableway.";}voidmain(){inti;for(i=1;i<=n;i=i+1)visited[i]=0;search();cout<