Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 30, средняя оценка - 4.67
Sashokk84
1 / 1 / 0
Регистрация: 02.11.2012
Сообщений: 7
#1

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

03.11.2012, 13:03. Просмотров 5157. Ответов 5
Метки нет (Все метки)

Всем привет!!!
Нужно найти минимальный элемент массива при помощи рекурсии. Просидел вчера весь день и никак не могу воткнуть как написать этот код, при том, что при помощи итерации написал решение за 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 )
//{
//  Что сюда писать???
 
//}
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2012, 13:03
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти минимальный элемент массива рекурсивно (C++):

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

Записать элементы массива X, удовлетворяющие условию в массив Y; найти минимальный элемент массива X - C++
4. Записать элементы массива X, удовлетворяющие условию Х, подряд в массив Y =. Определить минимальный элемент массива X.

Найти минимальный элемент массива (через указатели, запрещено обращаться к элементам массива по индексам) - C++
Написать программу, создающую массив из 10 случайных целых чисел из отрезка . Вывести на экран весь массив и на ...

Найти минимальный элемент массива - C++
Привет всем,ребят может кто помочь,очень сильно нужна помощь:cry: есть одномерный массив,состоящий из N элементов,необходимо найти...

Найти минимальный элемент массива - C++
1. Найти минимальный элемент массива. 2. Найти сумму элементов массива, расположенных между первым и последним положительными...

Найти минимальный элемент массива - C++
Найти минимальный элеммент массива.

5
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 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++ заменился на указатель_на_начало_массива++.
3
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
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;
}
1
igorrr37
1648 / 1276 / 133
Регистрация: 21.12.2010
Сообщений: 1,932
Записей в блоге: 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;
}
2
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
06.11.2012, 16:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.11.2012, 16:34
Привет! Вот еще темы с ответами:

Найти минимальный элемент массива - C++
Дан одномерный массив чисел {X(i)} i=1..12. вычислить частное от деления суммы отрицательных чисел на сумму положительных. Найти...

Найти минимальный элемент массива - C++
Добрый вечер. Я учусь на программиста. 1-й курс. Вот мое задание: В одномерном массиве, состоящем из n вещественных элементов, ...

Найти минимальный элемент массива - C++
Помогите, пожалуйста. 2. Дан массив А (15). Найти минимальный элемент массива.

Найти минимальный элемент массива - C++
Дан массив N. Найти и вывести минимальный элемент и его индекс. Если сумма минимального элемента и его индекса больше 12, то все нулевые...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.