Turbo Pascal Site | Лабораторная работа 23

Меню:

Главная

Видео уроки

Ссылки

Лабораторная работа 23

Найдите количество положительных четных чисел, сумма которых равняется 46!

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

Попытаемся представить, как это будет выглядеть для, например, Max=9.

1	1	1	1	1	1	1	1	1
2	1	1	1	1	1	1	1
2	2	1	1	1	1	1
2	2	2	1	1	1
2	2	2	2	1
3	1	1	1	1	1	1
3	2	1	1	1	1
3	2	2	1	1
3	2	2	2
3	3	1	1	1
3	3	2	1
3	3	3
4	1	1	1	1	1
4	2	1	1	1
4	2	2	1
4	3	1	1
4	3	2
4	4	1
5	1	1	1	1
5	2	1	1
5	2	2
5	3	1
5	4
6	1	1	1
6	2	1
6	3
7	1	1
7	2
8	1
9

Как видим - количество всех возможных комбинаций сокращено за счет сортировки по убыванию каждой из последовательности слагаемых.

Поробуем представить алгоритм будущей программы:

Число элементов не превышает Max, лучше организовать массив A[1..Max]
Из такой последовательности не составит большого труда выделить только все четные или нечетные числа.
Из последовательности нескольких одинаковых чисел, увеличиваем только тот элемент массива, порядковый номер которого меньше. Самый меньший номер A[1].

Теперь рассмотрим саму программу:

For I := 1 To Max Do A[I] := 1;

подготовка массива к работе, записываем во все ячейки массива 1, так как число элементов массива совпадает с Max, то их сумма тоже совпадает с Max.

WriteLn;

Print;

печатаем пустую строку, чтобы отличить этот вариант работы программы от предыдущего, и выводим на печать весь массив процедурой Print.

K := 1;

While A[1] <> Max Do Begin

начинаем увеличение значения элементов массива с первого элемента (3), назначим текущим элементом первый.

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

K1 := 0;	2	1	1	1	1	1	1	1	1
Inc(A[K]);

начальное значение суммы элементов массива "слева" от текущего равна 0. Увеличим значение текущего элемента массива на 1.

For I := K+1 To Max Do A[I] := 0;

обнулем элементы массива "справа" от текущего элемента K, чтобы "лишние" числа не повлияли на результат.

For I := 1 To K Do K1 := K1 + A[I];

находим сумма предыдущих элементов, включая текущий.

For I := K+1 To Max-K1+K Do A[I] := 1;

дополняем остальные элементы, "справа" от текущего, до Max. Те элементы, надобность в которых отпала хранят 0.

Во втором блоке цикла находим первую ячейку, которую можно увеличить.

I := Max-K1+K;

F := True;

While (I > 0) And F Do Begin

перебираем все элементы массива, но начинаем с наименьшего, имеющего значение отличное от 0. Флаг окончания цикла - установлен. Он будет сброшен, когда выполнится условие. Цикл будет длиться, пока не кончится массив или не сбросится флаг окончания.

If A[I] < A[I-1] Then Begin

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

K1 := 0;

For J := I To Max Do K1 := K1 + A[J];

сумма оставшихся элементов пока равна нулю. Найдем сумму элементов "справа" от "перепада".

If K1 > A[I] Then F := False;

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

Dec(I);

Переходим к следующему элементу массива (уменьшаем на 1).

K := I + 1;

Print;

Небольшая коррекция, когда считали "перепады" значение I изменилось. Выводим на печать весь массив процедурой Print.

Процедура Print играет немаловажную роль в данной программе.

F := True;

For I := 1 To Max Do If (A[I] mod Usl <> 0) Then F := False;

стоит ли вообще печатать эту последовательность? Если в ней встретится хоть один элемент, не удовлетворяющий условию: A[I] mod Usl <> 0 (A[I] делится без остатка на Usl)

If F Then Begin

значит печатать ничего не будем.

N := 0;

For I := 1 To Max Do If A[I] <> 0 Then Begin

сумма слагаемых пока равна 0. Перебираем все элементы массива, значения которых не равно 0.

Inc(N);

Write(A[I]:2,' ');

увеличиваем сумму слагаемых на 1. Печатаем значение элемента массива и пробел после него, чтобы числа на экране не "слипались"

Else Write(' ');

WriteLn(' N=',N);

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

Пахтусов Сергей, 30.09.2002

Лень учить? Смотри pascal на видео

Счетчики:

Design by Pahtusow S.V. (2001-2009)