6104、
題目內容:
求n个元素中的最大元素值，要求用递归与分治策略解决。
输入
第1行：元素个数n
第2行：n个元素的值
输出：
n个元素中的最大元素值
实例：
输入：
8 //元素个数
10 3 9 20 4 83 24 65 //8个具体的元素值
输出：
83 //最大元素值
#include<iostream> //二分搜索技术 using namespace std; int max(int a[],int m,int n){int mid=(m+n)/2;int max1,max2;if(m==n){return a[m];}else{max1=max(a,m,mid);max2=max(a,mid+1,n);}return max1>max2?max1:max2; } int main(){int n;cin>>n;int a[n];for(int i=0;i<n;i++){cin>>a[i];}cout<<max(a,0,n-1); }
6103、
題目內容:
给定n个元素组成的序列，利用递归与分治策略对其进行排序。
输入：
第1行：元素个数n
第2行：n个元素值
输出：
排好序的n个元素，元素之间用空格分开。
实例：
输入：
5 //输入元素个数
220 10 30 50 40 //输入5个元素
输出：
10 30 40 50 220 //输出排好序的5个元素
#include<iostream> using namespace std; void quicksort(int a[],int low ,int high){if(low>=high){//待排序列只有一个元素，返回空。return ;}int i=low;//从左往右扫描int j=high;//从右往左扫描；int key=a[low];//第一个数作为基数while(i<j){while(a[j]>=key&&i<j){//从右边找小于基数的元素。j--;//找不到j-1}a[i]=a[j];//找到则赋值。while(a[i]<=key&&i<j){//从左边找大于基数的值。i++;}a[j]=a[i];}a[i]=key;//当i和j相遇，将基数元素的值赋值到i处。quicksort(a,low,i-1);//i左边序列继续递归调用快排。quicksort(a,i+1,high); } int main(){int n;cin>>n;int a[n];for(int i=0;i<n;i++){cin>>a[i];}quicksort(a,0,n-1);for(int i=0;i<n;i++){cout<<a[i]<<" ";} }
6102、
題目內容:
在一个2k*2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一个特殊方格，且称该棋盘为一个特殊棋盘。在棋盘覆盖问题中，要用4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
输入：棋盘行数，特殊方格的行坐标，特殊方格的列坐标
输出：填完之后的棋盘状态，对应输出项占两列。
说明：特殊方格位置填写数字0，其它L型骨牌从1开始填写。递归按照左上角，右上角，左小角，右小角的顺序进行。
下面是一个输入，输出实例，第一行是输入，其它行是输出。
#include <iostream> #include<iomanip> using namespace std; int tile=1; int borad[20][20]={-1}; void chessboard(int tr, int tc, int dr, int dc, int size) {// tr棋盘左上角行号。tc棋盘左上角的列号。// dr特殊方格所在行号，dc特殊方格所在列号。// size:size为棋盘的行数。if (size == 1){return;}int t = tile++;int s = size / 2;if (dr < tr + s && dc < tc + s){//看棋盘左上角有无特殊方格chessboard(tr, tc, dr, dc, s);//有}else{borad[tr+s-1][tc+s-1]=t;//无chessboard(tr,tc,tr+s-1,tc+s-1,s);}if(dr<tr+s&&dc>=tc+s){//覆盖棋盘右上角chessboard(tr,tc+s,dr,dc,s);//you特殊方格。}else{borad[tr+s-1][tc+s]=t;chessboard(tr,tc+s,tr+s-1,tc+s,s);}if(dr>=tr+s&&dc<tc+s){chessboard(tr+s,tc,dr,dc,s);}else{borad[tr+s][tc+s-1]=t;chessboard(tr+s,tc,tr+s,tc+s-1,s);}if(dr>=tr+s&&dc>=tc+s){chessboard(tr+s,tc+s,dr,dc,s);}else{borad[tr+s][tc+s]=t;chessboard(tr+s,tc+s,tr+s,tc+s,s);} } int main(){int size;int dr,dc;cin>>size;cin>>dr>>dc;dr=dr-1;dc=dc-1;int array[size][size];array[dr][dc]=0;//特殊位置。for(int i=0;i<size;i++){for(int j=0;j<size;j++){borad[i][j]=array[i][j];}}chessboard(0,0,dr,dc,size);for(int i=0;i<size;i++){for(int j=0;j<size;j++){printf("%2d ",borad[i][j]);}cout<<endl;} }