8. Введение в программирование

8.1. Основные понятия программирования

Введем основные понятия программирования. Их рассмотрение позволит сосредоточить внимание на специфике вычислительной машины как средства выполнения разрабатываемых программ и подготовит Вас для восприятия дальнейшего материала.

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

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

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

Пример. Требуется найти произведение любых двух натуральных чисел n, m. Результат обозначить через k.

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

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

Переменную можно представить себе как ящик, обозначенный именем, идентифицирующим эту переменную. Присвоение переменной с именем n значения 5 можно представить себе так; положить в ящик, обозначенный n, 5 шаров. (Ящик является аналогом ячейки памяти ЭВМ.)

Значение одной переменной можно переслать в другую переменную. При этой операции значение пересылаемой переменной не изменяется. Например переслать значение n в переменную i, или присвоить переменной i значение n, означает задать i такое же значение, которое имеет переменная n, т.е, скопировать значение n. Если было, допустим, n=5, то присвоение i значения n (записывается i = ni присвоить значение n) означает, что нужно как бы посмотреть, какое число находится в ячейке памяти n, и такое же число "положить" в ячейку памяти i. Теперь будет i=5, но при этом n сохранило значение (n=5). Следует отметить также, что в выражении i = n знак "=" обозначает не равенство, а операцию присвоения.

Часто в программировании используется такая операция присваивания, когда слева и справа используется одна и та же переменная, например, i = i + 1. Такая запись означает, что сначала должна быть выполнена операция сложения (i+1), а затем полученная сумма присвоена переменной i в качестве ее нового значения. При этом старое значение i пропадает, "стирается". После выполнения этой операции i будет иметь значение на 1 больше, чем перед ее выполнением.

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

Но эта формула — не программа, хотя бы потому, что здесь есть неопределенность (например, многоточие),

Решение этой задачи можно представить как последовательность выполнения следующих простых шагов;

Положить k = 0.

Далее выполнить операцию

k = k + n

m раз. При этом после каждого выполнения указанной операции значение k увеличивается наn. В итоге в k будет получен результат решения задачи.

Чтобы выполнить операцию требуемое число раз, нужно считать, сколько раз эта операция уже выполнена. Используем для этого вспомогательную переменную i. Назовем ее счетчиком. Перед первым прибавлением к k значения n положим i = 1 и после очередного изменения k. значение счетчика i будем менять на 1.

Тогда программа может быть записана так:

1 задать конкретные значения n, m

2 k = 0

3 i =1

4 k = k + n

5.i = i +1

6 если i m идти к 4. (Повторить выполнение операций, начиная с п. 4)

7 закончить вычисления

Пояснения к программе.

1. Программа написана на обычном языке человеческого общения с использованием общепринятой математической символики (это так называемый "естественный" язык).

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

3. Оператор 4 при каждом своем выполнении увеличивает значение k на n. Оператор 5 увеличивает значение счетчика на 1 после того, как выполнено очередное сложение.

4. Оператор 6 проверяет условие i m, и если оно выполняется, т. е. не все m сложений еще выполнены, то происходит возврат к оператору 4 и повторное выполнение программы, начиная с оператора 4. Как только в процессе выполнения программы условие i m не будет выполнено, процесс вычислений заканчивается. Это произойдет, когда будет i > m, т. е. все нужные сложения выполнены.

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

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

Упражнение 1. Выполнить программу при n=5, m=3. Проследить за изменением переменных.

Указание. Для каждой переменной, используемой в программе (n, m, k., i), предусмотреть ячейку памяти. При задании значения переменной записать это значение в ячейке памяти с соответствующим именем. После выполнения программы сравнить содержимое ячейки k с правильным ответом (результатом умножения 3 на 5).

Решение. Содержимое ячеек памяти (значения переменных) после выполнения оператора 1.

Отсутствие записи означает, что значение переменной не определено.

Содержимое ячеек памяти после выполнения операторов 2, 3.

Содержимое ячеек n, m далее не изменяется.

После первого выполнения операторов 4, 5.

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

При первом выполнении оператора 6 проверяется условие 2 3. Оно имеет значение да, поэтому следующим выполняется оператор с номером 4.

После второго выполнения операторов 4, 5.

При втором выполнении оператора 6 условие 3 3 имеет значение да, и снова выполняется оператор 4.

После третьего выполнения операторов 4, 5.

При третьем выполнении оператора 6 условие 4 3 не удовлетворяется (имеет значение нет}, и выполнение программы прекращается.

Результатом является последнее значение переменной k, равное 15.

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

k

0

5

10

15

i

1

2

3

4

Отметим, что в рассмотренной программе после выполнения оператора 6 (если условие выполняется) осуществляется возврат к оператору 4 и повторное выполнение операторов 4—6. Многократно повторяющаяся при выполнении часть программы носит название цикл. Цикл является типичной структурой, реализуемой в программах для ЭВМ. Его использование позволяет записать последовательность действий один раз, а выполнять их многократно, после каждого выполнения возвращаясь к началу этой последовательности (цикла).

Упражнение 2. Составить программу на естественном языке для возведения числа х в степень k (k — натуральное число), используя операцию умножения. Результат обозначить через z.

Выполнить программу для х=4, k=3, фиксируя изменение переменных с использованием: а) ячеек памяти; б) трассировочной таблицы.

Решение. Необходимо составить программу для вычисления

Положим вначале z = 1, а далее выполним операциюz = z * x

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

Программа на естественном языке будет иметь вид

1 задать конкретные значения x, k

2 z = 1

3 i = 1

4 z = z * x

5 i = i +1

6 если i k идти к 4

7 закончить вычисления

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

Последнее значение z = 64 и является результатом выполнения программы.

8.2. Понятие алгоритма

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

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

Четко сформулированная последовательность правил, описывающих этот процесс, и является алгоритмом.

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

Например, вам предложено выполнить следующую последовательность действий при заданных значениях а = 1, b = 3, c = 2:

1. Вычислить D = b2 – 4ac

2. Сравнить D с нулем. Если D < 0, перейти к 3. Впротивном случае вычислить

3. Прекратить вычисления.

Оказывается, выполнив приведенную последовательность для указанных значений а, b и c, вы решили квадратное уравнение х2 + 3х + 2 = 0.

Свойства алгоритма

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

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

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

3. Результативность (или конечность). Это свойство состоит в том, что алгоритм должен приводить к решению задачи за конечное число шагов.

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

Например, приведенный выше алгоритм решения квадратичного уравнения применим для различных наборов коэффициентов а, b, c (а ¹ 0).

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

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

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

Разработанный алгоритм можно зафиксировать несколькими способами, например:

  • на естественном языке, как это было сделано в предыдущем примере;
  • в виде схемы;
  • на специальном языке для записи алгоритмов (алгоритмическом языке).

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

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

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

1. Этап обработки (вычисления)

v - выражение

(v — переменная, выражение задает правило вычисления значения, которое далее будет присвоено переменной v. Это может быть, например, знакомое нам алгебраическое (арифметическое) выражение).

2. Проверка условия

если условие идти к N.

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

3. Конец вычислений;

закончить вычисления.

4. Переход к этапу с номером N

идти к N

Изображение алгоритма в виде схемы

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

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

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

Этап обработки (вычисления) изображается прямоугольником (рис. 8.1а). Внутри прямоугольника записывается содержание этого этапа.

Проверка условия изображается ромбом. Условие записывается внутри ромба. В результате проверки условия осуществляется выбор одного из двух возможных путей вычислительного процесса (рис. 8.1б).

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

Рис. 8.1. Блоки, используемые в схемах алгоритма

Рис. 8.1. Блоки, используемые в схемах алгоритма

Начало и конец вычислительного процесса изображаются фигурой, показанной на рис. 8.1в. Внутри нее записывается слово начало или конец.

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

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

Комментарий используется в тех случаях, когда пояснение не помещается внутри блока (рис. 8.1з).

В качестве примера изобразим в виде схемы алгоритм вычисления произведения двух натуральных чисел n и m с использованием операции сложения, записанный ранее на естественном языке, добавив этапы ввода/вывода (рис. 8.2). Схема позволяет наглядно представить структуру алгоритма. В частности, на схеме хорошо видны циклы: это последовательности блоков, после последнего из которых осуществляется возврат к началу последовательности (на схеме это — замкнутые участки). Схемы обычно используются для изображения промежуточных вариантов алгоритма. Окончательный вариант, предназначенный для исполнителя–ЭВМ (программа), должен быть записан на алгоритмическом языке.

Рис. 8.2.

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

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

Понятие об алгоритмических языках

Алгоритмические языки близки к естественному языку. Именно такая цель ставилась при их разработке. Однако правила построения конструкций в алгоритмической языке более "жесткие". Это означает, что алгоритмически языки допускают меньшее разнообразие для описаний действий алгоритма, чем естественный язык и привычная математическая символика, и машина однозначно понимает любую конструкцию языка. Например, для умножение двух переменных a и b общепринятая математическая символикадопускает несколько возможных форм записи: 1) ab 2) а x b 3) а ×b и т. п. А на алгоритмическом языке во например на языке Basic, эту операцию можно записать только единственным образом как a*b. Небольшие, ошибки или описки, допускаемые в предложениях естественного языка и не искажающие, на наш взгляд, смысла, совершенно недопустимы в алгоритмическим языке, где каждый символ и его место в конструкции имеют строго фиксированное значение.

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

Программа, составленная на алгоритмическом языке, не может быть непосредственно выполнена ЭВМ, так как ЭВМ умеет выполнять только последовательность элементарных операций, а в программе на алгоритмическом языке в одном выражении может, например, содержаться несколько операций, и форма записи такой программы понятна человеку, но недоступна ЭВМ. Поэтому необходимо какое-то промежуточное звено, которое выполняло бы работу по расчленению отдельных действий программы и записи их на машинном языке. Работа эта несложная, но требует скрупулезного внимания и педантичности. К такой работе больше всего и приспособлена ЭВМ. Перевод программы с алгоритмического языка на машинный осуществляется ЭВМ с помощью специальной программы, которая носит название транслятор. В программе-трансляторе "заложены" все правила алгоритмического языка и способы преобразования различных его конструкций на машинный язык. Именно поэтому при составлении программы на алгоритмическом языке нужно скрупулезно придерживаться правил этого языка, иначе ЭВМ вас не поймет или поймет неправильно. Наиболее распространенными алгоритмическими языками в настоящее время являются Basic, Pascal, C.

8.3. Основные структуры алгоритмов

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

К основным структурам относятся:

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

2. Цикл До (рис. 8.3). Применяется при необходимости выполнить какие-либо вычисления несколько раз до выполнения некоторого условия. Особенность этого цикла в том, что он всегда выполняется хотя бы один раз, так как первая проверка условия выхода из цикла происходит после того, как тело цикла выполнено. Тело цикла — а последовательность действий, которая выполняется многократно (в цикле). Начальные присвоения — задание начальных значений тем переменным, которые используются в теле цикла.

Рис. 8.3

Рис. 8.4

На естественном языке циклу До соответствует последовательность операторов:

1 Операторы начальных присвоений

2 Операторы тела цикла

3 Если условие идти к 2

Цикл, использованный в приведенном выше примере, это цикл До.

3. Цикл Пока (рис. 8.4). Цикл Пока отличается от цикла До тем, что проверка условия проводится до выполнения тела цикла, и если при первой проверке условие выхода из цикла выполняется, то тело цикла не выполняется ни разу.

На естественном языке циклу Пока соответствует последовательность операторов:

1 Операторы начальных присвоений

2 Если условие идти к 5

3 Операторы тела цикла

4 Идти к 2

5 ...

4. Разветвление (рис. 8.5). Применяется, когда в зависимости от условия нужно выполнить либо одно, либо другое действие. Действие 1 или действие 2 может в свою очередь содержать несколько этапов.

Рис. 8.5

Рис. 8.6

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

1 Если условие идти к 4

2 Операторы действия 2

3 Идти к 5

4 Операторы действия 1

5 ...

5. Обход (рис. 8.6). Частный случай разветвления, когда одна ветвь не содержит никаких действий.

6. Множественный выбор (рис.8.7). Является обобщением разветвления, когда в зависимости от значения переменной (I) выполняется одно из нескольких действий. При I=1 выполняется действие S1, при I=2— действие S2 и т. д.

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

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

Рис. 8.7

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

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

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

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

Упражнение 1. Разделить натуральное число n на натуральное число m, получить в качестве результата частное от деления k и остаток l, т. е. представить число n в виде

n = k m + l ,

где l < m, k – целое. Операцию деления не использовать.

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

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

Рис. 8.8

Программа “Деление двух натуральных чисел”. Исходные данные: n, m - натуральные числа. Результат: k, l.
1 задать значения n, m
2 l = n
3 k = 0
4 если l < m идти к 8
5 l = l m
6 k = k +1
7 идти к 4
8 закончить вычисления

Обратите внимание на то, что проверка условия выхода из цикла проводится до входа в цикл (цикл Пока) и при n < m остается k = 0.

Выполнить программу при: 1) n = 15, m = 5; 2) n = 14, m = 5; 3) n = 3, m = 5;

Упражнение 2. Задано число х. Вычислить функцию знака числа

S=

 

-1, если x < 0;
0, если x = 0;
1, если x > 0.

Решение. Схема алгоритма приводится на рис. 1.9. Алгоритм представляет собой разветвление, содержащее в одной из ветвей еще одно разветвление.

Рис. 8.9

Программа “Вычисление знака числа”. Исходные данные: х — любое число. Результат: S.

  1. задать значение х
  2. если х < 0 идти к 8
  3. если х = 0 идти к 6
  4. S = 1
  5. идти к 9
  6. S = 0
  7. идти к 9
  8. S = -1
  9. закончить вычисления

Обратите внимание на использование оператора “идти к N” (операторы 5, 7) в этой программе. Он позволяет обойти одну из ветвей разветвления, если выполнена другая.

Выполнить программу при: 1) х = -6; 2) х = 0; 3) х = 12.

Упражнение 3. Выбрать максимальное из двух чисел х, у и присвоить его значение переменной u.

Решение. Для решения этой простой задачи будем просматривать числа по очереди. Пока мы “видим” только первое число х, будем считать его максимальными присвоим u значение х (u = х). Затем и сравним со вторым числом у, и если окажется, что значение u меньше у, то u присвоим новое значение, иначе u оставим без изменения. Схема алгоритма приведена на рис. 1.10.

Рис. 8.10

Программа “Нахождение максимального из двух чисел”. Исходные данные: х, у — любые числа.Результат: u - максимальное из х, у.

  1. задать значения х, у
  2. u = х
  3. если uу идти к 5
  4. u = у
  5. закончить вычисления

Следует обратить внимание на характерный прием, используемый в приведенной программе. Значение переменной u в результате выполнения программы будет равно либо х, либо у. Одно из этих значений и присваивается переменной u в начале программы (u = х). Далее, переменная u изменяет свое значение, только если х < у. Если же ху, то значение u сохраняется без изменений.

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

Программа “Нахождение максимального из трех чисел”. Исходные данные: х, у, z - любые числа. Результат: u —максимальное из х, у, z.

  1. задать значения х, у, z
  2. u = х
  3. если u у идти к 5
  4. u = y
  5. если u z идти к 7
  6. u = z
  7. закончить вычисления

Выполнить программу при: 1) х = 8, y = 12, z = 6; 2) х = 5, y = 3, z = 4; 3) х = 6, y=2, z = 13.

Упражнение 4. В переменную х по очереди помещаются (вводятся) 10 чисел. В переменной Р получить максимальное из этих чисел.

Решение. Если до входа в цикл переменной Р присвоить значение первого введенного числа х, то в цикле для очередного значения х нужно проверять условие P x, и если оно не выполняется, то заменить старое значение Р на новое, равное текущему значению х. После чего в х вводится следующее значение. Алгоритм представляет собой цикл До с обходом внутри цикла. Схема алгоритма представлена на рис. 8.11 в двух вариантах.

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

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

Программа “Нахождение максимального из десяти положительных чисел”.

  1. Р = -1
  2. i = 1
  3. задать очередное значение х
  4. если P x идти к 6
  5. Р = x
  6. i = i +1
  7. если i 10 идти к 3
  8. закончить вычисления

Выполнить программу для следующего набора чисел: 3, 18, 24, 8, 11, 6, 12, 19, 44, 23.

Упражнение 5. Задано n троек чисел a, b, c. Вводя их по очереди и интерпретируя как длины сторон треугольника, определить, сколько троек может быть использовано для построения треугольника (числа a, b, c при вводе расположены в порядке возрастания a b c). Результат получить в переменной k.
Указание. По трем сторонам с длинами a, b, c (a bc ) можно построить треугольник, если с<а+b.

Рис. 8.11а

Рис. 8.11б

Алгоритм решения задачи представлен на рис. 8.12.

Для каждой тройки чисел проверяется условие с³ a+b , и если оно не выполняется (треугольник может быть построен), то значение k, увеличивается на 1. До входа в цикл, пока ни одна тройка чисел не введена и не проверена на возможность построения треугольника, k полагается равным 0.

Программа “Определение числа треугольников”.

  1. задать значение n
  2. k = 0
  3. i = 1
  4. задать очередной набор a, b, c
  5. если сa+b идти к 7
  6. k = k + 1
  7. i = i + 1
  8. если i n идти к 4
  9. закончить вычисления

Выполнить программу для пяти (n = 5) троек чисел:

  1. 6, 12, 3; 2) 5, 2, 2; 3)11, 6, 2; 4) 1, 6, 3; 5) 4, 6, 2.

Рис. 8.12

Информатика и вычислительная техника


*****
© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.