Требуется написать программу, определяющую, сколько существует
способов вычеркивания из заданной строки некоторого (возможно
пустого) набора букв, чтобы оставшаяся строка была палиндромом.
Способы, отличающиеся порядком вычеркивания символов, считаются
одинаковыми.
Непустая строка называется палиндромом, если она одинаково читается как слева направо, так и справа налево. Пусть задана строка S, состоящая из N прописных букв латинского алфавита. Вычеркиванием из нее некоторых букв нужно получить палиндром.
Данная задача решается методом динамического программирования. Пусть A[i, j] —
это количество вычеркиваний (что результат является палиндромом), из подстроки
с i-гo по j-ый символ
исходной строки. Тогда, если в позициях i и j стоят разные символы, то
необходимо использовать выражение A[i,j]: =A[i+1,j]+A[i,j-1]-A[i+1, j-1];
если же одинаковые, то сюда еще
добавляется слагаемое A[i+1, j-1], и в результате получается,
что A[i,j]: =A[i+1,j]+A[i,j-1].
МАИ.
Факультет прикладной математики.
Кафедра вычислительной математики и программирования.
Преподаватель: Андрей Alk Калинин
в 2007 году это задание позиционировалось как Л. Р.
в 2008 уже стало курсачом.
Моя работа выполнена как Л. Р.
Отчет не прилагается.
Реализовано на С++ (-ansi );
В коментариях есть код на Pascal.
Непустая строка называется палиндромом, если она одинаково читается как слева направо, так и справа налево. Пусть задана строка S, состоящая из N прописных букв латинского алфавита. Вычеркиванием из нее некоторых букв нужно получить палиндром.
Данная задача решается методом динамического программирования. Пусть A[i, j] —
это количество вычеркиваний (что результат является палиндромом), из подстроки
с i-гo по j-ый символ
исходной строки. Тогда, если в позициях i и j стоят разные символы, то
необходимо использовать выражение A[i,j]: =A[i+1,j]+A[i,j-1]-A[i+1, j-1];
если же одинаковые, то сюда еще
добавляется слагаемое A[i+1, j-1], и в результате получается,
что A[i,j]: =A[i+1,j]+A[i,j-1].
МАИ.
Факультет прикладной математики.
Кафедра вычислительной математики и программирования.
Преподаватель: Андрей Alk Калинин
в 2007 году это задание позиционировалось как Л. Р.
в 2008 уже стало курсачом.
Моя работа выполнена как Л. Р.
Отчет не прилагается.
Реализовано на С++ (-ansi );
В коментариях есть код на Pascal.