Лицей №1

“Рекурсивное программирование”

Подготовила Щербук О.Ф.,

Барановичи

2004 год.

Введение

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

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

Данный материал рекомендуется учителям математики для факультативных занятий и спецкурсов по выбору в 9-11 классах, а также учащимся старших классов.

РЕКУРСИЯ

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

Определение 1.

Алгоритм, использующий в качестве вспомогательного самого себя, является рекурсивным алгоритмом.

Определение 2.

Способность функции обращаться к себе самой называется рекурсией.

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

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

! Содержание и мощность рекурсивного определения, а также его главное назначение состоит в том, что оно позволяет с помощью конечного выражения определить бесконечное множество объектов. Аналогично, с помощью рекурсивного алгоритма можно определить бесконечное вычисление, причем алгоритм не будет содержать повторений фрагментов текста.

Для создания рекурсивных алгоритмов необходимо и достаточно наличие понятия процедуры или функции. Это вытекает из того, что процедуры и функции позволяют дать любой последовательности действий имя, с помощью которого можно будет эту последовательность действий вызывать.

Например, следующая процедура будет бесконечно печатать известные всем строки.

program pr1;

procedure PopeAndDog1;

begin

writeln(`У попа была собака, он ее любил');

writeln(`Она съела кусок мяса, он ее убил');

writeln(`похоронил и надпись написал:');

PopeAndDog1

end;

Begin

PopeAndDog1

End.

Однако если оператор вызова процедуры поставить перед выводом текста, как показано ниже,

Program PR2;

Procedure PopeAndDog2;

begin

PopeAndDog2;

writeln(`У попа была собака, он ее любил');

writeln(`Она съела кусок мяса, он ее убил');

writeln(`похоронил и надпись написал:');

end;

Begin

PopeAndDog2

End.

то такая программа ничего не напечатает, хотя и будет работать также бесконечно, как и первая. Это объясняется тем, что оператор вызова процедуры стоит первым и, соответственно, вызов новой копии процедуры PopeAndDog2 произойдет раньше, чем вывод текста. В следующей копии процедуры будут сделаны аналогичные действия, и т.д. В результате произойдет бесконечный вызов процедуры PopeAndDog2 без какого-либо вывода текста, хотя оператор вывода в процедуре присутствует.

!В действительности при исполнении на компьютере такой бесконечный вызов приводит к переполнению стека и возникновению ошибки времени исполнения.

! Рекурсивная процедура указывает, что нужно делать, а нерекурсивная больше акцентирует внимание на том, как нужно делать.

Однако за эту простоту приходится расплачиваться неэкономным использованием ОП, т.к. выполнение рекурсивных процедур требует значительно большего размера ОП во время выполнения, чем нерекурсивных. При каждом рекурсивном вызове для локальных переменных, а также для параметров процедуры, выделяются новые ячейки памяти.

Таким образом, какой-либо локальной переменной А на разных уровнях рекурсии будут соответствовать различные ячейки памяти, которые могут иметь разные значения.

! Поэтому, воспользоваться значением переменной А i-го уровня рекурсии можно находясь только на i-гом уровне.

Дадим некоторые определения, имеющие отношения к рекурсии.

= Максимальное число рекурсивных вызовов процедуры без возвратов, который происходит во время выполнения программы, называемой глубиной рекурсии.

= Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии.

! Главное требование к рекурсивным процедурам заключается в том, что вызов рекурсивной процедуры должен выполнятся по условию, которое на каком-то уровне рекурсии станет ложным (т.к. бесконечной памяти не существует).

Если условие истинно, то рекурсивный спуск продолжается. Когда оно становится ложным, то спуск заканчивается и начинается поочередный рекурсивный возврат из всех вызванных на данный момент копий рекурсивной процедуры.

Структура рекурсивной процедуры может принимать 3 разные формы.

1. Форма с выполнением действий до рекурсивного вызова (с выполнением

действий на рекурсивном спуске).

Procedure Rec;

begin

S;

if условие then Rec;

end;

2. Форма с выполнением действий после рекурсивного вызова (с выполнением действий на рекурсивном возврате).

Procedure Rec;

begin

if условие then Rec;

S;

end;

3. Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).

Procedure Rec;

begin

S1;

if условие then Rec;

S2;

End;

или

Procedure Rec;

begin

if условие then begin

S1;

Rec;

S2;

end;

end;

Все виды рекурсивных процедур находят применение на практике. Многие задачи, в том числе вычисления n!, безразличны к тому, какая используется форма рекурсивной процедуры.

! Однако есть классы задач, при решении которых требуется (программисту) сознательно управлять ходом работы рекурсивных процедур и функций. Такими в частности являются задачи, использующие списковые и древовидные структуры данных.

Глубокое понимание рекурсивного механизма и умение управлять им по собственному желанию, являются необходимым качеством квалифицированного программиста.

Выполнение действий на рекурсивном спуске

Пример.

Алгоритм вычисления факториала. Введем дополнительно 2 параметра:

P-для выполнения операции умножения накапливаемого факториала на

очередной множитель (до рекурсивного вызова)

m-для обеспечения независимости рекурсивной функции от имени конкретной глобальной переменной, т.е. для повышения универсальности функции.

Program Factorial;

var n:integer;

function Fact_dn (p:longint; i, m,:integer):longint;

begin

p:=p* i; {накопление факториала стоит до оператора рекурсивного}

{ вызова, сл-но вычисление выполняется на спуске}

if i=m then Fact_dn:=p

else Fact_dn:=Fact_dn(p, i+1, m)

end;

Begin

write(`введите число');

readln(n);

writeln(`факториал n!=', Fact_dn(1,1,n));

End.



Текущий уровень рекурсии	Рекурсивный спуск	Рекурсивный возврат
0	Ввод (n=5)		Fact_dn(1,1,5)	Вывод n!=120
1	P:=1*1 (1)	I:=1	Fact_dn(1,2,5)	Fact_dn:=120
2	P:=1*2 (2)	I:=2	Fact_dn(2,3,5)	Fact_dn:=120
3	P:=2*3 (6)	I:=3	Fact_dn(6,4,5)	Fact_dn:=120
4	P:=6*4 (24)	I:=4	Fact_dn(24,5,5)	Fact_dn:=120
5	P:=24*5 (120)	I:=5	Fact_dn:=120	Fact_dn:=120

Выполнение действий на рекурсивном возврате

Приведем программу вычисления факториала, использующую функцию Fact_up, в которой рекурсивный вызов и оператор накопления факториала разделены явным образом.

Program Factorial;

var n: integer;

function fact_up (i: integer): longint;

var p: longint;

begin

if i=1 then p:=1

else p:=fact_up(i-1);

fact_up:= p*i; {накопление факториала стоит}

{после оператора рекурсивного}

{вызова. сл-но вычисление вы-}

{выполняется на возврат}

end;

Begin

write (`введите число n: ');

readln (n);

writeln (`факториал n!=',fact_up(n));

END.

Приведём таблицу трассировки по уровням рекурсии.

Текущий уровень рекурсии	Рекурсивный спуск	Рекурсивный возврат
0	ввод (n=5); Fact_up(5)	ввод n!=120
1	i =5; p:=fact_up(4)	Fact_up:=24*5 (120)
2	i =4; p:=fact_up(3)	Fact_up:=6*4 (24)
3	i =3; p:=fact_up(2)	Fact_up:=2*3 (6)
4	i =2; p:=fact_up(1)	Fact_up:=1*2 (2)
5	i =1; p:=1;	Fact_up:=1*1 (1)

Выполнение действий как на рекурсивном спуске, так и на возврате

Пример. Вывести на печать символы введённой строки 'HELLO' в Обратном направлении.

Program Reverse;

Procedure Rev;

Var Ch: char;

Begin

If not eoln then

Begin

Read (Ch);

Rev;

Write (Ch);

End

End;

Begin

Rev

End.

Текущий Уровень рекурсии	Рекурсивный спуск	Рекурсивный возврат
0	Rev;
1	Eoln=false; ввод: `н'; Rev;	Вывод: 'н';
2	Eoln=false; ввод: `e'; Rev;	Bывод: `e';
3	Eoln=false; ввод: `e'; Rev;	Вывод: `L';
4	Eoln=false; ввод: `e'; Rev;	Вывод: `L';
5	Eoln=false; ввод: `o'; Rev;	Вывод: `o';
6	Eoln:=true;

Задача о ханойских башнях

В центре мира в вершинах равностороннего треугольника в землю вбиты три алмазных шпиля. На одном из них надето 64 золотых диска убывающих радиусов(самый большой - нижний). Трудолюбивые буддийские монахи день и ночь переносят диски с одного шпиля на другой. При этом диски надо переносить по одному и нельзя класть большой диск на меньший. Когда все диски перенесут на другой шпиль, наступит конец света(задачу и рассказ придумал математик Э.Люка в 1883 году).

Оставляя временно вопрос о конце света поищем алгоритм для перенесения (всех) дисков с одного шпиля на другой.

Т.е. Задача: Даны три столбика- A,B,C. На столбике А один на другом находятся четыре диска разного диаметра, пронумерованные сверху вниз. Причём они располагаются так, что каждый меньший диск находится на большем. Требуется переместить эти четыре диска на столбик B, сократив их взаиморасположением. Столбик С разрешается использовать как вспомогательный. При решении за один шаг допускается перемещать только один из верних дисков какого-либо столбика. Кроме того, больший диск никогда не разрешается класть на диск меньшего размера.

Идея рекурсивного алгоритма: если алгоритм Р(m, a, b, c) должен перенести верхние m дисков со шпиля а на шпиль b, то легко пишем алгоритм

P(m, a, b,c)

Если m=1, то перенести верхний диск со шпиля А на шпиль В

Иначе Р(m-1,a, c, b);

P(1, a, b, c);

P(m-1,c,b, a);

«По человечески» этот алгоритм очень понятен если m=1, то перенести один диск с А на В.

Если же m>1, то перенесём временно m-1 верхних дисков с А на С.

Потом перенесём один оставшийся диск с А на В и, наконец, перенесём m-1 дисков, хранящихся на С, на шпиль В.

Что касается перенесения m-1 дисков, то для этого подойдёт тот же алгоритм, но переносимых дисков.

Т.о., мы перейдём от m к m-1

от m-1 к m-2

от m-2 к m-3 и т.д.

и дойдём до единицы.

Чтобы записать этот алгоритм на каком-либо языке программирования обозначим шпили А, В, С цифрами 0, 1, 2 и будем печатать нужные переносы дисков.

Перенос со шпиля А на В будет изображаться надписью 01, с В на С - надписью 12 и т.п.

Program HANOJ;

var n:integer;

procedure P(m, a, b, c:integer);

begin

if m=1 then write(a, `', b, ` `)

else begin

P(m-1, a, c, b);

P(1, a, b, c);

P(m-1, c, b, a)

end

end;

Begin

readln(n); write(`n=', n); P(n, 0, 1, 2);

End.

При n=4 эта программа напечатает

02 01 21 0 2 10 1 2

02 01 21 20 10 2 1

02 01 21

0.	P1(4,0,1,2)
1.		P1(3,0,2,1)
2.			P1(2,0,1,2)
3.				P1(1,0,2,1)
4.				P2(1,0,1,2)
5.				P3(1,2,1,0)
6.			P2(1,0,2,1)
7.			P3(2,1,2,0)	P1(1,1,0,2)
8.				P2(1,1,2,0)
9.				P3(1,0,2,1)
10.		P2(1,0,1,2)
11.		P3(3,2,1,0)	P1(2,2,0,1)	P1(1,2,1,0)
12.				P2(1,2,1,0)
13.				P3(1,1,0,2)
14.			P2(1,2,1,0)
15.			P3(2,0,1,2)	P1(1,0,2,1)
16.				P21,0,1,2)
17.				P3(1,2,1,0)

При n=3 эта программа напечатает:

01 02 12 01 21 20 21 01

1.	P1(3,0,1,2)
2.		P1(2,0,2,1)
3.			P1(1,0,1,2)
4.			P2(1,0,2,1)
5.			P3(1,1,2,0)
6.
7.		P2(1,0,1,2)
8.		P3(2,2,1,0)	P1(1,2,0,1)
9.			P2(1,2,1,0)
10.			P3(1,0,1,2)

Для нечетного n диски перекладываются на соседний шпиль по часовой стрелке, а для четного - против.

Задачи

Задача 1.

Написать рекурсивную программу вычисления n-й степени числа А.

Воспользуемся определением n-й степени числа х:

Аⁿ=A*A*A*…..*A=A^n-1*A

Из определения следует, что для того, чтобы вычислить n-ю степень числа, необходимо знать значение (n-1)-й степени этого числа. Если же значение показателя степени 0, то значение степени равно 1.

Опишем рекурсивную функцию St, параметрами которой являются значения m и х.

Роль “заглушки” будет играть отношение m=0.

Program Z1;

Var A, n: integer;

Function St(x, m: integer): integer;

begin

if m=0 then St:=1

else St:=St(x, m-1)*x;

end;

Begin

writeln(` ввод основания А');

writeln(`ввод показателя n');

writeln (n, `-я степень числа, А, 'равна', St(A, n))

End.

Текущий Уровень рекурсии	Рекурсивный спуск	Рекурсивный возврат
0	ввод(а=2, n=3), STEP(2, 3)	Вывод Аn=23=8
1	m=3, STEP:= STEP(2, 2)*2	STEP:=4*2
2	m=2, STEP:= STEP(2, 1)*2	STEP:=2*2
3	m=1, STEP:= STEP(2, 0)*2	STEP:=1*2
4	m=0, STEP:=1

Задача 2

Написать рекурсивную программу вычисления n- го члена арифметической прогрессии.

Для вычисления n-го члена арифметической прогрессии необходимо знать значение ее первого члена и значение разности d:

a_n=a_n-1+d.

Т.е., чтобы найти n-й член, нужно последовательно вычислить все предыдущие члены от (n-1)-го до 2-го. Опишем функцию ar_pr, (параметром которой является номер вычисляемого лена арифметической прогрессии), принимающую значения вещественного типа.

Program Z2;

var a1, d: real;

n: integer;

Function ar_pr (l: integer): real;

begin

if l=1 then ar_pr:=a1

else ar_pr:=ar_pr(l-1)+d;

end;

Begin

writeln(`ввод 1-го члена арифметической прогрессии а1');

readln(a1);

writeln(`ввод разности арифметической прогрессии d');

readln(d);

writeln (`ввод номера члена прогрессии n');

readln(n);

writeln(n, `-й член арифметической прогрессии равен', ar_pr(n), `.')

End.

Текущий Уровень рекурсии	Рекурсивный спуск	Рекурсивный возврат
0	ввод (a1=5, d=10, n=6) ar_pr(6)	Bывод ar_pr(6)=55
1	l=6 ar_pr:= ar_pr(5)+10	ar_pr:=45+10
2	l=5 ar_pr(4)+10	ar_pr:=35+10
3	l=4 ar_pr:= ar_pr(3)+10	ar_pr:=25+10
4	l=3 ar_pr:= ar_pr(2)+10	ar_pr:=15=10
5	l=2 ar_pr:= ar_pr(1)+10	ar_pr:=5+10
6	l=1 ar_pr:= a1	ar_pr:=5

Задача 3

Написать программу вычисления суммы n первых членов арифметической прогрессии.

Для вычисления суммы n первых членов нужно знать сумму (n-1) первых членов и значение n-го члена:

S_n=S_n-1+a_n

Опишем рекурсивную функцию SUM, принимающую вещественные значения, решающую поставленную задачу. В ней для вычисления n- го члена арифметической прогрессии используется функция, описанная в предыдущем примере.

Program V;

Var a1, d, s:real;

n: integer;

Function ar_pr (l: integer): real;

begin

if l=1 then ar_pr:=a1

else ar_pr:= ar_pr(l-1)+d;

end;

Function SUM(p: integer):real;

begin

if p=1 then SUM:=a1

else SUM:=SUM(p-1)+ ar_pr(p)

end;

Begin

writeln(`a1'); readln(a1);

writeln(`d'); readln(d);

writeln(`n'); readln(n);

writeln(SUM(n))

End.

Приведем таблицу трассировки по уровням рекурсии при a1=2

d=5 n=5



Текущий Уровень рекурсии	Рекурсивный спуск	Рекурсивный возврат
0	ввод (a1=2, d=5, n=5) SUM(5)	Bывод SUM(5)=60
1	n=5 SUM:= SUM(4)+ ar_pr(5)	SUM:=38+ar_pr(4)+5=60
2	n=4 SUM:= SUM(3)+ ar_pr(4)	SUM:=21+ar_pr(3)+5=38
3	n=3 SUM:= SUM(2)+ ar_pr(3)	SUM:=9+ar_pr(2)+5=21
4	n=2 SUM:= SUM(1)+ar_pr(2)	SUM:=2+ar_pr(1)+5=9
5	n=1 SUM:=2	SUM:=2

Задача 4

Написать рекурсивную программу поиска минимального элемента массива.

Опишем функцию P_min, которая определяет минимум среди первых n элементов массива. Параметрами этой функции является количество элементов в рассматриваемой части массива n и значение последнего элемента этой части массива - a[n]. При этом если n>2 то результатом является минимальное из двух чисел - a[n] и минимального числа из первых (n-1) элементов массива. Чтобы найти минимум всех элементов массива, нужно обратиться к функции P_min, указав в качестве параметров значение последнего его элемента. Минимальное из 2-х чисел определяется с помощью функции min, параметрами которой являются эти числа.

Program Example_4;

Const n=10;

a: ar=(4, 2, -1, 5, 2, 9, 4, 8, 5, 3);

type ar=array[1..n] of integer;

Function min(a, b:integer):integer;

begin

if a>b then min:=b

else min:=a;

end;

Function P_min(n, b: integer):integer;

begin

if n=2 then P_min:=min(a[2], a[1])

else P_min:=min(a[n], P_min(n-1, a[n]));

end;

Begin

writeln(`минимальный элемент массива-`, P_min(n, a[n])

End.

Задача 5 «Лабиринт»

Может ли путник выйти из лабиринта? Если может, то напечатать путь от выхода до начального положения путника.

Лабиринт задан массивом А размером 40х40, в котором:

А[k,m]=0, если клетка [k,m] «проходима»

А[k,m]=1, если клетка [k,m] «непроходима».

Начальное положение путника задаётся в проходимой клетке [i,j]. Путник может перемещаться из одной проходимой клетки в другую, если они имеют общую сторону. Путник выходит из лабиринта, когда попадает в граничную клетку (т.е. клетку [k,m], где k или m равны 1 или 40.

Решение распадается на 2 части: поиск пути для выхода и печать обратного пути - от выхода до начального положения путника.

Простейшее решение первой части такое:

- Запишем в клетку A[i,j], где вначале находится путник, число 2 и положим k=2.

- Просмотрим все клетки А лабиринта. Для каждой из них, если в ней записан 0, прочтём четырех из её соседей. Если хоть в одной из соседних клеток записано число k (сейчас ещё равное 2), то в рассматриваемую клетку А впишем число k+1/

- Теперь увеличим k:=k+1 и снова рассмотрим все клетки А. Этот процесс закончится когда-либо число будет вписано в граничную клетку (выхода нет). Просмотров всего массива будет столько, сколько клеток окажется в кратчайшей дорожке.

Предыдущий алгоритм легко улучшить. На каждом шаге будем по-прежнему рассматривать все клетки А лабиринта. Если в клетке записан 0, а в какой-либо соседней находится число k>=2, то впишем в клетку А число k+1. Ясно, что это тоже решение задачи. Но если повезет, то здесь решение найдётся быстрее.

Заведомо эффективнее будет программа, которая начиная с исходной клетки, (куда вначале записывается число 2), ищет первого же свободного (т.е. с числом 0) соседа. Вписывает в него 3 и ищет его свободного соседа, чтобы вписать в него 4 и т.д.

Процесс прервется либо при достижении границы (выход найден), либо оттого, что свободных соседей не будет (тупик).

Если тупик возникает в соседней клетке (где записано число 2), то выхода нет. Если же тупиковая клетка иная и в неё вписано число k>2, то следует вписать в неё число 1 (сделать её непроходимой) и перейти к её соседней клетке с числом k-1. такая клетка есть и единственна.

!!! Программу для решения задачи о лабиринте можно сильно сократить. Если записать её рекурсивно.

Program labirint;

Const m=15;

N=15;

Var i, j: integer;

otvet: _oolean;

A: array [1..m, 1..n] of byte.

Procedure L (i, j: integer);

begin

if not(otvet) then

if a[i, j]=0 then begin

if (i=1) or (i=m) or (j=1) or (j=m) then otvet:=true;

A[i, j]:=1; L(i, j-1); L(i, j+1); L(i-1, j); L(i+1, j);

If otvet then writeln (i, ` `,j)

end;

end;

Begin

For i:=1 to m do

For j:=1 to n do begin

Write(`A[`, i, ',',j, ']:=');

Readln (a[i,j])

end;

writeln;

writeln(`i, j:=');

readln(i, j);

writeln;

otvet:= false;

L(i,j);

If not(otvet) then writeln(`нет выхода')

End.

Задача 6 «Быстрая сортировка»

Реализация метода быстрой сортировки массива является прекрасным примером использования рекурсии. Этот метод был разработан в 1962 году профессором Оксфордского университета К. Хоаром.

Принцип метода:

Выбираем центральный элемент массива А и записываем его в переменную В. Затем элементы массива просматриваем поочередно слева-направо и справа-налево. При движении слева-направо ищем элемент А[i], который будет больше или равен В, и запоминаем его позицию. При движении справа-налево ищем элемент A[i], который будет меньше или равен В, и также запоминаем его позицию.

Найденные элементы меняем местами и т.д., пока при очередной итерации поиска встречные индексы i и j не пересекутся.

A В=7 n=10

1 2 3 4 5 6 7 8 9 10

После этого первый этап считается законченным, после чего элементы исходного массива окажутся разделёнными на 2 части относительно значения В - все элементы, которые <=В, будут располагаться слева от границы пересечения индексов i и j, а все элементы, которые >=В, будут располагаться справа от границы. Т.о., относительно значения В массив получается отсортированным, но левая и правая его части ещё не упорядочены.

2. На втором этапе повторяются действия первого этапа для левой и правой частей массива в отдельности. В результате массив окажется разбитым уже на 4 непересекающиеся по сортировке части, которые можно упорядочить по отдельности.

3. На 3 этапе повторяются действия первого этапа в отдельности для каждой из 4-х частей и т.д., пока длина сортируемых частей не станет равной одному элементу и, следовательно все элементы массива будут уже упорядочены.

Поскольку на каждом этапе повторяются одни и те же действия, но в разных индексных рамках массива, то их удобно оформить в виде самовызывающейся рекурсивной процедуры, которая используется в следующей программе:

Program QuickSort;

Uses Crt;

Const n=20;

Var A:array [1..n] of integer;

i: word;

Procedure QSort (L, R: word);

Var B, x: integer;

i, j: word;

begin

B:=A[(L+R) div 2];

i:=L; j:=R;

while i<=j do begin

while A[i]<B do i:=i+1;

while A[i]>B do j:=j-1;

if i<=j then begin

x:=A[i];

A[i]:=A[j];

A[j]:=x;

i:=i+1;

j:=j-1

end;

if L<R then QSort(L, j);

if i<R then QSort(i, R);

end;

Begin

ClrScr;

Writeln(` ведите элементы массива');

For i:=1 to n do read (A[i]);

Readln;

QSort(1,n);

Writeln (` Отсортированный массив:');

For i:=1 to n do write (A[i]:8);

End.

Механизм работы рекурсивной процедуры QSort продемонстрируем следующей схемой:

QSort (1, 10)

1-й уровень

A исходный массив

1 2 3 4 5 6 7 8 9 10

9	4	12	1	7	6	9	4	2	10

L=1 R=n

В=7

- - - - - - - - - - -- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

2=й уровень

QSort (1,5) QSort(6, 10)

L=1 R=5 L=6 R=10

1 2 3 4 5 6 7 8 9 10

B=12

B=4

j=2 i=4 j=9 i=10

i=R > вызов не

не выполняется

Задача 7

В написанном выражении ((((1?2)?3)?4)?5)?6)….?N вместо каждого знака ? вставить знак одной из четырёх операций: + - * / так, чтобы результат вычислений равнялся S (при делении дробная часть в частном отбрасывается). Найти все решения.

Обобщим задачу. Пусть требуется так расставить знаки

'+', '-', '*', '/' в выражении ((1?2)?3)...?N,

чтобы в результате выполнения получилось значение S.

Алгоритм.

Конкретную расстановку знаков будем кодировать массивом

c: array [0..(N-1)] of Integer

('+' -> 0,

'-' -> 1,

'*' -> 2,

'/' -> 3).

Чтобы сгенерировать все возможные комбинации знаков, требуется, фактически, построить все четверичные числа длины N-1. Будем строить их от 00..0 до 33..3. Элемент c[0] будет фиктивным и условие c[0] <> 0 сигнализирует об окончании генерации.

Алгоритм генерации, по сути, есть последовательное увеличение на 1 четверичного числа, хранящегося в _ивеивее (см. действия с многозначными числами).

}

program Signs;

uses

Crt;

const

N = 6;

S = 35;

var

I, p: Integer;

c: array [0..(N-1)] of Integer;

procedure WriteOneSign(Sgn: Integer);

begin

case Sgn of

0: Write(`+');

1: Write(`-`);

2: Write(`*');

3: Write(`/');

end;

end;

procedure OutputSigns;

var

i: Integer;

begin

for I:= 1 to N-2 do

Write(`(`);

Write(`1');

for I:= 1 to N-2 do

begin

WriteOneSign(c[i]);

Write(i+1, `)');

end;

WriteOneSign(c[N-1]);

Writeln(N, `=', S);

end;

begin

ClrScr;

for I:= 0 to N-1 do

c[i]:= 0;

while c[0] = 0 do

begin

{ Вычисление суммы при текущей комбинации знаков }

p:= 1;

for I:= 2 to N do

case c[i-1] of

0: Inc(p, i);

1: Dec(p, i);

2: p:= p * I;

3: p:= p div I;

end;

if p = S then OutputSigns;

{ Следующая комбинация }

Inc(c[N-1]);

I:= N-1;

while c[i] = 4 do

begin

c[i]:= 0;

Inc(c[i-1]);

Dec(i);

end;

end; { while }

end.

Задача 8 « О скобках»

Поострить все слова длины n>0 в алфавите скобок «(» и «)», представляющие правильные скобочные записи.

Алгоритм состоит в следующем:

Будем рекурсивно строить слова из скобок. Также для соблюдения верности расстановки будем хранить код строки Code: при новой скобке '(' Code увеличивается на 1, а при новой скобке ')' Code уменьшается на 1 (в конце должно выполняться Code = 0).

Кроме того, на каждом шаге должно выполняться Code > 0. По сути, на каждом шаге значение Code есть разность количества открывающих и закрывающих скобок.

Пусть на некотором шаге имеем слово S. Пробуем добавить скобки:

'(' - возможно, если до конца полного слова (длины N), возможно будет закрыть все открывающие скобки, т.е. если N - Length(S) > Code;

')' - возможно, если впереди есть хотя бы одна не закрытая открывающая скобка, т.е. если Code > 0.

При достижении длины слова, равной N, выводим слово.

program Problem8;

uses

Crt;

const

N = 10; { N должно быть четным! }

var

S: String;

Code: Integer;

procedure BuildWords;

begin

if Length(S) = N then

begin

if Code = 0 then Writeln(S)

end

else

begin

{ '(' }

if N - Length(S) > Code then

begin

S:= S + '(';

Inc(Code);

BuildWords;

{ Откат }

Dec(Code);

S[0]:= Pred(S[0]); { уменьшение длины слова на 1 }

end;

{ ')' }

if Code > 0 then

begin

S:= S + ')';

Dec(Code);

BuildWords;

{ Откат }

Inc(Code);

S[0]:= Pred(S[0]); { уменьшение длины слова на 1 }

end;

end;

end;

Задача 9.

Дана строка S и набор слов A[1], …, A[n]. Разбить строку S на слова набора всеми возможными способами.

Решение:

Общий алгоритм состоит в следующем. Рекурсивно пробуем разбить последовательно (слева направо) строку S на слова и проверить, чтобы они содержались в наборе и, к тому же, не повторялись.

Точнее.

Решение оформлено в виде рекурсивной процедуры Solve(pos: Integer), которая производит разбиение части строки S, начиная с символа pos+1. Принцип ее работы таков. Пробуем выделять слова S[(pos+1)..(pos+1)], S[(pos+1)..(pos+2)], …, S[(pos+1)..Length(S)]. Каждое такое слово ищем в наборе и проверяем, не использовано ли оно на текущий момент в текущем частичном разбиении. Если все верно, добавляем слово (а, точнее, его индекс) в разбиение и запускаем подпроцедуру.

В задаче приходится много раз искать слова в наборе. Это, явно, гораздо быстрее делать двоичным поиском (за время O(log₂N)). Для этого требуется предварительная сортировка набора А[ ]. Но поскольку при сортировке приходится обменивать значения элементов, а обмен строк (по сути, обмен массивов) - дело довольно долгое, вместо этого удобнее сортировать указатели на слова:

A[i] - i-ое слово до сортировки,

p[i] - указатель на i-ое слово после сортировки, фактически значение i-ого слова после сортировки будет A[p[i]].

Например, если вначале A = {`Z', `A', `CC'}, то после сортировки массив А не изменится но массив p будет выглядеть так: p = {2, 3, 1} (т.к. отсортированный массив должен был быть таким: A = {`A', `CC', `Z'}).

После сортировки возможен двоичный поиск в наборе. Он оформлен в виде функции FindWord(W: String): Integer, где W - искомое слово. Функция возвращает либо номер искомого слова (т.е. W=A[p[FindWord(W)]]), либо 0, если такого слова нет.

Логический массив used[ ] …

program Problem9;

uses

Crt;

const

MaxN = 100;

MaxWordLength = 10;

type

ShortStr = String[MaxWordLength];

var

N, i: Integer;

S: String;

A: array [1..MaxN] of ShortStr;

p: array [1..MaxN] of Integer;

used: array [0..MaxN] of Boolean;

razb: array [0..MaxN] of Integer;

{ Двоичный поиск заданного слова в

отсортированном наборе }

function FindWord(W: String): Integer;

var

L, R, C: Integer;

begin

L:= 1;

R:= N;

while R - L > 1 do

begin

C:= (L + R) div 2;

if A[p[C]] > W then

R:= C

else

L:= C;

end;

FindWord:= 0;

if A[p[L]] = W then

FindWord:= L

else

if A[p[R]] = W then

FindWord:= R;

end;

{ Сортировка указателей на слова набора }

procedure SortWords;

var

i, j, tmp: Integer;

begin

{ Пузырек;) }

for j:= N-1 downto 2 do

for i:= 1 to j do

if A[p[i]] > A[p[i+1]] then

begin

tmp:= p[i];

p[i]:= p[i+1];

p[i+1]:= tmp;

end;

end;

{ Рекурсивная процедура-решение задачи }

{ pos - позиция последнего занятого символа в S }

procedure Solve(pos: Integer);

var

i: Integer;

begin

if pos = Length(S) then

begin

for i:= 1 to razb[0] do

Write(A[p[razb[i]]], ' ');

Writeln;

End

else

begin

for i:= pos + 1 to Length(S) do

begin

{ Можно ли добавить выделенное слово? }

if not used[FindWord(Copy(S, pos+1, i - pos))] then

begin

Inc(razb[0]);

razb[razb[0]]:= FindWord(Copy(S, pos+1, i - pos));

used[razb[razb[0]]]:= True;

Solve(i);

{ Откат }

used[razb[razb[0]]]:= False;

Dec(razb[0]);

end;

end;

end;

end;

begin

ClrScr;

Readln(S);

Readln(N);

for i:= 1 to N do

begin

Readln(A[i]);

p[i]:= i;

used[i]:= False;

end;

ClrScr;

SortWords;

razb[0]:= 0;

used[0]:= True;

Solve(0);

end.

Задача 10.

Задана матрица из натуральных чисел А[1..n, 1..m], n<=m. За каждый проход через клетку (i, j) взимается штраф A[i,j]. Необходимо определить минимальный суммарный штраф, с которым можно пройти из клетки (1,1) в клетку (n, m). При этом из текущей клетки можно переходить в любую из 3 соседних клеток, находящихся в строке с номером, на 1 большим, чем текущий номер строки.

Program problem 10;

Var

N, M, i, j: byte;

A:array [1..100, 1..100] of byte;

MinP: array [1..100, 1..100] of word;

Procedure Solution (i, j: byte);

begin

if i=N then Exit;

{Where can we go from (i, j) ?}

{Down and left}

if (j>1) and (MinP[i+1, j-1] > MinP [i, j] + A[i, j]) then

begin

MinP[i+1, j-1]:= MinP[i, j] + A[i, j];

Solution(i+1, j-1);

end;

{Down}

if MinP[i+1, j] > MinP[i, j] + A[i, j] then

begin

MinP[i+1, j]:= MinP[i, j] + A[i, j];

Solution(i+j, j);

end;

{Down and right}

if (j < M) and (MinP[i+1, j+1] > MinP[i, j] + A[i, j] then

begin

MinP[i+1, j+1]:= MinP[i, j] + A[i, j];

Solution(i+j, j+1);

end;

end;

Begin

{input data}

Writeln (` input N & M …');

Readln (N, M);

Writeln (`input matrica A[`, N, `, `, M, `];

For i:=1 to N do

For j:=1 to M do

Read (A[i, j]);

{Initializing MinP}

FillChar (MinP, SizeOf(MinP), $FF);

{Solution}

MinP[1,1]:=0;

Solution(1, 1);

{Output results}

if MinP[N, M]=$FFFF then

writeln (`There isn't path from (1, 1) to (`, N, `, `, M, `).')

else

writeln (MinP[N, M] + A[N, M]);

End.

Задача 11 "Суммы"

Белорусская Республиканская олимпиада по информатике 2000.

Любое целое число N>0 можно представить в виде суммы натуральных слагаемых, каждое из которых является степенью числа 2. Суммы, различающиеся лишь порядком слагаемых, считаются одинаковыми.

Найти K - число способов, которыми можно представить число N в виде суммы натуральных слагаемых, каждое из которых является степенью числа 2.

Например,для N=7:

7=4+2+1

7=4+1+1+1

7=2+2+2+1

7=2+2+1+1+1

7=2+1+1+1+1+1

7=1+1+1+1+1+1+1

и, следовательно, K=6

Ограничения: N<=1000

Ввод из текстового файла SUM.IN N

Вывод в текстовый файл SUM.OUT

K

Пример входных и выходных данных

SUM.IN

132

SUM.OUT

31196

Попытаемся систематически составить подряд несколько разложений:

N=1 N=2 N=3 N=4 N=5 N=6 N=7

1 2 2+1 4 4+1 4+2 4+2+1

1+1 1+1+1 2+2 2+2+1 4+1+1 4+1+1+1

2+1+1 2+1+1+1 2+2+2 2+2+2+1

1+1+1+1 1+1+1+1+1 2+2+1+1 2+2+1+1+1

2+1+1+1+1 2+1+1+1+1+1

1+1+1+1+1+1 1+1+1+1+1+1+1

Введем обозначение

K(i)- количество разложений числа i по условиям задачи

Сразу замечаем, что

K(1)=1, K(2)=2

K(i)=K(i-1), если i - нечетное

(в каждой из строк для соответствующего предыдущего разложения добавляется +1, а количество строк не меняется)

Осталось выяснить, как искать K(i) для четного i. Естественно предположить, что K(i) зависит от K(i-1) следующим образом

K(i)=K(i-1) + X

То есть количество разложений i-того числа, равно количеству разложений i-1-го числа плюс еще сколько то. Сколько же ?

Для примера рассмотрим детальнее разложения при N=6 и отметим те строки, которые перешли в разложение N=6 из разложения N=5 добавлением +1:

N=5 N=6

4+1 4+2

2+2+1! 4+1+1

2+1+1+1 2+2+2

1+1+1+1+1! 2+2+1+1

! 2+1+1+1+1

! 1+1+1+1+1+1

Теперь выпишем строки, оставшиеся непомеченными, то есть те, которые добавлены по другому закону (как раз и определяющему наше X):

4+2

2+2+2

Интересно, что все они составлены из четных чисел. Поделим все эти числа на 2, получим

2+1

1+1+1

А теперь обращаем внимание, что это как раз разложение числа 3, которое можно получить из числа 6 тоже делением на 2. Итого получаем X=K(i div 2)

А окончательное рекуррентное соотношение имеет вид

/ K(i-1), если i нечетное

K(i)= <

\ K(i-1)+K(i div 2), если i четное

Проверим наши соображения еще на одном тестовом примере

N=7 N=8

4+2+1 8

4+1+1+1 4+4

2+2+2+1 4+2+2

2+2+1+1+1! 4+2+1+1

2+1+1+1+1+1! 4+1+1+1+1

1+1+1+1+1+1+1 2+2+2+2

! 2+2+2+1+1

! 2+2+1+1+1+1

! 2+1+1+1+1+1+1

! 1+1+1+1+1+1+1+1

Непомеченными остались строки:

8

4+4

4+2+2

2+2+2+2

После деления всех чисел на 2 получим

4

2+2

2+1+1

1+1+1+1

А это как раз и есть разложение числа 4, которое может быть получено из исходного N=8 делением на 2. И тогда полное решение задачи может состоять в рекуррентном заполнении массива K[1..N] и выводе значения K[N].

Можно также заметить, что k[2]=k[1]+k[2 div 2]=k[1]+k[1]=2

То есть k[2] можно вычислять общим порядком. Достаточно задать только начальное значение k[1]. Вот полное (!) решение данной задачи:

program by00m1t2;

var

N,i: longint;

K: array [1..1000] of longint;

begin

assign (input,'sum.in'); reset(input);

assign (output,'sum.out'); rewrite(output);

readln (N);

k[1]:=1;

for i:=2 to N do

if odd(i)

then k[i]:=k[i-1]

else k[i]:=k[i-1] + k [i div 2];

writeln(K[N]);

close (input); close (output);

end.

Замечание: здесь Odd(i) - стандартная функция, определяющая, является ли число i нечетным.

Задача 12 "Отбор в разведку"

Из N солдат, выстроенных в шеренгу, требуется отобрать нескольких в разведку. Для того, что бы сделать это, выполняется следующая операция: если солдат в шеренге больше чем 3, то удаляются все солдаты стоящие на четных позициях, или все солдаты, стоящие на нечетных позициях. Эта процедура повторяется до тех пор, пока в шеренге останется 3 или менее солдат. Их и отсылают в разведку. Подсчитайте сколькими способами могут быть сформированы таким образом группы разведчиков ровно из трех человек.

Ограничения:

0 < N <= 10 000 000

Ввод и вывод

Входной файл содержит число N. Выходной файл содержит решение - количество вариантов

Пример ввода #1

10

Вывод для примера ввода #1

2

Пример ввода #2

4

Вывод для примера ввода #2

0

Обозначим K(N) - количество способов, которым можно сформировать группы разведчиков из N человек в шеренге.

По условию задачи K(1) = 0, K(2)=1, K(3)=1

То есть из трех человек можно сформировать только одну группу, из одного или двух - ни одной.

Рассмотрим теперь случай с произвольным числом N солдат в шеренге.

Если N число четное, то применяя определенную в задаче операцию удаления солдат в шеренге, мы получим в качестве оставшихся либо N div 2 солдат стоящих на четных позициях, либо N div 2 солдат, стоящих на нечетных позициях. А общее количество способов можно найти по формуле: K(N) = 2 * K(N div 2) (если N четное)

Количество способов сформировать группу разведки из солдат, оставшихся на четных позициях плюс количество способов сформировать группу разведки из солдат, оставшихся на нечетных позициях.

Если N число нечетное, то у нас останется либо N div 2 солдат стоявших на четных позициях, либо (N div 2)+1 солдат, стоявших на нечетных позициях. А общее количество способов можно найти по формуле: K(N) = K(N div 2) + K((N div 2)+1) (если N нечетное)

Таким образом, ококнчательно рекуррентное соотношение имеет вид: / 0, если N=1 или N=2

/ 1, если N=3

K(N) = <

\ 2 * K(N div 2), если N - четное

\ K(N div 2) + K((N div 2)+1), если N - нечетное

Осталось только обратить внимание на следующие факты:

1. N до 10 000 000 - следовательно нам не удастся разместить в статической памяти массив для хранения всех значений рекуррентной величины K(N)

2. на самом деле нам для вычисления ответа для конкретного N нужно знать много меньше, чем все значения K(N).

Поэтому в данном случае очень удобно применить рекурсивное вычисление рекуррентной величины K(N).

function K(N:longint):longint;

begin

if N<3

then K:=0

else if N=3

then K:=1

else if odd(N)

then K:= K(N div 2) + K(N div 2 + 1)

else K:= 2 * K(N div 2);

end;

Полное же решение данной задачи выглядит следующим образом:

{$m 65520,0,0}

program problem9;

var

N: longint;

function K(N:longint):longint;

begin

...

end;

begin

assign(input,'input.txt'); reset(input);

assign(output,'output.txt'); rewrite(output);

read(N);

writeln(K(N));

close(input); close(output);

end.

Задача 13"Видеосалон"

Владелец видеосалона решил получить максимальный доход от своего бизнеса. В видеосалоне имеется неограниченное количество пустых видеокассет. Продолжительность каждой видеокассеты равна L. У владельца есть возможность записать на видеокассеты N фильмов, продолжительностью A(1),..., A(N), A(i)< К. число это Определить кассет. наибольшее прокат на взять вынужден был клиент фильмов всех просмотра для чтобы кассеты, фильмы записать образом таким стремится видеосалона Владелец целиком. пишутся кассету Фильмы кассете. этой записанных не фильмов, из один целиком помещается которое место, пустое такое кассете оставить может и дважды фильм видеокассету одну записывать он этом При>

Ввод (из файла Input3.txt)

L

N

A[1]

...

A[N]

где A[i], L, N - натуральные, L<=1000, N<=100

Вывод (в файл output3.txt)

K

Рассмотрим пример. Пусть

L=100 (продолжительность видеокассеты).

N=8 (количество различных фильмов)

A[i]: 2, 2, 3, 3, 97, 97, 97, 97 (продолжительности восьми фильмов)

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

1: 97(5) + 2(1)

2: 97(6) + 2(2)

3: 97(7) + 3(1)

4: 97(8) + 3(2)

И при таком раскладе его оплата за прокат всех фильмов была бы минимальна.

Но коварный владелец видеосалона записывает кассеты САМ. Как он их запишет, по - вашему? Было бы правильно, что бы вы прежде чем читать дальше, придумали "хитрый" расклад самостоятельно. А еще лучше и способ "хитрого" алгоритма записи фильмов на видеокассеты.

Ну а сейчас мы попробуем вместе составить этот "хитрый расклад". Первая кассета останется такой же:

1: 97(5) + 2(1)

А вот на вторую владелец видеосалона предпочтет писать только один новый фильм - 2(2):

2: 97(5) + 2(2)

Аналогично он поступит и с 3-ей и с 4-ой кассетами:

3: 97(5) + 3(1)

4: 97(5) + 3(2)

Итак клиент уже вынужден купить 4 кассеты 1-4, а ведь он еще не видел трех самых лучших фильмов: 97(6), 97(7), 97(8), для записи которых в "хитром" раскладе владельца видеосалона потребуется покупать еще три кассеты:

5: 97(5) + 2(1)

6: 97(6) + 2(1)

7: 97(7) + 2(1)

Чем дописывать эти три кассеты из имеющихся "короткометражных" фильмов в принципе безразлично, например, фильмом 2(1).

С данным раскладом вроде разобрались. А как с другими? И каков алгоритм "хитрой" записи фильмов? И, наконец, как узнавать требуемое количество видеокассет K по исходным данным L, N, A[i]?

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

Поскольку, как мы заметили из примера, более продолжительные фильмы более существенны для процесса записи, исходные данные переупорядочим так, что бы фильмы шли в порядке убывания их длин.

Рассмотрим "под микроскопом" одну видеокассету.

Она имеет продолжительность записи L (пусть минут, для определенности). Тогда мы можем рассматривать одну кассету как одномерный массив S[1..L]. И тогда каждой из вышеупомянутых сумм соответствует ровно одна позиция в этом массиве. Суммы, превышающие L, будем отбрасывать (поскольку они нас не интересуют, как комбинации фильмов, не помещающиеся на одной кассете). Будем хранить в S[j] единичку, если запись предыдущего фильма закончилась в позиции j.

Тогда для каждого нового фильма мы должны попытаться приписать его ко всем возможным позициям примерно так:

Если s[j]<>0 и j+a[i]<=L то s[j+a[i]]:=1;

То есть, если мы нашли место куда можно "приткнуть" фильм и он поместиться до конца кассеты (a[i]-это продолжительность текущего фильма), то помечаем, позицию, в которой закончиться этот фильм.

При этом, перед первым фильмом S[j]=0 для всех j от 1 до L, а S[0]=1 - то есть можно писать фильмы с начала кассеты.

Понятно, что вышеуказанную операцию нужно сделать для всех фильмов.

Как теперь параллельно вести учет количества вариантов?

Заведем еще один массив NS[1..L], его будем модифицировать параллельно с массивом S. Но если в S[j] мы будем отмечать только факт, что в этом месте закончена запись предыдущего фильма, то в NS[j] мы как раз будем вести учет - скольким количеством способов мы записали фильмы до этого места - следующим образом:

Если s[j]<>0 и j+a[i]<=L

то...

ns[j+a[i]]:= ns[j+a[i]] + max(1,ns[j]);

ns[j]:=0;

То есть, если мы нашли место, куда приткнуть новый фильм, то количество способов "перекочевывает" в конец записи этого фильма, при этом мы должны учитывать, что

1. количества нужно складывать - старое(ns[j+a[i]]) и новое(ns[j]

2. самый первый раз нужно просто прибавить один (max(1,ns[j]))

3. "перекочевывание" количества ns[j] означает, что после того, как мы его сложили "вперед", нужно обнулить в текущей позиции, что бы избежать "накрутки" количества вариантов.

Хорошо, теперь мы для всех сумм S[j], посчитаем, сколькими различными способами NS[j] можно их получить, используя N фильмов A[i] (i от 1 до N). А какие из этих сумм NS[j] нужно складывать, что бы получить ответ K?

Для ответа на этот вопрос заведем еще один массив: MS[1..L]. Вначале все его элементы будут равны 0. А затем будем заносить MS[j] единицу, в том случае, если мы из этой суммы формировали последующие и, стало быть, эта сумма - промежуточная, и ее не надо считать:

Если s[j]<>0 и j+a[i]<=L

то...

ms[j]:=1;

А для получения ответа K нужно складывать элементы массива ns[j] с конца, до тех пор, пока MS[j]=0:

K:=0; J:=L;

while (ms[j]=0) do

begin

K:=K+ns[j];

dec(j)

end;

writeln(K);

И, наконец, последнее замечание: вообще говоря нам нужны 2 массива S - один для текущего значения S, а другой - для следующего, что бы не приписывать фильм сам к себе на одну и ту же кассету. Но мы можем добиться того же эффекта, если будем работать с одним и тем же массивом S, но обрабатывать его для каждой песни i от последнего элемента S[L-a[i]] до к начальному S[0]:

...

for i:=1 to N do

for j:=L-a[i] downto 0 do

if (s[j]<>0) and (j+a[i]<=L)

...

Понятно, что s[j] для j>L-a[i] обрабатывать бесполезно - фильм a[i] заведомо не поместиться с этой позиции j.

Полное решение данной задачи приводится ниже:

program by96s2t3;

var

s,ns,ms: array [0..1000] of longint;

a,m: array [1..100] of integer;

i,j,N,L,K,ka,jk,jb,g,pk, ks,ix: longint;

procedure Sort;

var max: longint;

begin

for i:=1 to N-1 do

begin

max:=a[i]; k:=i;

for j:=i+1 to N do

if a[j]>max

then begin max:=a[j]; k:=j end;

a[k]:=a[i]; a[i]:=max;

end;

end;

function max(a,b:longint):longint;

begin

if a>b then max:=a else max:=b

end;

begin

assign(input,'input3.txt'); reset(input);

assign(output,'output3.txt'); rewrite(output);

read(L); read(N);

for i:=1 to N do read(a[i]);

Sort; s[0]:=1; ns[0]:=0;

for i:=1 to N do

for j:=L-a[i] downto 0 do

if (s[j]<>0) and (j+a[i]<=L)

then

begin

s[j+a[i]]:=1;

ns[j+a[i]]:=ns[j+a[i]]+max(1,ns[j]);

ns[j]:=0;

ms[j]:=1;

end;

K:=0; J:=L;

while (ms[j]=0) do

begin K:=K+ns[j]; dec(j) end;

writeln(K);

close(input); close(output);

end.

Список литературы

1. А.И. Марченко, Л.М. Марченко «Программирование в среде TURBO PASCAL 7.0»

изд. «Бином Универсал», Москва, 1998.

2. Ю.С. Бородич, А.Н. Вальвачев, А.И. Кузьмич «Паскаль для персональных компьютеров» изд. «Вышэйшая школа», Минск, 1991.

3. И.А. Бабушкина, Н.А. Бушмелева «Практикум по Турбо Паскалю» Киров, 1997.

4. Лекции Долинского (полный вариант) «Общие сведения о рекуррентных соотношениях»

5.Журнал «Репетитор» №9, Минск, 2001 г.