计算机算法设计与分析第二章递归与分治策略上机题

野性酷女 2023-10-03 17:40 77阅读 0赞

#### 文章目录 ####

*  第二章上机题
 *  7-1 二分查找 (20 分)
 *   *  1.题目描述
     *  2.参考代码
     *  3.习题答案
 *  7-2 改写二分搜索算法 (20 分)
 *   *  1.题目描述
     *  2.参考代码
     *  3.习题答案
 *  7-3 两个有序序列的中位数 (20 分)
 *   *  1.题目描述
     *  2.参考代码
     *  3.习题答案
     *   *  方法一：
         *  方法二

--------------------

## 第二章上机题 ##

## 7-1 二分查找 (20 分) ##

### 1.题目描述 ###

输入n值(1<=n<=1000)、n个非降序排列的整数以及要查找的数x，使用二分查找算法查找x，输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

**输入格式:**  
输入共三行： 第一行是n值； 第二行是n个整数； 第三行是x值。

**输出格式:**  
输出x所在的下标（0~n-1）及比较次数。若x不存在，输出-1和比较次数。

**输入样例:**

4
    1 2 3 4
    1
    //结尾无空行

**输出样例:**

0
    2
    //结尾无空行

### 2.参考代码 ###

#include <iostream>
    using namespace std;
    int cnt=0;
    //#书上的二分搜索写法：
    int BinarySearch(int a[],int x,int n)
    {
        
    	int left=0;
    	int right=n-1;
    	while(left<=right)
    	{
         
    		int middle=(right+left)/2;
    		if(x==a[middle])
    		{
        
    			cnt++;
    			return middle;
    		}
    		if(x>a[middle])
    		{
        
    			cnt++;
    			left=middle+1;
    		}
    		else{
        
    			cnt++;
    			right=middle-1;
    		}
    	}
    	return -1;
     } 
    int main()
    {
        
    	int n;
    	cin>>n;
    	int a[n];
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>a[i];
    	}
    	int x;
    	cin>>x;
    	cout<<BinarySearch(a,x,n)<<endl;
    	cout<<cnt;
    }

> 普通的二分搜索法，用cnt记录比较次数

### 3.习题答案 ###

#include <iostream>
    using namespace std;
    
    int count = 0; 
    //在数组a[left...right]中查找元素x
    int biSearch(int x, int a[],  int left, int right) {
        
      if (left > right) //当数组中没有元素时
          return -1;
      count++;
      int middle = (left + right) / 2;
      if (a[middle] == x) //如果找到，直接返回位置
         return middle;
      else if (a[middle] > x) //如果中间的数字大于x，在数组左半部分递归查找
         return biSearch(x, a, left, middle - 1);
      else //否则在数组右半部分递归查找
        return biSearch(x, a, middle + 1, right);
    }
    
    int main() {
        
      int n; 
      cin >> n;
      int a[n];
      for (int i = 0; i < n; i++)
      	cin >> a[i];
      int x;
      cin >> x;
      
      cout << biSearch(x, a, 0, n - 1) << endl;
      cout << count << endl;
    }

## 7-2 改写二分搜索算法 (20 分) ##

### 1.题目描述 ###

题目来源：《计算机算法设计与分析》，王晓东

设a\[0:n-1\]是已排好序的数组，请改写二分搜索算法，使得当x不在数组中时，返回小于x的最大元素位置i和大于x的最小元素位置j。当搜索元素在数组中时，i和j相同，均为x在数组中的位置。

**输入格式:**  
输入有两行：

第一行是n值和x值； 第二行是n个不相同的整数组成的非降序序列，每个整数之间以空格分隔。

**输出格式:**  
输出小于x的最大元素的最大下标i和大于x的最小元素的最小下标j。当搜索元素在数组中时，i和j相同。 提示：若x小于全部数值，则输出：-1 0 若x大于全部数值，则输出：n-1的值 n的值

**输入样例:**  
在这里给出一组输入。例如：

6 5
    2 4 6 8 10 12
    //结尾无空行

**输出样例:**  
在这里给出相应的输出。例如：

1 2
    ///
    结尾无空行

### 2.参考代码 ###

#include <iostream>
    using namespace std;
    void BinarySearch_2(int a[],int x,int left,int right,int &i,int &j)
    {
        
    	while(left<=right)
    	{
         
    		int middle=(right+left)/2;
    		if(x==a[middle])
    		{
        
    			i=j=middle;
    			return;
    		}
    		if(x>a[middle])
    		{
        
    			left=middle+1;
    		}
    		else{
        
    			right=middle-1;
    		}
    	}
    	i=right;
    	j=left;
    	return;
     } 
    int main()
    {
        
    	int n,x;
    	cin>>n>>x;
    	int a[n];
    	
    	for(int i=0;i<n;i++)
    	{
        
    		cin>>a[i];
    	}
    	int i,j;
    	BinarySearch_2(a,x,0,n-1,i,j);
    	cout<<i<<" "<<j;
    }

> 使用i和j记录left和right的下标，i，j经过空函数BinarySearch\_2处理后得出

### 3.习题答案 ###

#include <iostream>
    using namespace std;
    
    void biSearch(int x, int a[],  int left, int right) {
        
      if (left > right) {
         //当数组中没有元素时 
          cout << right << " " << left << endl;
    	  return;
      }
      int middle = (left + right) / 2;
      if (a[middle] == x) {
        
      	  cout << middle << " " << middle << endl;
      	  return;
      } else if (a[middle] > x)
         return biSearch(x, a, left, middle - 1);
      else
          return biSearch(x, a, middle + 1, right);
    }
    
    int main() {
        
      int n; 
      int x;
      cin >> n >> x;
      int a[n];
      for (int i = 0; i < n; i++)
      	cin >> a[i];
    
      biSearch(x, a, 0, n - 1);
    }

## 7-3 两个有序序列的中位数 (20 分) ##

### 1.题目描述 ###

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0,A1 ,⋯,A N−1的中位数指A(N−1)/2的值,即第⌊(N+1)/2⌋个数（A0为第1个数）。  
**输入格式:**  
输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。

**输出格式:**  
在一行中输出两个输入序列的并集序列的中位数。

**输入样例1:**

5
    1 3 5 7 9
    2 3 4 5 6
    //结尾无空行

**输出样例1:**

4
    //结尾无空行

**输入样例2:**

6
    -100 -10 1 1 1 1
    -50 0 2 3 4 5
    //结尾无空行

**输出样例2:**

### 2.参考代码 ###

#include <iostream>
    #include <algorithm>
    using namespace std;
    void Merge(int a[],int b[],int left,int mid,int right){
        
    	int i=left,j=mid+1,k=left;
    	
    	while((i<=mid)&&(j<=right)){
        
    		if(a[i]<=a[j])
    		{
        
    			b[k]=a[i];
    //			cout<<b[k]<<"1"<<" "<<k<<endl;
    			k++,i++;
    			
    		}
    		else{
        
    			b[k]=a[j];
    //			cout<<b[k]<<"2"<<" "<<k<<endl;
    			k++,j++;
    			
    		}
    		
    	}
    	if(i>mid)
    		{
        
    			for(int q=j;q<=right;q++)
    			{
        
    				b[k++]=a[q];
    			}
    			
    		}
    		else{
        
    			for(int q=i;q<=mid;q++){
        
    			b[k++]=a[q];
    		}
    }
    }
    void Copy(int a[],int b[],int left,int right)
    {
        
    	for(int i=left;i<right;i++)
    	{
        
    		a[i]=b[i];
    	}
    }
    //void MergeSort(int a[],int left,int right)
    //{
        
    //	if(left<right)
    //	{
        
    //		int i=(left+right)/2;
    //		MergeSort(a,left,i);
    //		MergeSort(a,i+1,right);
    //		Merge(a,b,left,i,right);
    //		Copy(a,b,left,right);
    //		
    //	}
    //}
    int main()
    {
        
    	int n;
    	cin>>n;
    	int a[2*n];
    	int b[2*n];
    	for(int i=0;i<2*n;i++)
    	{
        
    		cin>>a[i];
    	}
    //	for(int i=0;i<2*n;i++)
    //	{
        
    //		cout<<a[i]<<" ";
    //	}
    //	cout<<endl;
    	Merge(a,b,0,floor((2*n+1)/2)-1,2*n-1);
    //	for(int i=0;i<2*n;i++)
    //	{
        
    //		cout<<b[i]<<" ";
    //	}
    	Copy(a,b,0,2*n-1);
    	int res=floor((2*n+1)/2)-1;
    	cout<<a[res];
     }

### 3.习题答案 ###

#### 方法一： ####

方法一：
    #include <iostream>
    using namespace std;
    
    
    //查找两个等长有序系列的中位数
    /*
    解题思路：中位数满足大于且仅大于n-1个元素，小于且仅小于n个元素 
    1）当问题规模为1时，只有两个数字，直接输出较小的值
    a_mid = (a_left + a_right) / 2
    b_mid = (b_left + b_right) / 2
    2）当a[a_mid]=b[b_mid]时，中位数为a[a_mid]
    3）当a[mid]<b[mid]时:
          若n为奇数，中位数存在范围为a[a_mid...a_right], b[b_left...b_mid]
          若n为偶数，中位数存在范围为a[a_mid+1...a_right], b[b_left...b_mid]
    4）当a[mid]>b[mid]时：
          若n为奇数，中位数存在范围为a[a_left...a_mid], b[b_mid...b_right]
          若n为偶数，中位数存在范围为a[a_left...a_mid], b[b_mid+1...b_right]
    
    */ 
    int find(int a[], int a_l, int a_r, int b[], int b_l, int b_r) {
        
      int a_m, b_m;
      int num;
     
      //如果查找数组包含两个数字，则直接找出中位数
      if (a_r == a_l) {
        
    	return a[a_l] < b[b_l] ? a[a_l] : b[b_l];
      }
    
      //第1个数组查找范围的中位数a_m。
      a_m = (a_l + a_r) / 2;
      //第2个数组查找范围的中位数b_m。
      b_m = (b_l + b_r) / 2;
    
      //如果两个中位数相等，则找到退出
      if(a[a_m] == b[b_m])
      {
        
        num = a[a_m];
      } else if(a[a_m] < b[b_m]) {
        
        //如果n为偶数，右半部分的开始位置为中位数位置加1
        if ((a_r - a_l + 1) % 2 == 0) 
        	a_m += 1; 
        //第1个数组查找范围为右半部分，第2个数组查找范围为左半部分
        num = find(a, a_m, a_r, b, b_l, b_m);   		
    
      }
      else {
        
        //如果n为偶数，右半部分的开始位置中位数位置加1
        if ((b_r - b_l + 1) % 2 == 0) 
     		b_m += 1;
        //第1个数组查找范围为左半部分，第2个数组查找范围为右半部分
        num = find(a, a_l, a_m, b, b_m, b_r);	
      }
      return num;
    
    }
    
    int main() {
        
      int n;
      cin >> n;
      int a[n];//数组1
      int b[n];//数组2
    
      for (int i = 0; i < n; i++)
        cin >> a[i];
      for (int i = 0; i < n; i++)
        cin >> b[i];
      cout << find(a, 0, n - 1, b, 0, n - 1) << endl;
    
      return 0;
    }

#### 方法二 ####

方法二：
    #include <stdio.h>
    int main(){
        
        int n,m;
    	scanf("%d",&n);
    	int a[n],b[n];
    	for(int i=0; i<n;i++){
        
    		scanf("%d",&a[i]);
    	}
    	for(int i=0; i<n;i++){
        
    		scanf("%d",&b[i]);
    	}
    	int a_flag=0,b_flag=0;
    	while(a_flag+b_flag<n-1){
        
    		if(a[a_flag]>=b[b_flag])
    			b_flag++;
    		else
    			a_flag++;
    	}
    	m=a[a_flag]>b[b_flag]?b[b_flag]:a[a_flag];
    	printf("%d",m);
    }

> 本题主要运用合并排序的方法

一般cout<<endl后不接输出  
[C++endl的本质介绍][C_endl]

[C_endl]: https://blog.csdn.net/K346K346/article/details/49981695?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163340676516780274157359%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=163340676516780274157359&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-49981695.first_rank_v2_pc_rank_v29&utm_term=endl&spm=1018.2226.3001.4187