Размышления над задачей. Вариант решения задачи на языке Паскаль. Вопросы и задания. Размышление над задачей

Размышления над задачей

Недостатком программы Editor1 является ограниченное количество символов в исходной строке (n≤255). Чтобы решить эту проблему, для хранения исходных данных и промежуточных результатов можно использовать массив из n целых чисел или массив из n символов. При использовании массива длина n исходной цепочки будет ограничена максимально допустимым размером массива в компьютере.

Вариант решения задачи на языке Паскаль

program Editor2;

const n=300; {длинацепочки}

var a: array[1..n] of integer;

i, j, k, p: integer; {k – количество элементов в обрабатываемой части массива}

Label 10, 20;

begin

for i:=1 to n do a[i]:=8; {Инициализация массива}

p:=n; k:=n; j:=n;

while (j>=3) and (p<>0) do

begin

p:=0;

for i:=1 to k-2 do {Найти Образец 333}

if (a[i]=3) and (a[i+1]=3) and (a[i+2]=3)

then begin

p:=i; {Образец найден}

a[i]:=8; a[i+1]:=8; a[i+2]:=8; {Заменить на 8}

k:=k-2;

goto 10; end {Завершить обработку 333}

else p:=0; {Образец не найден}

10: for i:=1 to k-2 do {Найти Образец 888}

if (a[i]=8) and (a[i+1]=8) and (a[i+2]=8)

then begin

p:=i; {Образец найден}

a[i]:=3; {Заменить на 3}

k:=k-2;

goto 20; end {Завершить обработку 888}

else p:=0; {Образец не найден}

20: end;

for i:=1 to k do write (a[i]); writeln; {Вывод результата}

end.

Вопросы и задания

9. Объясните необходимость использования в программе Editor2 операторов перехода по метке goto 10 и goto 20.

10. Протестируйте программу Editor2 при различных исходных данных. Результаты запишите в таблицу 2.

Таблица 2

n	Результат	n	Результат

11. В результате работы программы Editor2 получили цифру 8. Строки какой длины n могли быть использованы, если известно, что n < 20?

Размышление над задачей

Недостатками программы Editor2, использующей массив для хранения данных, является большой объем памяти и увеличение времени работы программы при увеличении количества элементов массива.

Можно ли найти более эффективное по памяти и времени работы решение задачи?

Рассмотрим решение задачи при некоторых значениях n:

Пусть 1 ≤ n ≤ 8, например, n = 5.

Исходные данные: 88888

Заменяем 888 на 3: 388

Т.к. в полученной строке нет ни 888, ни 333, то завершаем преобразования.

Выполним аналогичные действия для других значений n. Полученные результаты занесем в таблицу 3.

⇐ Предыдущая 1 234 5 Следующая ⇒