Размещено на http://www.allbest.ru/

Решение 50 типовых задач по программированию на языке Pascal

Данил Душистов

Дата размещения сборника в сети: 31.08.2012

Онлайн-версия сборника находится на сайте http://el-prog.narod2.ru/

Со всеми вопросами и комментариями обращаться на E-mail: danildushistov@gmail.com

Аннотация

Этот сборник содержит подробные решения 50 практических задач, данных в рамках учебного курса «Введение в информатику и программирование», который читается в Адыгейском государственном университете. Он может быть интересен школьникам, студентам и всем, кто изучает основы программирования на языке Pascal.

В качестве дополнительного материала прилагаются тексты решений всех задач для сред PascalABC.NET и Borland Delphi 7.

Предисловие от автора

Этот сборник не может быть использован в качестве учебного пособия. В нем практически отсутствует теория, к тому же предполагается, что его читатель уже знает некоторые базисные понятия в программировании, умеет объявлять переменные и может самостоятельно скомпилировать «пустую» программу. Единственное исключение отводится для элементов синтаксиса - при первом упоминании их смысл раскрывается довольно подробно.

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

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

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

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

Глава 1. Линейные алгоритмы

Задача № 1. Вывести на экран сообщение «Hello World!»

Формулировка. Вывести на экран сообщение «Hello World!».

Некоторые учебные курсы по программированию рассматривают эту задачу как самую первую при изучении конкретного языка или основ программирования.

Решение. Эта задача включает в себя лишь демонстрацию использования оператора вывода write (или writeln), который будет единственным в теле нашей маленькой программы. С помощью него мы будем осуществлять вывод на экран константы 'Hello World!' типа string (или, как допускается говорить, строковой константы). В данном случае будем использовать оператор writeln.

Напомню, что при использовании оператора write курсор останется в той же строке, в которой осуществлялся вывод, и будет находиться на одну позицию правее восклицательного знака во фразе «Hello World!», а при использовании оператора writeln - на первой позиции слева в следующей строке.

Код:

1. program HelloWorld; 2. 3. begin 4. writeln('Hello World!') 5. end.

Задача № 2. Вывести на экран три числа в порядке, обратном вводу

Формулировка. Вывести на экран три введенных с клавиатуры числа в порядке, обратном их вводу.

Другими словами, мы ввели с клавиатуры три числа (сначала первое, потом второе и третье), и после этого единственное, что нам нужно сделать - это вывести третье, затем второе и первое.

Решение. Так как с клавиатуры вводится три числа, необходимо завести три переменные. Обозначим их как a, b и c. Ввиду того, что нам ничего не сказано о том, в каком отрезке могут располагаться введенные числа, мы возьмем тип integer, так как он охватывает и положительные, и отрицательные числа в некотором диапазоне (от -2147483648 до 2147483647). Затем нам нужно использовать оператор вывода write (writeln), в списке аргументов которого (напомним, что список аргументов write (writeln) может содержать не только переменные, но и константы и арифметические выражения) эти переменные будут находиться в обратном порядке. В данном случае будем использовать оператор writeln, который после вывода результата переведет курсор на следующую строку:

writeln(c, b, a);

Однако если мы оставим его в таком виде, то увидим, что при выводе между переменными не будет никакого пробела, и они будут слеплены и визуально смотреться как одно число. Это связано с тем, что при вводе мы использовали пробелы для разделения чисел, а сами пробелы никаким образом не влияют на содержимое переменных, которые будут последовательно выведены оператором writeln без каких-либо дополнений. Чтобы избежать этого, нам нужно добавить в список аргументов writeln две текстовые константы-пробелы. Проще говоря, пробельная константа - это символ пробела, заключенный в одиночные апострофы (апостроф - символ «'»). Первая константа будет разделять переменные a и b, вторая - b и c. В результате наш оператор вывода будет таким:

writeln(c, ' ', b, ' ', a);

Теперь он работает так: выводит переменную c, затем одиночный символ пробела, затем переменную b, потом еще один символ пробела и, наконец, переменную a.

Код:

1. program WriteThree; 2. 3. var 4. a, b, c: integer; 5. 6. begin 7. readln(a, b, c); 8. writeln(c, ' ', b, ' ', a) 9. end.

Задача № 3. Вывести на экран квадрат введенного числа

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

Решение. Для ввода числа нам необходима одна переменная. Обозначим эту переменную как a. Так как нам ничего не сообщается о необходимости сохранить исходное число, то для получения квадрата мы можем использовать ту же самую переменную, в которую считывали число с клавиатуры.

В условии задачи дается ограничитель величины вводимого числа - фраза «меньше 256». Это означает, что оно может быть охвачено типом byte. Но что произойдет, если в переменную a будет введено число 255, и затем мы попытаемся присвоить ей его квадрат, равный 65025? Естественно, это вызовет переполнение типа данных, так как используемой для переменной a ячейки памяти не хватит для того, чтобы вместить число 65025. Значит, для ее описания мы должны использовать более емкий числовой тип. При этом типом минимальной размерности, охватывающим данный отрезок (от 1 (это 1²) до 65025), является тип word. Его мы и будем использовать при описании a.

Далее нужно сформировать в переменной a квадрат. Для этого присвоим ей ее прежнее значение, умноженное само на себя:

a := a * a;

Теперь остается вывести результат на экран. Для этого будем использовать оператор writeln.

Код:

1. program SqrOfNum; 2. 3. var 4. a: word; 5. 6. begin 7. readln(a); 8. a := a * a; 9. writeln(a) 10. end.

Задача № 4. Получить реверсную запись трехзначного числа

Формулировка. Сформировать число, представляющее собой реверсную (обратную в порядке следования разрядов) запись заданного трехзначного числа. Например, для числа 341 таким будет 143.

Давайте разберемся с условием. В нашем случае с клавиатуры вводится некоторое трехзначное число (трехзначными называются числа, в записи которых три разряда (то есть три цифры), например: 115, 263, 749 и т. д.). Нам необходимо получить в некоторой переменной число, которое будет представлять собой реверсную запись введенного числа. Другими словами, нам нужно перевернуть введенное число «задом наперед», представить результат в некоторой переменной и вывести его на экран.

Решение. Определимся с выбором переменных и их количеством. Ясно, что одна переменная нужна для записи введенного числа с клавиатуры, мы обозначим ее как n. Так как нам нужно переставить разряды числа n в некотором порядке, следует для каждого из них также предусмотреть отдельные переменные. Обозначим их как a (для разряда единиц), b (для разряда десятков) и c (для разряда сотен).

Теперь можно начать запись самого алгоритма. Будем разбирать его поэтапно:

1) Вводим число n;

2) Работаем с разрядами числа n. Как известно, последний разряд любого числа в десятичной системе счисления - это остаток от деления этого числа на 10. В терминах языка Pascal это означает, что для получения разряда единиц нам необходимо присвоить переменной a остаток от деления числа n на 10. Этому шагу соответствует следующий оператор:

a := n mod 10;

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

n := n div 10;

3) Очевидно, что после выполнения п. 2 в переменной n будет храниться двухзначное число, состоящее из разряда сотен и разряда десятков исходного. Теперь, выполнив те же самые действия еще раз, мы получим разряд десятков исходного числа, но его уже нужно присваивать переменной b.

4) В результате в переменной n будет храниться однозначное число - разряд сотен исходного числа. Мы можем без дополнительных действий присвоить его переменной c.

5) Все полученные в переменных числа - однозначные. Теперь переменная n нам больше не нужна, и в ней нужно сформировать число-результат, в котором a будет находиться в разряде сотен, b - десятков, c - единиц. Легко понять, что для этого нам следует умножить a на 100, прибавить к полученному числу b, умноженное на 10 и c без изменения, и весь этот результат присвоить переменной c. Это можно записать так:

n := 100 * a + 10 * b + c;

6) Далее остается только вывести полученное число на экран.

Код:

1. program ReverseNum; 2. 3. var 4. n, a, b, c: word; 5. 6. begin 7. readln(n); 8. a := n mod 10; 9. n := n div 10; 10. b := n mod 10; 11. n := n div 10; 12. c := n; 13. n := 100 * a + 10 * b + c; 14. writeln(n) 15. end.

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

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

№ строки	n	a	b	c
7	514	--	--	--
8	514	4	--	--
9	51	4	--	--
10	51	4	1	--
11	5	4	1	--
12	5	4	1	5
13	415	4	1	5

программирование алгоритм число бит

Нетрудно понять, что написанная программа будет выводить правильный ответ для любого заданного трехзначного числа, так как в соответствии с алгоритмом заполнение данной таблицы возможно лишь единственным образом. Это значит, что мы можем представить число в виде абстрактного трехзначного числа xyz, (в нем каждая буква должна быть заменена на любое число от 0 до 9, конечно, за исключением тех случаев, когда оно перестает быть трехзначным), и работая с разрядами этого числа, показать, что в результате работы ответом будет число zyx.

Задача № 5. Посчитать количество единичных битов числа

Формулировка. Дано натуральное число меньше 16. Посчитать количество его единичных битов. Например, если дано число 9, запись которого в двоичной системе счисления равна 1001₂ (подстрочная цифра 2 справа от числа означает, что оно записано в двоичной системе счисления), то количество его единичных битов равно 2.

Решение. Нам необходима переменная для ввода с клавиатуры. Обозначим ее как n. Так как мы должны накапливать количество найденных битов, то возникает потребность в еще одной переменной. Обозначим ее как count («count» в переводе с англ. означает «считать», «подсчет» и т. д.). Переменные возьмем типа byte (они могут принимать значения от 0 до 255), и пусть в данном случае такой объем избыточен, но это не принципиально важно.

Как же сосчитать количество битов во введенном числе? Ведь число же вводится в десятичной системе счисления, и его нужно переводить в двоичную?

На самом деле все гораздо проще. Здесь нам поможет одно интересное правило:

Остаток от деления любого десятичного числа x на число p дает нам разряд единиц числа x (его крайний разряд справа) в системе счисления с основанием p.

То есть, деля некоторое десятичное число, например, на 10, в остатке мы получаем разряд единиц этого числа в системе счисления с основанием 10. Возьмем, например, число 3468. Остаток от деления его на 10 равен 8, то есть разряду единиц этого числа.

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

Но как это использовать для решения задачи? Воспользуемся тем, что в двоичной записи числа нет цифр, кроме 0 и 1. Легко убедиться в том, что сложив все разряды двоичного числа, мы получаем как раз таки количество его единичных битов. Это значит, что вместо проверки значений разрядов двоичного представления числа мы можем прибавлять к счетчику сами эти разряды - если в разряде был 0, значение счетчика не изменится, а если 1, то повысится на единицу.

Теперь, резюмируя вышеприведенный итог, можно поэтапно сформировать сам алгоритм:

1) Вводим число n;

2) Обнуляем счетчик разрядов count. Это делается потому, что значения всех переменных при запуске программы считаются неопределенными, и хотя в большинстве компиляторов Pascal они обнуляются при запуске, все же считается признаком «хорошего тона» в программировании обнулить значение переменной, которая будет изменяться в процессе работы без предварительного присваивания ей какого-либо значения.

3) Прибавляем к count разряд единиц в двоичной записи числа n, то есть остаток от деления n на 2:

count := count + n mod 2;

Строго говоря, мы могли бы не прибавлять предыдущее значение переменной count к остатку от деления, так как оно все равно было нулевым. Но мы поступили так для того, чтобы сделать код более однородным, далее это будет видно. Учтя разряд единиц в двоичной записи n, мы должны отбросить его, чтобы исследовать число далее. Для этого разделим n на 2. На языке Pascal это будет выглядеть так:

n := n div 2;

4) Теперь нам нужно еще два раза повторить п. 3 , после чего останется единственный двоичный разряд числа n, который можно просто прибавить к счетчику без каких-либо дополнений:

count := count + n;

5) В результате в переменной count будет храниться количество единичных разрядов в двоичной записи исходного числа. Осталось лишь вывести ее на экран.

Код:

1. program BinaryUnits; 2. 3. var 4. n, count: byte; 5. 6. begin 7. readln(n); 8. count := 0; 9. count := count + n mod 2; 10. n := n div 2; 11. count := count + n mod 2; 12. n := n div 2; 13. count := count + n mod 2; 14. n := n div 2; 15. count := count + n; 16. writeln(count) 17. end.

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

Глава 2. Условные операторы

Задача № 6. Вывести на экран наибольшее из двух чисел

Формулировка. Даны два числа. Вывести на экран то из них, которое больше.

Решение. Собственно, это самая простая задача, с помощью которой можно продемонстрировать использование условного оператора if. Напомним, как нужно использовать этот оператор. Мы вводим с клавиатуры числа в переменные a и b типа integer, затем в операторе if проверяем булевское выражение «a > b»: если оно истинно, то выполняется then-блок оператора, если ложно - else-блок. Соответственно, если a больше b (условие в заголовке истинно), то в then-блоке мы выводим a, а если a не больше b (условие в заголовке ложно), то выводим b (хотя сюда попадает и случай, когда a = b, что, впрочем, не нарушает решения).

На языке Pascal мы можем записать весь оператор с if- и then-блоками в одну строчку следующим образом:

if a > b then writeln(a) else writeln(b);

Данная строка легко понятна и читаема по причине того, что мы выполняем столь простой набор операторов в обоих блоках ветвления оператора if. Однако в более сложных примерах мы будем с первых же написанных строчек следовать принципу аккуратного оформления кода, чтобы не появлялось привычки «вытягивать» операторы ветвлений и другие конструкции в одну строчку, так как в будущем это может сильно сказаться на удобочитаемости и простоте понимания написанного программного кода, особенно при увеличении количества вложенных в блок операторов (которые, например, тоже могут быть операторами ветвления). Не стоит забывать о том, что при вложенности в тело какого-либо оператора хотя бы одного составного оператора или другой сложной конструкции требуется равномерный отступ для подчиненной конструкции с адекватной расстановкой операторных скобок! Например, для оператора if это распределение конструкций по мнемонической модели if-end, else-end, согласно которой эти ключевые слова должны стоять на одном уровне по вертикали, а их содержимое должно быть немного смещено вправо.

Конечно, для простейшей конструкции с условным оператором это вовсе не самоцель, и можно разместить ее в одной строке, если оби ветви оператора (и if-блок, и else-блок) не содержат составного оператора. В нашем же примере «аккуратное оформление» показывается лишь в качестве введения.

Код:

1. program MaxOfTwo; 2. 3. var 4. a, b: integer; 5. 6. begin 7. readln(a, b); 8. if a > b then begin 9. writeln(a) 10. end 11. else begin 12. writeln(b) 13. end 14. end.

При таком оформлении хорошо видно, какой код выполняется при истинности условия, а какой - при его ложности.

Задача № 7. Вывести на экран наибольшее из трех чисел

Формулировка. Даны три числа. Вывести на экран то из них, которое больше.

Решение. Даная задача обобщает предыдущую. В ее решении также нужно использовать условный оператор if, однако в данном случае для нахождения максимального числа нам нужно выполнить минимум два сравнения. Сам механизм выбора в виде условного оператора с вложенными в него двумя другими условными операторами можно легко пояснить следующей блок-схемой:

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

Код:

1. program MaxOfThree; 2. 3. var 4. a, b, c: integer; 5. 6. begin 7. readln(a, b, c); 8. if a > b then begin 9. if a > c then begin 10. writeln(a) 11. end 12. else begin 13. writeln(c) 14. end 15. end 16. else begin 17. if b > c then begin 18. writeln(b) 19. end 20. else begin 21. writeln(c) 22. end 23. end 24. end.

Задача № 8. Вывести название дня недели по его номеру

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

Решение. Задача простейшим образом решается с помощью оператора выбора case. Напомним, что этот оператор позволяет организовать ветвления в зависимости от значений некоторой переменной, для каждого из которых можно предусмотреть выполнение различных действий. Причем если значению переменной не соответствует ни один вариант, выполняется else-блок (если он присутствует). Кстати, не стоит забывать, что после перечисления всех вариантов оператора case необходимо написать ключевое слово end (выходит, ключевое слово case является еще и открывающей операторной скобкой).

Для того чтобы воспользоваться оператором case, нам необходимо произвести ввод номера дня недели в некоторую переменную i типа byte и по этому номеру вывести название текущего дня недели. Кстати, благодаря else-блоку в этой программке мы впервые предусмотрим сообщение об ошибке, связанной с некорректно введенным номером, которому не соответствует ни один из дней недели.

Код:

1. program DaysOfTheWeek; 2. 3. var 4. i: byte; 5. 6. begin 7. readln(i); 8. case i of 9. 1: writeln('Monday'); 10. 2: writeln('Tuesday'); 11. 3: writeln('Wednesday'); 12. 4: writeln('Thursday'); 13. 5: writeln('Friday'); 14. 6: writeln('Saturday'); 15. 7: writeln('Sunday') 16. else writeln('This day of the week does not exist!') 17. end 18. end.

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

Задача № 9. Проверить, является ли четырехзначное число палиндромом

Формулировка. Дано четырехзначное число. Проверить, является ли оно палиндромом.

Примечание: палиндромом называется число, слово или текст, которые одинакового читаются слева направо и справа налево. Например, в нашем случае это числа 1441, 5555, 7117 и т. д.

Примеры других чисел-палиндромов произвольной десятичной разрядности, не относящиеся к решаемой задаче: 3, 787, 11, 91519 и т. д.

Решение. Для ввода числа с клавиатуры будем использовать переменную n. Вводимое число принадлежит множеству натуральных чисел и четырехзначно, поэтому оно заведомо больше 255, так что тип byte для ее описания нам не подходит. Тогда будем использовать тип word.

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

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

Однако не стоит спешить с решением. Может быть, мы сможем упростить выведенную схему? Возьмем, например, уже упомянутое выше число 1441. Что будет, если разделить его на два числа двузначных числа, первое из которых будет содержать разряд тысяч и сотен исходного, а второе - разряд десятков и единиц исходного. Мы получим числа 14 и 41. Теперь, если второе число заменить на его реверсную запись (это мы делали в задаче 4), то мы получим два равных числа 14 и 14! Это преобразование вполне очевидно, так в силу того, что палиндром читается одинаково в обоих направлениях, он состоит из дважды раза повторяющейся комбинации цифр, и одна из копий просто повернута задом-наперед.

Отсюда вывод: нужно разбить исходное число на два двузначных, одно из них реверсировать, а затем выполнить сравнение полученных чисел с помощью условного оператора if. Кстати, для получения реверсной записи второй половины числа нам необходимо завести еще две переменные для сохранения используемых разрядов. Обозначим их как a и b, и будут они типа byte.

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

1) Вводим число n;

2) Присваиваем разряд единиц числа n переменной a, затем отбрасываем его. После присваиваем разряд десятков n переменной b и также отбрасываем его:

a := n mod 10;

n := n div 10;

b := n mod 10;

n := n div 10;

3) Присваиваем переменной a число, представляющее собой реверсную запись хранящейся в переменных a и b второй части исходного числа n по уже известной формуле:

a := 10 * a + b;

4) Теперь мы можем использовать проверку булевского выражения равенства полученных чисел n и a помощью оператора if и организовать вывод ответа с помощью ветвлений:

if n = a then writeln('Yes') else writeln('No');

Так как в условии задачи явно не сказано, в какой форме необходимо выводить ответ, мы будем считать логичным вывести его на интуитивно понятном пользователю уровне, доступном в средствах самого языка Pascal. Напомним, что с помощью оператора write (writeln) можно выводить результат выражения булевского типа, причем при истинности этого выражения будет выведено слово 'TRUE' («true» в пер. с англ. означает «истинный»), при ложности - слово 'FALSE' («false» в пер. с англ. означает «ложный»). Тогда предыдущая конструкция с if может быть заменена на

writeln(n = a);

Код:

1. program PalindromeNum; 2. 3. var 4. n: word; 5. a, b: byte; 6. 7. begin 8. readln(n); 9. a := n mod 10; 10. n := n div 10; 11. b := n mod 10; 12. n := n div 10; 13. a := 10 * a + b; 14. writeln(n = a) 15. end.

Задача № 10. Проверить, является ли четырехзначное число счастливым билетом

Формулировка. Дано четырехзначное число. Проверить, является ли оно «счастливым билетом».

Примечание: счастливым билетом называется число, в котором: а) при четном количестве цифр в числе сумма цифр его левой половины равна сумме цифр его правой половины; б) при нечетном количестве цифр - то же самое, но с отбрасыванием серединной цифры. Например, рассмотрим число 1322. Его левая половина равна 13, а правая - 22, и оно является счастливым билетом (т. к. 1 + 3 = 2 + 2). Аналогично: 1735 (1 + 7 = 3 + 5), 1111 (1 + 1 = 1 + 1) и т. д.

Примеры других счастливых билетов за рамками условия текущей задачи: 7 (отбросили единственную цифру), 39466 (3 + 9 = 6 + 6, а 4 отбросили), 11 (1 = 1), и т. д.

Решение. Для ввода достаточно одной переменной n типа word. Все, что необходимо сделать для решения - это последовательно получить все разряды исходного числа, причем из двух младших разрядов (единиц и десятков) сформировать первую сумму, а из двух старших разрядов - вторую, после чего вывести на экран результат булевского выражения равенства полученных сумм. Первую сумму будем хранить в переменной right, а вторую - в переменной left (выбрано по расположению цифр в записи числа). Значение обоих из них не может превосходить 18 (т. к. для наибольшего допустимого числа 9999 обе суммы равны 9 + 9 = 18), поэтому для их описания используем тип byte.

Более детальный разбор алгоритма:

1) Вводим число n;

2) Присваиваем переменной right значение последней цифры числа n, потом отбрасываем эту цифру, затем повторяем то же самое, но на этот раз уже прибавляем добытую цифру к прежнему значению right:

right := n mod 10;

n := n div 10;

right := right + n mod 10;

n := n div 10;

3) Присваиваем переменной left последнюю цифру n, отбрасываем ее и прибавляем к right единственную оставшуюся в переменной n цифру:

left := n mod 10;

n := n div 10;

left := left + n;

4) Выводим на экран результат сравнения накопленных сумм:

writeln(left = right);

Код:

1. program HappyTicket; 2. 3. var 4. n: word; 5. left, right: byte; 6. 7. begin 8. readln(n); 9. right := n mod 10; 10. n := n div 10; 11. right := right + n mod 10; 12. n := n div 10; 13. left := n mod 10; 14. n := n div 10; 15. left := left + n; 16. writeln(left = right) 17. end.

Задача № 11. Проверить, является ли двоичное представление числа палиндромом

Формулировка. Дано число типа byte. Проверить, является ли палиндромом его двоичное представление с учетом того, что сохранены старшие нули. Пример таких чисел: 102 (т. к. 102 = 0110 0110₂, а это палиндром), 129 (129 = 1000 0001₂) и т. д.

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

Но как же упростить решение, чтобы не делать сравнение всех разрядов «в лоб»? Для этого нам нужно вспомнить правило, упомянутое в задаче 5, на этот раз несколько уточненное и дополненное:

- Остаток от деления любого числа x в системе счисления с основанием p на само число p дает нам крайний справа разряд числа x.

- Умножение любого числа x в системе счисления с основанием p на само число p добавляет числу x новый разряд справа.

Для примера возьмем число 158 в десятичной системе счисления. Мы можем получить его крайнюю цифру справа, которая равна 8, если возьмем остаток от деления 158 на число 10, являющееся в данном случае основанием системы счисления. С другой стороны, если мы умножим 158 на 10, то появляется новый разряд справа, и в результате мы получаем число 1580.

Согласно правилу те же самые арифметические законы актуальны и для двоичной системы счисления. А это в свою очередь означает, что мы можем разработать алгоритм наподобие того, который использовался в задаче 9 для формирования числа, представляющего собой правую половину исходного числа, которая записана в реверсном порядке. Для этого нам нужно использовать четыре переменных для хранения двоичных разрядов правой половины двоичной записи введенного числа, добыть эти самые разряды с удалением их в исходном числе, сформировать из них двоичную реверсную запись и выполнить сравнение. Обозначим эти переменные типа byte как a, b, c, и d.

Опишем сам алгоритм:

1) Вводим число n;

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

a := n mod 2;

n := n div 2;

b := n mod 2;

n := n div 2;

c := n mod 2;

n := n div 2;

d := n mod 2;

n := n div 2;

3) Теперь нужно подумать, как видоизменится формула, с помощью которой мы получали реверсную запись числа в задаче 4 и задаче 9. Очевидно, что в десятичной системе счисления реверсную запись четырехзначного числа, разряд единиц которого находится в переменной k, разряд десятков - в переменной l, сотен - в m и тысяч - в n мы можем найти по следующей формуле (x в данной случае - любая переменная типа word):

x := 1000 * k + 100 * l + 10 * m + n;

Можно представить, что мы формируем четыре числа, которые затем складываем. Первое число 1000 * k - это разряд единиц исходного числа, к которому справа приписано три разряда (три нуля), то есть, трижды произведено умножение на основание системы счисления 10, проще говоря, число k умножено на 10³. Аналогично, к l нужно приписать два нуля, к m - один ноль, а n оставить без изменения, так как эта цифра будет находиться в разряде единиц формируемого «перевертыша». Вспомнив правило, высказанное немного выше, преобразуем предыдущую формулу для двоичной системы счисления (будем умножать цифры на двойку в соответствующих степенях). Она получится такой (для формирования числа используется переменная a):

a := 8 * a + 4 * b + 2 * c + d;

4) После применения вышеприведенной строки останется лишь вывести на экран результат сравнения полученных чисел:

writeln(n = a);

Код:

1. program BinaryPalindrome; 2. 3. var 4. n, a, b, c, d: byte; 5. 6. begin 7. readln(n); 8. a := n mod 2; 9. n := n div 2; 10. b := n mod 2; 11. n := n div 2; 12. c := n mod 2; 13. n := n div 2; 14. d := n mod 2; 15. n := n div 2; 16. a := 8 * a + 4 * b + 2 * c + d; 17. writeln(n = a) 18. end.

Выполним «ручную прокрутку» программы при вводе числа 102. Покажем в таблице, какие значения будут принимать переменные после выполнения соответствующих строк (операторов) кода. Значения переменных для наглядности представлены как в десятичной, так и в двоичной системе счисления (при этом дописаны старшие нули до заполнения тетрады). При этом прочерк означает, что значение переменных на данном шаге не определено, а красным цветом выделены переменные, которые изменяются:

№ строки	Десятичная система	Двоичная система
	n	a	b	c	d	n	a	b	c	d
7	102	--	--	--	--	0110 0110	--	--	--	--
8	102	0	--	--	--	0110 0110	0000	--	--	--
9	51	0	--	--	--	0011 0011	0000	--	--	--
10	51	0	1	--	--	0011 0011	0000	0001	--	--
11	25	0	1	--	--	0001 1001	0000	0001	--	--
12	25	0	1	1	--	0001 1001	0000	0001	0001	--
13	12	0	1	1	--	0000 1100	0000	0001	0001	--
14	12	0	1	1	0	0000 1100	0000	0001	0001	0000
15	6	0	1	1	0	0000 0110	0000	0001	0001	0000
16	6	6	1	1	0	0000 0110	0110	0001	0001	0000

Задача № 12. Решить квадратное уравнение

Формулировка. Даны вещественные числа a, b и c, причем a отлично от 0. Решить квадратное уравнение ax² + bx + c = 0 или сообщить о том, что действительных решений нет.

Решение. Из алгебры известно, что:

Квадратное уравнение ax² + bx + c = 0, выражение D = b² - 4ac - дискриминант:

- если D > 0, имеет два решения: ,;

- если D = 0, имеет единственное решение: ;

- если D < 0, не имеет действительных решений.

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

Три нерасшифрованных блока представляют собой стандартные операторы вывода. Разберем их подробнее:

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

x1 := (-b + sqrt(d)) / 2 * a;

x2 := (-b - sqrt(d)) / 2 * a;

writeln('x1 = ', x1:4:2, ', x2 = ', x2:4:2);

При этом выводимое выражение будет выглядеть так: 'x1 = m, x2 = n', где синим цветом выделены однозначные текстовые константы, которые берутся из списка аргументов writeln, красным - вычисленные значения x1 и x2. Причем корни выведены в форматированном виде: число после первого двоеточия задает ширину поля вывода для переменной вместе с точкой (при нехватке поля она будет расширено программой), а число после второго двоеточия - количество выводимых дробных знаков (его при работе программы изменить нельзя);

2) При выводе одного корня - все то же самое, только выводится один корень:

x1 := -(b / 2 * a);

writeln('x = ', x1:4:2);

3) При отсутствии действительных корней выводим сообщение:

writeln('No real solutions!');

В итоге внутренний условный оператор с телом включительно будет выглядеть так:

if d <> 0 then begin

x1 := (-b + sqrt(d)) / 2 * a;

x2 := (-b - sqrt(d)) / 2 * a;

writeln('x1 = ', x1:4:2, ', x2 = ', x2:4:2)

end

else begin

x1 := -(b / 2 * a);

writeln('x = ', x1:4:2)

end;

Код:

1. program QuadraticEquation; 2. 3. var 4. a, b, c, d, x1, x2: real; 5. 6. begin 7. readln(a, b, c); 8. d := b * b - 4 * a * c; 9. if d >= 0 then begin 10. if d <> 0 then begin 11. x1 := (-b + sqrt(d)) / 2 * a; 12. x2 := (-b - sqrt(d)) / 2 * a; 13. writeln('x1 = ', x1:4:2, ', x2 = ', x2:4:2) 14. end 15. else begin 16. x1 := -(b / 2 * a); 17. writeln('x = ', x1:4:2) 18. end 19. end 20. else begin 21. writeln('No real solutions!'); 22. end 23. end.

Глава 3. Циклы

Задача № 13. Вывести на экран все натуральные числа до заданного

Формулировка. Дано натуральное число. Вывести на экран все натуральные числа до заданного включительно.

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

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

Код:

1. program FromOneToN; 2. 3. var 4. i, n: word; 5. 6. begin 7. readln(n); 8. for i := 1 to n do begin 9. write(i, ' ') 10. end 11. end.

Пусть введено число 5, например. При входе i станет равно 1 и будет проверено существование отрезка в заданных границах. Так как 1 меньше 5, то произойдет вход в цикл, и будут выполняться следующие команды, пока i не превысит n:

1) Выполнение команд в теле цикла;

2) Увеличение i на 1;

3) Возвращение на шаг 1.

Нетрудно понять, что в нашем случае i будет принимать значения 1, 2, 3, 4, 5 и будет выведена на экран строка '1 2 3 4 5 '. Здесь красным цветом выделены изменяющиеся значения переменной цикла, а синим - выводящаяся неизменной пробельная константа.

Задача № 14. Найти наибольший нетривиальный делитель натурального числа

Формулировка. Дано натуральное число. Найти его наибольший нетривиальный делитель или вывести единицу, если такового нет.

Примечание 1: делителем натурального числа a называется натуральное число b, на которое a делится без остатка. То есть выражение «b - делитель a» означает: a / b = k, причем k - натуральное число.

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

Решение. Пусть ввод с клавиатуры осуществляется в переменную n. Попробуем решить задачу перебором чисел. Для этого возьмем число на единицу меньшее n и проверим, делится ли n на него. Если да, то выводим результат и выходим из цикла с помощью оператора break. Если нет, то снова уменьшаем число на 1 и продолжаем проверку. Если у числа нет нетривиальных делителей, то на каком-то шаге проверка дойдет до единицы, на которую число гарантированно поделится, после чего будет выдан соответствующий условию ответ.

Хотя, если говорить точнее, следовало бы начать проверку с числа, равного n div 2 (чтобы отбросить дробную часть при делении, если n нечетно), так как ни одно натуральное число не имеет делителей больших, чем половина это этого числа. В противном случае частное от деления должно быть натуральным числом между 1 и 2, которого просто не существует.

Данная задача также решается через for, но через другую его разновидность, и теперь счетчик будет убывать от n div 2 до 1. Для этого do заменится на downto, при позиции начального и конечного значений остаются теми же.

Алгоритм на естественном языке:

1) Ввод n;

2) Запуск цикла, при котором i изменяется от n div 2 до 1. В цикле:

1. Если n делится на i (то есть, остаток от деления числа n на i равен 0), то выводим i на экран и выходим из цикла с помощью break.

Код:

1. program GreatestDiv; 2. 3. var 4. i, n: word; 5. 6. begin 7. readln(n); 8. for i := n div 2 downto 1 do begin 9. if n mod i = 0 then begin 10. writeln(i); 11. break 12. end 13. end 14. end.

Кстати, у оператора ветвления if в цикле отсутствует else-блок. Такой условный оператор называется оператором ветвления с одной ветвью.

Задача № 15. Найти наименьший нетривиальный делитель натурального числа

Формулировка. Дано натуральное число. Найти его наименьший нетривиальный делитель или вывести само это число, если такового нет.

Решение. Задача решается аналогично предыдущей. При этом необходимо начать обычный цикл с увеличением, при котором переменная цикла i изменяется от 2 до n (такая верхняя граница нужна для того, чтобы цикл всегда заканчивался, так как когда i будет равно n, выполнится условие n mod i = 0). Весь остальной код при этом не отличается.

Код:

1. program SmallestDiv; 2. 3. var 4. i, n: word; 5. 6. begin 7. readln(n); 8. for i := 2 to n do begin 9. if n mod i = 0 then begin 10. writeln(i); 11. break 12. end 13. end 14. end.

Задача № 16. Подсчитать общее число делителей натурального числа

Формулировка. Дано натуральное число. Подсчитать общее количество его делителей.

Решение. Задача достаточно похожа на две предыдущие. В ней также необходимо провести перебор в цикле некоторого количества натуральных чисел на предмет обнаружения делителей n, но при этом необходимо найти не первый из них с какого-либо конца отрезка [1, n] (это отрезок, содержащий все числа от 1 до n включительно), а посчитать их. Это можно сделать с помощью счетчика count, который нужно обнулить непосредственно перед входом в цикл. Затем в условном операторе if в случае истинности условия делимости числа n (n mod i = 0) нужно увеличивать счетчик count на единицу (это удобно делать с помощью оператора inc).

Алгоритм на естественном языке:

1) Ввод n;

2) Обнуление переменной count (в силу необходимости работать с ее значением без предварительного присваивания ей какого-либо числа)

3) Запуск цикла, при котором i изменяется от 1 до n. В цикле:

1. Если n делится на i (то есть, остаток от деления числа n на i равен 0), то увеличиваем значение переменной count на 1;

4) Вывод на экран значения переменной count.

Код:

1. program CountDiv; 2. 3. var 4. i, n, count: word; 5. 6. begin 7. readln(n); 8. count := 0; 9. for i := 1 to n do begin 10. if n mod i = 0 then inc(count) 11. end; 12. writeln(count) 13. end.

Задача № 17. Проверить, является ли заданное натуральное число простым

Формулировка. Дано натуральное число. Проверить, является ли оно простым.

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

Решение. Задача отличается от предыдущей только тем, что вместо вывода на экран числа делителей, содержащегося в переменной count, необходимо выполнить проверку равенства счетчика числу 2. Если у числа найдено всего два делителя, то оно простое и нужно вывести положительный ответ, в противном случае - отрицательный ответ. А проверку через условный оператор, как мы уже знаем, можно заменить на вывод результата самого булевского выражения с помощью оператора write (writeln).

Код:

1. program PrimeTest; 2. 3. var 4. i, n, count: word; 5. 6. begin 7. readln(n); 8. count := 0; 9. for i := 1 to n do begin 10. if n mod i = 0 then inc(count) 11. end; 12. writeln(count = 2) 13. end.

Задача № 18. Вывести на экран все простые числа до заданного

Формулировка. Дано натуральное число. Вывести на экран все простые числа до заданного включительно.

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

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

count := 0;

for i := 1 to n do begin

if n mod i = 0 then inc(count)

end;

writeln(count = 2);

Здесь n - проверяемое на простоту число. Напомним, что данный фрагмент кода в цикле проверяет, делится ли n на каждое i в отрезке от 1 до самого n, и если n делится на i, то увеличивает счетчик count на 1. Когда цикл заканчивается, на экран выводится результат проверки равенства счетчика числу 2.

В нашем же случае нужно провести проверку на простоту всех натуральных чисел от 1 до заданного числа (обозначим его как n). Следовательно, мы должны поместить код 1 в цикл по всем k от 1 до n. Также в связи с этим необходимо заменить в коде 1 идентификатор n на k, так как в данном решении проверяются на простоту все числа k. Кроме того, теперь вместо вывода ответа о подтверждении/опровержении простоты k необходимо вывести само это число в случае простоты:

if count = 2 then write(k, ' ');

Обобщая вышесказанное, приведем алгоритм на естественном языке:

1) Ввод n;

2) Запуск цикла, при котором k изменяется от 1 до n. В цикле:

1. Обнуление переменной count;

2. Запуск цикла, при котором i изменяется от 1 до k. В цикле:

a. Если k делится на i, то увеличиваем значение переменной count на 1;

3. Если count = 2, выводим на экран число k и символ пробела.

Код:

1. program PrimesToN; 2. 3. var 4. i, k, n, count: word; 5. 6. begin 7. readln(n); 8. for k := 1 to n do begin 9. count := 0; 10. for i := 1 to k do begin 11. if k mod i = 0 then inc(count) 12. end; 13. if count = 2 then write(k, ' ') 14. end 15. end.

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

Давайте посчитаем количество выполненных операций в частном случае. Итак, пусть необходимо вывести все натуральные простые числа до числа 5. Очевидно, что проверка числа 1 пройдет в 1 + 2 шага, числа 2 - в 2 + 2 шага, числа 3 - в 3 + 2 шага и т. д. (прибавленная двойка к каждому числу - два обязательных оператора вне внутреннего цикла), так как мы проверяем делители во всем отрезке от 1 до проверяемого числа. В итоге количество проведенных операций (выполненных операторов на низшем уровне) пред...