조건에 맞는 두 수를 빠르게 찾기(두 수의 합은 주어진 값이다)

3585 단어 buffermerge
먼저 순서를 점차적으로 늘리고 첫 번째 지침을 더하면 목표 수보다 크고 끝 지침은 앞쪽으로 이동하며 목표 수보다 작고 첫 번째 지침은 뒤로 이동하며 두 지침이 마주칠 때까지 계속 비교한다.
프로그램은 아래와 같습니다. 이 문제를 빌려서 MergeSort를 연습해 봅시다.
#include <stdio.h>
#include <boost/scoped_ptr.hpp>
void FindTargetSum(int array[], int begin, int end, int target_value) {
  int min = begin;
  int max = end;
  int sum;
  while (min < max) {
    sum = array[min] + array[max];
    if (sum > target_value) {
      max--;
    } else if (sum < target_value) {
      min++;
    } else {
      printf("%d %d
", array[min], array[max]); FindTargetSum(array, min - 1, max - 1, target_value); break; } } } template<typename T> void Merge(T array[], int begin, int middle, int end) { int length1 = middle - begin + 1; int length2 = end - middle; boost::scoped_ptr<T> first_array_buffer(new T[length1]); T* first = first_array_buffer.get(); boost::scoped_ptr<T> second_array_buffer(new T[length2]); T* second = second_array_buffer.get(); for (int i = 0; i < length1; ++i) { first[i] = array[begin + i]; } for (int i = 0; i < length2; ++i) { second[i] = array[middle + 1 + i]; } int pos1 = 0; int pos2 = 0; int pos = begin; while (pos1 < length1 || pos2 < length2) { if (pos1 < length1 && pos2 < length2) { if (first[pos1] < second[pos2]) { array[pos++] = first[pos1++]; } else { array[pos++] = second[pos2++]; } } else if (pos1 < length1) { array[pos++] = first[pos1++]; } else { array[pos++] = second[pos2++]; } } } template<typename T> void MergeSort(T array[], int begin, int end) { if (begin < end) { int middle = (begin + end ) / 2; // int middle1 = begin + (end - begin + 1) / 2; // printf("--middle:%d, middle1:%d
", middle, middle1); MergeSort(array, begin, middle); MergeSort(array, middle + 1, end); Merge(array, begin, middle, end); } } template<typename T> void Merge1(T array[], int begin, int middle, int end) { int length1 = middle - 1 - begin + 1; int length2 = end - middle + 1; boost::scoped_ptr<T> first_buffer(new T[length1]); T* first = first_buffer.get(); boost::scoped_ptr<T> second_buffer(new T[length2]); T* second = second_buffer.get(); for (int i = 0; i < length1; ++i) { first[i] = array[begin + i]; } for (int i = 0; i < length2; ++i) { second[i] = array[middle + i]; } int pos = begin; int pos1 = 0; int pos2 = 0; while (pos1 < length1 || pos2 < length2) { if (pos1 < length1 && pos2 < length2) { if(first[pos1] < second[pos2]) { array[pos++] = first[pos1++]; } else { array[pos++] = second[pos2++]; } } else if (pos1 < length1) { array[pos++] = first[pos1++]; } else { array[pos++] = second[pos2++]; } } } template<typename T> void MergeSort1(T array[], int begin, int end) { if (begin < end) { int middle = begin + (end - begin + 1) / 2; MergeSort1(array, begin, middle - 1); MergeSort1(array, middle, end); Merge1(array, begin, middle, end); } } int main(int argc, char** argv) { int array[] = {1, 5, 4, 7, 8 ,10}; size_t array_size = sizeof(array) / sizeof(int); MergeSort1(array, 0, array_size - 1); for (int i = 0; i < array_size; ++i) { printf("%d ", array[i]); } printf("
"); FindTargetSum(array, 0, array_size - 1, 15); }

좋은 웹페이지 즐겨찾기