c - 设计一个算法来判断是否存在这样一个键等于数组中其他两个键的总和

Question

我正在尝试解决这个问题:给定一个包含 n 个键的数组，确定是否存在等于数组中其他两个键之和的键。如果是，打印出来。 我正在使用 mergesort 对数组进行排序，然后检查键。但是(for 循环)内部的求和函数每次都以某种方式无法递增。我已经尝试过(while 循环)和其他几种方法。没有任何作用。有任何想法吗？

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

void merge_sort(int input_array[], int first_element, int last_element);
void merge(int input_array[], int first_element, int middle_element,
           int last_element);
void find_summation(int input_array[], int first_element, int last_element);

int total_elements;
int main() {
  int input_array[100];
  printf("\nEnter number of elements in the array : ");
  scanf("%d", &total_elements);

  int i = 0;
  printf("\nEnter %d array elements: ", total_elements);
  while (i < total_elements) {
    scanf("%d", &input_array[i]);
    i++;
  }
  merge_sort(input_array, 0, total_elements - 1);

  printf("\nSorted Array: ");
  for (int i = 0; i < total_elements; i++) {
    printf("%d ", input_array[i]);
  }

  printf("\n");
  find_summation(input_array, 0, total_elements - 1);
  printf("\n");
  return 0;
}

void find_summation(int input_array[], int first_element, int last_element) {
  bool found;

  last_element = total_elements - 1;
  int j = 2;
  int current_num;

  for (int j = 2; j <= last_element;) {
    current_num = input_array[j];
    while ((first_element < last_element)) {
      int a = input_array[first_element];
      int b = input_array[last_element];
      int summation = a + b;
      printf("summation %d\n", summation);
      if (summation == current_num) {
        found = true;

      } else if (summation > current_num) {
        last_element--;

      } else if (summation < current_num) {
        first_element++;
      }
      if (found) {
        printf("\nKey: %d > sum of Keys: %d & %d", current_num, a,
               current_num - a);
        break;
      }
    }
  }
}

void merge(int input_array[], int first_element, int middle_element,
           int last_element) {
  int m = (middle_element - first_element) + 1;
  int n = last_element - middle_element;

  int left_array[m];
  int right_array[n];

  for (int i = 0; i < m; i++) {
    left_array[i] = input_array[first_element + i];
  }

  for (int j = 0; j < n; j++) {
    right_array[j] = input_array[(middle_element + 1) + j];
  }

  int i = 0, j = 0, k = 0;
  k = first_element;
  while (i < m && j < n) {
    if (left_array[i] <= right_array[j]) {
      input_array[k] = left_array[i++];

    } else {
      input_array[k] = right_array[j++];
    }
    k++;
  }

  while (i < m) {
    input_array[k++] = left_array[i++];
  }

  while (j < n) {
    input_array[k++] = right_array[j++];
  }
}

void merge_sort(int input_array[], int first_element, int last_element) {
  if (first_element < last_element) {
    int middle_element = (first_element + last_element) / 2;

    merge_sort(input_array, first_element, middle_element);
    merge_sort(input_array, middle_element + 1, last_element);

    merge(input_array, first_element, middle_element, last_element);
  } else
    return;
}

Answer 1

感谢大家的指导和支持。终于得到了适用于所有情况的代码。原始代码有很多错误。包括控制流和逻辑错误。我现在已经修复了代码。解决方案贴在下面: 测试用例:18 23 4 35 99 67 198 20 38 55 2 19 487 11 40 10 13 27 22

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

void merge_sort(int input_array[], int first_element, int last_element);
void merge(int input_array[], int first_element, int middle_element,
           int last_element);
void find_summation(int input_array[], int first_element, int last_element);
int binary_search(int input_array[], int first_element, int last_element,
                  int difference);


int main() {
  int total_elements;
  int input_array[100];
  printf("\nEnter number of elements in the array : ");
  scanf("%d", &total_elements);

  int i = 0;
  printf("\nEnter %d array elements: ", total_elements);
  while (i < total_elements) {
    scanf("%d", &input_array[i]);
    i++;
  }
  merge_sort(input_array, 0, total_elements - 1);

  printf("\nSorted Array: ");
  for (int i = 0; i < total_elements; i++) {
    printf("%d ", input_array[i]);
  }

  printf("\n");
  find_summation(input_array, 0, total_elements);
  printf("\n");
  return 0;
}

void find_summation(int input_array[], int first_element, int last_element) {
  for (int j = 0; j <= last_element; j++) {
    int current_num = input_array[j];

    // printf("current_num and j: %d %d\n", current_num, j);

    for (int i = 0; i < j; i++) {
      int element = input_array[i];
      int element_found =
          binary_search(input_array, first_element, j, (current_num - element));

      if (element_found > 0) {
        if (element != (current_num - element))
          printf("\nKey: %d > sum of Keys: %d & %d", current_num, element,
                 current_num - element);

      }  
    }    
  }
}
int binary_search(int input_array[], int first_element, int last_element,
                  int difference) {
  bool found;
  int current_num;

  int middle_element = (first_element + last_element) / 2;
  if ((last_element >= first_element) && (first_element < middle_element)) {
    // int middle_element = (first_element + last_element) / 2;
    /*
        while ((last_element - first_element) <= 2) {
          return binary_search(input_array, middle_element + 1, last_element,
                               difference);
        }*/
    if (input_array[middle_element] == difference) {
      return middle_element;
    }

    if (input_array[middle_element] > difference) {
      return binary_search(input_array, first_element, middle_element - 1,
                           difference);
    }

    return binary_search(input_array, middle_element + 1, last_element,
                         difference);
  }
  return -1;
}
void merge(int input_array[], int first_element, int middle_element,
           int last_element) {
  int m = (middle_element - first_element) + 1;
  int n = last_element - middle_element;

  int left_array[m];
  int right_array[n];

  for (int i = 0; i < m; i++) {
    left_array[i] = input_array[first_element + i];
  }

  for (int j = 0; j < n; j++) {
    right_array[j] = input_array[(middle_element + 1) + j];
  }

  int i = 0, j = 0, k = 0;
  k = first_element;
  while (i < m && j < n) {
    if (left_array[i] <= right_array[j]) {
      input_array[k] = left_array[i++];

    } else {
      input_array[k] = right_array[j++];
    }
    k++;
  }

  while (i < m) {
    input_array[k++] = left_array[i++];
  }

  while (j < n) {
    input_array[k++] = right_array[j++];
  }
}

void merge_sort(int input_array[], int first_element, int last_element) {
  if (first_element < last_element) {
    int middle_element = (first_element + last_element) / 2;

    merge_sort(input_array, first_element, middle_element);
    merge_sort(input_array, middle_element + 1, last_element);

    merge(input_array, first_element, middle_element, last_element);
  } else
    return;
}