Рекурсивная минимальная функция

Question

#include<stdio.h> 
#define SIZE 7 

int recursiveMinimum(int a[], int size); 

int main(void) { 
    int a[ SIZE ] = { 5, 7, 4, 3, 5, 1, 3 }; // Number 2 is not initialized. 

    printf("The smallest number is %d", recursiveMinimum(a, SIZE)); 

    return 0; 
} 

int recursiveMinimum(int a[], int size) { 
    static int min ; 
    static int i = 0; 

    min = a[ i ]; 
    if(a[ i + 1 ] < min) { 
     min = a[ i + 1 ]; 
    } 

    i++; 

    if(i == size ) { 
     return min; 
    } else { 
     return recursiveMinimum(a, size ); 
    } 
} 

Так почему же он печатает 2?

Answer 1

У вас есть доступ к вашему массиву по отдельности: вы получаете доступ к элементу a[7], но последний элемент вашего массива - a[6].

Посмотрите у вас есть:

i++; 
if(i == size ) { 

но выше вы обращаетесь к a[i + 1], что означает, в какой-то момент вы получите доступ к a[size] (который находится за пределами массива).

Изменить if (i == size) на if (i == size - 1), чтобы исправить вашу проблему.

Answer 2

• Вы не инициализировать min правильно, он должен быть установлен минимально возможного числа он может иметь, например, константа INT_MIN найденной в limits.h. Вместо этого вы переписываете min в каждом рекурсивном вызове с помощью строки min = a[ i ];.
• Вы получаете доступ к массиву вне пределов, в последнем вызове функции, когда i равно 6, вы запускаете код [ i + 1 ], который вызывает неопределенное поведение. К сожалению, ваша программа не сработала, но вместо этого вывела часть стоимости мусора.
• Нет абсолютно никакой причины использовать рекурсию для этого алгоритма, который вы пишете.

Answer 3

Показать этот код (я добавляю целую переменную статического ИНТ initialize_min для инициализации мин как [0] в вызове первой функции):

#include<stdio.h> 
#define SIZE 7 

int recursiveMinimum(int a[], int size); 

int main(void) { 
    int a[ SIZE ] = { 5, 7, 4, 3, 5, 1, 3 }; // Number 2 is not initialized. 

    printf("The smallest number is %d", recursiveMinimum(a, SIZE)); 

    return 0; 
} 

int recursiveMinimum(int a[], int size) { 
    static int min; 
    static int initialize_min = 1; 
    static int i = 0; 


    if(initialize_min) 
    { 
     min = a[0]; 
     initialize_min = 0; 
    } 



    if(a[ i ] < min) { 
     min = a[ i ]; 
    } 

    i++; 

    if(i == size ) { 
     return min; 
    } else { 
     return recursiveMinimum(a, size ); 
    } 
} 

Answer 4

Для использования INT_MIN, мы должны включить limits.h. Также он должен быть небезопасно, потому что мы хотим использовать неподписанные, долго, долго долго, __int8 и т.д.

Answer 5

Я думаю, что этот пример является то, что предназначено для рекурсивной функции минимума:

#include <stdio.h> 
#define SIZE 7 

#define min(a, b) (((a) < (b)) ? (a) : (b)) 

/*  assumes size != 0 */ 
int recursiveMinimum(int a[], size_t size){ 
int *beg;    /* ptr to beginning */ 
int *mid;    /* ptr to middle */ 
int *end;    /* ptr to end */ 
    if(size < 2)  /* if size == 1 */ 
     return a[0]; 
    beg = &a[0];  /* else split array */ 
    mid = &a[size/2]; /* and recurse */ 
    end = &a[size]; 
    return min(recursiveMinimum(beg, mid-beg), 
       recursiveMinimum(mid, end-mid)); 
} 

int main(void) 
{ 
    int a[SIZE] = {5, 7, 4, 3, 5, 1, 3 }; 
    printf("The smallest number is %d", recursiveMinimum(a, SIZE)); 
    return 0; 
} 

Answer 6

Вы могли бы попробовать этот метод:

double smaller(double a, double b){ 
    return (a<b)?a:b; 
} 

double min(double *p_array, int idx_low, int idx_high){ 
    if(idx_low==idx_high) 
    return p_array[idx_low]; 
    int idx_mid=idx_low+(idx_high-idx_low)/2; 
    return smaller(min(p_array,idx_low,idx_mid), min(p_array,idx_mid+1, idx_high)); 
} 

анализ алгоритма должен дать Вам O(n*log(n)) время работы - взять его с щепоткой соли, хотя.