Computer algorithm design and analysis (Chapter II computer practice)

7-1) binary search

Enter n values (1 < = n < = 1000), n integers in non descending order and the number x to be found. Use the binary search algorithm to find x, and output the subscript (0~n-1) where x is located and the number of comparisons. If X does not exist, output - 1 and the number of comparisons.

#include <iostream>
using namespace std;

int count = 0; 
//Find element x in array a[left...right]
int biSearch(int x, int a[],  int left, int right) {
  if (left > right) //When there are no elements in the array
return -1;
count++;
int middle = (left + right) / 2;
  if (a[middle] == x) //If found, return directly to the location
return middle;
  else if (a[middle] > x) //If the number in the middle is greater than x, search recursively in the left half of the array
returnbiSearch(x, a, left, middle - 1);
  else //Otherwise, recursive lookup is performed in the right half of the array
returnbiSearch(x, a, middle + 1, right);
}

int main() {
int n; 
cin>> n;
int a[n];
for (inti = 0; i< n; i++)
	cin>> a[i];
int x;
cin>> x;

cout<<biSearch(x, a, 0, n - 1) <<endl;
cout<< count <<endl;
}

7-2) Rewrite binary search algorithm

If a[0:n-1] is an ordered array, please rewrite the binary search algorithm so that when x is not in the array, the maximum element position i less than X and the minimum element position J greater than X are returned. When the search element is in the array, i and j are the same, both of which are the position of X in the array.

#include <iostream>
using namespace std;

voidbiSearch(int x, int a[],  int left, int right) {
  if (left > right) { //When there are no elements in the array
cout<< right << " " << left <<endl;
	return;
  }
int middle = (left + right) / 2;
if (a[middle] == x) {
	cout<< middle << " " << middle <<endl;
	return;
  } else if (a[middle] > x)
returnbiSearch(x, a, left, middle - 1);
else
returnbiSearch(x, a, middle + 1, right);
}

int main() {
int n; 
int x;
cin>> n >> x;
int a[n];
for (inti = 0; i< n; i++)
	cin>> a[i];

biSearch(x, a, 0, n - 1);
}

7-3) median of two ordered sequences

It is known that there are two non descending sequences S1 and S2 of equal length. Design the function to find the median of the union of S1 and S2. The median of the ordered sequences A0,A1,..., AN − 1 refers to the value of A(N − 1) / 2, that is, the number of ⌊ (N+1)/2 ⌋ (A0 is the first number).

Method 1:
#include <iostream>
using namespace std;


//Find the median of two ordered series of equal length
/*
Solution idea: the median is greater than and only greater than n-1 elements, and less than and only less than n elements
a_mid = (a_left + a_right) / 2
b_mid = (b_left + b_right) / 2
 When a[a_mid]=b[b_mid], the median is a[a_mid]
When a [mid] < B [mid]:
If n is an odd number, the median range is a[a_mid...a_right], b[b_left...b_mid]
If n is an even number, the median range is a[a_mid+1...a_right], b[b_left...b_mid]
When a [mid] > b [mid]:
If n is an odd number, the median range is a[a_left...a_mid], b[b_mid...b_right]
If n is an even number, the median range is a[a_left...a_mid], b[b_mid+1...b_right]
When the problem scale is 1, there are only two numbers, and the smaller value is directly output
*/ 
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 the lookup array contains two numbers, find the median directly
if (a_r == a_l) {
	return a[a_l] < b[b_l] ? a[a_l] : b[b_l];
  }

  //Median a of the first array lookup range_ m. 
a_m = (a_l + a_r) / 2;
  //Median B of the second array lookup range_ m. 
b_m = (b_l + b_r) / 2;

  //If the two median values are equal, exit is found
if(a[a_m] == b[b_m])
  {
num = a[a_m];
  } else if(a[a_m] < b[b_m]) {
    //If n is an even number, the starting position of the right half is the median position plus 1
if ((a_r - a_l + 1) % 2 == 0) 
	a_m += 1; 
    //The search range of the first array is the right half, and the search range of the second array is the left half
num = find(a, a_m, a_r, b, b_l, b_m);   		

  }
else {
    //If n is an even number, add 1 to the median position of the start position of the right half
if ((b_r - b_l + 1) % 2 == 0) 
		b_m += 1;
    //The search range of the first array is the left half, and the search range of the second array is the right half
num = find(a, a_l, a_m, b, b_m, b_r);	
  }
return num;

}

int main() {
int n;
cin>> n;
int a[n];//Array 1
int b[n];//Array 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;
}
Method 2:
#include <stdio.h>
int main(){
intn,m;
	scanf("%d",&n);
	int a[n],b[n];
	for(inti=0; i<n;i++){
		scanf("%d",&a[i]);
	}
	for(inti=0; i<n;i++){
		scanf("%d",&b[i]);
	}
	inta_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);
}

Chapter II homework questions

7-2) find the smallest number k

Design an algorithm with an average time of O(n), and find the smallest number k in n (1 < = n < = 1000) unordered integers.
Tip: the function int partition(int a[],int left,int right) divides a[left]a[right] according to an element X (such as a[left]) in a[left]a[right]. After the division, the left segment of X is less than or equal to X and the right segment is greater than or equal to X. at the same time, the position of X can also be used to calculate that x is the number of this batch of data in ascending rather than descending order. Therefore, you can compile the int find(int a[],int left,int right,int k) function, obtain the partition point by calling the partition function, and judge whether the partition point is smaller than K. if not, call the find function recursively to continue searching in the left or right segment.

#include <iostream>
using namespace std;

//The first element of the array is used to divide the array into two parts. The front part is smaller than the first element,
//The latter is larger than the first element, which is exactly the same as the quick sort division
int partition(int a[], int left, int right) {
int i = left + 1;
int j = right;
int x = a[left];
while(true) {
while (a[i] < x &&i< right) i++;
while (a[j] > x) j--;
if (i>= j) break;
swap(a[i], a[j]);
  }
swap(a[left], a[j]);
return j;
}

//Output the K-th smallest number in the array elements with subscripts from left to right
int find(int num[], int left, int right, int k) {
int p = partition(num, left, right); //Returns the subscript of the partition element
int n = p - left + 1; // Divide the element into the nth smallest
int t;
if ( n == k)
        t = num[p];
    else if (n < k) //Find the k-n minor in the right half
        t = find(num, p + 1, right, k - n);
    else //Find the small k in the left half
        t = find(num, left, p - 1, k);
return t;
}

int main() {
int n, k;
cin>> n >> k;
intnum[n];
for (inti = 0; i< n; i++)
cin>>num[i];
cout<< find(num, 0, n - 1, k) <<endl;
return 0;
}

7-3) find the number of pairs in reverse order

Problem Here's what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example: Start with: 2 8 0 3 swap (2 8) 8 2 0 3 swap (2 0) 8 0 2 3 swap (2 3) 8 0 3 2 swap (8 0) 0 8 3 2 swap (8 3) 0 3 8 2 swap (8 2) 0 3 2 8 swap (3 2) 0 2 3 8 swap (3 8) 0 2 8 3 swap (8 3) 0 2 3 8
So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps: Start with: 2 8 0 3 swap (8 0) 2 0 8 3 swap (2 0) 0 2 8 3 swap (8 3) 0 2 3 8
The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence? Since Charlie does not have Raymond's mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question in O(nlogn). Rest assured he will pay a very good prize for it.

#include <iostream>
usingnamespace std;

//Finding the cross inverse ordinal number of l~m and m+1~r array elements in ordered a array by divide and conquer method
//Returns an inverse ordinal number
intcrossInv(int a[], int l, int m, int r) {
int i = l; 
int j = m + 1;
int k = 0;
int b[r - l + 1];
int count = 0; //Save cross inverse number
while (i<= m && j <= r) {
if (a[i] <= a[j]) {
      //When copying the array elements of l~m subarray of array a to array b, several elements of m+1~r subarray have been copied to array b, which is the reverse order of the array elements
count += j - (m + 1);
b[k++] = a[i++];
    }
else
b[k++] = a[j++];
  }

  ///Copy the remaining elements of array a ~ b to array m ~ in reverse order
while (i<= m) {
b[k++] = a[i++];
count += j - (m + 1);
  }

while (j <= r)
b[k++] = a[j++];

  //Copy the ordered numbers of b array back to a[l..r] 
for (int i = 0; i< k; i++)
a[l + i] = b[i];
return count;
}

int inverse(int a[], int l, int r) {
if (l == r)
return 0;
int m = (l + r) / 2;
int count = 0; //Save reverse order number
  count += inverse(a, l, m); //The number in reverse order of the left array
  count += inverse(a, m + 1, r); //The reverse order of the array on the right
  count += crossInv(a, l, m, r); //Cross inverse ordinal number of left and right arrays
return count;
}

int main() {
int n;
cin>> n;
int* a = new int[n];
for (inti = 0; i< n; i++)
cin>> a[i];
int count = inverse(a, 0, n - 1);
cout<< count <<endl;
delete a;
return 0;
}

7-4) maximum number in a unimodal array

include<iostream>
using namespace std;

constint MAXN = 10010;

int find(int* a, int l, int r) {
	//If there is only one number, return it directly
	if (l == r)
		return a[l];
		
	int mid = (l + r) / 2;
	//If it descends, find the left half; Otherwise, find the right half
	if (a[mid] > a[mid + 1])
		return find(a, l, mid);
	else
		return find(a, mid + 1, r);
}

int main() {
	int n;
	cin>> n;
	int a[n];
	for (inti = 0; i< n; i++) {
		cin>> a[i];
	}
	cout<<find(a, 0, n - 1);
	return 0;
}

7-5) finding the zero point of the function by dichotomy

There is a function: f(x)=x5 − 15x4+85x3 − 225x2+274x − 121. It is known that f (1.5) > 0, f (2.4) < 0, and the equation f(x)=0 has only one root in the interval [1.5,2.4]. Please find the root by dichotomy. Tip: judge whether the function is 0, and use the expression Fabs (f (x)) < 1e-7.

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

//Calculate the value of the function
double f(double x) {
	return pow(x, 5) - 15 * pow(x, 4) + 85 * pow(x, 3) - 225 * pow(x, 2) + 274 * x - 121;
}

//Divide and conquer. Using recursive solution
double solve(double l, double r) {
	if (r - l < 1e-7) return l; //When the interval is approximately a point, return
	double mid = (l + r) / 2;
	double value = f(mid);
	//If the value of the midpoint is approximately 0, the midpoint is returned; If it is greater than zero, find the right half interval;
	//If less than zero, find the left half interval
	if (fabs(value)  < 1e-7) 
		return mid;
	else if (value > 0) 
		return solve(mid, r);
	else
		return solve(l, mid);
}

int main() {
	double l = 1.5;
	double r = 2.4;
	cout<<fixed <<setprecision(6) << solve(1.5, 2.4) <<endl;
	return 0;
}

(7-6) (choose a topic)

My birthday is coming! According to custom, I need to distribute some pie to everyone. I have N pies of different flavors and sizes. F friends will come to my party and everyone will get a piece of pie (one piece of pie must be made up of several pieces of pie; it can be a whole pie).
My friends are very stingy. If someone gets a bigger piece, they will start to complain. So everyone gets the same size of pie (but it doesn't need to be the same shape). Although some pies will be wasted, it's better than screwing up the whole party. Of course, I also want to keep one for myself, and this one should be the same size as others.
What's the maximum amount of pie each of us gets? Each pie is a cylinder with a height of 1 and different radii.

#include <iostream>
#include <iomanip>
using namespace std;
const double PI = 3.1415926;
constint MAX_NUM = 100002;

double pie[MAX_NUM];//Volume of each pie
int n;//Number of pie
int f;//Number of people

doublemaxPie(double l, double r) { 
	if (r - l < 1e-7) 
		return r;
	double mid = (l + r) / 2;
	
	//Determine the maximum number of mid sized pies
	int max = 0;
	for (inti = 0; i< n; i++)
		max += int(pie[i] / mid);
		
	//If enough points, use two points to find a bigger pie; Or find a smaller pie
	if (max >= f + 1)
		returnmaxPie(mid, r);
	else
		returnmaxPie(l, mid);
}

int main() {
	cin>> n >> f;
	double sum = 0;
	double max = 0;
	int r;
	for (inti = 0; i< n; i++) {
		cin>> r;
		pie[i] = PI * r * r;
		sum += pie[i];
		if (pie[i] > max)
			max = pie[i];
	}
	
	//The maximum value of each pie is equal to the volume of all pies
	doubleavg = sum / f;

	cout<< fixed <<setprecision(3) <<maxPie(0, max) <<endl;
}

Tags: C++ Algorithm data structure Binary Search

Posted by YappyDog on Fri, 13 May 2022 10:12:34 +0300