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

Задачи на рекурсию - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.68
ninja1
5 / 0 / 1
Регистрация: 11.06.2012
Сообщений: 6
11.06.2012, 08:07     Задачи на рекурсию #1
Здорова господа!
У меня щас появилась проблема.
Решаю задачки на рекурсию от первая задача //палиндромы//создать функцию testPalindrome которая возвращает 1, если хранящаяся в массиве строка-палиндром, и 0 в противном случаю
вот код:
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
//ГЏГ*ëèГ*äðîìû
#include <iostream>
using std::cout;
using std::endl;
 
int testPalindrome(int[],int,int);
 
int main()
{
    int const arraySize=7;
    int mas[arraySize]={1,2,3,4,2,2,1};
    cout <<testPalindrome(mas,arraySize,0)<<endl;
    
    return 0;   
}
 
int testPalindrome(int mas[],int arraySize,int k)
{
    if((arraySize%2)==0)
    {
        cout <<0<<" ";
        return 0;
    }
    
    int k2=0;
    k2=arraySize-(k+1);
    
    if(k2<=k)
    {
        cout <<1<<" ";
        return 1;
    }
    
    cout <<"mas["<<k<<"]= "<<mas[k]<<" mas["<<k2<<"]= "<<mas[k2]<<endl;
    
    if(mas[k]!=mas[k2])
    {
        cout <<0<<" ";
        return 0;
    }
    else
        testPalindrome(mas,arraySize,k+1);   
 
}
В данном случае массив не палиндром но функция каким то макаром возвращает не 0 а число 2293512
0 прописываетса cout том программа идет правильно в чем может быть проблема

И еще одна задачка //линейный поиск// создаем рекурсивную функцию linearSeach ищет ключ поиска если найден то возвращаем индекс массива в противном случае -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
//ËèГ*ГҐГ©Г*ûé ïîèñê
#include <iostream>
using std::cout;
using std::endl;
 
int linearSeach(int[],int,int,int);
 
int main()
{
    int const arraySize=5;
    int mas[]={3,5,6,5,3};
    cout <<linearSeach(mas,arraySize,2,0);
    
    return 0;   
}
 
int linearSeach(int mas[],int arraySize, int key, int k)
{
    if(mas[k]==key&&k<arraySize)
    {
        cout <<k<<" key= "<<key<<endl;
        return k;  //âîçâðГ*ГІГЁГІГј ïîçèöèþ êëþ÷Г*
    }
    else if(k==arraySize)
    {
        cout <<-1;
        return -1;  
    }
    else
        linearSeach(mas,arraySize,key,k+1); 
}
Программа должна вернуть -1 так как значения 2 нет в массиве, а она возвращает 16384-непонятное число (откуда оно взялось) . cout том прописываю -1 программа работает правильно тока возвращает неправильно что одна что другая.
В чем может быть проблема?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.06.2012, 08:07     Задачи на рекурсию
Посмотрите здесь:

Постигая рекурсию. C++
C++ Программа на рекурсию
Задачка на рекурсию... C++
Вставить рекурсию C++
Задача на рекурсию C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Кот Ангенс
 Аватар для Кот Ангенс
317 / 267 / 37
Регистрация: 24.05.2012
Сообщений: 629
11.06.2012, 08:51     Задачи на рекурсию #2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool _testPalindrome(char* s, char* s2) {
    if (s >= s2)
        return true;
    if (*s != *s2)
        return false;
    return testPalindrome(s + 1, s2 - 1);
}
 
inline bool testPalindrome(char* s, unsigned n) {
    return _testPalindrome(s, s + n - 1);
}
 
int linearSearch(const int a[ ], int key, unsigned n) {
    if (!n)
        return -1;
    if (a[n - 1] == key)
        return n - 1;
    return linearSearch(a, key, n - 1);
}
ninja1
5 / 0 / 1
Регистрация: 11.06.2012
Сообщений: 6
11.06.2012, 10:06  [ТС]     Задачи на рекурсию #3
Да я написал функцию мне ни понятно чо она не 0 возвращает а число 2293512 (откуда оно взялось)
выводит cout-том 0 а вместо return 0; выводиться число. В чом проблема?

Кто может проверить мою программу может ана тока у меня так работает неправильно?
Catstail
Модератор
 Аватар для Catstail
21430 / 10215 / 1664
Регистрация: 12.02.2012
Сообщений: 17,086
11.06.2012, 10:22     Задачи на рекурсию #4
Загрузил твой код в VC++ (6) - он работает верно...
ninja1
5 / 0 / 1
Регистрация: 11.06.2012
Сообщений: 6
11.06.2012, 11:00  [ТС]     Задачи на рекурсию #5
А у меня неверно
попробуй без cout (просто может ты принял 0 выводится cout том за 0 шо должен выводится return)
вот такой код

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
//Палиндромы
#include <iostream>
using std::cout;
using std::endl;
 
int testPalindrome(int[],int,int);
 
int main()
{
    int const arraySize=7;
    int mas[arraySize]={1,2,3,4,2,2,1};
    cout <<testPalindrome(mas,arraySize,0)<<endl;
    
    return 0;   
}
 
int testPalindrome(int mas[],int arraySize,int k)
{
    if((arraySize%2)==0)
    {
        return 0;
    }
    
    int k2=0;
    k2=arraySize-(k+1);
    
    if(k2<=k)
    {
        return 1;
    }
    
    cout <<"mas["<<k<<"]= "<<mas[k]<<" mas["<<k2<<"]= "<<mas[k2]<<endl;
    
    if(mas[k]!=mas[k2])
    {
        return 0;
    }
    else
        testPalindrome(mas,arraySize,k+1);   
 
}
От без cout попробуй выведется 0 или число левое ?
Кот Ангенс
 Аватар для Кот Ангенс
317 / 267 / 37
Регистрация: 24.05.2012
Сообщений: 629
11.06.2012, 11:29     Задачи на рекурсию #6
Цитата Сообщение от ninja1 Посмотреть сообщение
Да я написал функцию, мне не понятно, что она не 0 возвращает, а число 2293512 (откуда оно взялось)
Значит, Вы написали функцию неправильно.
К тому же, у Вас функции принимают 3 и 4 аргумента, а у меня - 2 и 3, что означает меньший расход памяти.
ninja1
5 / 0 / 1
Регистрация: 11.06.2012
Сообщений: 6
11.06.2012, 11:40  [ТС]     Задачи на рекурсию #7
Значит, Вы написали функцию неправильно.
К тому же, у Вас функции принимают 3 и 4 аргумента, а у меня - 2 и 3, что означает меньший расход памяти.
Да так где же ошибка?
А то что 4 аргумента меня как-то несильно волнует только б работало.

Кстати вот еще одну задачку решил та же проблема.
Поиск наименьшего значения в массиве, функция 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
37
38
//Ïîèñê Г*Г*èìåГ*ГјГёГҐГЈГ® Г§Г*Г*Г·ГҐГ*ГЁГї Гў Г¬Г*Г±Г±ГЁГўГҐ
#include <iostream>
using std::cout;
using std::endl;
 
int recursiveMinimum(int[],int,int,int);
 
int main()
{
    int const arraySize=7;
    int mas[7]={3,4,6,7,1,43,4};
    cout <<recursiveMinimum(mas,arraySize,0,99999999);
    
    return 0;   
}
 
int recursiveMinimum(int mas[],int arraySize,int k,int min)
{
    cout <<"1111"<<endl;
    cout <<"min= "<<min<<endl;
    if(arraySize==1)
        return 0;
        
    if(k==0)
        min=mas[k];
    else
    {
        if(min>mas[k])
            min=mas[k];   
    }   
    if(k<arraySize-1)
        recursiveMinimum(mas,arraySize,k+1,min);
    else
    {
        cout <<endl<<min<<endl<<endl;//минимум находит правильно
        return min;//а здесь вместо min возвращается левое число нипонятно откуда взявшееся-16384
    }
}
Опять находит минимум правильно но возвращает 16384.
Должно вернутся 1 а возвращается 16384.
Где ошибка подскажите господа

Почему когда cout том вывожу выводит 1 то есть правильно , а когда return min выводит 16385 неправильно ?
Гуру объясните новичку где ошибка?

Компилятор Dev-C++ , программы запускаю в командной строке.
LK
11.06.2012, 11:54
  #8
 Комментарий модератора 
Правила
3.15. Запрещено создавать темы с множеством вопросов во всех разделах, кроме разделов платных услуг. Один вопрос - одна тема.
Или продолжаем/завершаем обсуждение вопроса №1 - //палиндромы//, или тема будет закрыта.
ninja1
5 / 0 / 1
Регистрация: 11.06.2012
Сообщений: 6
11.06.2012, 12:06  [ТС]     Задачи на рекурсию #9
Цитата Сообщение от LK Посмотреть сообщение
ПравилаИли продолжаем/завершаем обсуждение вопроса №1 - //палиндромы//, или тема будет закрыта.
Продолжаем палиндромы
Кот Ангенс
 Аватар для Кот Ангенс
317 / 267 / 37
Регистрация: 24.05.2012
Сообщений: 629
11.06.2012, 12:15     Задачи на рекурсию #10
C++
1
2
3
4
5
6
7
8
9
10
11
int _min_recursive(const int* a, unsigned n, int min) {
    if (!n)
        return min;
    if (*a < min)
        min = *a;
    return _min_recursive(a + 1, n - 1, min);
}
 
inline int min_recursive(const int a[ ], unsigned n) {
    return _min_recursive(a, n, a[0]);
}
Цитата Сообщение от ninja1 Посмотреть сообщение
recursiveMinimum(mas,arraySize,k+1,min);
Нужно возвращать рекурсивный вызов.

Добавлено через 1 минуту
Цитата Сообщение от ninja1 Посмотреть сообщение
if((arraySize%2)==0)
{
return 0;
}
Вы хотите сказать, что строка "1221" не является палиндромом, потому что у нее четная длина?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.06.2012, 12:29     Задачи на рекурсию
Еще ссылки по теме:

Задача на рекурсию C++
Реализовать рекурсию C++
C++ Программу, которая реализует решение задачи, через рекурсию, так и итеративной функции

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

Или воспользуйтесь поиском по форуму:
ninja1
5 / 0 / 1
Регистрация: 11.06.2012
Сообщений: 6
11.06.2012, 12:29  [ТС]     Задачи на рекурсию #11
Нужно возвращать рекурсивный вызов.
ОО и все задачки начали работать правильно. Спасибо за помощь!

Вы хотите сказать, что строка "1221" не является палиндромом, потому что у нее четная длина?
Да я как то не подумал на скорую руку решаю хо быстрее с++ до конца изучить (на мелочах неохота зацикливаться).
Yandex
Объявления
11.06.2012, 12:29     Задачи на рекурсию
Ответ Создать тему
Опции темы

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