Нахождение минимального элемента при помощи рекурсивной функции в одномерном массиве

Question

Прошу пояснить что делает функция minimal(построчно) и для чего мы выполняем то или иное действие в функции minimal. В частности, я не понимаю что делает k=size>>1, array+k и size-k.

#include <stdio.h>
#include <conio.h>
     
int minimal (int *array, int size)
{
    int l, r, k;
     
    if (size==1) 
        return *array;
     
    l = minimal(array, k=size>>1);
    r = minimal(array+k, size-k);
     
    return l < r ? l : r; 
}
     
void main(void) 
{
    int i;
    int a[10];
     
    for(i=0; i<10; i++)
    {
        printf("Vvedite znachenie elemnte %d massiva a: ", i);
        scanf("%d", &a[i]);
    }
    printf ("Minimalnoe znachenie massiva = %d", minimal(a,10));
    getch();
}

Answer 1

Опираясь на комментарий @avp, распишу немного подробнее.

Во-первых, соглашусь с комментатором, что это то ещё извращение.

Во-вторых, по непонятному:

k=size>>1: здесь используется оператор побитового сдвига >>. Он сдвигает двоичное представление числа вправо на столько бит, сколько стоит после >>. В данном случае на 1. То есть, если, например, size в двоичном виде был 1000100110001011, то станет 0100010011000101 (сдвинулось вправо на 1, самый правый элемент пропал, слева добавился 0). В данном случае это сделано для простого деления на 2 с округлением в меньшую сторону. То есть, эквивалентной записью было бы k = floor(size / 2). Но сдвигом это работает быстрее (процессору так проще).
array+k наращивает указатель на массив на k. Теперь, при рекурсивном вызове функции, array будет начинаться не с нулевого элемента, а с k-ого. Это аналогично передаче указателя на k-ый элемент массива вот так: &array[k].
size - k – здесь всё просто. На предыдущей строке k присваивается половина размера массива с округлением в меньшую сторону, а значит оставшаяся часть массива, те самые size - k элементов идут в следующий рекурсивный вызов.
Назначение функции – найти наименьший элемент массива с помощью дробления его на половинки, тех половинок на ещё половинки и так далее, пока половинки не станут размером в 1 элемент. Потом выбирается, какая из половинок больше, и возвращается в результат.
Бонусом расскажу, что значит запись l < r ? l : r. Вдруг это тоже не понятно. Это аналогично простому условию if. Всё, что до знака ? – условие. Между вопросом и : – действие, если условие выполнено. Всё, что после : – если не выполнено. То есть в данном случае это можно переписать как:

if (l < r)
    return l;
else
    return r;

P.S. Я пояснил только непонятные моменты. Если Вам непонятно абсолютно всё, Вам не сюда, а в учебники по C.

БЛОГ НА HUSL

Нахождение минимального элемента при помощи рекурсивной функции в одномерном массиве

Ответы (1 шт):