Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.76/25: Рейтинг темы: голосов - 25, средняя оценка - 4.76
0 / 0 / 0
Регистрация: 11.08.2016
Сообщений: 10

Задача. Наименьший палиндром

19.08.2016, 23:11. Показов 4679. Ответов 8
Метки c++ (Все метки)

Студворк — интернет-сервис помощи студентам
Доброго времени суток! Помогите пожалуйста в коде перевести char to int, и наоборот. Мне нужно целое число увеличть на 1, но у меня увеличивается только последний символ. Заодно можете проверить правильный ли код?
Условия: Натуральное число называется если читается слева направо и справа налево одинаково. Вам дано одно натуральное число N, которое состоит из не более чем 106 цифр. Найдите наименьший палиндром, который строго больше N. Формат входного файла В единственной строке входного файла содержится одно натуральное число N. N не содержит лидирующих нулей и состоит из не более чем 106 цифр.
Пример: 1)Ввод: 365 Вывод:373; 2)Ввод: 1 Вывод:2;

Сам код:
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
#include <iostream>
#include <cstring>
using namespace std;
bool palindrom(char *number)
{
  int left_index=0, right_index=strlen(number)-1;
  while (left_index<right_index)
  {
    if(number[left_index++]!=number[right_index--])
    {
        return false;
    }
  }
  return true;
    
}
int main()
{
    char number_char[1024];
    int number_int;
    cin>>number_char;
        //convert char to int
    number_int=number_char-'0';
        number_int++;
        //convert int to char
       *number_char=number_int+'0';
        cout<<number_int;
    while (palindrom(number_char)==false)
    {
        number_int=*number_char-'0';
        number_int++;
        *number_char=number_int+'0';
        palindrom(number_char);
    }
    
    cout<<number_char;
    
    return 0;
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
19.08.2016, 23:11
Ответы с готовыми решениями:

цифры в слове ( задача про палиндром )
Нужно сделать так чтобы при попытке пользователя ввести что то типа 22222 или п2о2п или 22привет или привет22 ему выводилось сообщение о...

Олимпиадная задача - наименьший палиндром
Палиндромом будем называть число, запись которого в десятичной системе счисления одинаково читается слева направо и справа налево....

Задача палиндром
Анна написала генератор красивых строк. Она считает строку красивой, если она одинаково читается как слева направо, так и справа налево....

8
 Аватар для Новичок
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,360
20.08.2016, 00:12
Цитата Сообщение от Naomi Aori Посмотреть сообщение
из не более чем 106 цифр
В int не вместится никак.

Добавлено через 1 минуту
Думаю, тут без длинной арифметики не обойтись.

std::string
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
#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
void inc(string& num) {
    int mod = 1;
    for (size_t i = 0; i < num.size(); i++) {
        int dig = num[i] - '0' + mod;
        mod = dig / 10;
        num[i] = dig % 10 + '0';
    }
    if (mod) num += to_string(mod);
}
 
bool is_palindrom(const string& num) {
    for (size_t i = 0; i < num.size() / 2; i++)
        if (num[i] != num[num.size() - i - 1])
            return false;
    return true;
}
 
int main() {
    string num;
    cin >> num;
    reverse(num.begin(), num.end());
    do inc(num);
    while (!is_palindrom(num));
    cout << num;
}


C string
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
#include <iostream>
#include <cstring>
 
using namespace std;
 
void inc(char* num) {
    size_t len = strlen(num);
    int mod = 1;
    for (size_t i = 0; i < len; i++) {
        int dig = num[i] - '0' + mod;
        mod = dig / 10;
        num[i] = dig % 10 + '0';
    }
    if (mod) {
        num[len] = mod + '0';
        num[len + 1] = '\0';
    }
}
 
void reverse_str(char* str) {
    size_t len = strlen(str);
    for (size_t i = 0; i < len / 2; i++)
        swap(str[i], str[len - i - 1]);
}
 
bool is_palindrom(const char* num) {
    size_t len = strlen(num);
    for (size_t i = 0; i < len / 2; i++)
        if (num[i] != num[len - i - 1])
            return false;
    return true;
}
 
int main() {
    char num[1024];
    cin >> num;
    reverse_str(num);
    do inc(num);
    while (!is_palindrom(num));
    cout << num;
}
1
0 / 0 / 0
Регистрация: 11.08.2016
Сообщений: 10
20.08.2016, 01:09  [ТС]
Новичок, огромное спасибо!
Не могли бы вы разъяснить эту часть кода?
Цитата Сообщение от Новичок Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
void inc(string& num) {
* * int mod = 1;
* * for (size_t i = 0; i < num.size(); i++) {
* * * * int dig = num[i] - '0' + mod;
* * * * mod = dig / 10;
* * * * num[i] = dig % 10 + '0';
* * }
* * if (mod) num += to_string(mod);
}
0
1394 / 1023 / 325
Регистрация: 28.07.2012
Сообщений: 2,813
20.08.2016, 01:27
Цитата Сообщение от Naomi Aori Посмотреть сообщение
Найдите наименьший палиндром, который строго больше N.
Нусь, берем строку с нашим числом и делаем так:
1) Делим строку пополам
2) Старшую половинку записываем в младшую в перевернутом виде
3) Получаем некоторый палиндром
4) Сравниваем получившееся число с исходным (достаточно проверить лексикографическую упорядоченность двух строк)
4.1) Если наше больше - готово решение
4.2) Если меньше - увеличиваем старшую половинку на 1 (да-да, немного длинной арифметики). Повторяем пункты 2-3 и сразу получаем решение.

Я думаю, что это должно прокатить, только нужно правильно обработать случай нечетной длины числа =)
1
 Аватар для Новичок
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,360
20.08.2016, 01:38
Цитата Сообщение от Naomi Aori Посмотреть сообщение
Не могли бы вы разъяснить эту часть кода?
Это просто реализация прибавления единицы к числу. Причем само число хранится перевернутым чтобы было удобнее.
Вот возьмем к примеру число 199. Оно будет храниться как 991. Если нам надо прибавить единицу то мы прибавим ее к первой (в реальности к последней) цифре, возьмем остаток от деления на 10, потом к второй цифре прибавим остаток если он есть и.т.д.
C++
7
8
9
10
11
12
13
14
15
void inc(string& num) {
    int mod = 1; // Остаток, изначально равен 1 потому что мы 1 прибавляем
    for (size_t i = 0; i < num.size(); i++) { // Идем по всем цифрам числа
        int dig = num[i] - '0' + mod; // num[i] - '0' Так мы получаем цифру, а потом остаток прибавляем
        mod = dig / 10; // Изменяем остаток
        num[i] = dig % 10 + '0'; // Записываем цифру нового числа
    }
    if (mod) num += to_string(mod); // Если есть остаток то дописываем его в конец строки(to_string используем чтобы int перевести в string
}
1
354 / 135 / 28
Регистрация: 16.12.2012
Сообщений: 607
Записей в блоге: 1
25.08.2016, 15:33
Задача решается не так
0
 Аватар для Новичок
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,360
25.08.2016, 17:37
Ромаха, да, мое решение совсем лобовое. Наверняка по времени не пройдет. Не знаю почему я не подумал об этом когда писал код...
0
Почетный модератор
 Аватар для Puporev
64314 / 47610 / 32743
Регистрация: 18.05.2008
Сообщений: 115,167
25.08.2016, 18:00
Цитата Сообщение от Naomi Aori Посмотреть сообщение
не более чем 106 цифр.
А мне кажется 106
0
Эксперт С++
 Аватар для Mr.X
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
26.08.2016, 02:18
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
//Натуральное число называется палиндромом, если читается слева направо и справа налево
//одинаково. Вам дано одно натуральное число N, которое состоит из не более
//чем 10^6 цифр. Найдите наименьший палиндром, который строго больше N.
//Формат входного файла.
//В единственной строке входного файла содержится одно натуральное
//число N. N не содержит лидирующих нулей и состоит из не более чем 10^6 цифр.
 
//Пример:
//1)  Ввод: 365
//    Вывод:373;
 
//2)  Ввод: 1
//    Вывод:2;
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <string>
///////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
///////////////////////////////////////////////////////////////////////////////
T_str   get_left_s
    (
        T_str   const   &   s,
        size_t              palindrom_len
    )
{
    return  s.substr    (
                            0,
 
                                palindrom_len
                            -   palindrom_len / 2
                        );
}
///////////////////////////////////////////////////////////////////////////////
T_str   get_palindrom
    (
        T_str   const   &   s,
        size_t              palindrom_len
    )
{
    auto    left_s      =   get_left_s  (
                                            s,
                                            palindrom_len
                                        );
 
    auto    right_s     =   left_s.substr   (
                                                0,
 
                                                    palindrom_len
                                                -   left_s.size()
                                            );
 
    if  (
            right_s.size()
        )
    {
        std::reverse
            (
                right_s.begin   (),
                right_s.end     ()
            );
    }//if
 
    return      left_s
            +   right_s;
}
///////////////////////////////////////////////////////////////////////////////
T_str   get_inc( T_str  const   &   s )
{
    auto    res     =   '0' + s;
 
    for (
            auto    rev_it  =   res.rbegin();
            ;
            ++rev_it
        )
    {
        if  (
                *rev_it     <   '9'
            )
        {
            ++*rev_it;
            break;
        }
 
        *rev_it     =   '0';
    }//for
 
    if  (
                res.front()
            ==  '0'
        )
    {
        res.erase(0, 1);
    }
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
T_str   min_of_palindrom_greater_than( T_str    const   &   s )
{
    auto    palindrom_len   (
                                s.size()
                            );
 
    auto    res         =   get_palindrom   (
                                                s,
                                                palindrom_len
                                            );
 
    if  (
            res     <=  s
        )
    {
        auto    left_s      =   get_left_s  (
                                                s,
                                                palindrom_len
                                            );
 
        auto    new_left_s  =   get_inc( left_s );
 
        if  (
                    new_left_s  .size()
                >   left_s      .size()
            )
        {
            ++palindrom_len;
        }
 
        res     =   get_palindrom   (
                                        new_left_s,
                                        palindrom_len
                                    );
    }//if
 
    return  res;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    for(;;)
    {
        T_str   s;
 
        std::cout   <<  "s = ";
        std::cin    >>  s;
 
        std::cout   <<  min_of_palindrom_greater_than(s)
                    <<  std::endl
                    <<  std::endl;
    }//for
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
26.08.2016, 02:18
Помогаю со студенческими работами здесь

Задача про палиндром!
Добрый День! У меня проблема с задачей про палиндром, нужно ввести любую цифру(n&gt;0) и найти все палиндромы меньше данной цифры, включая...

Задача на палиндром, сигнум и косинус.
Поступил на первый курс. Сразу дали такие задачки. Препод ничё не объясняет, мол сами делайте как хотите. Помогите решить эти задачки....

Слово-палиндром, насколько эффективно решена задача
Здравствуйте, вот готовлюсь к ЕГЭ, тренируюсь решать С4. Скажите пожалуйста, насколько эффективно решена эта задача: На вход...

Найти ближайший простой палиндром, больший заданного n (задача из раздела C++)
Мое решение: isPal n = s == rs where s = show n rs = reverse s isPrime n |...

Проверить слово на палиндром и почти палиндром
Нужно проверить слово на палиндром и почти палиндром. например: КАЗАК - палиндром МЕЧОМ - почти палиндром


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

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли
8Observer8 30.01.2026
Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm
8Observer8 30.01.2026
Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .
SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 29.01.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru