Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
DariaI
0 / 0 / 0
Регистрация: 27.12.2013
Сообщений: 3
#1

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

27.12.2013, 22:35. Просмотров 655. Ответов 11
Метки нет (Все метки)

Написала программу, которая обрабатывает строки, но одну функцию никак не могу написать. На вход подается строка, а функция должна находит в этой строке палиндромы и сосчитать их. Алгоритм вроде продумала правильно, но как только не писала код, с каждым исправлением выходит только хуже! Может кто-нибудь может подсказать мне, в чем моя ошибка?
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 пополнялась не тогда, когда одна пара букв в слове совпадет, а тогда, когда совпадут все?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.12.2013, 22:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос функция подсчета палиндромов (C++):

функция нахождения палиндромов - C++
Не могли бы помочь в написании функции,которая будет удалять палиндромы в тексте,который был введен.

Рекурсивная функция для определения палиндромов - C++
Нужно написать программу , которая с помощью рекурсивной функции определяет, является ли строка палиндромом (радар, потоп, т.е. слова...

Функция подсчета времени - C++
Добрый вечер. Мне нужно узнать время выполнения сортировки в миллисекундах.Почему то когда хочу узнать время следующим способом, выводит...

функция подсчета слов - C++
Здравствуйте! Помгите исправить ошибку в функции подсчета слов оканчивающихся на символ Пркатически все варианты пробывал но ничего...

Функция подсчета введенных чисел - C++
Функции.Вводятся целые числа, пока не будет введен 0. Подсчитать, сколько всего будет введено чисел, а также получить сумму тех чисел,...

Не работает функция подсчета элементов - C++
Задание состоит в формировании 2 массивов, вычислении среднего значения одного из этих массивов, и вычислении количества элементов, которые...

11
gazlan
3133 / 1909 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
27.12.2013, 23:46 #2
Цитата Сообщение от DariaI Посмотреть сообщение
вроде, продумала правильно
Такой кошмарный код не может быть правильным по определению.
0
ArtyrSvAn
1 / 1 / 0
Регистрация: 26.12.2013
Сообщений: 13
27.12.2013, 23:56 #3
находит отдельные слова или целые фразы?
0
DariaI
0 / 0 / 0
Регистрация: 27.12.2013
Сообщений: 3
28.12.2013, 00:00  [ТС] #4
Я говорила про алгоритм. Идея в том, чтобы найти крайний элемент перед пробелом и начать сравнивать с первым посимвольно. Если бы я считала, что код не ужасный и правильный, я бы не просила помочь. К тому же, я написала, что сама вижу, как с каждой попыткой что то исправить, он становится всё хуже и хуже. Первоначального его вида я уже и не вспомню. И никто не начинал правильно писать с рождения. Все учились и учатся.

Добавлено через 59 секунд
Цитата Сообщение от ArtyrSvAn Посмотреть сообщение
находит отдельные слова или целые фразы?
Отдельные слова. От пробела (или точки или скобок) и до другого из этих знаков...
0
uhx
60 / 60 / 6
Регистрация: 11.07.2013
Сообщений: 304
28.12.2013, 00:00 #5
Может выложите весь код?
0
gazlan
3133 / 1909 / 285
Регистрация: 27.08.2010
Сообщений: 5,132
Записей в блоге: 1
28.12.2013, 00:06 #6
Кажется, неверно понял условие.

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

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

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

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

P.S.

"все слова" - это все суффиксы данной строки (без разделителей: пробелы итп)
1
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.

"все слова" - это все суффиксы данной строки (без разделителей: пробелы итп)
Спасибо! Эта идея мне не приходила в голову, я слишком зациклилась на идее, которую пыталась воплотить. Завтра же попробую пойти этим путем.
0
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;
}
Если я правильно понял условие то можно сделать акто так
0
MrGluck
Модератор
Эксперт CЭксперт С++
7496 / 4611 / 694
Регистрация: 29.11.2010
Сообщений: 12,621
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;
}
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
28.12.2013, 16:37 #10
MrGluck, 17-19 строки логичнее представить через std::count_if, имхо.
1
MrGluck
Модератор
Эксперт CЭксперт С++
7496 / 4611 / 694
Регистрация: 29.11.2010
Сообщений: 12,621
28.12.2013, 16:40 #11
Tulosba, верно, я просто не захотел еще писать почему код у ТС не компилируется и написал под С++98 с разжовыванием ключевых моментов.
И только сейчас заметил, что все равно по привычке использовал лямбду Вот не хотел писать, руки сами все сделали.
А еще там вначале вывод был, потом понял, что в задании не вывести, а подсчитать надо и заменил.
0
Tulosba
:)
Эксперт С++
4397 / 3233 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
28.12.2013, 16:47 #12
MrGluck, ещё, я думаю, для эффективности стоит сравнивать первую половину слова с последней. Однако для наглядности (и первого приближения) сравнение полностью развернутого слова лучше.
0
28.12.2013, 16:47
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.12.2013, 16:47
Привет! Вот еще темы с ответами:

Функция подсчета максимума строки - C++
Есть массив : #include &lt;iostream&gt; using namespace std; int main(){ int const n=3; int i,j,max; int...

Функция подсчета количества символов - C++
С помощью функции вывести на экран количество символов предложения. int fun(int s=strlen()){ return s; } Жалкая попытка...

Дружественная функция подсчета площадей - C++
В общем простенькую программу для подсчета площадей написал, а вот как переделать с дружественной функцией - не совсем понял, пробовал,...

Функция подсчета времени потраченного на вычисления - C++
Нужно найти время, потраченное программой на математические исчисления. Я сделал с помощью ф-ции clock(), но она подсчитывает время от...


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

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

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