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

Рекурсивный спуск - Функция не останавливается на "else return" - C++

Восстановить пароль Регистрация
 
pavlikzlo
0 / 0 / 0
Регистрация: 09.08.2014
Сообщений: 3
09.08.2014, 12:54     Рекурсивный спуск - Функция не останавливается на "else return" #1
не могу понять, почему функция не останавливается на "else return *(a+mid);"
делал отладку, после этого return'a происходит еще два вызова? и в итоге возвращает -1

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
using namespace std;
#include <iostream>
 
 
int search ( int *a, int nel, int k )
{
    int mid = 0, high = nel - 1, low = 0;
    
        mid = ( low + high )/2;
    
        cout << "My number is:" << *( a + mid ) << endl;
    
        if (*(a + mid) > k)
        
            search (a, high - mid, k);
        
        else
            if (*(a + mid) < k)
 
                search ( a + mid + 1, high - mid, k);
            
            else return *(a + mid);
    
    
    
    return -1;
}
 
 
 
 
int main () {
    
    int *array = new int;
    int el, size;
    
    cout << "Put size of your array:" << endl;
    cin >> size;
    cout << "Now put your first element:" << endl;
    cin >> el;
    
    for (int i = 0 ; i < size ; i++ )
    {
        *(array + i ) = el++;
        cout << *(array + i)<< " ";
    }
    cout << endl;
    cout << search ( array, size, 9);
    
    
    return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Справлюсь
 Аватар для Справлюсь
23 / 23 / 5
Регистрация: 24.07.2014
Сообщений: 203
09.08.2014, 13:21     Рекурсивный спуск - Функция не останавливается на "else return" #2
Можите подробней объяснить что выполняет функция search()?
И вот еще, вы не правильно объявляете массив у вас:
C++
1
int *array = new int;
то есть память выделяется под один элемент,а нужно
C++
1
int *array = new int[size];
, для этого сперва пользователь вводит зачение size а потом инициализируется массив.
pavlikzlo
0 / 0 / 0
Регистрация: 09.08.2014
Сообщений: 3
09.08.2014, 14:31  [ТС]     Рекурсивный спуск - Функция не останавливается на "else return" #3
За ошибку спасибо )
а функция search это поиск нужного элемента, делением пополам в упорядоченном массиве ( по другому логорифмический поиск вроде ). Берется медиана массива -> сравнивается с искомым элементом, далее в зависимости от сравнения рассматривается левая или правая часть массива, где опять таки находится медиана и так до победного.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
09.08.2014, 17:08     Рекурсивный спуск - Функция не останавливается на "else return" #4
только пишется это все нерекурсивно.

Добавлено через 5 минут
если вы пишете рекурсивно, то явно не хватает параметров в функции. хотелось бы
C++
1
search(массив, левая_граница_поиска, правая_граница_поиска, искомый элемент)
и условие выхода из рекурсии - такое же, как и в нерекурсивном бинпоиске - http://www.cyberforum.ru/cgi-bin/latex.cgi?(left \ == \ right \ - \ 1)

Добавлено через 1 минуту
советую узнать, что такое "левый" бинпоиск и что такое "правый" - бывает полезно.
pavlikzlo
0 / 0 / 0
Регистрация: 09.08.2014
Сообщений: 3
10.08.2014, 01:51  [ТС]     Рекурсивный спуск - Функция не останавливается на "else return" #5
Спасибо, но вопрос был совсем в другом, почему в моей функции не происходит выход, хотя по отладке он проходит через этот шаг.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
10.08.2014, 07:14     Рекурсивный спуск - Функция не останавливается на "else return" #6
Цитата Сообщение от salam Посмотреть сообщение
если вы пишете рекурсивно, то явно не хватает параметров в функции.
я намекнул, что программа, скорее всего, не может работать правильно. дебажить надо программу после того, как устранили очевидные логические ошибки.
Yandex
Объявления
10.08.2014, 07:14     Рекурсивный спуск - Функция не останавливается на "else return"
Ответ Создать тему
Опции темы

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