Программирование на языке Pascal

Формулировка. Даны натуральные числа n и k (k не превышает n). Вычислить число сочетаний из n по k.

Примечание: в комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов; при этом наборы, отличающиеся только порядком следования элементов, считаются одинаковыми. Обозначение числа сочетаний из n по k элементов: . При этом считается, что , и для любого натурального n.

Например, найдем все 2-элементные сочетания 3-элементного множества {1, 2, 3}. Таковыми являются {1, 2}, {1, 3} и {2, 3}. То есть, таковых сочетаний 3. При этом, например, {1, 2} и {2, 1} - одинаковые сочетания, так как они отличаются только порядком следования элементов.

Решение. Из комбинаторики известна формула:

Не интересуясь вопросом ее вывода и корректности, мы будем использовать тот ее вариант, который написан после второго знака равенства (если смотреть слева направо), так как он наиболее оптимален для вычислений и позволит обойтись двумя циклами (для числителя for с downto, для знаменателя - просто for). Для числителя и знаменателя предусмотрим соответственно переменные num (от англ. numerator - «числитель») и denom (от англ. denominator - «знаменатель»), которым нужно поначалу присвоить значения 1, чтобы осуществить контроль частных случаев (этот вопрос упомянут в предыдущей задаче):

1) При k = 0 переменная num останется неизменной и будет равна 1, так как невозможен вход в цикл с уменьшением от n до (n + 1), переменная denom будет равна 1 как 0!;

2) При n = k num и denom будут вычислены и при делении дадут единицу;

3) При n = k = 0 переменная denom будет вычислена как 0!, а переменная num не изменится по невозможности входа в цикл с уменьшением от 0 до 1.

Код:

Задача № 30. Вывести таблицу квадратов и кубов всех натуральных чисел до n

Формулировка. Дано натуральное число n, меньшее 256. Используя псевдографику, вывести на экран таблицу квадратов и кубов всех натуральных чисел от 1 до n включительно.

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

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

Решение. В этой задаче мы впервые займемся графическим оформлением выходных данных программы. Для начала подумаем, как может выглядеть таблица в простейшем случае (n = 3):

Несмотря на то, что кодовые страницы для DOS имеют определенный набор символов для рисования графических примитивов, в частности, таблиц, мы будем пользоваться лишь символами '-' и '|' для построения линий таблицы, а также '/' и '\' для формирования ее угловых элементов.

Построим псевдографический эквивалент этой таблицы:

/-----------------------\

| x | x^2 | x^3 |

|-----------------------|

| 1 | 1 | 1 |

| 2 | 4 | 8 |

| 3 | 9 | 27 |

\-----------------------/

Примечание: в случае ограниченных возможностей вывода для обозначения возведения выражения в степень используется постфикс «^k», где k - показатель степени. Кстати, здесь мы выравниваем значения в середине столбцов, сдвигая к середине разряд единиц упорядоченных по правому краю столбцов.

Как же сформировать вывод на экран такой таблицы? Понятно, что это нужно сделать построчно. Однако какой ширины сделать таблицу и как организовать вывод строк со степенями? Так как максимальное число, которое может быть подано на вход - 255, и его куб равен 16581375 (он состоит из 8 цифр), то нам нужно сделать колонки ширины 1 + 8 + 8 + 1 = 18 (крайние единицы для отступов) символов, чтобы таблица выглядела равномерно:

/--------------------------------------------------------\

| x | x^2 | x^3 |

|--------------------------------------------------------|

| 1 | 1 | 1 |

| 2 | 4 | 8 |

|... |... |... |

|255 | 65025 | 16581375 |

\--------------------------------------------------------/

Как видим, при постепенном увеличении числа будут «вырастать» справа налево. Чтобы вывести такую строку, нужно вывести константу '|', затем вывести соответствующее число с шириной поля вывода 9, потом вывести константу '|' с шириной поля вывода 10 и аналогично вывести оставшиеся колонки:

writeln('|', i:9, '|':10, i * i:9, '|':10, i * i * i:9, '|':10);

Схематически с учетом форматирования это будет выглядеть так:

'|255 | 65025 | 16581375 |'

Изменение цветов соответствует чередованию аргументов в операторе вывода.

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

writeln('/--------------------------------------------------------\');

writeln('| x | x^2 | x^3 |');

writeln('|--------------------------------------------------------|');

После вывода всех строк нужно вывести нижнюю границу таблицы:

writeln('\--------------------------------------------------------/');

Вообще, все эти константы и правила не взялись «просто так» или из расчетов. Единственный использованный факт - разрядность числа не более 8, поэтому мы и взяли ширину колонок «по максимуму». В остальном нужно было экспериментировать, чтобы найти наиболее легкое и наглядное решение. Конечно, псевдографика - это не алгоритмическое программирование, и в нем тестирование и эксперимент играют чуть ли не самую важную роль.

Код:

Задача № 31. Сформировать реверсную запись заданного числа

Формулировка. Дано натуральное число n заранее неизвестной разрядности. Сформировать и вывести на экран число, представляющее собой реверсную запись n.

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

Пусть дано число 25893. Возьмем его последнюю цифру как остаток от деления на 10 - это 3. Очевидно, она должна быть первой. Отбросим ее у числа n и возьмем последнюю цифру 9 - она должна быть второй. Чтобы сформировать две цифры реверсного числа, умножим 3 на 10 и прибавим 9, потом добавим третью цифру и т. д.

Так как разрядность числа неизвестна, мы будем использовать цикл с предусловием. Его тело будет выглядеть так:

r := r * 10;

r := r + n mod 10;

n := n div 10;

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

Каким же будет условие продолжения? Нетрудно понять, что когда мы будем добавлять последнюю оставшуюся цифру исходного числа n к реверсной записи r, мы умножим r на 10, прибавим к ней как n mod 10 (в данном случае этот остаток равен n) и разделим n на 10. Тогда n станет равно 0 и цикл должен закончиться, так что условие его продолжения - n < > 0.

Код:

Задача № 32. Проверить монотонность последовательности цифр числа

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

Примечание: в математике строго возрастающие и строго убывающие последовательности называются строго монотонными. В строго возрастающей последовательности каждый следующий член больше предыдущего. Например: 1, 3, 4 ,7, 11, 18. В строго убывающей последовательности каждый следующий член меньше предыдущего. Например: 9, 8, 5, 1.

Решение. Здесь нам нужно будет последовательно получить разряды восьмеричной записи числа, двигаясь по записи числа справа налево. Как мы уже знаем, последний разряд числа в восьмеричной системе счисления есть остаток от деления этого числа на 8.

Попытаемся определить несколько общих свойств строго возрастающих (обозначим пример как 1) и строго убывающих (обозначим как 2) последовательностей (для наглядности будем сразу брать восьмеричные последовательности):

1) 3, 4, 5, 8, 9, 11.

2) 8, 7, 3, 2, 0.

Для начала введем в рассмотрение некоторую формулу, обозначим ее как (I):

delta_i = a_i - a_i+1,

где a_i - член заданной последовательности с индексом i. Нетрудно понять, что эта формула определяет разность между двумя соседними элементами: например, если i = 5 (то есть, мы рассматриваем пятую разность), то формула будет выглядеть так: delta₅ = a₅ - a₆. При этом стоит учитывать множество всех значений, которые может принимать i. Например, для последовательности (1) i может принимать значения от 1 до 5 включительно, для последовательности (2) - от 1 до 4 включительно. Легко проверить, что для всех других i формула (I) не имеет смысла, так как в ней должны участвовать несуществующие члены последовательности.

Найдем все delta_i для последовательности (1): delta₁ = 3 - 4 = -1, delta₂ = 4 - 5 = -1, delta₃ = 5 - 8 = -3, delta₄ = 8 - 9 = -1, delta₅ = 9 - 11 = -2.

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

Выпишем все delta_i для последовательности (2), не расписывая при этом саму формулу: 1, 4, 1, 2. Видим, что все они положительны.

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

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

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

Теперь нам необходимо попробовать унифицировать проверку знакопостоянства всех delta для последовательностей обоих видов. Для этого рассмотрим произведение каких-либо двух delta в последовательностях (1) и (2). Примечательно, что оно положительно как произведение чисел одного знака. Таким образом, мы можем в любой последовательности взять delta₁ и получить произведения его со всеми остальными delta (обозначим эту формулу как (II)):

p = delta₁ * delta_i

Если все p положительны, то последовательность строго монотонна, а если же возникает хотя бы одно отрицательное произведение p, то условие монотонности нарушено.

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

Каким же образом двигаться по разрядам числа n и обрабатывать все delta?

Сначала мы можем получить последнюю цифру числа n (назовем ее b), отбросить ее и получить предпоследнюю цифру n (назовем ее a), отбросить ее тоже, а затем вычислить delta = a - b. Кстати, отметим, что при таком подходе мы будем для всех i находить delta_i, двигаясь по ним справа налево. Начальному фрагменту этих действий соответствует следующий код:

b := n mod 8;

n := n div 8;

a := n mod 8;

n := n div 8;

delta:= a - b;

Теперь мы можем войти в цикл с предусловием n < > 0. В каждом шаге цикла мы должны присвоить переменной b число a, затем считать следующий разряд в a и отбросить этот разряд в n. Таким способом мы «сдвигаем» текущую пару: например, на 1-ом шаге в примере (2) мы до входа в цикл использовали бы цифры 2 (в переменной a) и 0 (в переменной b), затем при входе в цикл скопировали бы 2 в b и 3 в a - таким образом, все было бы готово для исследования знака по произведению. В связи с этим основной цикл будет выглядеть так:

while n <> 0 do begin

b := a;

a := n mod 8;

n := n div 8;

...

end;

На месте многоточия и будет проверка знакопостоянства произведений. Воспользовавшись формулой (II), мы заменим delta_i в качестве текущего на саму разность a - b, чтобы не задействовать дополнительную переменную. В итоге, если теперь delta * (a - b) <= 0, то выходим из цикла:

if delta * (a - b) <= 0 then break;

Теперь рассмотрим развитие событий по завершении цикла:

1) Если произойдет выход по завершению цикла, то есть «закончится» число в связи с превращением его в 0 на некотором шаге, то значения a, b и delta будут содержать значения, подтверждающие строгую монотонность последовательности, что можно проверить с помощью вывода значения булевского выражения на экран.

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

writeln(delta * (a - b) > 0);

Код:

Кстати, что будет при вводе числа n, меньшего 8, ведь его восьмеричная запись однозначна? Хотя наша цепочка делений еще до входа в цикл требует двух цифр в записи числа!

Посмотрим, как поведет себя программа при вводе числа n из единственной цифры k: сначала k идет в b (строка 9), затем отбрасывается в n (строка 10), которое теперь равно 0, затем в a идет число 0, так как 0 mod 8 = 0 (строка 11). При этом строка 12 уже ничего не дает, так как n, которое сейчас равно нулю, присваивается значение 0 div 8 = 0. Далее вычисляется delta = -k (строка 13), затем игнорируется цикл, так как n = 0 (строки 14 - 19), затем выводится на экран значение выражения -k * -k > 0 (строка 20), которое истинно для любого действительного k кроме нуля, который и не входит в условие нашей задачи, так как n натуральное.

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

Задача № 33. Получить каноническое разложение числа на простые сомножители