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

@Sashokk84 · Регистрация: 02.11.2012

Author24 — интернет-сервис помощи студентам

Всем привет!!!
Нужно найти минимальный элемент массива при помощи рекурсии. Просидел вчера весь день и никак не могу воткнуть как написать этот код, при том, что при помощи итерации написал решение за 20 мин.
Могу решить рекурсивно самые простые задачи такие как поиск факториала и т.п., но когда что-то сложнее, то сразу ступор.
Если можно, то подскажите самый простой способ, т.к. главная моя задача сейчас это понять рекурсию.
Вот собственно код:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
using std::cout;
using std::cin;
using std::endl;
 
 
 
int main()
{
    setlocale( LC_ALL, "rus" );
    void pechatMassiva( int[], int const );
    int minMassivaIter( int mass[], int const arraySize );
    //int minMassivaRekurs( int mass[], int const arraySize );
 
    int const arraySize = 10;
    int mass[ arraySize ] = { 12, 34, 6, 45, 18, 37, 11, 83, 92, 33 };
   
    cout << "Массив: ";
    pechatMassiva( mass, arraySize );
    cout << endl;
    cout << "Минимальное число массива (итерация): " << minMassivaIter( mass, arraySize ) << "\n\n";
 
    cout << "Массив: ";
    pechatMassiva( mass, arraySize );
    cout << endl;
    cout << "Минимальное число массива (рекурсия): " /*<< minMassivaRekurs( mass[], arraySize )*/ << "\n\n";
 
}
 
 
void pechatMassiva( int mass[], int const arraySize )
{
    for( int i = 0; i < arraySize; i++ )
        cout << mass[ i ] << " ";
    
}
 
 
int minMassivaIter( int mass[], int const arraySize )
{
    int min = mass[ arraySize - 1 ];//min = последний элемент массива
 
    for( int i = 0; i < arraySize; i++ )
    {
        if( mass[ i ] < min )
            min = mass[ i ];
    }
 
    return min;
}
 
//int minMassivaRekurs( int mass[], int const arraySize )
//{
//  Что сюда писать???
 
//}

@OhMyGodSoLong · 03.11.2012, 13:35

Хотите научу читерской штуке «Как превратить цикл в рекурсию за 5 минут»?

Вот у вас есть код

C++
1
2
3
4
5
6
7
8
9
10
int minMassiva( int mass[], int const arraySize )
{
    int min = mass[ arraySize - 1 ];
    for( int i = 0; i < arraySize; i++ )
    {
        if( mass[ i ] < min )
            min = mass[ i ];
    }
    return min;
}

Рекурсия — это повторное выполнение собственного тела. Цикл — это тоже повторное выполнение собственного тела. Цикл зависит от какой-то переменной-счётчика и ещё этого min. Рекурсивная функция зависит от своих параметров. Значит, шаг первый: вынести все локальные переменные в параметры, теперь они инициализируются там:

C++
1
2
3
4
5
6
7
8
9
int minMassiva( int mass[], int const arraySize, int min, int i )
{
    for( i; i < arraySize; i++ )
    {
        if( mass[ i ] < min )
            min = mass[ i ];
    }
    return min;
}

Теперь смотрим, как изменяются эти переменные в одной итерации цикла. i увеличивается на единичку, min становится равной mass[i], если mass[i] < min. Остальные не меняются. Вот то же самое нам надо повторить в теле рекурсивной функции:

C++
1
2
3
4
5
6
7
8
int minMassiva( int mass[], int const arraySize, int min, int i )
{
    if( mass[ i ] < min )
        min = mass[ i ];
    i++;
    minMassiva( mass, arraySize, min, i );
    return min;
}

Вот только с возвратом у нас всё не так круто. Цикл продолжается, пока i < arraySize, значит так должна вести себя и рекурсия. Когда цикл закончился, он возвращает min. Если он не закончился, то он, очевидно, возвращает то, что навычисляет его следующая итерация.

C++
1
2
3
4
5
6
7
8
9
10
11
12
int minMassiva( int mass[], int const arraySize, int min, int i )
{
    if( i < arraySize)
    {
        if( mass[ i ] < min )
            min = mass[ i ];
        i++;
        return minMassiva( mass, arraySize, min, i );
    }
    else
        return min;
}

Осталось только задать начальные значения и запустить цикл:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minMassiva_rec( int mass[], int const arraySize, int min, int i )
{
    if( i < arraySize)
    {
        if( mass[ i ] < min )
            min = mass[ i ];
        i++;
        return minMassiva( mass, arraySize, min, i );
    }
    else
        return min;
}
 
int minMassivaRec( int mass[], int const arraySize )
{
    return minMassiva_rec( mass, arraySize, mass[ arraySize - 1], 0 );
}

Добавлено через 14 минут
Но это, как видите, тот же итерационный вариант, только записанный по-другому. Можно, конечно, выкинуть пару локальных переменных, заменив их неявным временными. Минимум массива — это наименьшее число среди первого элемента массива и минимума всего остального массива. Вот так и запишем:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// минимум двух чисел
inline
int min(int a, int b)
{
    return (a < b) ? a : b;
}
 
int minArray(int *beginArray, int *endArray)
// минимум массива, ограниченного [beginArray, endArray] это
{
    // если массив состоит из одного элемента, то это этот элемент
    if (beginArray == endArray) {
        return *beginArray;
    }
    // иначе это минимум среди первого элемента и минимума всего остального массива
    else {
        return min(*beginArray, minArray(beginArray + 1, endArray));
    }
}
 
// How to use
int array[5] = { 3, 4, 1, 5, 2 };
std::cout << minArray(&array[0], &array[4]);

По сути, правда, всё равно одно и то же. Переменная min неявно запоминается как аргумент функции min(), а i++ заменился на указатель_на_начало_массива++.

@salam · 03.11.2012, 13:46

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
vector <int> v;
 
    int fmin(int x)
    {
        if(x > 0)
            return min(v[x], fmin(--x));
        else
            if(x == 0)
                return v[x];
    }
 
int main()
{
    int n;
    cin >> n;
    v.resize(n);
    for(int i=0; i < n; i++)
        cin >> v[i];
    cout << fmin(n) << endl;
    system("pause");
    return 0;
}

@igorrr37 · 03.11.2012, 22:37

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <algorithm>
 
template<typename T>
T MinElement(T const* p, size_t const size)
{
    return (1 == size ? *p : std::min(MinElement(p, size / 2), MinElement(p + size / 2, size - size / 2)));
}
 
int main ()
{
    double arr[] = {1.1, -3.3, -3.31, 0.01};
    std::cout << MinElement(arr, std::end(arr) - std::begin(arr)) << std::endl;
    return 0;
}

@Sashokk84 · 04.11.2012, 12:27 **[ТС]**

Всем спасибо! Буду вникать...

@Sashokk84 · 06.11.2012, 16:34 **[ТС]**

Отдельное спасибо ~OhMyGodSoLong~, очень познавательно, решил уже несколько более сложных задач таким методом...

Новые блоги и статьи Все статьи Все блоги /
Что нового в C# 14 UnmanagedCoder 10.03.2025 Предстоящая версия C# 14 обещает принести изменения, которые сделают разработку еще более приятной и эффективной. Что стоит отметить, так это влияние сообщества разработчиков на формирование новых. . .	Формулы поворота Igor3D 10.03.2025 Добрый день Тема Эти формулы приводятся во множестве тьюториалов, часто под видом "матрица вращения на плоскости". x' = x * cos(a) - y * sin(a) y' = y * cos(a) + x * sin(a) Как бы Вы их. . .	Что нового в .NET 10 UnmanagedCoder 10.03.2025 . NET 10 выходит как релиз с длительной поддержкой (LTS), включающей три года обновлений. В этом обновлении Microsoft сфокусировались на нескольких направлениях: производительность, оптимизация. . .	Отложенное высвобождение, RCU и Hazard Pointer в C++26 NullReferenced 09.03.2025 Многопоточное программирование стало важной частью современной разработки. Когда несколько потоков одновременно работают с общими данными, возникает целый ряд проблем, связанных с синхронизацией и. . .	Неблокирующийся стек на C++26 NullReferenced 09.03.2025 Традиционные способы синхронизации в многопоточном программировании — мьютексы, семафоры, условные переменные — часто превращаются в узкое место в плане производительности. При этом неблокирующиеся. . .
Обработка строк в C++26: Новые возможности string и string_view NullReferenced 09.03.2025 Новый стандарт C++26 предлагает много улучшений для работы с привычными string и относительно новыми string_view. string_view - это невладеющая ссылка на последовательность символов, появившаяся в. . .	Мой первый аддон для Blender 3D, с помощью нейронки (не зная даже азов пайтона, но это не значит что так и с остальным). Hrethgir 09.03.2025 Потратил весь день. Пол-дня мне хватило, чтобы понять что с версией с 14B мне не одолеть написание функционального кода, на языке с которым я вообще никак не знаком - пайтон. Версия 22B от другого. . .	Einstein@Home сегодня исполняется двадцать лет! Programma_Boinc 09.03.2025 Einstein@Home сегодня исполняется двадцать лет! Отправлено 19 февраля 2025 года в 17:20:21 UTC Я хочу поздравить всех наших волонтеров, разработчиков и ученых из Einstein@Home. Мы официально. . .	Заполнители и расширенный набор символов в C++26 NullReferenced 09.03.2025 C++26 представляет два важных обновления: заполнители и расширенный набор символов. Заполнители (placeholders) решают давнюю проблему лаконичности кода в шаблонных выражениях и лямбда-функциях. Они. . .	Контракты в C++26 NullReferenced 09.03.2025 Контракты – это механизм, позволяющий указывать предусловия, постусловия и инварианты для функций в коде. Эта функциональность должна была стать частью C++20, но была исключена на встрече комитета. . .

@Sashokk84 1 / 1 / 0 Регистрация: 02.11.2012 Сообщений: 7
	04.11.2012, 12:27 [ТС]	5
	Всем спасибо! Буду вникать... 0

@Sashokk84 1 / 1 / 0 Регистрация: 02.11.2012 Сообщений: 7
	06.11.2012, 16:34 [ТС]	6
	Отдельное спасибо ~OhMyGodSoLong~, очень познавательно, решил уже несколько более сложных задач таким методом... 0

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

Решение