«Т. В. Диканев, С. Б. Вениг, И. В. Сысоев ПРИНЦИПЫ И АЛГОРИТМЫ ПРИКЛАДНОГО ПРОГРАММИРОВАНИЯ Учебное пособие для студентов, обучающихся на факультете нано- и биомедицинских технологий Саратов Издательство Саратовского ...»

Саратовский государственный университет им. Н. Г. Чернышевского

Т. В. Диканев, С. Б. Вениг, И. В. Сысоев

ПРИНЦИПЫ И АЛГОРИТМЫ

ПРИКЛАДНОГО

ПРОГРАММИРОВАНИЯ

Учебное пособие для студентов, обучающихся

на факультете нано- и биомедицинских технологий

Саратов

Издательство Саратовского университета 2012 УДК 519.683, 372.862 ББК 32.973-018.2я73 Д45 Диканев, Т. В.

Д45 Принципы и алгоритмы прикладного программирования : учебное пособие для студентов, обучающихся на факультете нано- и биомедицинских технологий / Т. В. Диканев, С. Б. Вениг, И. В. Сысоев. – Саратов : Изд-во Сарат. ун-та, 2012. – 140 с. : ил.

ISBN 978-5-292-04146- Идея книги – объяснить основные принципы и базовые алгоритмы написания прикладных программ людям, для которых программирование не является профессией, а только средством повысить продуктивность своего труда. При этом упор делается не на знание конкретного языка, а на формирование алгоритмического мышления. Овладение программированием невозможно без практики, для чего в книге имеется обширный набор заданий.

Для студентов естественно-научных направлений подготовки.

Рекомендуют к печати:

кафедра динамического моделирования и биомедицинской инженерии факультета нано- и биомедицинских технологий Саратовского государственного университета доктор физико-математических наук, профессор В. В. Астахов Работа издана по тематическому плану 2012 года (утвержден на Ученом совете Саратовского государственного университета, протокол № 2 от 31 января 2012 г.) УДК 519.683, 372. ББК 32.973-018.2я © Диканев Т. В., Вениг С. Б., ISBN 978-5-292-04146- Сысоев И. В., © Саратовский государственный университет, Введение Данное пособие представляет собой начальный курс программирования для студентов 1-го курса кафедры динамического моделирования и биомедицинской инженерии факультета нано- и биомедицинских технологий СГУ. Основным его отличием от большинства других книг для начинающих является упор не на язык программирования (изложением которого обычно и ограничиваются), а на выделение различных алгоритмических приемов.

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

В качестве языка программирования используется старый добрый Паскаль. На хорошо знакомую критику, что данный язык устарел и следует изучать популярные Java, C++ и т.п., отвечаем: главной целью курса является выработка навыков алгоритмического мышления и хорошего стиля при процедурном программировании. Специфические именно для языка Паскаль вещи занимают в данном пособии совершенно незначительное место. Упомянутые навыки мы считаем необходимой базой, без которой невозможен переход к изучению объектно-ориентированных языков и других современных технологий программирования.

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

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

Хотим предупредить, что данное состояние совершенно естественно.

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

Таким образом, начальный ступор и непонимание есть неизбежная ступень, которую вам придется преодолеть. Скорее всего, кроме личного упорства вам здесь ничто не поможет. Бесполезно просить товарищей или преподавателя решить вам задачу. Знание, как именно она решается, не даст вам решительно ничего. Важно не оно, а путь его получения, который будет скрыт от вас.

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

Выбор среды программирования Для написания программ на языке Паскаль можно использовать несколько различных компиляторов и сред программирования. Они отличаются как функционалом, так и удобством. При выполнении заданий из данного учебного пособия мы рекомендуем использовать среду Geany (доступна по адресу http://www.geany.org/Download/Releases) и компилятор FreePascal (http://freepascal.org/download.var). Можно также воспользоваться средой PascalABC.NET со встроенным компилятором (скачать можно по адресу http://pascalabc.net/ssyilki-dlya-skachivaniya.html).

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

отсутствие существенных ошибок. Это важное качество при обучении – можно быть уверенным, что когда что-то не работает, ошибка именно ваша, а не разработчиков сред;

поддержка многих современных конструкций (в том числе практически полная поддержка конструкций Delphi 7 и некоторых более поздних версий) и богатая стандартная библиотека, позволяющая переходить к более сложным программам, не меняя средств разработки;

кроссплатформенность: доступность на Windows, Linux, Mac OS X, FreeBSD, что может быть важно для образовательных учреждений в свете постепенного их перехода на использовангие СПО;

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

Основные недостатки:

стандартная среда разработки малопригодна для использования.

Именно поэтому мы рекомендуем пользоваться Geany;

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

2. PascalABC.NET – это современная бесплатная среда, разработанная на факультете математики, механики и компьютерных наук Южного федерального университета специально для целей обучения. К ее достоинствам можно отнести:

простой интерфейс (ничего, что не потребуется при начальном обучении);

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

неплохая выверенность. За 2 года использования на кафедре ошибки встречались нечасто. Большинство из них исправлено в новых версиях. Совместимость с современным языком Delphi.

Недостатки также имеют место:

не всегда хорошо документированные мелкие отличия от наиболее распространённого диалекта Pascal - Delphi в языковых конструкциях;

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

отсутствие компиляции – вы не сможете сделать выполняемый файл (часто называемый также exe-шник или бинарник) и перенести на другой компьютер, для исполнения программ необходимо установить среду разработки;

отсутствие поддержки в Linux и Mac OS X, что иногда может стать препятствием в учебных учреждениях и не обрадует поклонников MacBook’ов, iMac’ов и заядлых линуксоидов.

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

3. Borland Pascal 7. Это ставший классическим компилятор и среда программирования, часто используемая при обучении в школах и университетах до сих пор (упрощённая и более дешёвая версия с урезанной стандартной библиотекой называлась Turbo Pascal). К достоинствам можно отнести выверенность – если что-то не работает, можно быть на 99,99% уверенным, что виноват программист, а не «глюки» среды.

Основной недостаток – устаревший интерфейс (последняя версия выпущена в 1993 году). Привыкшие к традиционным для Windows интерфейсам студенты поначалу испытывают определенные трудности с самыми простыми операциями (сохранение/загрузка, копирование/вставка, навигация между закладками и т.п.). Кроме того, это 16-битный компилятор, который на современных версиях Windows просто не работает. У Borlan Pascal есть проблема легального использования: этот компилятор уже давно не продаётся, но свободное его копирование по-прежнему запрещено законами об авторском праве, т.е. стать его обладателем легально фактически нельзя.

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

Lazarus – бибилиотека компонентов для создания визульных программ и среда разработки для FreePascal. Lazarus + FreePascal иногда рассматривают как бесплатный аналог Delphi, хотя такой подход отражает только один из аспектов их использования. Применение Lazarus на начальном этапе нецелесообразно по тем же причинам, что и Delphi. Кроме того, он не свободен от ошибок и ограничений, в результате чего иногда не сразу можно понять, является ли сбой в работе программы следствием ошибки программиста или «глюком» среды (надо также отметить, что Lazarus в целом лучше работает в Linux, чем в Windows, особенно это касается ситуации, когда права пользователя ограничены).

Дальнейшее изложение будет вестись таким образом, чтобы задания могли быть выполнены в любой из сред: Geany+FreePascal или PascalABC.NET; при наличии отличий от Borland Pascal 7.0 или различий между этими средами будут даваться соответствующие пояснения.

1. Линейные программы: арифметические операторы, стандартные функции и ввод/вывод в текстовом режиме 1.1. Алгоритмы Алгоритм – система четких однозначных указаний, которые определяют последовательность действий над некоторыми объектами и после конечного числа шагов приводят к желаемому результату. Запись алгоритма на языке программирования называется программой.

Чтобы расшифровать упомянутые в определении «некоторые объекты», рассмотрим простую схему работы компьютера (рис. 1.1).

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

«Некоторыми объектами» у нас будут ячейки памяти, содержимое которых мы будем менять, а также экран монитора, на который мы будем выводить информацию.

1.2. Переменные и их типы Обратиться к содержимому ячеек памяти в Паскале можно, вводя переменные. Переменная – это область памяти, которой назначено имя (идентификатор).

Правила составления идентификаторов:

1) идентификатором может быть любое сочетание латинских букв, цифр и знака подчеркивание;

2) цифра не может быть первым символом;

3) большие и малые латинские буквы не различаются (идентификатор A1 эквивалентен идентификатору a1).

Примеры правильных идентификаторов: A, x1, x_1, _b1, SxCf.

Примеры неправильных: 1b, a–b.

Информация, записанная в ячейках памяти с помощью двоичного кода, может быть самого разного рода: двоичное представление чисел, коды текстовых символов, строк и т.д. Какие операции над ячейками памяти допустимы, зависит от типа хранимой в ней информации. Например, хранимое в памяти число можно возвести в квадрат. Но если в тех же ячейках памяти хранится закодированный текст (скажем, ваше имя), то что есть квадрат от вашего имени – неясно. Формальное выполнение тех же действий, что и при возведении числа в квадрат, приведет к бессмысленному результату. В силу этого в языках высокого уровня существует строгая типизация переменных. Иными словами, прежде чем использовать переменную, необходимо указать ее тип. Набор допустимых операций зависит от выбранного вами типа.

Перечислим основные типы, используемые в Паскале:

Integer – целый тип. Его переменные могут хранить целые числа в диапазоне -2147483648 до 2147483647 (это -231 и 231-1).

Real – вещественный тип. Так называемые числа с плавающей точкой. Может быть обычной десятичной дробью (например, 1234.543), а также содержать порядок – символ «е» и какое-либо число за ним, например, 1.2345е3. Такая запись означает, что число 1.2345 нужно умножить на 103. Максимальное количество цифр в числе 15, порядок может быть в диапазоне от -308 до 308.

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

String – строка. Значения переменных – наборы символов.

Boolean – логический тип. Переменная может принимать два значения: true (истина) и false (ложь). Такие значения могут быть, например, у логических выражений набодобие «x>2». Если истинно, что x>2, то выражение принимает значение true иначе значение false.

Чтобы указать тип переменной в Паскале, нужно написать ключевое слово var, затем имя переменной, двоеточие и тип. Например:

var x: integer;

y, z: real;

a22: char;

b_b: string;

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

Особенности среды Borland Pascal Если в качестве среды разработки вы используете Borland Pascal, то следует иметь в виду следующие особенности:

допустимые значения типа integer будут лежать в диапазоне от 32768 до 32767 (это 215 и 2151);

значения типа real могут содержать не более 11 цифр, а допустимые порядки варьируются от 38 до 38;

строка (переменная типа string) может содержать не более 255 символов.

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

Одно из самых фундаментальных действий, которые можно сделать с переменной, – это присваивание значения. Соответствующая инструкция имеет вид x := 2;

Символ «:=» (двоеточие и равно) называется оператором присваивания. Слева от оператора должна стоять переменная, справа – выражение, значение которого имеет тот же тип, что и переменная.

Примеры неправильного использования оператора присваивания:

x := 2.5;

x := y;

значение переменной вещественного типа} Однако инструкция y := x; допустима, так как целые числа являются подмножеством вещественных. Чтобы присвоить значения переменным символьного и строкового типа, соответствующий символ или строку надо взять в одинарные кавычки:

a22 := 'x';

b_b := 'Hello, world!';

Отдельные инструкции в Паскале (а каждое присваивание является отдельной инструкцией) разделяются символом «;».

Арифметические операторы: +, –, *, /, div, mod. Первые четыре обычные операции – сложение, вычитание, умножение, деление. div – взятие целой части от деления двух целых чисел, mod – взятие остатка от деления двух целых чисел. Результат работы этих операторов может быть присвоен переменной:

x := 2*2;

y := (2+x)/5;

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

x := 4/2;

Вместо этого следует писать:

x := 4 div 2;

Сама переменная, которой присваивается значение, может использоваться в выражении, стоящем справа от оператора присваивания. Допустимы, например, следующие инструкции:

x := x+1; {увеличивает значение переменной x на 1} x := 2*x*x;

и т.п.

1.4. Стандартные функции Кроме арифметических операторов, в выражениях могут участвовать функции. У функций есть аргументы, и говорят, что функция возвращает значение. Аргументы пишутся в скобках вслед за именем функции, например, sin(y) – возвращает синус от значения переменной y. Возвращаемые значения можно присваивать переменным или использовать в выражениях:

z := sin(y);

y := (1+2*sin(y))/2;

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

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

Кроме того, возвращаемое функцией значение тоже имеет определенный тип. Функция sin возвращает вещественное значение и его нельзя присвоить целочисленной переменной, а скажем, функция length(s) возвращает целочисленное значение.

Перечислим несколько наиболее распространенных стандартных функций:

round(y) – округление числа. Аргумент целое или вещественное число. Возвращаемое значение целого типа;

trunc(y) – отбрасывание дробной части. Возвращаемое значение целого типа;

sin(y), cos(y) – синус и косинус;

ln(y) – натуральный логарифм;

exp(y) – экспонента;

sqr(y) – возведение в квадрат. Тип возвращаемого значения зависит от типа аргумента. Если аргумент был целым, то результат будет целым.

Иначе результат будет вещественным;

sqrt(y) – квадратный корень. Возвращаемое значение вещественного типа;

abs(y) – модуль. Тип возвращаемого значения зависит от типа аргумента. Если аргумент был целым, то результат будет целым. Иначе результат будет вещественным;

arctan(y) – арктангенс.

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

random – возвращает случайное число в диапазоне от 0 до 1;

pi – возвращает число.

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

x := 2+round(sin(2*pi*y)+2);

1.5. Структура программы Структура программы на Паскале представлена ниже:

program ;

begin end.

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

program MyFirstProgram;

var x: integer;

begin end.

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

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

writeln('Hello');

Печатается слово 'Hello'.

writeln(x);

Напечатается значение переменной x.

x := 2;

writeln('x = ', x);

В одну строчку напечатаются строка «x = » и значение переменной x, т. е. в результате будет напечатано «x = 2».

x := 2;

y := 3;

writeln(x, y);

В одну строчку напечатаются значения переменных x и y, т. е. «23».

Между значениями x и y будет располагаться пробел.

writeln(x);

writeln(y);

Значения x и y будут напечатаны на разных строках.

writeln(2*x+y);

Будет напечатано значение выражения 2*x+y.

writeln;

Вызов writeln без параметров приводит к переходу на новую строку.

Несколько таких вызовов подряд вставят в выводимый текст несколько пустых строк.

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

Ввод информации осуществляется с помощью процедуры readln();

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

Например:

readln(x);

Выполнение программы приостановится, пока пользователь не введет значения переменной x и не нажмет Enter.

readln(x, y, z);

Программа ожидает ввода значений трех переменных. После каждого ввода следует жать Enter.

write('x = ');

readln(x);

Курсор будет мигать не на пустой строке, а на строке, содержащей приглашение вида «x = ».

readln;

В отсутствие параметров процедура просто приостанавливает выполнение программы до нажатия пользователем клавиши Enter.

Используем наши новые знания, написав программу, запрашивающую у пользователя два числа и печатающую их сумму:

program Summa;

var x, y: integer;

begin write('x = ');

readln(x); {ввод значения переменной x пользователем программы} write('y = ');

readln(y); {ввод значения переменной y пользователем программы} writeln('Summa = ', x+y); {печать результата} end.

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

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

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

В данном случае мы имеем дело с простейшей ситуацией – по сути, требуется придумать программу, состоящую из одной строки. Набор операций дан, требуется их скомбинировать так, чтобы получился необходимый результат. Решение данных задач позволит выработать правильный подход и настрой для работы в ситуации, когда «неизвестно, что делать».

Задачи Используя арифметические операторы (+, -, *, /, div, mod), а также функции round(), trunc() и abs(), составьте арифметические выражения для вычисления следующих величин:

1. n-е четное число (первым считается 2, вторым 4 и т.д.).

2. n-е нечетное число (первое – 1, второе – 3 и т.д.).

3. В очереди стоит n людей, сколько человек находится между i-м и k-м 4. Сколько нечетных чисел на отрезке (a, b), если a и b – четные?

a и b – нечетные? a – четное, b – нечетное?

5. Сколько полных минут и часов содержится в x секундах?

6. В доме 9 этажей, на каждом этаже одного подъезда по 4 квартиры.

В каком подъезде и на каком этаже находится n-я квартира?

7. Старинными русскими денежными единицами являются: 1 рубль – 100 копеек, 1 гривна – 10 копеек, 1 алтын – 3 копейки, 1 полушка – 0,25 копейки. Имеется А копеек. Запишите выражения для представления имеющейся суммы в рублях, гривнах, алтынах и полушках.

8. Стрелка прибора вращается с постоянной скоростью, совершая w оборотов в секунду (не обязательно стрелка прибора, это может быть волчок в игре «Что? Где? Когда?» и т.п.). Угол поворота стрелки в нулевой момент времени примем за 0. Каков будет угол поворота через t секунд?

9. Вы стоите на краю дороги и от вас до ближайшего фонарного столба x метров. Расстояние между столбами y метров. На каком расстоянии от вас находится n-й столб?

10. Та же ситуация, что и в предыдущей задаче. Длина вашего шага z метров. Мимо скольких столбов вы пройдете, сделав n шагов?

11. x – вещественное число. Запишите выражение, позволяющее выделить его дробную часть.

12. x – вещественное число. Запишите выражение, которое округлит его до сотых долей (останется только два знака после запятой).

13. n – целое число. Запишите выражение, позволяющее узнать его последнюю цифру.

14. n – четырехзначное целое число. Запишите выражение, позволяющее узнать его первую цифру.

15. Оператор div в Паскале работает только для целых чисел. Составьте выражение, позволяющее получить целую часть от деления вещественных чисел.

16. Выразите операцию mod через другие арифметические операции.

17. x – вещественное число. Запишите выражение, которое даст +1, b := x > 2;

b := (sqrt(x)-1)/2 > sqr(x);

и т.п.

Первый из приведенных операторов запишет в переменную b значение false. Результат работы остальных зависит от значения переменной x.

Операторы сравнения применимы и к самим логическим переменным и выражениям. При этом считается, что true больше, чем false. Так, например, возможны выражения:

b := b > false;

b := b = true; {снова Иногда, когда требуется проверить равенство сразу трех величин, студенты ошибочно пишут условие вида Паскаль интерпретирует это выражение следующим образом. Первое равенство x = y даст значение true или false, и уже это значение будет сравниваться со значением переменной z. Если z не является переменной логического типа, то среда выдаст сообщение об ошибке. Действительно, нет смысла проверять равенство логического значения и, например, числового. Чтобы проверить равенство сразу трех чисел, необходимо использовать логические операторы.

2.3. Логические операторы Из логических переменных и выражений можно строить более сложные (составные) логические выражения с помощью логических операторов: not (отрицание, логическое НЕ), or (логическое ИЛИ) и and (логическое И).

Выражение not A (где A – логическая переменная или выражение) истинно тогда, когда выражение A ложно, и ложно, когда A истинно.

Выражение A and B истинно, когда одновременно истинны выражения A и B. Если хотя бы одно из этих выражений (A или B) ложно, то A and B ложно.

Выражение A or B истинно, когда любое из выражений A или B истинно, и ложно, когда оба исходных выражения ложны.

Правила работы логических операторов можно также задать с помощью таблиц истинности, в которых указывается истинность составного выражения, в зависимости от значений исходных простых выражений (табл. 1). Составное логическое выражение может содержать сколько угодно логических операторов. При этом в первую очередь выполняются все операторы сравнения (, =, =, ), затем логические отрицания (not), затем логическое И (and) и в последнюю очередь логическое ИЛИ (or). Выражения могут содержать скобки, которые влияют на приоритетность выполнения операций.

Пример вычисления сложного условия:

a:=5;

С помощью логических операторов мы, наконец, можем записать условие равенства сразу трех переменных. Правильный вариант имеет вид (x=y) and (y=z) 2.4. Задачи на составление логических выражений Попробуйте самостоятельно составить логические выражения, принимающие значение true в перечисленных ниже случаях.

1) переменная x попадает в диапазон от –2 до 1 ( x [2; 1] ). Ниже данный диапазон показан на числовой оси (рис. 2.1):

2) переменная x лежит за пределами заданного диапазона, как показано на числовой оси (рис. 2.2):

3) переменная x лежит в одной из показанных на числовой оси областей (рис. 2.3):

4) запишите условия, истинные, когда точка с координатами (x, y) лежит точно на прямой, показанной на рис. 2.4, а, выше этой прямой (рис. 2.4, б) и ниже этой прямой (рис. 2.4, в):

Указание. Чтобы записать уравнение прямой, проходящей через точки ( x1, y1 ) и ( x 2, y 2 ), в виде y = kx + b, необходимо решить систему уравнений:

В результате приходим к уравнению прямой 5) запишите условие, истинное, когда точка с координатами (x, y) лежит в заштрихованных областях рис. 2.5. Задания а – п соответствуют различным вариантам.

6) укажите на плоскости XY область, где истинными являются следующие логические выражения:

(abs(x – y) < 1) and (abs(x) + abs(y) > 1) (abs(x – y) < 1) and (abs(x) + abs(y) > 1) (abs(x) < 1) or (abs(y) < 1) x2 + y2 > (x + y) 7) пусть A и B – логические выражения, принимающие значения true или false. Какие из приведенных пар составных логических выражений эквивалентны, т. е. при любых ли значениях A и B значения выражений слева и справа совпадают?

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

((not A) and (not B)) (not (A or B)) and A (A or B) and (not B) 8) зарплата выдается 5-го числа каждого месяца. Составьте логическое выражение, которое истинно, если на k-е число m-го месяца зарплата уже была выдана 10 раз с начала года.

2.5. Условный оператор Условный оператор позволяет проверить некоторое условие и в зависимости от результатов проверки выполнить то или иное действие.

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

Условный оператор имеет следующую структуру:

if then begin end else begin end;

if, then, else – зарезервированные слова (если, то, иначе).

Если условие имеет значение true, то выполняется 1-я группа операторов, иначе 2-я группа. Если при истинности (или не истинности) условия требуется выполнить всего один оператор, то слова begin и end можно опустить.

Пример. Программа, выбирающая меньшее число из двух веденных:

var x, y: integer;

begin readln(x, y);

begin writeln('Max(x, y) = ', x);

end else begin writeln('Max(x, y) = ', y);

readln;

end.

Пример неправильного оформления:

{Переменные на той же строке, что и var} var x, y: real;

begin readln(x, y);

{Оператор на той же строке, что и if} if x > y then writeln('Max(x, y) = ', x) {begin с отступом относительно if} {writeln без отступа относительно begin} writeln('Max(x, y) = ', y);

{readln без отступа} readln;

end.

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

6) внутри условного оператора могут располагаться любые другие операторы, в том числе и другие условные операторы. То, что находится внутри них, пишется с еще большим отступом.

Например:

begin readln(x, y, z);

begin if x > z then {вложенный if с дополнительным writeln(x); {writeln с еще большим отступом} end.

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

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

Контрольная работа 1. Вычислите, какое значение будет присвоено логической переменной b:

b := not((x>=2)and(x*y4)and(y mod 21));

2. Составьте логическое выражение, которое истинно, когда точка с координатами (x, y) попадает в заштрихованную область на рис. 2.6:

3. Какое значение примут переменные после выполнения следующих операторов:

Задание 2. Составление логических выражений, условный оператор 1. Напишите программу, которая запрашивает два числа, а затем выводит их в порядке возрастания – сначала меньшее, затем большее.

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

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

4. Даны три числа – a, b, c. Если среди них есть отрицательные, возведите их в квадрат. Если после возведения в квадрат число стало больше 20, умножьте его на 2.

5. Напишите программу, которая запрашивает значение x, а затем выводит значение следующей функции от x:

6. Напишите программу, которая запрашивает значения x, y, z, а затем выводит значение следующих функций:

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

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

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

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

10. Пользователь вводит три числа – длины сторон треугольника.

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

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

11. «Узник замка Иф».

За многие годы заточения узник замка Иф проделал вилкой в стене прямоугольное отверстие размером d e. Замок Иф сложен из кирпичей размером a b c. Узник хочет узнать, сможет ли он выбрасывать кирпичи в море из этого отверстия, чтобы сделать подкоп. Снабдите его необходимым для решения задачи софтом. На вход программе подаются 5 чисел (a, b, c, d, e), программа должна давать ответ YES или NO.

12. Напишите программу, которая в зависимости от введенного возраста добавляет слова «год», «года» или «лет». Например, при вводе возраста 1, программа сообщает «1 год», при числе 2 – «2 года», при числе 125 – «125 лет».

3. Цикл for 3.1. Цикл с параметром (for) Современные компьютеры выполняют миллиарды операций в секунду. Однако, к счастью, программистам не приходится писать программы из миллиардов строк кода. Чтобы с помощью короткой программы указать на необходимость выполнения большого количества операций, используется оператор цикла, суть которого в многократном повторении одного и того же набора инструкций. Работа циклов с помощью блок-схем показана на рис. 3.1. В варианте (а), если «условие» истинно, выполняются «операторы» (см. рис. 3.1). После этого снова проверяется «условие», и если оно попрежнему истинно, то снова выполняются операторы и т. д., пока условие не станет ложным. Вариант (б) подобен варианту (а) (см. рис. 3.1), отличие только в том, что сначала выполняются «операторы» и только затем делается проверка «условия», на основе которой мы решаем, нужно ли повторять их выполнение.

В языке Паскаль существует несколько вариантов организации циклов. Рассмотрим один из них, так называемый цикл с параметром или цикл for. Чтобы записать его, нам потребуется переменная целого типа, например:

var i: integer;

Схема его записи выглядит следующим образом:

for i:= to do begin end;

Здесь i – так называемая переменная-счетчик (разумеется, ее не обязательно называть именно i, это может быть любая переменная целого типа). Начальное и конечное значения – это любые выражения, имеющие значение целого типа.

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

Процесс повторяется, пока счетчик не окажется больше конечного значения. Например, если начальное значение 2, а конечное 3, то будут выполнены 2 раза.

Область между словами begin и end, где располагаются повторяющиеся в цикле операторы, называется телом цикла.

Блок-схема работы этого цикла показана на рис. 3.2.

5. Составьте таблицы изменения переменных для циклов Задание 3. Цикл for. Приемы накопления суммы 1.1. Напечатайте таблицу умножения на 5, желательно печатать 1.2. Напечатайте в столбик нечетные числа от 3 до 25.

1.3. Напечатайте свое имя в углах экрана.

1.4. Выведите на экран таблицу значений синуса от 0 до 2. В каждой строке должны стоять один аргумент и одно значение. Количество значений аргумента пусть задает пользователь.

2. Прием накопления суммы 2.1. Напишите программу, которая вычисляет сумму квадратов чисел от 1 до N. Число N программа должна запрашивать у пользователя.

2.2. Напишите программу, перемножающую целые числа без использования операции умножения. Например, при умножении целых чисел n m число m надо сложить само с собой n раз (m+m+…+m).

2.3. Используя прием накопления суммы, найдите сумму нечетных чисел от 1 до N. Число N программа должна запрашивать у пользователя.

2.4. Выведите на экран последовательность сумм чисел от 1 до n; n меняется от 1 до 10. Иными сорвами, первые члены последовательности – 1, 3 (1+2), 6 (1+2+3), 10 (1+2+3+4) и т.д.

2.5. Вычислите сумму элементов последовательности сумм из предыдущего задания.

2.6. Найдите сумму 100 синусов от аргументов в диапазоне от до 2.

3. Прием накопления произведения 3.1. Факториалом целого числа n (обозначается n!) называется произведение всех целых чисел от 1 до n. Напишите программу вычисления факториала введенного пользователем числа.

3.2. Напишите программу возведения числа в целую степень. Число и степень запрашивайте у пользователя.

4. Комбинация обоих приемов 4.1. Используя комбинацию обоих приемов, напишите программу, вычисляющую функцию 1 + x + x 2 + K + x10.

Из математического анализа известно, что lim s n = exp( x). Выясниn те, насколько 5-й и 10-й члены последовательности таких сумм отличаются от exp(x).

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

Будем говорить, что последовательность векторов {x n } задана рекуррентным соотношением, если заданы начальный вектор x0 = ( x0, x0,K, x0 ) и функциональная зависимость последующего вектора от предыдущего Вектора xn можно интерпретировать как наборы значений переменных. Таким образом, они характеризуют состояние вычислительного процесса. Функцию f будем понимать как преобразование значений переменных на каждом шаге цикла.

Задача. Пусть задано рекуррентное соотношение начальное значение x0 = 0. Найдите x5.

Пример 1. Запишите рекуррентные соотношения для нахождения суммы целых чисел от 1 до m и факториала m!

Для суммы начальное значение x0 = 0, рекуррентное соотношение x n+1 = x n + n. Требуемая сумма будет найдена на m-м шаге.

Аналогично для факториала: x0 = 1, x n+1 = n x n, требуемое значение также будет найдено на m-м шаге.

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

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

4.2. Задачи на составление рекуррентных соотношений 1. Придумайте рекуррентное соотношение, задающее следующие числовые последовательности:

2. Придумайте рекуррентные соотношения для вычисления последовательностей следующего вида:

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

4. Составьте рекуррентные соотношения для приведенных ниже величин.

Указание. Как видно, данные формулы основаны на повторении одной или нескольких операций. Рекуррентное соотношение должно содержать их однократное выполнение:

а) золотое сечение Если вычисления продолжать до бесконечности, то результат сойдется к числу, называемому золотое сечение (оно же золотая пропорция, гармоническое деление и число Фидия). Данное число было известно еще до нашей эры (его открытие приписывают Пифагору), а само название было дано Леонардо да Винчи. Считается, что объекты, в которых присутствуют пропорции, равные этому числу, воспринимаются как красивые;

4.3. Многомерные рекуррентные соотношения Размерностью рекуррентного соотношения называют размерность (количество компонент) вектора состояния xn. Соответственно говорят об одномерных или многомерных рекуррентных соотношениях. Программирование вычислений с помощью одномерного рекуррентного соотношения заключается в простом помещении его внутрь цикла. Например, если надо найти 10-й член последовательности xn +1 = 2 xn при x0 = 0.5 :

x:=0.5;

for i:=1 to 10 do x:=2-x*x;

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

for i:=1 to 10 do begin x:=f(x, y);

y:=g(x, y);

end;

получится, что строчка x:=f(x, y);

запишет в x значение xi +1, которое будет использовано в следующей строке вместо требуемого xi. Таким образом, чтобы корректно итерировать многомерные рекуррентные соотношения, надо перед вычислением очередного члена последовательности запоминать предыдущее значение. Для двумерного рекуррентного соотношения (2) корректная программа будет выглядеть как for i:=1 to 10 do begin x:=f(x, y); {вычисляем следующий элемент xi +1 } y:=g(x2, y); {для вычислений используем запомненное значение xi } end;

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

for i:=1 to 10 do begin x2:=f(x, y); {новый член последовательности запоминается в дополнительной переменной y:=g(x, y);

x:=x2;

end;

Контрольная работа 1. Укажите 4-й член последовательности, заданной рекуррентным соотношением 2. Какими рекуррентными соотношениями задаются последовательности?

3. Какую функцию переменной x вычисляет программа? Укажите также рекуррентные соотношения, в соответствии с которыми происходят вычисления:

Контрольная работа 1. Каким рекуррентным соотношением описывается последовательность?

2. Запишите рекуррентное соотношение и первый член последовательности, необходимые для вычисления величины 3. Запишите рекуррентные соотношения, необходимые для вычисления функции:

4. Какую функцию переменной x вычисляет программа?

writeln(y);

5. Имеется двумерное рекуррентное соотношение Начальные условия x1 = 1, y1 = 1. Напишите программу, которая найдет x 20 и y 20.

Задание 4. Вычисления с помощью рекуррентных соотношений 1. Последовательность определяется соотношением xn +1 = xn, где 2. Вычислите золотое сечение по формуле Сделайте 20 шагов. Определите, на сколько точнее вы узнаете золотое сечение, если сделать 30 шагов.

3. В 1674 году Г. Лейбниц показал, что число = 1 + +...

Найдите приближенное значение числа, просуммировав 100 членов этого ряда.

4. Составив соответствующие рекуррентные соотношение, вычислите значения следующих выражений:

6) sin x + sin(sin x) +... + sin(sin(sin(...))).

5. Пользователь вводит 10 чисел. Определите, образуют ли они возрастающую последовательность.

5. Вложенные циклы 5.1. Вложенные циклы: теория Циклы позволяют повторять выполнение любого набора операторов.

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

Пример 1. Напечатать числа в виде следующей таблицы:

Данная таблица состоит из четырех строчек, в каждой из которых число 3 напечатано 5 раз. Строчку из пяти чисел можно напечатать с помощью одного цикла for:

for i:=1 to 5 do write(3, ' ');

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

for k:=1 to 4 do {4 раза делаем то, что написано между begin’ом и end’ом} begin writeln; {переводим курсор на следующую строку} end;

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

Помнить об этом особенно важно, поскольку данная ошибка не обнаруживается на этапе компиляции. Ваша программа запустится, но делать будет вовсе не то, что вы от нее ждете. В приведенном примере (если допустить ошибку, заменив переменную k на i) внешний цикл выполнится всего 1 раз вместо 4. Возможна также ситуация, когда такая ошибка приведет к зацикливанию: внешний цикл будет выполняться бесконечно долго – программа зависнет.

Рассмотрим еще один пример.

Пример 2. Напечатайте числа в виде следующей таблицы:

9 10 13 14 Снова используем внешний цикл для вывода строк, а внутренний для отдельных чисел в одной строке. Используем также отдельную переменную-счетчик n, в которой будет храниться выводимое число:

n:=1;

for i:=1 to 4 do begin for k:=1 to 4 do begin writeln;

end;

Дополнительная переменная-счетчик (n) здесь введена для большей прозрачности алгоритма. Заметив, что всегда выполняется n = ( i 1) 4 + k, можно обойтись без нее.

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

for n:=1 to 16 do begin end;

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

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

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

for i:= to do В частности, если речь идет о вложенных циклах, то пределы изменения переменной во внутреннем цикле могут зависеть от значения переменной внешнего цикла.

Пример 3. Напечатайте числа в виде следующей таблицы:

7 8 9 Решение:

for i:=1 to 4 do begin for k:=2*i-1 to (2*i-1)+4 do writeln;

end;

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

for i:=1 to 10 do begin end;

for i:=1 to 10 do for k:=1 to 10 do В заключение небольшое замечание, касающееся правильного стиля написания программы, содержащей множество циклов (в частности, вложенных). Следует избегать одновременного использования в качестве счетчиков пар переменных с именами i и j, а также p и q. На вид они очень похожи, что часто приводит к трудно обнаруживаемым ошибкам.

Контрольная работа 1. Какое значение примет переменная x после выполнения программ:

2. Что выведут программы?

Задание 5. Вложенные циклы 1. Из математического анализа известно, что последовательность сумм вида сходится к функции sin x. Исследуйте зависимость от x точности приближения синуса десятым членом последовательности. Для этого рассчитайте величину sin x s10 ( x) в 20 точках в диапазоне от 0 до 2.

2. «Рисование» символами.

а) выведите на экран числа в следующем виде:

и т.д.

б) выведите на экран числа в следующем виде:

в) выведите на экран числа в следующем виде:

г) выведите звездочки «полуелочкой» (рис. 5.1) заданное количество раз.

д) превратите «полуелочку» в полную елочку.

6. Задачи на перебор вариантов 6.1. Перебор вариантов: теория Имеется целый класс задач, решение которых сводится к перебору различных вариантов, среди которых выбирается такой, который удовлетворяет условию задачи.

Пример 1. Поиск делителей целого числа N.

Целое число K является делителем N, если остаток от деления N на K равен 0. Чтобы найти все делители, достаточно перебрать все числа от 1 до N и проверить, являются ли они делителями. Данный алгоритм можно реализовать с помощью программы:

readln(n);

for i:=1 to n do На этом простейшем примере ясна общая структура решения задач на перебор вариантов. Для организации перебора используется цикл, каждый шаг выполнения которого соответствует рассмотрению одного из вариантов. Внутри цикла стоит проверка, подходит ли данный вариант под условие задачи.

Решая задачи методом перебора, всегда следует подумать, а нельзя ли каким-то образом сократить количество перебираемых вариантов. В данном случае заметим, что любое число делится само на себя и на 1. Поэтому эти варианты можно исключить из перебора. Более того, наибольшим делителем, отличным от самого числа N, может быть только N/2, а все числа, большие N/2, заведомо делителями не являются. Учет этих особенностей приводит к более эффективной программе:

readln(n);

write(1, ' ');

for i:=2 to n div 2 do write(n);

Конец примера.

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

Пример 2. Найти минимумы функции f ( x) = x 4 x 2 с точностью до 0. на отрезке от –5 до 5.

Для поиска минимума будем перебирать все числа от –5 до 5 с шагом 0.001. Условием нахождения минимума будем считать то, что значение функции f ( x min ) меньше, чем в соседних точках. А именно:

Данный алгоритм можно реализовать с помощью программы:

Step:=0.001;

MinX:=-5;

MaxX:=5;

{Вычисляем количество перебираемых вариантов решения} VarNumber:=trunc((MaxX – MinX)/Step)+1;

for i:=1 to VarNumber do begin {Вычисляем вариант, соответствующий номеру i} x:=MinX + (i-1)*step;

{Проверяем вычисленный вариант} if (sqr(sqr(x)) –sqr(x) < sqr(sqr(x-step)) – sqr(sqr(x+step))) end;

Кроме перебора вариантов, в начале программы использован еще один важный прием, называемый параметризацией. Такие характеристики, как точность и диапазон поиска были записаны в отдельные переменные, а затем вместо чисел использовались имена этих переменных. Такой подход позволяет легче модифицировать программу, если параметры задачи изменятся, программа становится более универсальной, а также понятнее, особенно если имена переменных выбраны так, чтобы соответствовать смыслу хранимого в них параметра (MinX – минимальное значение переменной x и т.п.) Каждый следующий проверяемый вариант можно также вычислять не по номеру x:=MinX + (i-1)*step;

а по предыдущему значению x:=x + step;

Очевидно, это ничем не хуже.

Пример 3. Пусть двумя числами (H и V) задано положение коня на шахматной доске. Найдите координаты всех клеток, куда конь может пойти следующим ходом (других фигур на доске нет).

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

Всего клеток 64. Пронумеруем клетки, как показано на рис. 6.1. Теперь, если мы будем перебирать в цикле номера клеток N, необходимо уметь по этим номерам определять номер горизонтали X и вертикали Y. Нетрудно видеть, что номер горизонтали определяется тем, сколько раз по 8 клеток надо взять, пока мы не доберемся до числа N:

X := N div 8 + 1;

Остаток после удаления целого числа раз по 8 клеток позволит вычислить номер вертикали:

Y := N mod 8;

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

Пусть проверяется клетка с координатами (x, y). Тогда условие сдвига по вертикали на 2 будет выглядеть так:

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

abs(y–V) = 1.

Полное условие возможности пойти на клетку конем будет выглядеть как ((abs(x-H) = 2)and(abs(y-V) = 1)) or Иными словами, либо сначала по горизонтали на две клетки, а потом на одну по вертикали, или на две по вертикали, потом на одну по горизонтали.

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

readln(H, V); {запрашиваем расположение коня} for n:=1 to 64 do begin if ((abs(x-H) = 2) and (abs(y-V) = 1)) or ((abs(yV) = 2) and (abs(x-H) = 1)) then end;

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

readln(H, V);

for x:=1 to 8 do if ((abs(x-H) = 2) and (abs(y-V) = 1)) or ((abs(y-V) = 2)and(abs(x-H) = 1)) then Рассмотрим еще один пример, где вариант задается несколькими числами.

Пример 4. Составить программу-генератор пифагоровых троек. Пифагоровой тройкой называют такие целые числа a, b и c, которые удовлетворяют условию a 2 + b 2 = c 2. Такие числа могут быть сторонами прямоугольного треугольника. Найти такие числа для c 25.

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

MaxC := 25;

MaxAB:=trunc(sqrt(MaxC));

for a:=1 to MaxAB do for b:=1 to MaxAB do Как всегда при решении задачи методом перебора, следует задуматься, можем ли мы сократить число перебираемых вариантов. Оказывается, можно ограничиться только перебором a и b, а c вычислять по теореме Пифагора: c = a 2 + b 2. Вычисленное таким образом c может оказаться нецелым, поэтому условие задачи для него проверять все равно необходимо:

MaxC := 25; {используем параметризацию} MaxAB := trunc(sqrt(MaxC));

for a := 1 to MaxAB do begin for b := 1 to MaxAB do begin if a*a+b*b = c*c then end;

Задание 6. Задачи на перебор вариантов 1. Для заданного целого числа проверьте, является ли оно кубом другого целого числа.

2. Задача Ал-Хорезми. Разложить число 10 на 2 слагаемых, сумма квадратов которых равна 58.

3. Задача Л. Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он уплатил по 31 талеру, а за каждого быка по 21 талеру. Сколько лошадей и быков купил чиновник? Используйте прием параметризации, чтобы легче было модифицировать программу при изменении рыночных цен и финансовых возможностей чиновника.

4. Теорема Ферма утверждает, что не существует решения в целых числах уравнения x n + y n = z n при n > 2. Напишите программу, проверяющую это утверждение при заданном n для всех x, y и z меньших 100.

5. Найдите все трехзначные числа, сумма цифр которых равна произведению цифр.

6. Решите следующие числовые ребусы:

БУЛОК + БЫЛО = МНОГО Здесь каждая буква взаимно-однозначно соответствует какой-нибудь цифре. Первая цифра числа не может быть нулем.

7. Переменные-флаги 7.1. Переменные-флаги: теория Флаг – это полотнище правильной (как правило, прямоугольной) формы, прикрепленное к древку или поднимаемое на специальной мачте (флагштоке). Исторически флаги появились для передачи простых сигналов на поле боя. Например: подняли флаг, и конница понеслась в атаку!

Как-то так. В простейшем случае с помощью флага передается информация объемом 1 бит (одно из двух: флаг поднят или нет).

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

1) подводится баланс коммерческого предприятия. Дальнейшие действия могут зависеть от того, будет он положительным или отрицательным. Если отрицательный, надо просить кредит, положительный – планировать отдых на Багамах. В общем, самая существенная информация может быть передана одним битом;

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

3) детям на уроке физкультуры велено построиться по росту. Если они построились не по росту, надо на них наорать. Опять действия учителя зависят от информации объемом 1 бит.

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

Пример 1. Решение квадратного уравнения.

Предположим, что программу решения квадратного уравнения пишут два человека (ну, можно же).

Пусть первый умеет решать квадратные уравнения, но не знает, как вывести результат (не ходил на лекции).

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

var a, b, c: real; {коэффициенты RootsExist: boolean; {переменая-флаг} begin {Блок, написанный первым программистом} readln(a, b, c);

d := sqr(b)-4*a*c;

RootsExist := (d>=0);{флаг служит для хранения информации о наличии корней} if RootsExist then begin x1 := (-b+sqrt(d))/(2*a);

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

{Блок, написанный вторым программистом} if RootsExist then writeln('Roots don’t exist');

end.

Переменная-флаг передает информацию о наличии корней. С ее помощью первый блок сигнализирует второму блоку. Вы скажете, почему бы второму программисту вместо строчки if RootsExist then не написать if d >= 0 then Зачем использовать еще одну переменную? Давайте вспомним, что второй программист ничего не знает о квадратных уравнениях и, в частности, не в курсе, что наличие корней определяется знаком дискриминанта.

Не вдаваясь в тонкости чужой задачи, он просто просит первого программиста передать существенную информацию через переменную-флаг.

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

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

Как уже отмечалось, флаги минимизируют информацию, передаваемую между блоками. Так, в примере с квадратным уравнением использование флага позволило передавать всего 1 бит вместо 6-ти байт, которые пришлось бы потратить на значение дискриминанта. Общий принцип здесь такой – чем меньше информации, тем труднее допустить ошибку. При разработке сложных программ поиск ошибок занимает больше времени, чем собственно их написание, и любая возможность уменьшить вероятность их появления должна приветствоваться.

В дополнение еще один пример.

Пример 2. Проверка упорядоченности последовательности.

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

Решение:

Growing := true; {переменная-флаг} readln(x);

for i:=2 to 10 do begin readln(x);

Growing := Growing and (x0) then end;

writeln(Counter);

Пример 2. Пользователь вводит 10 чисел. Проверить, упорядочены ли они по возрастанию.

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

Counter := 0;

readln(x);

for i := 2 to 10 do begin readln(x);

if x2 > x then Counter : =Counter + 1;

end;

if Counter = 0 then writeln('Последовательность упорядочена') else writeln('Последовательность не упорядочена');

Пример 3. Вычисление площади сложных фигур методом Монте-Карло.

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

Рассчитаем таким способом площадь под кривой графика y = sin x (см. рис. 8.1) в диапазоне от 0 до.

N := 1000;

C := 0; {Инициализируем счетчик} for i := 1 to N do begin чайные координаты точки внутри прямоугольника} x := Pi * random;

y := random;

{В случае попадания в область под кривой увеличиваем счетчик} if y < sin(x) then C := C + 1;

end;

{Подсчитываем площадь фигуры} S := Pi * C / N;

writeln(S);

Задание 8. Переменная-счетчик событий 1. Создайте программу, запрашивающую у пользователя 10 чисел.

Если больше 4 из них окажутся больше 10, выведите сообщение «Караул!

Сейчас все взорвется». Иначе сообщите, сколько введенных чисел больше 10, а сколько больше 5.

2. Напишите программу, которая генерирует n случайных чисел, способных принимать значения в диапазоне [–1; 2], и подсчитывает, сколько среди них отрицательных.

3. С помощью метода Монте-Карло получите приближенное значение числа. Для этого подсчитайте площадь окружности единичного радиуса.

4. Напишите программу для подсчета числа точек с целочисленными координатами, находящихся внутри круга с центром в начале координат и радиусом 1000.

9. Циклы while и repeat 9.1. Синтаксис циклов while и repeat В отличие от цикла for циклы while (оператор цикла с предусловием) и repeat (оператор цикла с постусловием) позволяют повторять выполнение тех или иных операторов не фиксированное количество раз, а только пока выполняется некоторое условие. Структура записи этих операторов выглядит следующим образом:

while do begin end;

– любое логическое выражение.

– любые операторы.

Перед каждым выполнением тела цикла анализируется значение выражения. Если оно истинно (true), выполняется тело цикла.

Затем снова проверяется условие и т.д. Если значение условия ложно (false), то работа цикла завершается. Если результат условия окажется ложным при первой проверке, то тело цикла не выполнится ни разу.

Цикл repeat работает похожим образом, однако в нем условие проверяется в конце цикла (после выполнения каждого шага). Структура записи оператора выглядит следующим образом:

repeat until ;

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

Повторение продолжается пока не выполнится условие, стоящее после слова until («пока не»). Таким образом, если в цикле while мы задаем условие для продолжения повторений, то в случае repeat‘а ставится условие на прекращение повторений. Блок-схемы работы циклов while (а) и repeat (б) представлены на рис. 9.1.

Пример 1. Имитация работы цикла for.

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

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

Пример 2. Напечатайте все нечетные числа от 3 до 25.

i := 3;

while i 10;

Если вы забудете строку с увеличением счетчика, то i никогда не станет больше 10. Это настолько распространенная ошибка, что рекомендуется первым делом писать увеличение счетчика, а только потом возвращаться назад и писать все остальные операторы в теле цикла.

9.3. Цикл, управляемый меткой Циклом, управляемым меткой, называется такой цикл, в теле которого на каждом шаге происходит запрос данных у пользователя, а сигналом к выходу из цикла служит ввод пользователем так называемой «метки выхода».

Для примера создадим программу, которая запрашивает у пользователя числа и подсчитывает их сумму. Количество чисел заранее не оговаривается, меткой выхода служит ввод числа 0:

s := 0;

repeat readln(x);

until x = 0;

writeln(s);

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

s := 0;

readln(x); {Запрос первого числа} while x 0 do begin readln(x);

end;

writeln(s);

9.4. Вычисление номера шага Когда в параграфе 9.1 с помощью циклов с условиями имитировалась работа цикла for, счетчик шагов использовался для определения момента выхода из цикла. Однако легко представить себе ситуацию, когда выход из цикла осуществляется по какому-нибудь другому условию, а счетчик служит для определения числа шагов, потребовавшегося для вычислений.

Пример 3. Коммерсант, имея стартовый капитал k рублей, занялся торговлей, которая ежемесячно увеличивает его капитал на p процентов. Через сколько лет он накопит сумму s, достаточную для покупки собственного магазина?

Решение:

x := k;

n := 0;

while x < s do begin x := x * (1 + p / 100); {увеличиваем ее на p процентов} end;

writeln(n div 12, ' years and ', n mod 12, ' 9.5. Вычисления с заданной точностью При реализации многих численных методов точность вычислений зависит от числа шагов. Однако за какое именно число шагов будет достигнута приемлемая точность, заранее сказать трудно, и желательно, чтобы программа сама определяла, когда следует остановиться.

Например, синус можно разложить в так называемый ряд Тейлора:

Чем большее количество членов ряда будет просуммировано, тем точнее будет вычислен синус. Пусть требуется вычислить до 5-го знака после запятой. Иными словами, приемлемая погрешность = 10 5. Для этого достаточно суммировать члены ряда до тех пор, пока очередной его член не окажется меньше 105 :

eps := 1e-5;

readln(x);

p := x;

s := x;

n := 2;

4. При выполнении следующей программы пользователь ввел числа 1, 20, 17, 6, 10, 13. Какое число выведет программа?

readln(x);

writeln(m);

Задание 9. Циклы while и repeat 1. Напечатайте на экране 10 раз слово Hello с помощью цикла while и столько же с помощью цикла repeat.

2. Напечатайте в столбик нечетные числа от 3 до 25.

3. Найдите минимальное число большее 300, которое делится на 19.

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

5. Из математического анализа известно, что последовательность сумм вида сходится к функции cos x. Напишите программу, которая будет суммировать этот ряд до тех пор, пока очередная добавка не окажется меньше 10 6.

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

7. Последовательность Фибоначчи определяется рекуррентным соотношением x n+1 = x n + x n1, где x0 = 1, x1 = 1. Найдите первое число в последовательности Фибоначчи, которое больше 1000.

8. Для n-го члена в последовательности Фибоначчи существует явная формула x n = 2 2. Поскольку операции с вещественными числами происходят с конечной точностью, то с ростом n результат вычисления по этой формуле будет все больше отличаться от настоящего числа Фибоначчи. Найдите n, начиная с которого, отличие от истинного значения составит 0.001.

9. Создайте программу, играющую с пользователем в орлянку. Программа должна спрашивать у пользователя, орел или решка? Если пользователь вводит 0, то выбирает орла, 1 – решку, любое другое число – конец игры. Программа должна вести учет выигрышей и проигрышей и после каждого раунда сообщать пользователю о состоянии его счета. Пусть вначале на счету будет 1 рубль и ставка в каждом коне тоже 1 рубль. Если денег у пользователя не осталось, игра прекращается.

10. Усовершенствуйте разработанный в предыдущем задании «игровой автомат» таким образом, чтобы выигрыш происходил только в 40% случаев.

11. В 1593 году Франсуа Виет предложил для вычисления числа формулу В 1655 году профессор Оксфордского университета Джон Уоллис (John Wallis) предложил формулу Сообщив о ней лорду Брункеру (Lord Brouncker), он получил в ответ разложение Наконец, 1674 году Г. Лейбниц показал, что число Определите, какой из этих способов обеспечивает более быструю сходимость.

10. Массивы 10.1. Структурные типы данных Для большинства рассмотренных ранее типов данных было характерно два свойства: неделимость и упорядоченность их значений. Например, целое число есть объект, не распадающийся на компоненты (неделимость), а множество целых чисел упорядочено. Можно, конечно, сказать, что число состоит из цифр, но отдельная цифра, как правило, не имеет самостоятельного смысла. Скажем, есть число – количество студентов в группе. Что означает вторая цифра этого числа? По-видимому, ничего. Такие типы называются скалярными.

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

Приведем примеры.

1. Оценка за контрольную конкретного студента – скалярное значение, а результаты контрольной по студенческой группе образуют структурное значение.

2. Вектор задается своими координатами. Отдельные координаты – скалярные значения, вектор целиком – структурное.

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

10.2. Основные определения Переменная, имеющая структуру массива, является совокупностью компонент одного и того же типа. В математике наиболее близкими понятиями являются вектора и числовые последовательности, где целая группа чисел обозначается одним именем, а для обращения к каждому отдельному числу последовательности используются различные индексы. Выглядеть это может, например, так: a1, a 2, a3,K a n. Иными словами, обращаемся к конкретному элементу, например a3, указав имя последовательности или вектора (а) и номер (индекс) элемента (3).

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

type Конкретный пример:

type TMassive = array [1..10] of real;

Здесь – произвольный правильный идентификатор, любое имя, которое вы захотите дать своему типу. Согласно правилам хорошего стиля имя начинается с большой буквы T (это позволяет отличать идентификаторы типов от всех прочих). Остальная часть имени придумывается в соответствии со смыслом данных, которые будут храниться в переменных этого типа, и пишется с заглавной буквы (опять это не обязательное требование, но желательное с точки зрения стиля). Примеры стилистически правильных имен:

TGrades – для хранения оценок за контрольную;

TVector – для хранения координат абстрактного вектора;

TMassiv – просто массив, когда не приходится задумываться, что означают его отдельные элементы (просто куча чисел);

– произвольный стандартный или ранее введенный вами тип. Если это, например, тип real, то массив представляет собой несколько вещественных чисел;

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

Например, в качестве типа можно указать –5..5. В этом случае массив будет содержать 11 элементов, первому из которых соответствует индекс –5, второму –4 и т. д.

Приведем несколько примеров описания типов массивов:

TMassive2 = array [0..100] of real; – набор из 101 вещественного числа с индексами в диапазоне от 0 до 100.

TNames = array [1..20] of string; – массив, подходящий для хранения имен 20 человек.

TLargeMassive = array [integer] of real; – массив из 4294967296 ( 232 ) вещественных чисел. Каждая переменная такого типа будет занимать в памяти 232 8 байт = 16 Гб, что довольно много. Именно поэтому рекомендуется заранее подумать, сколько элементов вам реально понадобится, и использовать тип-диапазон с нужным количеством возможных значений.

TIntMassive = array [1..20] of integer; – массив, значением которого будет набор из 20 целых чисел.

После того как описан тип, можно вводить его переменные.

var x, y: TMassive;

Можно обойтись и без введения специального типа, описывая переменные как a, b: array [1..10] of real;

Однако впоследствии (при изучении темы «Процедуры и функции») потребуется именно введение типа, так что лучше привыкать сразу и всегда пользоваться заранее описанным типом.

В описанных переменных хранятся сразу 10 вещественных значений.

Индексами являются числа от 1 до 10. Для простоты индексы можно понимать как номера хранящихся в массиве чисел. Элемент массива a с индексом i обозначается как a[i]. Например, a[1] – элемент с индексом 1.

Каждый элемент можно рассматривать как переменную типа real и соответственно с ней обращаться – присваивать ему значения, использовать в выражениях и т.д. Например, операторы a[1]:=2.5;

readln(a[2]);

a[3]:=2*a[2]+a[1];

запишут в 1-й элемент число 2.5, во второй – то, что пользователь введет с клавиатуры, а третий элемент будет вычислен по первым двум.

10.3. Вычислимость индексов До сих пор массив ничем не отличался от набора однотипных элементов. В конце концов, мы могли бы сделать объявление:

a1, a2, a3, a4, a5, a6, a7, a8, a9, a10: real;

и также пользоваться этими переменными. Массивы разве что сокращали длину описания (представьте, что таких переменных вам понадобится штук). Однако есть радикальное отличие, столь важное, что разговор о нем выносится нами в отдельный раздел. Дело в том, что индексы элементов массива в отличие от номеров переменных в сделанном выше объявлении можно вычислять. Иными словами, для указания элемента массива можно использовать не только числа (1, 2 и т. д.), но и произвольное выражение, тип значения которого совместим с типом индекса.

Например, если объявлены переменные var i: integer;

x: array [1..10] of real;

y: array [1..10] of integer;

допустимы следующие обращения к элементам массива x:

x[2*2] – обращение к 4-му элементу массива;

x[i] – обращение к элементу массива, индекс которого хранится в переменной i;

x[2*i] – индексом является удвоенное значение переменной i;

x[i+1] – снова индекс – арифметическое выражение;

x[random(10)+1] – случайный элемент массива;

x[y[i]] – в качестве индекса берется число, хранящееся в i-м элементе другого массива. Если значение y[i] не попадает в диапазон 1..10, то такое обращение вызовет ошибку.

10.4. Примеры программ, работающих с массивами Пример 1. Заполнение массива случайными числами.

const type TMassive = array [0..n-1] of real; {тип-массив из n var x: TMassive;

i: integer;

begin for i:=0 to n-1 do x[i]:=random; {заполнение writeln(x[i]); {вывод элементов массива} end.

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

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

Пример 2. Вычисление среднего арифметического элементов массива.

Вычисление состоит из двух этапов – подсчета суммы элементов и ее деления на общее число элементов:

const type TMassive = array [0..n-1] of real;

var x: TMassive;

s: real;

i: integer;

begin … {Присвоение значений элементам массива x} s:=0;

for i:=0 to n-1 do s:=s+x[i];

s:=s/n;

writeln('Mean value = ', s);

end.

Смысл программы кажется прозрачным и не нуждается в пояснениях.

Пример 3. Поиск элемента в массиве.

Пусть заданы вещественнозначный массив x[1], x[2], …, x[n], а также число y. Определить, есть ли в массиве элемент x[k], такой что x[k] = y, и чему равен его индекс k:

const type TMassive = array [0..n-1] of integer;

var x: TMassive;

y: real;

k: integer;

begin … {Присвоение значений элементам массива x} readln(y);

k:=0;

while (k < n)and(x[k] y) do writeln('No such element') writeln('Element has number: ', k);

end.

Цикл while может закончиться по двум причинам: когда найден нужный элемент (x[k] = y) или когда были проверены все элементы ( k >= n ). Понять, что послужило причиной окончания цикла, можно по значению переменной k.

Заметим, что если в массиве нет искомого элемента, то на последнем шаге цикла k = n + 1. По этой причине принципиально, в каком порядке стоят условия продолжения цикла while. Если поменять их местами, сделав (x[k]y)and(kx[Kmax] then запоминаем его номер. На следующем шаге цикла новый элемент будет сравниваться уже с ним} writeln('Max = ', x[Kmax]);

writeln('Max element index = ', Kmax);

end.

10.5. Сортировка массивов Одна из важнейших задач, связанных с массивами, – сортировка, т. е.

расположение элементов массива по возрастанию или убыванию. Пусть есть массив, содержащий 4 элемента:

x[1] = 0.5, x[2] = 0.75, x[3] = 0.12, x[4] = 0.62.

Сортировка будет заключаться в преобразовании этого массива к виду x[1] = 0.12, x[2] = 0.5, x[3] = 0.62, x[4] = 0.75.

Чаще всего сортировка применяется для последующего поиска.

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

Есть и масса других применений.

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

Идея следующая. На первом шаге в массиве ищется самый маленький элемент и меняется местами с первым. На втором шаге ищется самый маленький, начиная со второго, и ставится на 2-е место (второй элемент, естественно, не забываем: ставим его на место, где раньше был самый маленький). И так далее, на i-м шаге ищется самый маленький, начиная с i-го, и ставится на i-е место. Программную реализацию этого метода оставим для самостоятельной реализации.

10.6. Хороший стиль при решении задач на массивы Большинство правил уже упоминалось выше в предыдущих параграфах. Теперь просто сведем их воедино:

1. Количество элементов массива следует задавать с помощью константы. Далее в программе всюду следует использовать эту константу, а не задавать количество элементов явно цифрами. Так, во всех приведенных в параграфе 10.4 примерах использовалась константа n, а не само число элементов (10).

2. Следует описывать тип-массив и использовать его переменные.

3. Следует стремиться разделять такие задачи, как:

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

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

Контрольная работа 1. Пусть описан тип-массив:

TMas = array [-n..n] of real;

Какой индекс будет иметь второй по счету, третий, предпоследний и третий с конца элементы этого массива? Каким по счету идет элемент с индексом 0?

2. Пусть имеется массив с шестью целочисленными элементами, равными x[0] = 2, x[1] = 8, x[2] = 10, x[3] = 3, x[4] = 2, x[5] = –6.

а) какие значения примут элементы массива после выполнения операторов?

i := 2;

c := x[1+i];

x[1+i] := x[2*i-2];

x[2*i-2] := x[2*i-1];

x[2*i-1] := c;

б) какое число выведет программа?

s1 := 0;

s2 := 0;

for i := 0 to 2 do begin s1 := s1 + x[2*i+1];

s2 := s2 + x[2*i];

end;

writeln(s2 - s1);

в) какое число выведет программа?

s := 0;

for i := 0 to 2 do s := s + x[i] - x[6-i];

writeln(s);

г) какие значения примут элементы массива после выполнения операторов?

n:=6;

for i:=0 to 2 do begin c:=x[n-1];

for k:=n-2 downto 0 do x[k+1]:=x[k];

x[0]:=c;

end;

3. Пусть имеется массив с элементами: x[0] = 6, x[1] = 3, x[2] = 9, x[3] = 1. Какие значения примут элементы массива после выполнения операторов?

until n=0;

for i:=0 to N-1 do writeln(x[y[i]]);

Задание 10. Массивы 1. Заполнение массивов.

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

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

2. Пусть описаны константа и два типа-массива:

const type TMas1 = array [1..2*m+1] of real;

TMas2 = array [-m..m] of real;

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

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

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

а) Если элементы меньше заданного числа, замените их этим числом.

б) Замените все элементы с индексами в диапазоне [a, b] нулями.

в) Поменяйте местами первый и последний элементы массива.

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

е) Поменяйте местами элементы с четными и нечетными индексами ж) Сожмите массив, выбросив из него каждый второй элемент.

Оставшуюся половину массива заполните нулями.

з) Вставьте дополнительный элемент в массив в заданное место.

Чтобы освободить это место, все элементы, начиная с него, сдвиньте вправо. Последний элемент будет некуда девать – и) Определите индекс указанного пользователем элемента массива.

Если такого элемента нет, сообщите об этом пользователю.

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

а) Получите массив из разностей соседних элементов исходного б) Получите массив из скользящих сумм n соседних элементов.

Иными словами, каждый i-й элемент нового массива – это сумма n элементов старого, начиная с i-го. Новый массив, очевидно, будет содержать на n-1 элементов меньше. Пусть массивы заданы с одинаковой длиной, просто не выводите элементы нового массива, которые невозможно вычислить.

6. Получите сумму и среднее арифметическое всех элементов массива.

7. Получите корень из суммы квадратов всех элементов массива (модуль вектора).

8. Для двух массивов получите сумму попарных произведений их членов (скалярное произведение).

9. Для двух массивов получите евклидово расстояние между ними.

10. Найдите максимальный и минимальный элементы массива.

11. Отсортируйте элементы массива методом выбора.

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

Пример 1. Создадим программу с процедурой, печатающей на экране слово Hello:

program HelloProc;

procedure P1; {заголовок процедуры. P – имя процедуры} begin {начало тела процедуры} writeln('Hello');

end; {конец тела процедуры} begin {начало программы} P1; {вызов процедуры} P1; {еще один вызов процедуры} end. {конец программы} На этом примере мы видим следующее:

1) Описание процедуры располагается в разделе описаний программы (там же, где описываются переменные, типы, константы и т.п.). Традиционно описание процедур ставится в конец раздела (после того как описаны все переменные), но это не обязательно.

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

3) Тело процедуры ограничено словами begin и end. После end’а ставится точка с запятой. В теле процедуры пишутся все инструкции, которые будут выполняться при ее вызове.

4) Вызов процедуры производится в разделе операторов программы.

Для вызова достаточно написать имя процедуры. В приведенном примере вызов производится два раза. Соответственно дважды будет напечатано слово Hello.

11.2. Локальные переменные Каждая процедура может иметь собственный раздел описания переменных (а также типов, констант и т.п.). Переменные, описанные в этом разделе, называются локальными и действуют только внутри процедуры.

Часто некоторые переменные используются только внутри некоторой последовательности инструкций и не имеют смысла за их пределами.

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

Пример 2. Программа с процедурой, печатающей слово Hello 10 раз.

var i: integer;