См. также
{ A. B - входные последовательности m, n - длина A и B соответственно L - матрица размера m x n } выделить память для матрицы L; for i := m downto 0 do for j := n downto 0 do begin if ( A[i] == 0 ) or ( B[j] == 0 ) L[i,j] := 0; else if A[i+1] = B[j+1] L[i,j] := 1 + L[i+1, j+1]; else L[i,j] := max ( L[i+1, j], L[i, j+1] ); end; { в L[0,0] будет длина максимальной общей подпоследовательности }После построения матрицы L для получения самой общей подпоследовательности достаточно выполнить следующий проход:
S := ''; i := 0; j := 0; while ( i < m ) and ( j < n ) do begin if A[i] = B[j] then begin S := S + A[i]; i := i + 1; j := j + 1; end else if L[i+1,j] >= L[i,j+1] i := i + 1; else j := j + 1; end
A A+1 _ 1111 0000 | 10010 — делитель 1001 0 ________ _ 110 00 100 10 ________ _ 01 100 00 000 ________ _ 1 1000 1 0010 _______ 0110 — это и есть CRC-4Надо заметить, что, во-первых, запоминать частное не нужно, важен только остаток. А во-вторых, количество бит делителя на единицу больше, чем разрядность самого циклического кода, и старший бит делителя всегда установлен. Это требование определяет разрядность вычисляемого избыточного кода, так как при его невыполнении получится меньший диапазон значений «остатков». Выбор делителя — важная задача, подробно рассмотренная в [2]. Наиболее популярными являются значения:
x := tg....(a); |||| | || y := arcsin(b);В варианте б) вывод различий двух текстов можно оформить горизонтальными разделителями. Например, пусть даны два текста:
i := 1; for j := 1 to 10 do i := i * j; writeln;
// i := 1; readln (i); for j := 1 to 10 do i := i * j; writeln (i);Тогда вывод различий может выглядеть так:
——————————————————————-(1) 001 i := 1; ——————————————————————-(2) 001 // i := 1; 002 readln (i); ———————————————————————- ====================================================================== 002 003 for j := 1 to 10 do 003 004 i := i * j; ====================================================================== ——————————————————————-(1) 004 writeln; ——————————————————————-(2) 005 writeln (i); ———————————————————————-