Найти минимальное число в массиве с рекурсией?

Question

int i = 0;
int min = x[i];
while ( i < n ){
    if ( x[i] < min ){
        min = x[i];
    }
    i++;
}
return min;

Я написал итерационную форму, чтобы найти минимальный номер массива. Но я бы хотел написать функцию с рекурсией. Пожалуйста, помогите!

Answer 1

Поскольку это звучит как домашнее задание, вот подсказка: минимальное значение в массиве - это либо первый элемент, либо минимальное число в rest массива, в зависимости от того, что меньше.

Answer 2

Это не оптимальное решение, потому что вы можете сохранить результат рекурсивного вызова в переменной int, но мне не разрешили в моем упражнении.

В любом случае, эта функция ищет самое низкое значение в массиве int с помощью рекурсии. Сначала он проверяет, сколько элементов в массиве, проверяя, равен ли размер 1, а затем возвращает первое значение в качестве результата. Если таблица больше 1 (и технически также ниже), она сравнивает последнее значение в массиве с рекурсивным вызовом с остальной частью массива.

Рекурсия останавливается на 0-индексе, а затем сравнивает это значение с индексом 1. Затем она сравнивает наименьшее значение индекса 0 и 1 со значением из индекса 3 и т. Д., Пока не достигнет последнего значения.

int minimum(int array[], int size) {
    if (size == 1) {
        return array[0];
    }
    else {
        return (array[size] < minimum(array, size - 1))
            ? array[size]
            : minimum(array, size - 1);
    }
}

int array[5] = {5, 99, 205, 1, 15};
int smallest = minimum(array, 4); // 4 = index of the last element

Правила в моем упражнении:

• Не изменять массив
• Не используйте переменные
• Использовать рекурсию

Answer 3

Минимальное количество одноэлементного массива - один элемент в массиве.

Минимальное число массива с размером> 1 является минимумом первого элемента и минимумом остальной части массива.

(Минимальное количество пустого массива не определено.)

Answer 4

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

<code>min( array ) {
   if size of array == 1 return array[0]
   else if size of array == 2 return array[0] < array[1] ? array[0] : array[1]
   else {
      firstmin = min( firsthalf) // stored to avoid double calls
      secondmin = min( secondhalf)
      firstmin < second_min ? firstmin : secondmin
   }
 }

для дальнейшей оптимизации:
- избегать копий массива - рассмотрите возможность использования сигнатуры, подобной быстрой сортировке (array, from, to)
- избегать рекурсивных вызовов для размеров <2 </p>

Answer 5

Вот функция, которая будет возвращать указатель на минимальное значение:

#include <stddef.h>

int *recursiveMin(int *x, int n) {
  if (x == NULL || n == 0)
      return NULL;
  if (n == 1)
      return x;
  int *t = recursiveMin(x + 1, n - 1);
  return *x < *t ? x : t;
}

Answer 6

Звучит как домашняя работа, но ваша лучшая ставка выглядит примерно так:

int main(void) {
    int size = 2;
    int test[] = {0,1};
    int min = test[0];
    findMin(&min, test, size);
    printf("%d", min);
}

void findMin(int* min, int* test, int* length);

void findMin(int* min, int* test, int* length) {
    if (length >= 0) {
         if (*test < *min) {
            *min = test;
         }
         findMin(min, test++, (*length)--);
    }
}

Answer 7

#include <iostream>
#include <cstdlib>
using namespace std;

int min(int [], int);
void mostrar(int [], int);

int main() {
    int f[] = {4, 9, 0, -1, 5, 8, -3, 6, -4, 0};
    int t = sizeof(f)/sizeof(int);
    cout << "\nEl valor m\xa1nimo para los valores:\n";
    mostrar(f, t);
    cout << "\nes: " << min(f, t);
    system("pause>nul");
}

int min(int x[], int p) {
    if (p == 1)
        return x[0];
    int aux = min(x+1, p-1);
    return x[0] < aux ? x[0] : aux;
}

void mostrar(int v[], int k) {
    if (k > 1)
        mostrar(v, k-1);
    cout << v[k-1] << " ";
}

Answer 8

int findMin(int a[], int len) {
//  normal version
//  if (len==1) return a[0];
//  return (a[len-1] < findMin(a,len-1))? a[len-1] : findMin(a,len-1);
//  memoization version, sort of?

    int rightside;
    if (len==1) return a[0];

    rightside = findMin(a,len-1);

    return (a[len-1] < rightside)? a[len-1] : rightside;
}

Answer 9

const int = 20;

int getmin (int v[], int n);

main ()
{
    int v[N];
    int i,n,min;

    printf("\n\tType number of elements:\t");
    scanf("%d",&n);

    for (i=0;i<n;i++)
    {
        printf("\nv[%d]:\t",i);
        scanf("%d",&v[i]);             
    }

    min = getmin (v,n);

    printf("\n\n\tMinimume value is %d.",min); 
}

int getmin (int v[],int n)
{
    if (n>0)
    {
        if ( v[n-2] > v[n-1] )
        {
            v[n-2]=v[n-1];               
        }
        getmin (v,n-1);
    }

    return v[n-2];       
}

Answer 10

Попробуйте:

  int recursive_min(list<int> arr) {
    return recursive_min(arr);
  }

Хотя это не работает в императивных языках.

Более серьезный ответ в псевдокоде:

func recursive_min( list l ) {
 head = l[1]
 tail = l[2<->end]
 if l.length==1 return head else return min(head,recursive_min(tail))
}

Хотя это не сработает, если l пусто.