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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
archivist
0 / 0 / 0
Регистрация: 25.04.2013
Сообщений: 5
#1

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

25.04.2013, 00:13. Просмотров 1740. Ответов 7
Метки нет (Все метки)

Срочно до утра нужно построить несколько алгоритмов на С++. Кто может помогите!
Вот задания:
4.Из данной строки удалите наименьшее количество символов, так, чтобы получился палиндром (строка, одинаково читающаяся как справа налево, так и слева направо).
Формат входных данных: программа получает на вход непустую строку, длиной не более 100 символов. Строка состоит только из заглавных латинских букв. Формат выходных данных. Программа должна вывести строку-палиндром максимальной длины, которую можно получить из данной вычеркиваем нескольких букв. При наличии нескольких решений необходимо вывести одно (любое) из них.
Пример: Входные данные: ABYCXDCBA Выходные: ABCDCBA

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

Требуется изменить порядок букв так, чтобы получился палиндром - C++
Восстановление палиндрома Задано слово, состоящее из маленьких латинских букв. Требуется изменить порядок букв так, чтобы получился...

Получить из строки палиндром, удаляя наименьшее количество символов - C++
Помогите пожалуйста,Дана строка символов,получить из нее путем удаления наименьшего количества символов палиндром.

Определить минимальное количество символов, которые нужно добавить в строку, чтобы получить палиндром - C++
Определить минимальное количество символов, которые нужно добавить в строку, чтобы получить палиндром например: ввод aziz ...

Определить минимальное количество символов, которые нужно добавить в строку, чтобы получить палиндром - C++
Здравствуйте, помогите пожалуйсто, был бы очень признателен хотя бы за идею решения(поидеи методом ветвей и границ она решается) ...

В данной строке символов посчитать количество вхождений данной буквы - C++
Указатели и строки. 1) В данной строке символов посчитать кол-во данной буквы 2) Дана последовательность слов, найти кол-во слов в...

Дана строка, состоящая из M попарно различных символов. Вывести все перестановки символов данной строки. - C++
Дана строка, состоящая из M попарно различных символов. Вывести все перестановки символов данной строки. Ввод В первой строке файла...

7
Aymurat
101 / 95 / 29
Регистрация: 07.11.2014
Сообщений: 638
Завершенные тесты: 5
03.11.2016, 05:38 #2
Поднимаю тему. Актуально

Добавлено через 28 минут
Ну и как же без наработок)
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
#include <iostream>
using namespace std;
int main()
{
    string str;
    cin>>str;
    string newstr;
    int j = str.length()-1;
    bool visited[100];
    for(int i = 0; i < 100; i++) visited[i] = false;
    for(int i = 0; i<j && i < str.length()/2+1; i++)
    {
        if (str[i] == str[j]) newstr.push_back(str[i]); else
        for(int g = i; g < j && g < str.length()/2+1; g++)
        {
            if (str[g] == str[j] && visited[g] == false) {newstr.push_back(str[g]); visited[g] == true; i = g; break;}
        }
    /*  for(int g = j; g > i && g >= str.length()/2+1; g--)
        {
            if (str[g] == str[i] && visited[i] == false) {newstr.push_back(str[g]); visited[i] == true; j = g; break;}
        }*/
        j--;
    }
    cout<<newstr;
    if (str.length()%2 == 0) cout<<str[str.length()/2]; else cout<<str[str.length()/2+1];
    for(int i = newstr.length()-1; i >=0; i--)
    cout<<newstr[i];
}
Только тут правда некоторые крайние случаи не учтены, например, при QWEERTYY выводит R, а должно EE
Прошу помощи)

Добавлено через 8 часов 26 минут
Актуально
0
Aymurat
101 / 95 / 29
Регистрация: 07.11.2014
Сообщений: 638
Завершенные тесты: 5
04.11.2016, 10:34 #3
Проблема актуальна
0
Babysitter
108 / 114 / 36
Регистрация: 23.11.2015
Сообщений: 346
Завершенные тесты: 1
04.11.2016, 13:58 #4
Цитата Сообщение от Aymurat Посмотреть сообщение
Проблема актуальна
набросал говнокод для классического решения

Добавлено через 27 минут
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
#include <iostream>
#include <algorithm>
#include <array>
#include <string>
 
std::string palindrome(const std::string& s) {
    if (s.size() == 0 || s.size() == 1) {
        return s;
    }
    if (s.front() == s.back()) {
        return s.front() + palindrome(s.substr(1, s.size() - 2)) + s.back();
    }
    std::array<std::string, 3> branches; 
    branches[0] = palindrome(s.substr(1));
    branches[1] = palindrome(s.substr(0, s.size() - 1));
    branches[2] = palindrome(s.substr(1, s.size() - 2));
 
    return *std::max_element(branches.begin(), branches.end(), []
        (const std::string& a, const std::string& b) {
            return a.size() < b.size();
        });
}
 
int main()
{
    std::string target{ "12343271" };
    std::cout << palindrome(target) << std::endl;
}
нужно сидеть кэши прикручивать, а то совсем все будет печально.
1
Aymurat
101 / 95 / 29
Регистрация: 07.11.2014
Сообщений: 638
Завершенные тесты: 5
04.11.2016, 14:46 #5
Babysitter, а можно вот все это ускорить в раз эдак 10? А то по времени отстает, хотя бы 2 сек
0
Babysitter
108 / 114 / 36
Регистрация: 23.11.2015
Сообщений: 346
Завершенные тесты: 1
04.11.2016, 15:51 #6
Цитата Сообщение от Aymurat Посмотреть сообщение
можно вот все это ускорить в раз эдак 10?
нужно! я думал ты сам что-нибудь придумаешь.
в лоб я что-то такое написал. если у кого есть идеи хорошие - буду рад выслушать ругань.

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 <cassert>
#include <algorithm>
#include <array>
#include <string>
#include <unordered_map>
#include <chrono>
 
// S('t' "alpha" 'h')
std::string palindrome(const std::string& s) {
    // so slow ... trying to search in cache
    static std::unordered_map<std::string, std::string> cache;
    if (cache.find(s) != end(cache)) {
        return cache[s];
    }
    //////////////////////////////////////////
    if (s.size() == 0 || s.size() == 1) {
        return s;
    }
    std::string alpha{ s.substr(1, s.size() - 2) };
    if (s.front() == s.back()) {
        std::string result = s.front() + palindrome(alpha) + s.back();
        cache[s] = result;
        return result;
    }
    std::array<std::string, 3> branches;
    // S(alpha t)
    std::string alpha_t{ s.substr(1) };
    branches[0] = palindrome(alpha_t);
    if (branches[0].size() == alpha_t.size()) {
        cache[s] = branches[0];
        return branches[0];
    }
    // S(h alpha)
    std::string h_alpha{ s.substr(0, s.size() - 1) };
    branches[1] = palindrome(h_alpha);
    if (branches[1].size() == h_alpha.size()) {
        cache[s] = branches[1];
        return branches[1];
    }
    // S(alpha)
    branches[2] = palindrome(alpha);
 
    auto result = std::max_element(branches.begin(), branches.end(), []
    (const std::string& a, const std::string& b) {
        return a.size() < b.size();
    }); 
    
    cache[s] = *result;
    return *result;
}
1
Aymurat
101 / 95 / 29
Регистрация: 07.11.2014
Сообщений: 638
Завершенные тесты: 5
05.11.2016, 08:50 #7
Babysitter, вот! Этой скорости достаточно) Благодарю!
0
Mr.X
Эксперт С++
3050 / 1695 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
07.11.2016, 15:44 #8
Цитата Сообщение от Babysitter Посмотреть сообщение
что-то такое написал
Вот так несколько побыстрее работает:
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
///////////////////////////////////////////////////////////////////////////////
//3.
///////////////////////////////////////////////////////////////////////////////
//Из данной строки удалите наименьшее количество символов
//так, чтобы получился палиндром.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <map>
#include <string>
#include <utility>
///////////////////////////////////////////////////////////////////////////////
typedef std::string                                 T_str;
typedef T_str::size_type                            T_pos;
typedef T_pos                                       T_len;
typedef std::pair   < T_pos,            T_len   >   T_pos_and_len;
typedef std::map    < T_pos_and_len,    T_str   >   T_palindrom_of_pos_and_len;
///////////////////////////////////////////////////////////////////////////////
bool    ends_equal
    (
        T_str           const   &   s,
        T_pos_and_len   const   &   pos_and_len
    )
{
    auto    pos     =   pos_and_len.first;
    auto    len     =   pos_and_len.second;
 
    return      s[ pos              ]
            ==  s[ pos + len - 1    ];
}
///////////////////////////////////////////////////////////////////////////////
T_str   get_palindrom_of_pos_and_len
    (
        T_str                       const   &   s,
        T_palindrom_of_pos_and_len          &   palindrom_of_pos_and_len,
        T_pos_and_len               const   &   pos_and_len
    )
{
    auto    it  =   palindrom_of_pos_and_len.find( pos_and_len );
 
    if  (
            it  !=  palindrom_of_pos_and_len.end()
        )
    {
        return  it->second;
    }
 
    T_str   res;
    auto    pos     =   pos_and_len.first;
    auto    len     =   pos_and_len.second;
 
    if  (
                len
            <=  1
        )
    {
        res     =   s.substr( pos, len );
    }
    else if (
                ends_equal( s, pos_and_len )
            )
    {
        res     =       s[ pos ]
 
                    +   get_palindrom_of_pos_and_len
                            (
                                s,
                                palindrom_of_pos_and_len,
 
                                {
                                    pos     +   1,
                                    len     -   2
                                }
                            )
 
                    +   s[ pos ];
    }
    else
    {
        auto    L   =   get_palindrom_of_pos_and_len
                            (
                                s,
                                palindrom_of_pos_and_len,
 
                                {
                                    pos,
                                    len     -   1
                                }
                            );
 
        auto    R   =   get_palindrom_of_pos_and_len
                            (
                                s,
                                palindrom_of_pos_and_len,
 
                                {
                                    pos     +   1,
                                    len     -   1
                                }
                            );
 
        res     =       L.size()
                    >   R.size()
                        ?   L
                        :   R;
    }//else
 
    palindrom_of_pos_and_len[ pos_and_len ]   =   res;
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
T_str   max_palindrom( T_str    const   &   s )
{
    T_palindrom_of_pos_and_len  palindrom_of_pos_and_len;
 
    return  get_palindrom_of_pos_and_len
                (
                    s,
                    palindrom_of_pos_and_len,
 
                    {
                        0,
                        s.size()
                    }
                );
}
///////////////////////////////////////////////////////////////////////////////
T_str   rand_str_with_size( int  size )
{
    const   T_str   LETTERS     =   "abcdefghijklmnopqrstuvwxyz";
    T_str           res;
 
    for( int  i{}; i < size; ++i )
    {
        res     +=  LETTERS[ rand() % LETTERS.size() ];
    }
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        T_str   s   =   rand_str_with_size(2000);
 
        std::cout   <<  std::endl
                    <<  std::endl
                    <<  s
                    <<  std::endl
                    <<  std::endl
                    <<  "-> ";
 
        T_str   res     =   max_palindrom(s);
 
        std::cout   <<  res
                    <<  std::endl;
 
        system("pause");
    }//for
}
1
07.11.2016, 15:44
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2016, 15:44
Привет! Вот еще темы с ответами:

Переставить цифры в этом числе так, чтобы получить наименьшее из чисел - C++
Задача такая: Задано натуральное N, состоящее не более, чем из 6 цифр. Переставить цифры в этом числе так, чтобы получить наименьшее из...

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

Из символов данной строки составить три новых слова - C++
Нужна помощь , Дана строка символов.Из символов данной строки составить три новых слова.Каждое в отдельной строке.

Определить, можно ли переставить буквы так, чтобы получился палиндром - Free Pascal
3.На вход программы подаются прописные латинские буквы, ввод этих символов заканчивается точкой. Напишите эффективную по времени работы и...


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

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

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