Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Михаил_НН
0 / 0 / 0
Регистрация: 17.03.2016
Сообщений: 1
#1

Рекурсивный, линейный поиск с использованием вектора - C++

17.03.2016, 13:50. Просмотров 496. Ответов 6
Метки нет (Все метки)

Изучаю C++ по книжке Дейтелов "Как прогарммировать на C++". Попалась задача на рекурсию: "(Поиск наименьшего значения в массиве) Напишите рекурсивную функцию recursiveMinimum, которая принимает массив и размер массива как аргументы и возвращает наименьший элемент массива. Функция должна прекращать свою работу и возвращаться, если принимаемый массив имеет один элемент." Данную задачу решил без особого труда:
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
#include<iostream>
#include<cstdlib>
using namespace std;
 
int minimum( int[], int );
 
int main()
{
    const int size = 100;
    int array[ size ];
    for( int count = 0; count < 100; count++ )
        array[ count ] = rand() % 200;
    for( int count = 0; count < 100; count++ )
        cout << array[ count ] << " ";
    cout << endl;
    int m = minimum( array, size );
    cout << "minimum is " m << endl;
    return 0;
}
 
 
 
int minimum( int a[], int s )
{
    static int min = 9999999;
    if( s == 0 )
        return min;
    else
    {
        if( a[ s - 1 ] < min )
        {
            min = a[ s - 1 ];
        }
        minimum( a, s - 1 );
    }
}
Затем идет задача с продолжением: "(Поиск наименьшего значения в векторе) Модифицируйте свое решение
упражнения 7.37 для поиска наименьшего значения не в массиве, а в векторе."
Делаю по тому же принципу с изменениями в виду особенностей вектора, но наименьшее значение всегда получается, как я понял, из случайно попавшейся ячейки памяти, всегда разное, например: -1075921740. Вот код:
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
#include<iostream>
#include<cstdlib>
#include<vector>
#include<iomanip>
using namespace std;
 
int minimum( const vector< int > & );
 
int main()
{
    const int size = 100;
    vector< int > array( size );
    for( int count = 0; count < 100; count++ )
        array[ count ] = rand() % 200;
    for( int count = 0; count < 100; count++ )
    {
        if( count % 8 == 0 )
            cout << endl;
        cout << setw( 4 ) << array[ count ];
    }
    cout << endl;
    int m = minimum( array );
    cout << "Minimum is " << m << endl;
    return 0;
}
 
 
 
int minimum( const vector< int > &a )
{
    static int min = 9999999;
    if( a.size() == 1 )
        return min;
    else
    {
        if( a[ a.size() - 1 ] < min )
        {
            min = a[ a.size() - 1 ];
        }
        vector< int > b( a.size() - 1 );
        for ( size_t count = 0; count < b.size(); count++ )
            b[ count ] = a[ count ];
        }
        cout << endl;
        minimum( b );
    }
}
Помогите разобраться, пожалуйста. Сам никак не могу найти ошибку ошибку.

Добавлено через 1 час 18 минут
извиняюсь за неверное название темы. Речь идет о поиске наименьшего

Добавлено через 48 секунд
Использую компилятор g++ в ubuntu, если это как то поможет
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.03.2016, 13:50
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Рекурсивный, линейный поиск с использованием вектора (C++):

Почему не происходит рекурсивный реверс всего вектора?
здравствуйте, есть код: #include &lt;boost/mpl/vector_c.hpp&gt; #include...

Рекурсивный вывод стека с использованием классов
:'(Помогите пожалуйста написать прогу с определением класса рекурсии для вывода...

Рекурсивный поиск в глубину
Нужно найти путь по простому лабиринту от точки к точке, используя в программе...

Рекурсивный поиск в списке
Добрый вечер. Я решал одну задачку из книги Х.Дейтела и П.Дейтела &quot;Как...

поиск в ширину(Рекурсивный)
Программа запускается но выдает ошибку(Задача такая: Создать программу для...

рекурсивный поиск файлов
Всем привет! Нажно реализовать поиск файлов по маске. Набрасал вот такой код:...

6
Liss29
26 / 15 / 4
Регистрация: 18.11.2012
Сообщений: 572
Завершенные тесты: 1
30.06.2016, 07:03 #2
Если ещё интересно, то вот мой вариант, правда, для VC g++ у меня нет!
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <vector>
using std::vector;
int recursiveMinimum(vector<int> &a, int i);
void printV(vector<int> &);
using namespace std;
int main()
{
    vector<int> min(100);
    srand(time(0));
    int i = 0;
    for(size_t n = 0; n < min.size(); n++)
        min[n] = rand() % 200;
    cout << endl;
    printV(min);
    
    cout << "Минимальное значение в векторе = " << recursiveMinimum(min, i) << endl;
    return 0;
}
 
int recursiveMinimum(vector<int> &a, int i)
{
    static int min = 9999999;
    if(a.size() == 1)
        return a[i];
    else if(i < a.size())
    {
        if(a[i] < min)
        {
            min = a[i];
            return recursiveMinimum(a, i + 1);
        }
        return recursiveMinimum(a, i + 1);
    }
    return min;
}
 
void printV(vector<int> &m)
{
    for(int i = 0; i < m.size(); i++)
    {
        cout << setw(5) << m[i];
        if((i + 1) % 10 == 0)
            cout << endl;
    }
}
0
_Ivana
3232 / 1860 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
30.06.2016, 14:36 #3
C++
1
int vmin(vector<int> &a, int b, int e) {int m = (b+e)/2; return b>=e ? a[b] : min(vmin(a, b, m), vmin(a, m+1, e));}
0
Liss29
26 / 15 / 4
Регистрация: 18.11.2012
Сообщений: 572
Завершенные тесты: 1
30.06.2016, 21:48 #4
Что за min? Как-то сложно, на мой взгляд!
0
_Ivana
3232 / 1860 / 235
Регистрация: 01.03.2013
Сообщений: 5,091
Записей в блоге: 5
30.06.2016, 21:59 #5
Цитата Сообщение от Liss29 Посмотреть сообщение
Что за min?
из cmath, возвращает миниальное значение двух аргументов
Цитата Сообщение от Liss29 Посмотреть сообщение
Как-то сложно, на мой взгляд!
конечно, чистый однострочник сложнее 20 строк со статической переменной.
0
Liss29
26 / 15 / 4
Регистрация: 18.11.2012
Сообщений: 572
Завершенные тесты: 1
30.06.2016, 23:40 #6
Цитата Сообщение от _Ivana Посмотреть сообщение
из cmath
Интересно, но по моему о включении в проект библиотек С++ речи не шло.

Цитата Сообщение от _Ivana Посмотреть сообщение
чистый однострочник сложнее 20 строк со статической переменной.
Как могу! Или лучше вообще ничего не писать, я на самы короткий и оптимальный код не претендую, пока что!
А
C++
1
b и e
- это что за индексы? Я так понял с их помощью осуществляется проход по массиву, первоначально они равны нулю, далее в вызове
Код
b
будет элементом, который сравнвается с предыдущим, в данном случае
Код
e
, это вроде сортировка какая-то или как... Условие выхода тоже напрягает, если b >= e и b постоянно увеличивается на еденичку, как условие может выполниться, только сильно керзовыми спогами не пинай)
0
Namat
12 / 12 / 5
Регистрация: 02.12.2014
Сообщений: 35
01.07.2016, 00:34 #7
Ты забыл выход из рекурсии и не сравниваешь самый первый элемент.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minimum( const vector< int > &a )
{
    static int min = 9999999;
    if( a.empty() )
        return min;
    else
    {
        if( a[ a.size() - 1 ] < min )
        {
            min = a[ a.size() - 1 ];
        }
        vector< int > b( a.size() - 1 );
        for ( size_t count = 0; count < b.size(); count++ ){
            b[ count ] = a[ count ];
        }
        cout << endl;
        return minimum( b );
    }
}
1
01.07.2016, 00:34
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.07.2016, 00:34
Привет! Вот еще темы с решениями:

Помогите зациклить рекурсивный поиск
Помогите зациклить поиск(пока работает для 2 список, если их больше не...

Рекурсивный поиск файлов и папок
в консоли выводится бесконечный повторяющийся список, как этого избежать?!...

Рекурсивный и нерекурсивный поиск в глубину
Не уверен в правильности работы даной функции. Если начинать с вершины 2, то...

Рекурсивный поиск файла. Падаю
используя различные примеры из интернета, написал функцию, которая ищет файл и...


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

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

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