Задача №11

Задана матрица натуральных чисел A(n,m). За каждый проход через клетку (i,j) взымается штраф A(i,j). Необходимо минимизировать штраф и

А) Пройти из какой-либо клетки 1-ой строки в n-ую строчку, при этом из текущей клетки можно перейти

1) в любую из 3-х соседних, стоящих в стpоке с номеpом на 1-цу большем;

2) в любую из 8 соседних клеток;

Б) Реализовать пункт a) для перехода из клетки (1,1) в (n,m).

Для решения пункта 1 задачи достаточно воспользоваться

тем фактом, что для определения минимальной величины штрафа, взимаемого за проход в клетку i-той строки достаточно знать минимальные величины штрафа, взимаемого за проход в клетки (i-1)-той строки, которые являются соседними рассматриваемой клетке. Поэтому алгоритм решения пункта 1 следующий:

для i от 1 до nШтраф[i,1]:=A[i,1] для i от 2 до nдля j от 1 до mнцШтраф[i,j]:=Штраф[i-1,j]+A[i,j];если j>1 и Штраф[i,j] < Штраф[i-1,j-1]+A[i,j]; то Штраф[i,j]:=Штраф[i-1,j-1]+A[i,j];если j<m и Штраф[i,j] < Штраф[i-1,j+1]+A[i,j]; то Штраф[i,j]:=Штраф[i-1,j+1]+A[i,j];

кц

Задача №12

Даны две строки x и y. Строка x состоит из нулей и единиц, строка y из символов A и B. Можно ли строку x преобразовать в строку y по следующему правилу: цифра 0 преобразуется в непустую последовательность букв A, а цифра 1 - либо в непустую последовательность букв A, либо в непустую последовательность букв B?

Пусть строка S₁ состоит из цифр 0 и 1 и имеет длину N, а строка S₂ (из символов A и B) - длину M.

Заведем матрицу А размера N на M, при этом строки матрицы помечаются i-ой цифрой строки S₁, а j-й столбец - j-м символом строки S₂.

Возьмем в качестве примера S₁='00110', S₂='AAAABBAA'.

Первая цифра строки S₁ (цифра 0) может быть преобразована в одну из последовательностей букв 'A','AA','AAA','AAAA', являющиеся префиксами строки S₂. Заносим символ 'x' в те столбцы первой строки, буквы-пометки которых соответствуют последним буквам возможных последовательностей. Таким образом, помечаются элементы A[1,1], A[1,2], A[1,3] и A[1,4].

Шаг алгоритма: будем преобразовывать очередную цифру S₁[i], которой соответствует строка i.

Находим 'x' в предыдущей строке при просмотре ее слева направо (этому столбцу соответствует последняя буква в какой-то из непустых последовательностей букв, порожденных на предыдущем шаге). Если текущую цифру можно преобразовать в последовательность букв, помечающих следующие за данным столбцы, то в этих столбцах в данной строке ставим 'x'.

Далее от места над последней помеченной ячейкой ищем в предыдущей строке 'x' и, когда находим, повторяем указанные выше операции.

Эти действия проводим далее для i=2,...,N.

Вид матрицы после N шагов:

Замечание: Можно обойтись и одномерным массивом. В самом деле, при заполнении следующей строки мы обращаемся только к элементам предыдущей строки, к каждому - по одному разу.

Алгоритм (без учета замечания) может быть следующим:

for i:=1 to N dofor j:=1 to M doA[i,j]:=' '; {инициализация}if S1[1]=0then element:='A' {0 преобразуется в A}else element:=S2[1]; {1 - в A или в B}i:=1;while (i<=M) and (S2[i]=element) do begin {первый шаг}A[1,i]:='x';i:=i+1end;for i:=2 to N do beginj:=2;while j<M do begin {просмотр строки i}if A[i-1,j-1]='x'then beginif S1[i]=0then element:='A'else element:=S2[j];if S2[j]=elementthenwhile (j<=M) and (S2[j]=element) do beginA[i,j]:='x';j:=j+1;end {end for while}else j:=j+1end {end for then}else j:=j+1end {end for while}end; {end for for}if A[N,M]='x'

then writeln('Можно преобразовать') else writeln('Нельзя преобразовать');</P></DIR>

Напишите программу, использующую одномерный массив.