Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.85/39: Рейтинг темы: голосов - 39, средняя оценка - 4.85
Почетный модератор
 Аватар для Lord_Voodoo
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873

Построение минимального палиндрома

01.10.2009, 16:10. Показов 8819. Ответов 39
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Никак не могу придумать алгоритма:
есть входная строка в n символов, необходимо добавить такое кол-во символов, чтобы вышел минимально возможный палиндром...

палиндром
Палиндро́м (от греч. πάλιν — «назад, снова» и греч. δρóμος — «бег») — число (например, 404), буквосочетание, слово (например, топот, финск. saippuakauppias = продавец мыла — самое длинное употребительное слово-палиндром в мире) или текст, одинаково (или почти одинаково) читающиеся в обоих направлениях.


т.е. вход: abcb выход: abcba
вход: aaabbba выход: aaabbbaaa
0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
01.10.2009, 16:10
Ответы с готовыми решениями:

Упорядочить по убыванию элементы целочисленного массива, расположенные после минимального числа-палиндрома
Доброго времени суток!!! Пожалуйста помогите. Упорядочить по убыванию элементы целочисленного массива, расположенные после минимального...

Построение минимального остовного дерева. Использовать алгоритм Борувки
Нужно в delphi показать принцип работы алгоритма

Помогите составить программу транспортной задачи.Построение опорного плана перевозок методом минимального элемента.
Однородный груз сосредоточен у 3х поставщиков в объемах 200,300,500 тонн .Данный груз необходимо доставить 4ем потребителям в обьемах...

39
Почетный модератор
 Аватар для Lord_Voodoo
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
02.10.2009, 11:06  [ТС]
Студворк — интернет-сервис помощи студентам
odip, ну я же про его алгоритм говорил, он его поправил, а я еще не дописал его (в разработке, если на работе покой будет - допишу)... а аналог твоего алгоритма я тоже реализовал, но не так витиевато, как у тебя... хотя сейчас потестируем, что уж там)))


вопросов нет... работает... но просто вместо витиеватого кода, хотелось витиеватого алгоритма, слишком просто все выходит... хоть и простота рулит, но вот такая взяла меня блажь...
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
02.10.2009, 11:47
Не знаю что ты подразумеваешь под словом "витиеватый алгоритм", IMHO алгоритм очень прост.
Можно еще ускорить.
Во-первых нужно не использовать функцию is_pal(), вставить проверку сразу в тело функции.
Во-вторых у меня сначала копируется хвост из начало в конец, а потом проверяется - не палиндров ли это.
Так вот - можно не копировать хвост, так как ясно, что скопированный хвост и так является копией. Нужно просто проверять пропустив копирование хвоста.

Добавлено через 20 минут
Программа, версия 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
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
/* Thread 53550, variant 2 */
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
/********************************************************************/
#define MAX_SIZE    1000
 
 
/********************************************************************/
int calc_minpal( const char *str, int buf_size, char *buf );
 
 
/********************************************************************/
int main( int argc, char *argv[] ) {
 
int buf_size;
char buf[2*MAX_SIZE+1];
 
 
argc--; argv++;
if ( argc != 1 ) {
    fprintf( stderr, "Usage: minpal digit-string\n" );
    exit( 2 );
}
 
buf_size= calc_minpal( argv[0], sizeof(buf), buf );
if ( buf_size<0 ) {
    fprintf( stderr, "Invalid argument\n" );
    exit( 1 );
}
printf( "Original |%s|\n", argv[0] );
printf( "Minpal   |%s|\n", buf );
 
return 0;
 
} /* main() */
 
 
/********************************************************************/
int calc_minpal( const char *str, int buf_size, char *buf ) {
 
int i, j, add, str_size;
int pal_flag;
 
 
/* Check */
str_size= strlen( str );
if ( str_size*2+1>buf_size ) { return -1; }
 
/* Check original */
add= 0;
pal_flag= 1;
for ( i= 0, j= str_size+add-1; i<j; i++, j-- ) {
    if ( str[i] != str[j] ) { pal_flag= 0; break; }
}
if ( pal_flag ) { goto ret_pal; }
 
/* Loop */
for ( add= 1; add<str_size; add++ ) {
 
    /* Check */
    pal_flag= 1;
    for ( i= add, j=str_size-1; i<j; i++, j-- ) {
        if ( str[i] != str[j] ) { pal_flag= 0; break; }
    }
    if ( pal_flag ) { goto ret_pal; }
 
}
 
fprintf( stderr, "Internal error\n" );
return -1;
 
 
/* Create palindrom and return */
ret_pal:
memcpy( buf, str, str_size );
for ( i= 0; i<add; i++ ) { buf[str_size+i]= buf[add-1-i]; }
buf[str_size+add]= '\0';
return str_size+add;
 
} /* calc_minpal() */
0
Почетный модератор
 Аватар для Lord_Voodoo
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
02.10.2009, 11:51  [ТС]
odip, ну вот видишь, пошла оптимизация алгоритма))) а на счет витиеватого алгоритма, если у меня все же получится реализовать - покажу и расскажу...
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
02.10.2009, 11:53
ну вот видишь, пошла оптимизация алгоритма
Она не пошла - я сразу знал про этот метод оптимизации
Просто для простоты сделал более тупой метод.
0
Почетный модератор
 Аватар для Lord_Voodoo
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
02.10.2009, 11:57  [ТС]
odip, у меня возникли неприятные смутные подозрения по поводу тупого метода, но промолчу дабы не оффтопить
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
02.10.2009, 11:58
Не знаю какие у тебя там подозрения, но метод работает.
0
Почетный модератор
 Аватар для Lord_Voodoo
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
02.10.2009, 12:03  [ТС]
odip, я не про метод... ну да ладно... будет желание еще что-нить придумать, выкладывай
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
02.10.2009, 12:04
Вот тут задача про палиндром: https://www.cyberforum.ru/pascal/thread53635.html
0
Почетный модератор
 Аватар для Lord_Voodoo
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
02.10.2009, 12:06  [ТС]
odip, думаю это его сюда надо направлять, а не наоборот
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
02.10.2009, 12:08
Там несколько другая задача.
Алгоритм для той задачи я уже написал
0
556 / 510 / 25
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
02.10.2009, 12:19
еще один возможной алгоритм (хотя в принципе все возможные - варианты одного и того же):

в цикле проверяем, не палиндром ли строка(без нуля), затем строка без первого символа, строка без второго и т.д. количество "непалиндромов" - это количество символов, которые нужно потом переписать "зеркально" из начала в конец.

например:

c = 0;

abcded - не палиндром c++
bcded - не палиндром c++
cded - не палиндром c++
ded - палиндром. с = 3, значит переписать нужно три символа.
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
02.10.2009, 12:20
Угу, один в один как в Построение минимального палиндрома
0
556 / 510 / 25
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
02.10.2009, 12:28
Цитата Сообщение от odip Посмотреть сообщение
вполне возможно я не читаю код написанный одной строкой с отступами непонятно по какому признаку хотя все это и с++ конечно не спорю.
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
02.10.2009, 12:32
2novi4ok: Пургу несешь. Код нормально написан.
Если у тебя все в одну строку - проверь свой броузер или еще чего.
0
556 / 510 / 25
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
02.10.2009, 12:57
Цитата Сообщение от odip Посмотреть сообщение
2novi4ok: Пургу несешь. Код нормально написан.
Если у тебя все в одну строку - проверь свой броузер или еще чего.
пургу так пургу. с браузером у меня все нормально. тебе говорю как layout твоего кода воспринимается, а ты или обижайся или выводы сделай.
0
Эксперт С++
 Аватар для odip
7176 / 3234 / 82
Регистрация: 17.06.2009
Сообщений: 14,164
02.10.2009, 13:34
То есть ты предлагаешь мне изменить мой код под такой вариант отступов, который нравится именно тебе ?
Извини, но не собираюсь.
с отступами непонятно по какому признаку хотя все это и с++ конечно не спорю.
Вообще это С, а не C++.
0
Почетный модератор
 Аватар для Lord_Voodoo
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
02.10.2009, 14:19  [ТС]
novi4ok, odip, за форматирования программного кода - создайте тему и спорьте, а здесь это флуд...
0
 Аватар для mirso
562 / 373 / 55
Регистрация: 05.04.2009
Сообщений: 767
02.10.2009, 23:49
Цитата Сообщение от VoodooMan Посмотреть сообщение
обрезать первые символы до палиндрома, а потом их приписать в конец
VoodooMan,
можно приписывать сразу.
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
#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
int main ()//============================================
{
    string txt = "1234erus3454545";
    string tmp1 = txt, tmp2;
 
    for ( size_t i = 0; i < txt.length() - 1; i++ )
    {   
        tmp2 = tmp1;
        reverse ( tmp2.begin(), tmp2.end() );
        if ( tmp1 != tmp2 )//--------------------------
        {
            tmp1.erase ( 0, 1 );
            txt.insert ( txt.length() - i, 1, txt[i] );     
        }
        еlse 
            break;
    }//------------------------------------------------
 
cout << txt << endl;    
system ( "pause > nul" );
return 0;
}//=====================================================
1
556 / 510 / 25
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
03.10.2009, 00:21
остроумно, но не быстрее уже здесь представленного. скорее всего - самый медленный алгоритм. но логически легко прослеживаемый.
0
Почетный модератор
 Аватар для Lord_Voodoo
8785 / 2538 / 144
Регистрация: 07.03.2007
Сообщений: 11,873
03.10.2009, 09:59  [ТС]
mirso, этот алгоритм я тоже уже реализовал... по простоте думаю ему первое место...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
03.10.2009, 09:59

Определение палиндрома
Народ, помогите прогу составить. Является ли введенное число с клавиатуры палиндромом. В языке Си

Нахождение палиндрома
Жду кртики и замечаний по поводу программы В ней проводится поиск палиндромов с учетом знаков пунктуации и пробелов class Polindrom:...

Поиск Палиндрома
Нужна Ваша помощь в решении задачи: Палиндром - это число, запись которого будет читаться одинаково сначала и с конца. Например 4554,...

Выделение палиндрома.
Дана последовательность символов, заканчивающаяся точкой. Определите, есть ли в этой последовательности символы, соответствующие десятичным...

Нахождение палиндрома
Помогите с задачей нахождения палиндрома числа через цикл while?


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Про "Windows must die!"
kumehtar 04.11.2026
Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .
Красочные поля с номером страницы svg+background-image
russiannick 04.11.2026
Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .
Вступаем в новую фазу генерации favicons, векторную.
russiannick 02.11.2026
Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .
Генератор паролей (вариант №4)
Maks 01.11.2026
После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков | 1 l I;. . .
Генератор паролей (вариант №3)
Maks 30.10.2026
Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .
Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени)
zorxor 30.10.2026
Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .
За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ)
zorxor 30.10.2026
Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .
Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени)
zorxor 30.10.2026
Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru