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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 16, средняя оценка - 4.75
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
#1

И снова палиндром - C++

07.09.2011, 21:24. Просмотров 2405. Ответов 20
Метки нет (Все метки)

Здравствуйте! У кого какие идеи на счет решения этой задачи?

Палиндром — это строка, которая читается одинаково как справа налево, так и слева направо.
Во входном файле записан набор больших латинских букв (не обязательно различных). Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется написать программу, которая из данных букв по указанным правилам составит палиндром наибольшей длины, а если таких палиндромов несколько, то первый в алфавитном порядке.

Я думаю так, надо с начало отсортировать символьный массив, затем посчитать сколько рас встречается каждый символ в массиве. Если символ встречается четное количество рас, то делим его по палам, часть в начало, часть в конец. Если символ встречается один рас и он еще встречается в алфавите раньше то мы его отправляем в середину.

на данном моменте проблема с подсчетом количества символов в символьном массиве.

Добавлено через 2 минуты
пример:
вход:QAZQAZ
выход: AQZZQA
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.09.2011, 21:24
Здравствуйте! Я подобрал для вас темы с ответами на вопрос И снова палиндром (C++):

Как сделать чтобы таймер дойдя до 0 стартовал снова и снова? - C++
Здравствуйте :) Как сделать чтобы таймер дойдя до 0 стартовал снова и снова? TimerSec = 59; TimerMin = 6; for(int i = TimerSec;...

Палиндром 2 С++ - C++
Задание: Напишите программу проверки, является ли введенное число палиндромом. Организуйте многократный ввод чисел для проверки, признак...

Палиндром - C++
Нужна программа которая распознает палиндром строчка, слово или нет ! Help ! 12321 ; abcba ;абв гв ба ; И мал Иван, а лупил у лип улана...

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

Палиндром с++ - C++
Помогите, пожалуйста, написать программу: Найдите самый большой палиндром, образованный в произведение двух трехзначных чисел.

Палиндром - C++
разработать программу которая определяет является ли данный текст палиндромом в среде C++

20
ValeryLaptev
Эксперт С++
1045 / 824 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
07.09.2011, 21:49 #2
jambas92, используй стандартный string. Или надо ОБЯЗАТЕЛЬНО использовать массив char?
Для char есть функция strlen()
1
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
07.09.2011, 21:55 #3
если длина строки сильно больше набора используемых символов, то я бы предложил не сортировать всю строку. проще за один обход заполнить встречаемыми символами список, который будет сортироваться при добавлении элементов и иметь счетчик повторений. и уже на основе обхода этого спсика делать палиндром: если символ встретился 1 раз, то пропустить, если 2n раз - вставить n раз, если 2n+1 раз, то вставить опять же n раз. вторую половину можно получить либо обратным обходом, либо придумать что-то элегантнее.

а если набор символов велик, то вставка и обход списка символов займет ничуть ен меньше времени, чем сортировка строки и ее однократный обход. тогда проще действовать, как ты предложил.
1
OstapBender
584 / 523 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
07.09.2011, 22:00 #4
можно проще - из каждого прочитанного слова составить ассоциативный массив (да-да map).
в него записать все буквы (ключ - буква, значение - скока раз встречается в слове).
все значения в map-e должны быть четными, допускается только 1 нечетное значение (серединка )
- если это так - то палиндром можно сделать .
1
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
07.09.2011, 22:07  [ТС] #5
как видите решить эту задачу можно несколькими путями, но сложность в реализации...
ValeryLaptev, можно использовать все что угодно
0
OstapBender
584 / 523 / 35
Регистрация: 22.03.2011
Сообщений: 1,585
07.09.2011, 22:22 #6
ну как-то так:
...
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
bool canBePoly(const std::string& s) {
        
    std::map<char,size_t> data;
    bool contain_odd=false;
 
    for (size_t i=0; i<s.size(); i++)
        data[s[i]]++;
 
    for (std::map<char,size_t>::iterator it=data.begin(); it!=data.end(); it++) {
        if ((it->second)&1) {
            if (contain_odd) 
                return false;
            else 
                contain_odd=true;
        }
    }
 
    return true;
 
}
 
 
int main(int argc, char* argv[])
{
    std::ifstream ifs("f.txt");
    std::string s;
    
    while (ifs >> s) {
        std::cout << s << ": ";
        if (canBePoly(s)) {
            std::cout << "Yep\n";
        } else {
            std::cout << "Nope\n";
        }
    }
    std::cin.get();
    return 0;
}
1
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
07.09.2011, 22:27  [ТС] #7
OstapBender, честно сказать как то не понятно)) я видел решение этой задачи, тольк на паскале. как та тамвсе было легко и просто
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
07.09.2011, 22:30 #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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/////////////////////////////////////////////////////////////////////////////////////////
// Палиндром — это строка, которая читается одинаково как справа налево, так и слева направо.
// Во входном файле записан набор больших латинских букв (не обязательно различных). 
// Разрешается переставлять буквы, а также удалять некоторые буквы. Требуется написать 
// программу, которая из данных букв по указанным правилам составит палиндром наибольшей 
// длины, а если таких палиндромов несколько, то первый в алфавитном порядке.
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <set>
#include <string>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string          T_str;
typedef std::multiset<char>  T_symb_multiset;
/////////////////////////////////////////////////////////////////////////////////////////
const char  SYMB_FRONT  = 'A';
const char  SYMB_BACK   = 'Z';
/////////////////////////////////////////////////////////////////////////////////////////
struct  T_gen_rand_A_Z
{
    char operator() ()
    {
        return  rand() % (SYMB_BACK - SYMB_FRONT + 1) + SYMB_FRONT;
    }
};
/////////////////////////////////////////////////////////////////////////////////////////
T_str  make_palyndrom(const T_str&  s)
{
    T_symb_multiset  symb_multiset( s.begin(), s.end() );
    T_str            palynlrom;
    char             symb_centr = 0;
 
    for(char  symb = SYMB_FRONT; symb <= SYMB_BACK; ++symb)
    {
        int  n = symb_multiset.count(symb);        
        if(    symb_centr  == 0 
            && n % 2       == 1 )
        {
            symb_centr = symb;
        }
 
        palynlrom += T_str(n / 2, symb);    
    }
    T_str  rev_palyndrom = palynlrom;
    std::reverse( rev_palyndrom.begin(), rev_palyndrom.end() );
    if(symb_centr)
    {
        palynlrom += symb_centr;
    }
    return  palynlrom += rev_palyndrom;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    srand(unsigned(time(0)));
    const int LINE_LEN = 50;
    T_str  s;
    std::generate_n
        (
            std::back_inserter(s),
            LINE_LEN,
            T_gen_rand_A_Z()
        );
 
    std::cout << "Исходная строка: "
              << std::endl
              << s
              << std::endl;
    
    std::sort( s.begin(), s.end() );
    std::cout << std::endl
              << "Исходная строка отсортированная: "
              << std::endl
              << s
              << std::endl;
 
    T_str  palyndrom = make_palyndrom(s);
    std::cout << std::endl
              << "Палиндром, полученный из букв этой строки:"
              << std::endl
              << palyndrom
              << std::endl;    
}
0
grizlik78
Эксперт С++
1970 / 1463 / 122
Регистрация: 29.05.2011
Сообщений: 3,029
07.09.2011, 22:32 #9
А у меня так-себе вариант. Использует только буквенные символы из ASCII.
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
#include <stdio.h>
#include <ctype.h>
 
#define NUM_CHARS 128
 
int main(void)
{
    int i, cnt[NUM_CHARS];
    char middle = '\0';
    unsigned char buf[256];
 
    printf("Input chars: ");
    scanf("%255s", buf);
 
    for (i = 0; i < NUM_CHARS; ++i)
        cnt[i] = 0;
 
    for (i = 0; buf[i] != '\0'; ++i)
        if (isalpha(buf[i]) && buf[i] < NUM_CHARS)
            ++cnt[buf[i]];
 
    for (i = NUM_CHARS; i-- > 0; )
    {
        if (cnt[i] & 1)
            middle = i;
        cnt[i] /= 2;
    }
 
    printf("First max-length palindrome: ");
    for (i = 0; i < NUM_CHARS; ++i)
    {
        int rep = cnt[i];
        while (rep-- > 0)
            printf("%c", i);
    }
    if (middle != '\0')
        printf("%c", middle);
 
    for (i = NUM_CHARS; i-- > 0; )
    {
        int rep = cnt[i];
        while (rep-- > 0)
            printf("%c", i);
    }
    printf("\n");
 
    return 0;
}
По-моему работает по заданию.
0
x1Mike7x
218 / 131 / 6
Регистрация: 06.11.2010
Сообщений: 234
07.09.2011, 22:35 #10
Примерно такой алгоритм:
- считываем строку всех возможных символов ( в примере - латинские в верхнем регистре )
- в массив-счётчик закидываем количество каждой буквы
- бежим по массиву-счётчику, для каждой буквы закидываем в две строковые переменные ( начало и конец палиндрома ) по 1 символу, которые соответствует поточному символу
- если остался еще 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
string S, Start = "", End = "", Centr = "", R = "";
unsigned Count[26] = {};
 
cin >> S;
for ( unsigned i = 0; i < S.size(); ++i )
    ++Count[ S[i] - 'A' ];
 
for ( unsigned i = 0; i < 26; ++i )
{
    for ( unsigned k = Count[i]; k > 1; k -= 2 )
    {
        Start += i + 'A';
        End += i + 'A';
    }
    if ( Count[i] && Centr.empty() )
        Centr += i + 'A';
}
 
R = Start + Centr;
for ( unsigned i = End.size() - 1; i + 1; --i )
    R += End[i];
 
cout << R << endl;
0
silent_1991
Эксперт С++
4989 / 3046 / 149
Регистрация: 11.11.2009
Сообщений: 7,028
Завершенные тесты: 1
07.09.2011, 22:36 #11
Ещё вариант:

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
#include <iostream>
#include <string>
#include <algorithm>
 
std::string get_palindrome(std::string letters)
{
    typedef std::string str_t;
    typedef std::string::size_type str_size_t;
    typedef std::string::value_type str_value_t;
 
    std::sort(letters.begin(), letters.end());
 
    str_t palindrome;
    str_value_t middle;
    bool has_middle = false;
 
    for (str_size_t i = 0; i < letters.length(); ++i)
    {
        size_t cnt = std::count(letters.begin(), letters.end(), letters[i]);
 
        if ((cnt & 1) == 1)
        {
            if (!has_middle)
            {
                middle = letters[i];
                has_middle = true;
            }
        }
 
        palindrome += std::string(cnt / 2, letters[i]);
 
        i += cnt - 1;
    }
 
    return palindrome + (has_middle ? std::string(1, middle) : "") + std::string(palindrome.rbegin(), palindrome.rend());
}
 
int main()
{
    std::string letters;
 
    std::cout << "Enter letters: ";
    std::cin >> letters;
 
    std::cout << "Palindrome: " << get_palindrome(letters) << std::endl;
 
    return 0;
}
Добавлено через 1 минуту

Не по теме:

Хм... Пока писал, куча вариантов появилась, так что возможно, я повторяю кого-нибудь. Проверять лень))

1
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
07.09.2011, 22:54  [ТС] #12
silent_1991Точное решение задачи! если не сложно можешь свою функцию про комментировать?
0
silent_1991
Эксперт С++
4989 / 3046 / 149
Регистрация: 11.11.2009
Сообщений: 7,028
Завершенные тесты: 1
08.09.2011, 14:58 #13
jambas92, решение "в лоб" на самом деле... Думаю, можно было и красивее эту задачу решить. Вот с комментариями:

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
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <string>
#include <algorithm>
 
// Функция из строки символов letters составляет максимальный по длине и первый
// по алфавиту палиндром
std::string get_palindrome(std::string letters)
{
    // Для удобства переопределяем имена типов
    typedef std::string str_t;
    typedef std::string::size_type str_size_t;
    typedef std::string::value_type str_value_t;
 
    // Сортируем строку символов
    std::sort(letters.begin(), letters.end());
 
    // Результирующая строка-палиндром
    str_t palindrome;
    // Средний элемент
    str_value_t middle;
    // Наличие среднего элемента
    bool has_middle = false;
 
    // В цикле идём по строке символов
    for (str_size_t i = 0; i < letters.length(); ++i)
    {
        // Считаем количество входнеий очередного символа в строке символов
        size_t cnt = std::count(letters.begin(), letters.end(), letters[i]);
 
        // Если это количество нечётно
        if ((cnt & 1) == 1)
        {
            // Если средний символ ещё не определён
            if (!has_middle)
            {
                // Определяем средний символ
                middle = letters[i];
                has_middle = true;
            }
        }
 
        // К результирующему палиндрому добавляем cnt / 2 символов
        palindrome += std::string(cnt / 2, letters[i]);
 
        // В строке символов пропускаем все одинаковые символы
        i += cnt - 1;
    }
 
    // Возвращаем в качестве результата вычисленную в цикле половинку палиндрома
    // плюс середину (если она есть) плюс обращённую половину вычисленного
    // палиндрома
     return palindrome + (has_middle ? std::string(1, middle) : "") + std::string(palindrome.rbegin(), palindrome.rend());
}
 
int main()
{
    std::string letters;
 
    std::cout << "Enter letters: ";
    std::cin >> letters;
 
    std::cout << "Palindrome: " << get_palindrome(letters) << std::endl;
 
    return 0;
}
1
AkA_ZadR
0 / 0 / 0
Регистрация: 07.09.2011
Сообщений: 8
08.09.2011, 18:12 #14
разве нет решения проще вы пишите долгим способом когда я катев сдавал решения были проще
0
jambas92
58 / 57 / 3
Регистрация: 18.11.2010
Сообщений: 315
08.09.2011, 19:55  [ТС] #15
AkA_ZadR, жду твоего решения))
0
08.09.2011, 19:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.09.2011, 19:55
Привет! Вот еще темы с ответами:

Палиндром - C++
Здравствуйте. Пытаюсь написать программу которая проверяет является ли введёное число с клавиатуры палиндромом. Метод проверки...

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

Палиндром - C++
Здравствуйте! Наткнулся на такую задачу. Дана строка и нужно посчитать сколько палиндрома можно из нее сделать. Например: ввод: ababc ...

палиндром - C++
имеется 3 класса 1. проверяет является ли строка char* палиндромом 2. проверяет является ли vector&lt;int&gt; палиндромом 3. проверяет...


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

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

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