Нахождение минимального значения массива из определенной точки

Question

Я пытаюсь создать рекурсивную функцию, которая будет возвращать наименьшее значение массива после определенной точки, которая будет введена в функцию.

Это должно быть сделано рекурсивно без использования циклов.

Это то, что у меня есть до сих пор:

#include <stdio.h>

int findMinpos(int arr[], int mid, int len){
  int minimum;
  if(len==1)
    return arr[0+mid];

  else {
    minimum = findMinpos(arr, mid, len-1);
    if(minimum<arr[len-1])
      return minimum;
    else
      return arr[len-1];
  }
}

int main(void) {
  int array[7]= {23,17,8,7,9,32,56};
  printf("%d", findMinpos(array, 2, 7));
  return 0;
}

Я не уверен, что делаю неправильно, я мог бы помочь.

Answer 1

Я подозреваю, что это домашняя работа, чтобы научить подходить к проблемам с Разделяй и властвуй . Это разбивает проблему на две более простые подзадачи, которые затем решаются рекурсивно. Обычно это полезно для сортировки и поиска.

Просто найти наименьший элемент в списке - это перебор, это O (nlogn), где простым циклом будет O (n), но он обучает технике. Я надеюсь.

В этом случае вы найдете наименьший элемент массива, разделив его на две половины, найдя наименьший элемент из этих половин, а затем взяв минимум из них. Вы продолжаете расщепление, пока у вас не будет только одного элемента, который завершает рекурсию.

@ chux уже написал код , мне не нужно повторять это.

Почему они хотят, чтобы вы делали это, начиная с определенного индекса, не имеет большого смысла. Я подозреваю, что на самом деле вы должны использовать среднюю точку, чтобы разделить массив пополам и выполнить рекурсивные операции, например ...

int findMin(int arr[], int start, int len) {
  assert(len > 0);
  if(len == 1 ) {
    return arr[start];
  }
  int mid = len/2;
  int left_min = findMin(arr, start, mid);
  int right_min = findMin(arr, mid, len - mid);
  return left_min < right_min ? left_min : right_min;
}

int main(void) {
  int array[7]= {23,17,8,7,9,32,56};
  printf("%d\n", findMin(array, 0, 7));
}

Это избавляет от необходимости выполнять арифметику указателей. Арифметика с указателями, как правило, быстрее и проще, но часто ее обучают только позже.

Answer 2

mid никогда не обновляется.

Код "работает" с тестовым набором по счастливой случайности.

---

Это нужно сделать рекурсивно, без использования циклов.

Конечно, для поиска минимума int.

рекурсия не требуется и не рекомендуется.

---

Хотя и вызывается mid, findMinpos(arr, mid, len-1) подразумевает, что код будет вызывать findMinpos() N раз (N - исходное количество элементов массива) , а обеспечивает глубину рекурсии O (N).

Такое линейное использование рекурсии дает рекурсиям дурную славу.

Вместо этого делите задачу пополам на каждый findMinpos вызов.

int findMinpos_alt(int arr[], int len){
  assert(len > 0);
  if(len == 1 ) {
    return arr[0];
  }
  int left_len = len/2
  int left_min =  findMinpos_alt(arr, left_len);
  int right_min =  findMinpos_alt(arr + left_len, len - left_len);
  return left_min < right_min ? left_min : right_min;
}

Это вызывает функцию N раз, но глубина рекурсии O (log (N)).

---

Более продвинутый код будет использовать

int findMinpos_alt2(const int arr[], size_t len);