Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 30, средняя оценка - 4.67
Sashokk84
1 / 1 / 0
Регистрация: 02.11.2012
Сообщений: 7
03.11.2012, 13:03     Найти минимальный элемент массива рекурсивно #1
Всем привет!!!
Нужно найти минимальный элемент массива при помощи рекурсии. Просидел вчера весь день и никак не могу воткнуть как написать этот код, при том, что при помощи итерации написал решение за 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 )
//{
//  Что сюда писать???
 
//}
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
03.11.2012, 13:35     Найти минимальный элемент массива рекурсивно #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Хотите научу читерской штуке «Как превратить цикл в рекурсию за 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
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
03.11.2012, 13:46     Найти минимальный элемент массива рекурсивно #3
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
 Аватар для igorrr37
1593 / 1221 / 118
Регистрация: 21.12.2010
Сообщений: 1,868
Записей в блоге: 7
03.11.2012, 22:37     Найти минимальный элемент массива рекурсивно #4
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
1 / 1 / 0
Регистрация: 02.11.2012
Сообщений: 7
04.11.2012, 12:27  [ТС]     Найти минимальный элемент массива рекурсивно #5
Всем спасибо! Буду вникать...
Sashokk84
1 / 1 / 0
Регистрация: 02.11.2012
Сообщений: 7
06.11.2012, 16:34  [ТС]     Найти минимальный элемент массива рекурсивно #6
Отдельное спасибо ~OhMyGodSoLong~, очень познавательно, решил уже несколько более сложных задач таким методом...
Yandex
Объявления
06.11.2012, 16:34     Найти минимальный элемент массива рекурсивно
Ответ Создать тему
Опции темы

Текущее время: 07:18. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru