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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.73
archivist
0 / 0 / 0
Регистрация: 25.04.2013
Сообщений: 5
25.04.2013, 00:13     Из данной строки удалите наименьшее количество символов, так, чтобы получился палиндром #1
Срочно до утра нужно построить несколько алгоритмов на С++. Кто может помогите!
Вот задания:
4.Из данной строки удалите наименьшее количество символов, так, чтобы получился палиндром (строка, одинаково читающаяся как справа налево, так и слева направо).
Формат входных данных: программа получает на вход непустую строку, длиной не более 100 символов. Строка состоит только из заглавных латинских букв. Формат выходных данных. Программа должна вывести строку-палиндром максимальной длины, которую можно получить из данной вычеркиваем нескольких букв. При наличии нескольких решений необходимо вывести одно (любое) из них.
Пример: Входные данные: ABYCXDCBA Выходные: ABCDCBA

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

Строки. Подсчитать количество заглавных букв в тексте; вывести на экран слова, имеющие наименьшее количество букв... (подправить) C++
C++ Переставить цифры в этом числе так, чтобы получить наименьшее из чисел
C++ Дана строка, состоящая из M попарно различных символов. Вывести все перестановки символов данной строки.
Из символов данной строки составить три новых слова C++
C++ Как в данной программе сделать так чтобы все генерируемые числа стояли по возрастанию или по убыванию
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Aymurat
90 / 84 / 25
Регистрация: 07.11.2014
Сообщений: 572
Завершенные тесты: 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 минут
Актуально
Aymurat
90 / 84 / 25
Регистрация: 07.11.2014
Сообщений: 572
Завершенные тесты: 5
04.11.2016, 10:34     Из данной строки удалите наименьшее количество символов, так, чтобы получился палиндром #3
Проблема актуальна
Babysitter
 Аватар для Babysitter
78 / 103 / 34
Регистрация: 23.11.2015
Сообщений: 315
Завершенные тесты: 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;
}
нужно сидеть кэши прикручивать, а то совсем все будет печально.
Aymurat
90 / 84 / 25
Регистрация: 07.11.2014
Сообщений: 572
Завершенные тесты: 5
04.11.2016, 14:46     Из данной строки удалите наименьшее количество символов, так, чтобы получился палиндром #5
Babysitter, а можно вот все это ускорить в раз эдак 10? А то по времени отстает, хотя бы 2 сек
Babysitter
 Аватар для Babysitter
78 / 103 / 34
Регистрация: 23.11.2015
Сообщений: 315
Завершенные тесты: 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;
}
Aymurat
90 / 84 / 25
Регистрация: 07.11.2014
Сообщений: 572
Завершенные тесты: 5
05.11.2016, 08:50     Из данной строки удалите наименьшее количество символов, так, чтобы получился палиндром #7
Babysitter, вот! Этой скорости достаточно) Благодарю!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2016, 15:44     Из данной строки удалите наименьшее количество символов, так, чтобы получился палиндром
Еще ссылки по теме:

C++ Определить минимальное количество символов, которые нужно добавить в строку, чтобы получить палиндром
C++ Получить из строки палиндром, удаляя наименьшее количество символов
Что нужно изменить, чтобы получился однонаправленный список? C++

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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2798 / 1574 / 246
Регистрация: 03.05.2010
Сообщений: 3,651
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
}
Yandex
Объявления
07.11.2016, 15:44     Из данной строки удалите наименьшее количество символов, так, чтобы получился палиндром
Ответ Создать тему
Опции темы

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