Программирование, т. 5.1.

Гайс! плз нид хелп.

Палиндром – строка, которая одинаково читается слева направо и справа налево. Требуется по заданной строке определить минимальное количество символов, которые необходимо вставить в строку для преобразования ее в палиндром

Подскажите плз идею как это надо сделать, нужно методом ветвей и границ но я хз каким боком тут его юзать.

типа вставить в конец?

типа вставить в конец?

необязательно

а ты каким методом эту точку находишь с которой палиндром в обе стороны начинается?

а ты каким методом эту точку находишь с которой палиндром в обе стороны начинается?

в этом и фишка я хз как её решать, единственная идея что у меня возникала это искать максимальные похожиепоследовательности (не максимально похожие а максимальные и чтобы они были похожи,типо похуй что они различаются на немного, можно символов докинуть же и в середину), но я не уверен что это оптимально и хз толком как реализовать

Изменено 3 мая 2014 пользователем P0JIT0H

короче, есть строка, делишь ее на две ровные части (округляя в большую, если нужно)

 

и в цикле (длиной равной второй строке) проверяешь вхождение частей второй строки в первую, только сперва второй кусок перверни

 

чтобы проверить вхождение частей, ты внутри цикла добавляешь еще один цикл, так же на всю длину второй строки, и вторую строку делишь на куски ([0, length], [1, length-1], [2, length-2], ..., [length-1, 1]) и каждый кусок идешь в первой части нашего изначального предложения. Оба куска при этом должны разделять первую часть нашего ихначального предложения максимум на один кусок (который не вошел в нашу вторую часть) записываешь длину этого куска в общий массив. Так проходишь до конца.

 

потом ищещь в массиве минимальное значение это и есть твой ответ

http://stackoverflow.com/questions/10729282/convert-string-to-palindrome-string-with-minimum-insertions

короче, есть строка, делишь ее на две ровные части (округляя в большую, если нужно)

 

и в цикле (длиной равной второй строке) проверяешь вхождение частей второй строки в первую, только сперва второй кусок перверни

 

чтобы проверить вхождение частей, ты внутри цикла добавляешь еще один цикл, так же на всю длину второй строки, и вторую строку делишь на куски ([0, length], [1, length-1], [2, length-2], ..., [length-1, 1]) и каждый кусок идешь в первой части нашего изначального предложения. Оба куска при этом должны разделять первую часть нашего ихначального предложения максимум на один кусок (который не вошел в нашу вторую часть) записываешь длину этого куска в общий массив. Так проходишь до конца.

 

потом ищещь в массиве минимальное значение это и есть твой ответ

если я правильно понял то на какой нибудь строке abcdeeda этот алгоритм будет работать неверно

есть тут люди умеющие в flex+as?

т.е. нужно разобраться в чужом коде, поменять по чуть чуть.

задачки не сложные, но нужен человек которые знает синтаксис ну или который просто сможет понять, разобраться

заплачу за помощь офк, пишите в личку.

короче, есть строка, делишь ее на две ровные части (округляя в большую, если нужно)

 

и в цикле (длиной равной второй строке) проверяешь вхождение частей второй строки в первую, только сперва второй кусок перверни

 

чтобы проверить вхождение частей, ты внутри цикла добавляешь еще один цикл, так же на всю длину второй строки, и вторую строку делишь на куски ([0, length], [1, length-1], [2, length-2], ..., [length-1, 1]) и каждый кусок идешь в первой части нашего изначального предложения. Оба куска при этом должны разделять первую часть нашего ихначального предложения максимум на один кусок (который не вошел в нашу вторую часть) записываешь длину этого куска в общий массив. Так проходишь до конца.

 

потом ищещь в массиве минимальное значение это и есть твой ответ

если я правильно понял то на какой нибудь строке abcdeeda этот алгоритм будет работать неверно

если решений нет, то вся длина строки

короче, есть строка, делишь ее на две ровные части (округляя в большую, если нужно)

 

и в цикле (длиной равной второй строке) проверяешь вхождение частей второй строки в первую, только сперва второй кусок перверни

 

чтобы проверить вхождение частей, ты внутри цикла добавляешь еще один цикл, так же на всю длину второй строки, и вторую строку делишь на куски ([0, length], [1, length-1], [2, length-2], ..., [length-1, 1]) и каждый кусок идешь в первой части нашего изначального предложения. Оба куска при этом должны разделять первую часть нашего ихначального предложения максимум на один кусок (который не вошел в нашу вторую часть) записываешь длину этого куска в общий массив. Так проходишь до конца.

 

потом ищещь в массиве минимальное значение это и есть твой ответ

если я правильно понял то на какой нибудь строке abcdeeda этот алгоритм будет работать неверно

если решений нет, то вся длина строки

решение есть abcdeedcba - 2 символа

 

http://stackoverflow...imum-insertions

спасибо огромное
Изменено 3 мая 2014 пользователем P0JIT0H

а ну да, такое решение должно найтись, как раз текст разделит первую часть на один кусок - bc

а ну да, такое решение должно найтись, как раз текст разделит первую часть на один кусок - bc

блин, я с примером касячнул), abcdeeca при такой строке разве твой алгоритм будет работать(ответ тот же)
Изменено 3 мая 2014 пользователем P0JIT0H

то есть можно делать не одну вставку, а сколько угодно?

то есть можно делать не одну вставку, а сколько угодно?

да

Увидел конкурс на олимпиадное программирование, решил тряхнуть стариной, мб че выиграю. Полтора дня пота, а один хрен задроты с codeforces набежали и даже в топ 50 не удалось войти. Даже рюкзачок не выиграл. Впрочем, пох, он всё равно стрёмный.

 

максимум 700? лол

Привет юзерам этого топана.

Я учусь в универе, на первом курсе. Изучаю язык Си, но т.к. в последние месяца 2-3 подзабил на учёбу, отстал от одногруппников, а через месяц нужно уже будет сдавать курсач. Сам читаю книги, гуглю, но это слабо помогает.

Ищу человека, который мог бы достаточно понятно объяснить двусвязные списки, структуру в структуре, и помочь реализовать это в проге. Если реально поможете, в долгу не останусь.

Скайп: yggshka

тебе в паблик типичного программиста

http://habrahabr.ru/post/221835/

 

казику дали инвайт