|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
03.03.2013, 14:37 | #1 |
Пользователь
Регистрация: 25.02.2013
Сообщений: 13
|
Написать программу на C
Даны 2 последовательности "x" и "y". Найти последовательность "z", которую можно получить вычеркиванием элементов как из "x", так и из "y"
|
03.03.2013, 14:49 | #2 |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
Наработки есть?
I'm learning to live...
|
04.03.2013, 18:29 | #3 |
Пользователь
Регистрация: 25.02.2013
Сообщений: 13
|
в данный момент нет
|
10.03.2013, 14:48 | #4 |
Пользователь
Регистрация: 25.02.2013
Сообщений: 13
|
нашел эту программу на паскале:
Пусть x=x1,x2, ... ,xm, y=y1,y2, ... ,yn. Заведем матрицу A[0..m,0..n]. Элемент A[i,j] будет длиной максимальной общей подпоследовательности y x1, ... ,xi и y y1, ..., yj. Сначала A[i,0]=A[0,j]=0, i=0, ... ,m, j=0, ... ,n. Пусть xi=yj, тогда требуется увеличить длину максимальной общей подпоследовательности x1, ... ,xi-1 и y1, ... ,yj-1 на 1: A[i,j]=A[i-1,j-1]+1, если xi=yj. В случае, если xi<>yj, то, очевидно, A[i,j]=max{A[i-1,j],A[i,j-1],A[i-1,j-1]}, но так как всегда A[i-1,j-1]<=A[i,j-1], то A[i,j]=max{A[i-1,j],A[i,j-1]}. Величина A[m,n] и дает длину максимальной общей подпоследовательности. Найдем саму подпоследовательность. Пусть A[m,n]=d. Двигаясь по последней строке справа налево ищем самый левый элемент в этой строке со значением d. Двигаемся от него вверх по столбцу в поиске элемента столбца с минимальным первым индексом и значением d. Пусть это A[i,j]. Элемент A[i-1,j-1] обязан быть равен d-1, а xi и yi - это последние общие совпадающие элементы в x и y. Начиная от элемента A[i-1,j-1] повторяем, как было описано выше, движение влево и вверх по матрице, находим предпоследний совпадающий элемент в x и y, и т.д. Программа: Код:
Последний раз редактировалось Stilet; 10.03.2013 в 16:13. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Задача на множества.Написать программу не позволяющую вводить буквы русского алфавита.(написать подпрограммой используя процедуры | ANTON1994 | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 09.02.2013 13:53 |
Написать программу | Арсланова | Общие вопросы C/C++ | 1 | 25.09.2012 21:38 |
Написать программу для перевода из 16-ричной системы счисления в 10-тичную, использовать процедурую(написать Delphi) | BLADIMIR | Помощь студентам | 3 | 07.09.2011 16:35 |
Написать программу | Holzz | Фриланс | 3 | 16.07.2011 12:27 |