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

функция подсчета палиндромов - C++

Восстановить пароль Регистрация
 
DariaI
0 / 0 / 0
Регистрация: 27.12.2013
Сообщений: 3
27.12.2013, 22:35     функция подсчета палиндромов #1
Написала программу, которая обрабатывает строки, но одну функцию никак не могу написать. На вход подается строка, а функция должна находит в этой строке палиндромы и сосчитать их. Алгоритм вроде продумала правильно, но как только не писала код, с каждым исправлением выходит только хуже! Может кто-нибудь может подсказать мне, в чем моя ошибка?
C++
1
2
3
4
5
6
7
8
9
10
11
int palindromi(char *a)
{ int p, d, kol, j=0;
for (i=0; i<strlen(a); i=j+1)
{for (j=0; j<strlen(a); j++)
{if (a[j]==' ') p=j-i;
{for (d=0; d<=p/2; d++)
if (a[i]+d==a[j]-d) kol++
}
}
}
}
В этом последнем своем варианте поняла, что не знаю, как сделать так, чтобы переменная kol пополнялась не тогда, когда одна пара букв в слове совпадет, а тогда, когда совпадут все?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gazlan
2861 / 1809 / 272
Регистрация: 27.08.2010
Сообщений: 4,896
Записей в блоге: 1
27.12.2013, 23:46     функция подсчета палиндромов #2
Цитата Сообщение от DariaI Посмотреть сообщение
вроде, продумала правильно
Такой кошмарный код не может быть правильным по определению.
ArtyrSvAn
1 / 1 / 0
Регистрация: 26.12.2013
Сообщений: 13
27.12.2013, 23:56     функция подсчета палиндромов #3
находит отдельные слова или целые фразы?
DariaI
0 / 0 / 0
Регистрация: 27.12.2013
Сообщений: 3
28.12.2013, 00:00  [ТС]     функция подсчета палиндромов #4
Я говорила про алгоритм. Идея в том, чтобы найти крайний элемент перед пробелом и начать сравнивать с первым посимвольно. Если бы я считала, что код не ужасный и правильный, я бы не просила помочь. К тому же, я написала, что сама вижу, как с каждой попыткой что то исправить, он становится всё хуже и хуже. Первоначального его вида я уже и не вспомню. И никто не начинал правильно писать с рождения. Все учились и учатся.

Добавлено через 59 секунд
Цитата Сообщение от ArtyrSvAn Посмотреть сообщение
находит отдельные слова или целые фразы?
Отдельные слова. От пробела (или точки или скобок) и до другого из этих знаков...
uhx
 Аватар для uhx
56 / 56 / 6
Регистрация: 11.07.2013
Сообщений: 300
28.12.2013, 00:00     функция подсчета палиндромов #5
Может выложите весь код?
gazlan
2861 / 1809 / 272
Регистрация: 27.08.2010
Сообщений: 4,896
Записей в блоге: 1
28.12.2013, 00:06     функция подсчета палиндромов #6
Кажется, неверно понял условие.

Если палиндром, это слово, которое одинаково читается в обоих направлениях и границы слов заданы разделителями, то достаточно составить список всех слов и сравнить их с их же реверсными версиями. Совпадения и будут палиндромами.

Если же разделители игнорируются, то задача резко усложняется. Один из вариантов решения:
  1. найти все слова в исходной строке и занести в первый словарь
  2. реверсировать строку
  3. найти все слова в реверсированной строке и занести во второй словарь
  4. сравнить словари

Палиндромами будут слова, присутствующие в обоих словарях И находящиеся на тех же позициях исходной строки.

Если экономить, то можно обойтись и одним словарем: если на втором проходе находим слово из первого словаря, то это палиндром, но я рекомендовал бы сначала реализовать "наивный" алгоритм и понять его, а потом переходить к оптимизации.

P.S.

"все слова" - это все суффиксы данной строки (без разделителей: пробелы итп)
DariaI
0 / 0 / 0
Регистрация: 27.12.2013
Сообщений: 3
28.12.2013, 00:12  [ТС]     функция подсчета палиндромов #7
Цитата Сообщение от uhx Посмотреть сообщение
Может выложите весь код?
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
#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <cstdlib>
#include <string.h>
using namespace std;
int a, i;
int probel(char *a ) 
{
    int i, j;
    for (i=0; i<strlen(a); i++)
    if (a[i]==' '&&a[i+1]==' ')
    {
        for (j=i; j<strlen(a)+1; j++) // dlina+1 potomu chto posledniy simvol toje nado budet zamestit
        a[j]=a[j+1];
        i--;
    }
}
int skobki(char *a)
{
    int k=0;
    for (i=0; i<strlen(a); i++)
    {
        if (a[i]=='(') k=k+1;
        if (a[i]==')') k=k-1;
     }
    if (k==0) cout<<"skobki sinhronni\n";
    else cout<<"skobki assinhronni\n";
}
int palindromi(char *a)
{ int p, d, kol, j=0;
    for (i=0; i<strlen(a); i=j+1)
    {for (j=0; j<strlen(a); j++)
    {if (a[j]==' '||'.'||'('||')') p=j-i;
    {for (d=0; d<=p/2; d++)
    if a[i]+d==a[j]-d
}
    
 
int main ()
{
    char str[200]; //maksimalnoe chislo simvolov v stroke
 
    cout << "Vvedite "<<15<< "predlojeniya";
    for (int i=0; i<15; i++)
    {
        gets(str);
        probel(str);
        puts(str);
        skobki(str);
    }
}
Добавлено через 2 минуты
Цитата Сообщение от gazlan Посмотреть сообщение
Кажется, неверно понял условие.

Если палиндром, это слово, которое одинаково читается в обоих направлениях и границы слов заданы разделителями, то достаточно составить список всех слов и сравнить их с их же реверсными версиями. Совпадения и будут палиндромами.

Если же разделители игнорируются, то задача резко усложняется. Один из вариантов решения:
  1. найти все слова в исходной строке и занести в первый словарь
  2. реверсировать строку
  3. найти все слова в реверсированной строке и занести во второй словарь
  4. сравнить словари

Палиндромами будут слова, присутствующие в обоих словарях И находящиеся на тех же позициях исходной строки.

Если экономить, то можно обойтись и одним словарем: если на втором проходе находим слово из первого словаря, то это палиндром, но я рекомендовал бы сначала реализовать "наивный" алгоритм и понять его, а потом переходить к оптимизации.

P.S.

"все слова" - это все суффиксы данной строки (без разделителей: пробелы итп)
Спасибо! Эта идея мне не приходила в голову, я слишком зациклилась на идее, которую пыталась воплотить. Завтра же попробую пойти этим путем.
Hrollo
34 / 34 / 6
Регистрация: 05.11.2013
Сообщений: 147
28.12.2013, 00:32     функция подсчета палиндромов #8
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>
#include <conio.h>
#include <cstring>
#include <windows.h>
using namespace std;
 
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    char str[100];
    cout<<"Input string:";
    cin.getline(str,100);
    char *p,*razd=" ,.!?\n\t";
    int rezult = 0;
    p = strtok(str,razd);
    while(p)
    {
        int count = 0;
        int size = strlen(p);
        for(int i(0),j=size-1;i<size/2;i++,j--)
        {
            if(p[i]==p[j])
                count++;
        }
        if(size/2==count)
            rezult++;
        count=0;
        p=strtok(NULL,razd);
    }
    if(rezult==0)
        cout<<"В строке нет слов палиндромов"<<endl;
    else
        cout<<"В строке "<<rezult<<" слов палиндромов"<<endl;
    _getch();
    return 0;
}
Если я правильно понял условие то можно сделать акто так
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,416
28.12.2013, 13:15     функция подсчета палиндромов #9
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <cctype>
#include <iostream>
#include <sstream>
#include <string>
 
int main()
{
    std::string str = "Eniki, beniki - eli 1 ff vareniki. oraro";
    size_t counter = 0; // счетчик палиндромов
 
    // удаляем из строки знаки препинания
    std::remove_if(str.begin(), str.end(), [](const char x) {return ispunct(x); });
    // инициализируем ей объект для считывания
    std::istringstream ist(str);
    // пока удалось считать новое слово из него, выполняем проверку
    for (std::string word; ist >> word; )
        if (word == std::string(word.rbegin(), word.rend()))
            counter++;
 
    std::cout << "Result: " << counter << std::endl;
}
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
28.12.2013, 16:37     функция подсчета палиндромов #10
MrGluck, 17-19 строки логичнее представить через std::count_if, имхо.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,416
28.12.2013, 16:40     функция подсчета палиндромов #11
Tulosba, верно, я просто не захотел еще писать почему код у ТС не компилируется и написал под С++98 с разжовыванием ключевых моментов.
И только сейчас заметил, что все равно по привычке использовал лямбду Вот не хотел писать, руки сами все сделали.
А еще там вначале вывод был, потом понял, что в задании не вывести, а подсчитать надо и заменил.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.12.2013, 16:47     функция подсчета палиндромов
Еще ссылки по теме:

C++ функция нахождения палиндромов
Дружественная функция подсчета площадей C++
Функция подсчета введенных чисел C++

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

Или воспользуйтесь поиском по форуму:
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
28.12.2013, 16:47     функция подсчета палиндромов #12
MrGluck, ещё, я думаю, для эффективности стоит сравнивать первую половину слова с последней. Однако для наглядности (и первого приближения) сравнение полностью развернутого слова лучше.
Yandex
Объявления
28.12.2013, 16:47     функция подсчета палиндромов
Ответ Создать тему
Опции темы

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