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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Не определяется равносторонний треугольник по заданным координатам http://www.cyberforum.ru/cpp-beginners/thread687522.html
Делаю программу для определения типа треугольника по введённым координатам.Столкнулся с проблемой:не определяется равносторонний треугольник.Как решить данную проблему?
C++ ** - что это? long ** mass; Что это значит? Если бы было написано long *mass; - это объявление указателя mass типа int. Но две звездочки что означают? http://www.cyberforum.ru/cpp-beginners/thread687519.html
C++ Поменять местами наименьшие из положительных элементов массивов А (55) и В (8х7)
Помогите сделать программу: Поменять местами наименьшие из положительных элементов массивов А (55) и В (8х7). Буду благодарен.
C++ Что-то непонятное с памятью
Есть два класса, базовый: class Rand{ protected: double *masRand;//Указатель на массив сл.вел long size;//Размер массива public: double* rnd( long N = 100, long x0 = 9340718,
C++ base64decode с русскими символами http://www.cyberforum.ru/cpp-beginners/thread687490.html
приветствую всех! Возникла необходимость декодировать сроку закодированную base64. Пришёл к такому выводу, пользуясь онлайн декодерами. Строки, изначально написанные только латинскими символами и/или цифрами декодириются корректно, а вот с русскими получаешься в результате абра кадабра. Прошу подсказать, как реализовать декодирование средствами си++, что бы оно шло корректно и с русскими...
C++ Потоковый ввод/вывод текста Добрый день! Помогите пожалуйста разобраться. Почему при вводе текста в консоли, он сохраняется каракулями? #include <cstdlib> #include <iostream> #include <fstream> using namespace std; подробнее

Показать сообщение отдельно
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
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++ заменился на указатель_на_начало_массива++.
 
Текущее время: 10:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru