알고리즘 분석 과 디자인 실험 - 중위 수 문제

분 치 법 해결 중위 수 문제 실험
문제 설명
X [0: n - 1] 과 Y [0: n - 1] 을 두 개의 배열 로 설정 하고 각 배열 에는 n 개의 정렬 된 순서 가 포함 되 어 있 습 니 다.X 와 Y 의 2n 개 수의 중위 수 를 찾 아 라.분할 전략 을 이용 하여 O (log n) 시간의 알고리즘 을 시험 적 으로 설계 하여 이 2n 개의 수의 중위 수 를 구하 십시오.파일 input. txt 에서 입력 데 이 터 를 제공 합 니 다. 파일 의 첫 번 째 줄 에는 정수 n (n < 200) 이 있 습 니 다. 각 배열 에 n 개의 수가 있 음 을 표시 합 니 다.다음 두 줄 은 각각 X, Y 배열 의 요소 이다.프로그램 실행 이 끝 났 을 때 계 산 된 중위 수 를 파일 output. txt 에 출력 합 니 다.
실험 설계
fstream f ("D: / / 알고리즘 분석 및 디자인 / input. txt");파일 istringstream is1 (row 2) 읽 기;stoi () 에 맞 춰 빈 칸 분석 문자열 에 따라 배열 a 와 b 의 재 귀 알고리즘 으로 중위 알고리즘 을 구 합 니 다. temp (int * a, int * b, int size) {m 는 두 배열 의 중간 위치 if (두 배열 의 중위 가 같 음) {return a [m]; 직접 되 돌아 갑 니 다} else if (a 배열 의 중위 > b 배열 의 중위){a 배열 의 전반 부 를 취하 고 b 배열 의 후반 부 를 취하 여 재 귀 합 니 다. 배열 의 길이 가 1 이면 b} else {b 배열 의 전반 부 를 취하 고 a 배열 의 후반 부 를 취하 여 재 귀 합 니 다. 배열 의 길이 가 1 이면 바로 a 로 돌아 갑 니 다.

	}

}

ofstream of("D://       /output.txt"); //  output.txt  。

절차 가 끝나다.
실험 코드

#include 
#include
#include
#include
using namespace std;
int  temp(int *a, int *b, int size) {
	
		int m = (size - 1) / 2;  //    
		if (a[m] == b[m]) {  //    ，    
			return a[m];
		}
		else if (a[m] > b[m]) {   //  a>b,   a    ，b    ，  2     
			return size == 1 ? b[m] : temp(a, b + size - m - 1, m + 1);  //       1，  （    ）
		}
		else
		{
			return size == 1 ? a[m] : temp(a + size - m - 1, b, m + 1); //   
		}
		
	
}
int main()
{
	string row1;
	string row2;
	string row3;

	fstream f("D://       /input.txt");// input.txt       
	getline(f, row1);
	getline(f, row2);
	getline(f, row3);

	int size = stoi(row1); //    

	int* a = new int[size];
	int* b = new int[size];
	string r1;
	string r2;
	istringstream is1(row2);
	istringstream is2(row3);
	int i = 0;
	while (is1>>r1)     //         ，   a b 
	{
		a[i] = stoi(r1);
		i++;
	}
	i = 0;
	while (is2>>r2)
	{
		b[i] = stoi(r2);
		i++;
	}
	f.close();
	int median = temp(a, b, size);

	ofstream of("D://       /output.txt"); //  output.txt  。 
	of << median << endl;
	of.close();
	cout << median;

}