0 / 0 / 0
Регистрация: 06.03.2015
Сообщений: 11
1

Проверка строки на симметричность через рекурсию

23.03.2015, 22:36. Показов 2252. Ответов 11
Метки нет (Все метки)

Функция проверки должна иметь только 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
#include <conio.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
bool Proverka(char *m);
 
void main()
{
    char Buf[200];
    cout << "Vvedite masiv";
    cin >> Buf;
    if (Proverka(Buf))
        cout << "Polindrom";
    else
        cout << "Ne polindrom";
    _getch();
}
bool Proverka(char *m)
{
    int StartIndex = 0;
    int EndIndex = strlen(m) - 1;
    if (StartIndex >= EndIndex)
        return true;
    if (m[StartIndex] == m[EndIndex])
        StartIndex++;
    EndIndex--;
    return Proverka(m);
    return false;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.03.2015, 22:36
Ответы с готовыми решениями:

Проверка на симметричность через стек
Дана строка чётной длины. Через стек проверить симметрична она или нет. Вот, написал. #include...

Проверка на симметричность слова
void main() { char line; printf(&quot;vvedite stroku\n&quot;); scanf(&quot;%s&quot;,line); for (int...

Проверка квадратной матрицы на симметричность
Помогите сделать программу, вот мой код: #include &quot;stdafx.h&quot; #include &quot;stdio.h&quot; #include...

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

11
Комп_Оратор)
Эксперт по математике/физике
8760 / 4502 / 605
Регистрация: 04.12.2011
Сообщений: 13,431
Записей в блоге: 16
24.03.2015, 00:44 2
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
#include<iostream>
#include<string>
using namespace std;
 
bool isSymmetricalString(char *str, bool ok, int shift)
{
if(!ok) return false;
if(str+shift > str+strlen(str)-shift)return true;
bool isOk = *(str+shift) == *(str+strlen(str)-shift-1);
 
//эти 2 строки я написал, чтобы Вы поняли как это работает
//когда разберётесь закомментируйте их)
cout<< *(str+shift)<<" "<< *(str+strlen(str)-shift-1)<<endl;
cout<<"isOk "<<isOk<<endl;
 
if(!isOk)return false;
return isSymmetricalString(str, isOk, shift+1);
}
char *toStrOrNotToStr(bool toStr){
if(toStr)return "is symmetrical";
return "is not symmetrical";
}
 
int main()
{
char *nonSymmetrStr="NonSymmetrStr";    
char *SymmetrStr="SymmetrStrrtSrtemmyS";
char *SymmStr="SymmStrtSmmyS";
char *messBeg = "The string ";
cout<<messBeg<<" "<<nonSymmetrStr<<" "<<toStrOrNotToStr(isSymmetricalString(nonSymmetrStr, true, 0))<<endl;
cout<<messBeg<<" "<<SymmetrStr<<" "<<toStrOrNotToStr(isSymmetricalString(SymmetrStr, true, 0))<<endl;
cout<<messBeg<<" "<<SymmStr<<" "<<toStrOrNotToStr(isSymmetricalString(SymmStr, true, 0))<<endl;
system("pause");
return 0;
}
0
4814 / 2275 / 287
Регистрация: 01.03.2013
Сообщений: 5,933
Записей в блоге: 26
24.03.2015, 04:32 3
Вот только
Цитата Сообщение от Annushkaa Посмотреть сообщение
Функция проверки должна иметь только 1 параметр
Хотя не сказано какой, может можно сам стринг плюсовый со всеми методами или структуру со 100500 полями Но это не так интересно, как "разрушающий контроль" с одним честным указателем:
C++
1
2
3
4
5
6
7
8
9
10
11
12
char *rp (char *p) { return (*p) ? rp(p+1) : p-1; }
bool isp (char *p) { char *r=rp(p), a=*p, b=*r; *r=0;
                     return (p>r) ? true : (a!=b) ? false : isp (p+1); }
void tst (char *p) { cout<<p<<" WAS palindrome: "; cout<<isp(p)<<endl; }
 
int _tmain(int argc, _TCHAR* argv[]) {
    char a[]="NonSymmetrStr";
    char b[]="SymmetrStrrtSrtemmyS";
    char c[]="SymmStrtSmmyS";
    tst(a); tst(b); tst(c);
    system("pause"); return 0;
}
1
Форумчанин
Эксперт CЭксперт С++
8191 / 5041 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
24.03.2015, 10:53 4
C++
1
2
3
4
5
6
7
8
9
bool check(const std::string &str)
{
    const auto len = str.length();
    if (len == 0 || len == 1)
        return true;
    if (str.back() == str.front())
        return check(str.substr(1, len - 2));
    return false;
}
Добавлено через 9 минут
Задача явно требует compile-time решения.
Пока так:
C++
1
2
3
4
5
6
constexpr bool check(const std::string &str, const size_t len)
{
    return len == 0 || len == 1 ? true :
        str.back() == str.front() ?
        check(str.substr(1, len - 2), len - 2) : false;
}
Буду думать дальше

Добавлено через 40 минут
C++
1
2
3
4
5
6
7
8
9
10
11
constexpr const char* last(const char *c)
{
    return *(c+1) == '\0' ? c : last(c+1);
}
 
constexpr bool check(const char *beg, const char *end = nullptr)
{
    return *beg == '\0' || *(beg+1) == '\0' ? true :
        *beg == *(end = (end ? end : last(beg))) ?
        check(beg+1, end-1) : false;
}
Добавлено через 7 минут
Итог:
C++
1
2
3
4
5
6
7
8
9
constexpr const char* last(const char *c)
{
    return *(c+1) == '\0' ? c : last(c+1);
}
 
constexpr bool check(const char *beg, const char *end = nullptr)
{
    return *beg == '\0' || *(beg+1) == '\0' || (*beg == *(end = (end ? end : last(beg))) && check(beg+1, end-1));
}
1
Комп_Оратор)
Эксперт по математике/физике
8760 / 4502 / 605
Регистрация: 04.12.2011
Сообщений: 13,431
Записей в блоге: 16
24.03.2015, 14:35 5
Цитата Сообщение от _Ivana Посмотреть сообщение
Но это не так интересно, как "разрушающий контроль"
Я решил поразмыслить над функцией которая проверяя не модифицирует результат. Ничего смешного не получилось. Времени уже нет поэтому положу "горбыль" как есть:
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
#include<iostream>
#include<exception>
using namespace std;
 
int &isSymmetricalString(const char *str)
{
    static int retVal=2;
    if(str==0){     
    return retVal=2;
    }
    
    int len = strlen(str);  
    if(len<2) return retVal=1;  
char *copyStr = 0;
    if(retVal!=2){
if(*str != *(str+len-1)) return retVal=0;
copyStr = new char[len-1];
retVal=1;
for(int i=0; i < len-2; i++) *(copyStr+i) = *(str+i+1);
*(copyStr+len-2)='\0';
delete []str;
    }else {
        if(*str != *(str+len-1)) return retVal=0;
copyStr = new char[len-1];
retVal=1;
for(int i=0; i < len-2; i++) *(copyStr+i) = *(str+i+1);
*(copyStr+len-2)='\0';
return isSymmetricalString(copyStr);
    }
return retVal=isSymmetricalString(copyStr);
}
 
void output(char *str)
{
    isSymmetricalString(0);
    int a=isSymmetricalString(str);
if(a==1)cout<<str<<" is symmetrical"<<endl;
else cout<<str<<" is not symmetrical"<<endl;
}
 
int main()
{
char str[]="ABBA";
char Str[]="ABBABA";
char Sstr[]="ABRBA";
output(str);
output(Str);
output(Sstr);
system("pause");
return 0;
}
И глядя на условие хочется спросить, а кто это отпускает через лес к бабушке таких девочек. С корзинкой пирожков, персиков, бананов и гранатов. Противотанковых, имхо.
0
4814 / 2275 / 287
Регистрация: 01.03.2013
Сообщений: 5,933
Записей в блоге: 26
24.03.2015, 14:48 6
MrGluck, все хорошо, но с двумя параметрами нарушается условие, а с передачей стринга - читерство
IGPIGP, можно имхо проще - вызвать для моей разрушающей функции обертку, которая принимает указатель на строку, создает внутри себя ее локальную (не статическую) копию и вызывает разрушающий контроль со ссылкой на копию. Все чисто - у нас 3 функции, каждая принимает единственный указатель, исходная строка не разрушается Но да, решение через бананы/пирожки/гранаты
0
Комп_Оратор)
Эксперт по математике/физике
8760 / 4502 / 605
Регистрация: 04.12.2011
Сообщений: 13,431
Записей в блоге: 16
24.03.2015, 14:57 7
Цитата Сообщение от _Ivana Посмотреть сообщение
через бананы
Именно. Весенний авитаминоз у старушек.

Добавлено через 3 минуты
Цитата Сообщение от _Ivana Посмотреть сообщение
функции обертку, которая принимает указатель на строку, создает внутри себя ее локальную (не статическую) копию и вызывает разрушающий контроль со ссылкой на копию.
Если обёртка не рекурсивна то порвём условие, а если рекурсивна то стек... Впрочем чёрт с ними, главное чтобы серый волк гранату не скушал. Или что-то в этом роде.
0
4814 / 2275 / 287
Регистрация: 01.03.2013
Сообщений: 5,933
Записей в блоге: 26
24.03.2015, 15:08 8
Кстати, с функцией-оберткой и созданием локальной копии строки у нас появляется возможность проверять таким образом даже константные строки, которые запрещены для записи и изменения. Так что имхо со всех сторон в условиях задачи это самое трушное решение И задачка получилась неплохая, если трактовать условие подобным образом

Добавлено через 3 минуты
Цитата Сообщение от IGPIGP Посмотреть сообщение
Если обёртка не рекурсивна то порвём условие
Ну тут вопрос терминов - сама "функция проверки" можно сказать что рекурсивная, а нерекурсивна обертка Хотя согласен, тонкий момент. Но для обхода этого можно в обертку засунуть какую-нибудь ненужную рекурсию типа предварительного расчета факториала, чтобы она вызывала сама себя несколько раз, а при финальном вызове вызывала рекурсивный же разрушающий контроль, вызывающий рекурсивный же поиск нового указателя на конец обрезанной строки

Добавлено через 5 минут
ЗЫ возникла идея как это выпендрежно реализовать, но сейчас на работе - ночью дома напишу, ждите кота Будет путь через лес и обратно с ответом
0
Форумчанин
Эксперт CЭксперт С++
8191 / 5041 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
24.03.2015, 15:30 9
Цитата Сообщение от _Ivana Посмотреть сообщение
Кстати, с функцией-оберткой и созданием локальной копии строки у нас появляется возможность проверять таким образом даже константные строки, которые запрещены для записи и изменения. Так что имхо со всех сторон в условиях задачи это самое трушное решение
Там смотри на код у меня в конце, там как раз оно и есть. В CT.

Добавлено через 21 секунду
C++
1
2
3
4
5
6
7
8
9
constexpr const char* last(const char *c)
{
    return *(c+1) == '\0' ? c : last(c+1);
}
 
constexpr bool check(const char *beg, const char *end = nullptr)
{
    return *beg == '\0' || *(beg+1) == '\0' || (*beg == *(end = (end ? end : last(beg))) && check(beg+1, end-1));
}
Добавлено через 39 секунд
Вызов не требует второго параметра.
C++
1
check("abba")
0
4814 / 2275 / 287
Регистрация: 01.03.2013
Сообщений: 5,933
Записей в блоге: 26
24.03.2015, 15:38 10
При вызове не требует, потому что указано его значение по умолчанию, но формально то функция "имеет 2 параметра", и вызывается внутри с двумя А "чистое" решение задачи подразумевает только один параметр и безо всяких внешних растяжек в виде статиков и глобальных переменных.
0
Форумчанин
Эксперт CЭксперт С++
8191 / 5041 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
24.03.2015, 15:47 11
Цитата Сообщение от _Ivana Посмотреть сообщение
При вызове не требует, потому что указано его значение по умолчанию, но формально то функция "имеет 2 параметра", и вызывается внутри с двумя А "чистое" решение задачи подразумевает только один параметр и безо всяких внешних растяжек в виде статиков и глобальных переменных.
Да ну. Пусть будет так, если важна эта формальность:
C++
1
2
3
4
constexpr bool check2(const char *p)
{
    return check(p);
}
0
Комп_Оратор)
Эксперт по математике/физике
8760 / 4502 / 605
Регистрация: 04.12.2011
Сообщений: 13,431
Записей в блоге: 16
24.03.2015, 18:58 12
Цитата Сообщение от _Ivana Посмотреть сообщение
Хотя согласен, тонкий момент.
Дело не в том, что логика подобных задачек противоестественна, а скорее в том, что сам ход мысли создателей не здоров. Такие вещи со стонами обдумывают старые матёрые педагоги при виде как юных девственниц так и обычных пирожков.
Вот почему сочетание красоты и честности при решении невозможно. Тут альтернатива - или-или. Функция со статической переменной рекурсивна, имеет один параметр, но вызывается в 2 приёма. Причем, это "но" нигде не ограничено, а по сему всё честно. Эстетика, как уже говорилось не для обсуждения.
Ну а если полукавить то:
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
#include<iostream>
using namespace std;
bool isSymmetricalString(char *str=0)
{
if(!str)return true;//первая нерекурсивная ветвь)
char *beg=str;
char *end=strlen(str)-1 +str;
while(end>beg)//вторая нерекурсивная ветвь))
{
if(*beg != *end)return false;
beg++;
end--;
}
return isSymmetricalString();//рекурсия!
 
}
 
char *toStrOrNotToStr(bool toStr){
if(toStr)return "is symmetrical";
return "is not symmetrical";
}
 
int main()
{
char *nonSymmetrStr="NonSymmetrStr";    
char *SymmetrStr="SymmetrStrrtSrtemmyS";
char *SymmStr="SymmStrtSmmyS";
char *messBeg = "The string ";
cout<<messBeg<<" "<<nonSymmetrStr<<" "<<toStrOrNotToStr(isSymmetricalString(nonSymmetrStr))<<endl;
cout<<messBeg<<" "<<SymmetrStr<<" "<<toStrOrNotToStr(isSymmetricalString(SymmetrStr))<<endl;
cout<<messBeg<<" "<<SymmStr<<" "<<toStrOrNotToStr(isSymmetricalString(SymmStr))<<endl;
 
system("pause");
return 0;
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.03.2015, 18:58
Помогаю со студенческими работами здесь

Не работает проверка слова на симметричность
Задача такова: Дана непустая последовательность слов (не более 50). в каждом слове не более 8...

Проверка на симметричность относительно главной диагонали
Дан массив целых чисел размера n x n, элементами которого являются 0 и 1. Проверить, является ли...

симметричность строки на С++
Описать рекурсивную функцию, проверяющую, является ли симметричной часть строки s, начинающаяся i-м...

Проверка строки матрицы на симметричность
Как проверить строку матрицы на симметричность, если строка симметрична то в вектор b занести 1...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru