Рассмотрим несколько задач, решение которых на компьютере получается с помощью ветвящихся алгоритмов.
Первая задача: даны два числа; выбрать большее из них.
Пусть исходными данными являются переменные А и В. Их значения будут задаваться вводом. Значение большего из них должно быть присвоено переменной С и выведено на экран компьютера. Например, если А = 5, В = 8, то должно получиться: С = 8.
Блок-схема алгоритма решения этой задачи изображена на рис. 3.6.
| Рис. 3.6. Алгоритм выбора большего из двух чисел (с полным ветвлением) |
Нетрудно понять смысл этого алгоритма. Если значение переменной А больше, чем В, то переменной С присвоится значение А. В противном случае, когда А В. Изучая базы данных и электронные таблицы, вы узнали, что такое отношение является логическим выражением. Если оно справедливо, то результатом будет логическая величина «истина» и выполнение алгоритма продолжится по ветви «да»; в противном случае логическое выражение примет значение «ложь» и выполнение алгоритма пойдет по ветви «нет».
Пишем программу: нахождения НОД и НОК двух чисел | Алгоритм Евклида
До выполнения на компьютере правильность алгоритма можно проверить путем заполнения трассировочной таблицы. Вот как будет выглядеть трассировка нашего алгоритма для исходных значений А = 5, В = 8.
| Шаг | Операция | А | В | С | Проверка условия |
| 1 | ввод А, В | 5 | 8 | ||
| 2 | А>В | 5 | 8 | 5 > 8, нет (ложь) | |
| 3 | С:=В | 5 | 8 | 8 | |
| 4 | вывод С | 5 | 8 | 8 |
Ветвление является структурной командой. Его исполнение происходит в несколько шагов: проверка условия (выполнение логического выражения) и выполнение команд на одной из ветвей «да» или «нет». Поэтому в трассировочной таблице записываются не команды алгоритма, а отдельные операции, выполняемые компьютером на каждом шаге.
В алгоритме на рис. 3.6 используется полное ветвление. Эту же самую задачу можно решить, применяя структурную команду неполного ветвления. Блок-схема такого алгоритма изображена на рис. 3.7.
| Рис. 3.7. Алгоритм выбора большего из двух значений (с неполным ветвлением) |
Выполните самостоятельно трассировку этого алгоритма для вариантов 1) А = 0,2, В = 0,3; 2) А = 7, В = 4; 3) А = 5, В = 5. Если вы все проделаете правильно, то убедитесь, что алгоритм верный.
А теперь запишем рассмотренные алгоритмы на Алгоритмическом языке (АЯ). Во-первых, нужно решить вопрос о том, как описать переменные в этом алгоритме. Вспомним, что для всех переменных в алгоритме на Алгоритмическом языке необходимо указать их тип.
Блок-схемы для начинающих (Блок схемы алгоритмов)
Переменные А, В, С — числовые величины. В этой задаче они могут принимать любые значения. В программировании числовые величины, которые могут иметь любые значения — целые, дробные, — называются вещественными. Им ставится в соответствие вещественный тип. На Алгоритмическом языке этот тип указывается служебным словом вещ.
Как выглядит команда ветвления, вы уже знаете. Вот два алгоритма на АЯ, соответствующие блок-схемам на рис. 3.6 и 3.7:
| алг БИД1 вещ А, В, С нач ввод А, В если А>В то С:=А иначе С:=В кв вывод С кон |
алг БИД2 вещ А, В, С нач ввод А, В С:=А если В>А то С:=В кв вывод С кон |
Под сокращенным названием алгоритмов ВИД подразумевается «Большее из двух».
Для программирования характерно то, что одна и та же задача может быть решена с помощью разных алгоритмов. И чем сложнее задача, тем больше можно придумать различных алгоритмов ее решения. Для больших задач (производственных, научных) практически невозможно точное совпадение алгоритмов, составленных разными программистами.
Следующая задача: упорядочить значения двух переменных X и Y по возрастанию. Смысл этой задачи следующий: если для исходных значений переменных справедливо отношение X Y (например, X = 2, Y = 1), то выполнить обмен значениями.
Алгоритм обмена значениями двух переменных был рассмотрен в предыдущем параграфе. Вспомним, что для обмена нужна третья вспомогательная переменная.
В алгоритме решения данной задачи используется неполное ветвление. Приведем блок-схему (рис. 3.8) и алгоритм на АЯ.
Здесь роль вспомогательной переменной для обмена выполняет С.
Сложные ветвящиеся алгоритмы
Получим алгоритм решения еще одной задачи: найти наибольшее значение среди трех величин: А, В, С.
Естественно, возникает следующая идея этого алгоритма: сначала нужно найти большее из значений АИВИ присвоить его какой-то дополнительной переменной, например D; затем найти большее среди D и С. Это значение можно присвоить той же переменной D.
Решение задачи сводится к двукратному применению уже знакомого алгоритма нахождения большего из двух значений. Блок-схема алгоритма — на рис. 3.9
Нетрудно догадаться, что «БИТ» обозначает «Большее из трех». В структуре этого алгоритма содержатся два последовательных ветвления: первое — полное, второе — неполное.
Эту же задачу можно решить с помощью алгоритма, имеющего структуру вложенных ветвлений. Его блок-схема приведенная на рис. 3.10.
А вот как выглядят описание этого алгоритма на АЯ и трассировочная таблица при А = 5,В = 7,С = 2.
| Шаг | Операция | А | В | С | D | Проверка условия |
| 1 | ввод А, В, С | 5 | 7 | 2 | — | |
| 2 | А>В | 5 | 7 | 2 | — | 5 > 7, нет |
| 3 | В>С | 5 | 7 | 2 | — | 7 > 2, да |
| 4 | D:=B | 5 | 7 | 2 | 7 | |
| 5 | вывод D | 5 | 7 | 2 | 7 |
1. Какую структуру имеет алгоритм нахождения большего из двух значений?
2. Почему отношение неравенства можно назвать логическим выражением?
3. В каком случае для числовой переменной следует указывать цб лый тип, в каком — вещественный?
4. Составьте алгоритм (в виде блок-схемы и на АЯ) нахождения меньшего из двух значений.
5. Составьте алгоритм нахождения наименьшего из трех значений.
6. Для вывода на экран произвольной символьной строки нужно в команде вывода записать эту строку в апострофах. Например, по команде
Определите, какая задача решается по следующему алгоритму:
Нахождение наибольшего числа из двух
Найти наибольшее число из двух. Если числа равны, то вывести любое из них.
Входные данные
В единственной строке входного файла INPUT.TXT записано 2 числа через пробел. Оба числа целые, не меньше -10000 и не больше 10000.
Выходные данные
В файл OUTPUT.TXT выведите единственное число.
| INPUT.TXT | OUTPUT.TXT |
| 4 7 -10 -1000 8 8 |
7 -10 8 |
Задача максимально упрощена за счет того, что при равенстве чисел можно вывести любое из них. Надо заметить, что даже в самой простой задаче, подобной этой, можно получить правильный результат несколькими способами. Сейчас мы рассмотри два варианта решения.
Как видно из приведенной блок-схемы (см. рис), можно обойтись неполным ветвлением. Наибольшее значение можно получить в переменной «х», и затем вывести ее на экран или в файл.
Текст программы на Паскале.
Работоспособен и алгоритм, блок-схему которого вы видите ниже.
Обратите внимание, что согласно блок схемы, мы вроде никак явно не учитываем вариант равности чисел и просто выводим наибольшее из них. Тем не менее, алгоритм вполне рабочий, т.к. в том случае, когда условие x > y является ложным, истинным является либо то, что y > x или, что y = x , т.е. в любом случае, верный результат окажется в переменной y .
Текст программы на Паскале.
При копировании материалов обратная ссылка обязательна
Вывести на экран наибольшее из двух чисел
Задача № 1. Вывести на экран наибольшее из двух чисел
Формулировка. Даны два числа. Вывести на экран то из них, которое больше.
Решение. Собственно, это самая простая задача, с помощью которой можно продемонстрировать использование условного оператора if. Мы вводим с клавиатуры числа в переменные a и b типа integer, затем в операторе if проверяем булевское выражение «a > b»: если оно истинно, то выполняется then-блок оператора, если ложно – else-блок. Соответственно, если a больше b (условие в заголовке истинно), то в then-блоке мы выводим a, а если a не больше b (условие в заголовке ложно), то выводим b (хотя сюда попадает и случай, когда a = b, что, впрочем, не нарушает решения).
На языке Pascal мы можем записать весь оператор с if — и then-блоками в одну строчку следующим образом:
if a > b then writeln(a) else writeln(b);
При решении некоторых задач иногда не требуется проверки условия, а надо перейти на какую-либо строку. Тогда около строки устанавливается числовая метка N. И по оператору GOTO N программа переходит к этой строке и продолжает работать с этого места. Такие операторы часто применяются при многоразовом возвращении к началу программы после выполнения ряда команд, для ожидания нового задания. Работа безусловного перехода заключается в том, что переход на указанную строку не зависит от условий и выполняется всегда, как только будет встречаться данный оператор.
На следующем примере можно показать работу условного и безусловного перехода:
5 INPUT А, В
А> В THEN PRINT A ELSE PRINT В
Задачу №2 из предыдущих примеров можно переделать с использованием оператора безусловного перехода:
Input «введите значение переменной А «, А
Источник: ozlib.com
1 Программирование на языке Паскаль Ветвления. 2 Разветвляющиеся алгоритмы Задача. Ввести два целых числа и вывести на экран наибольшее из них. Идея решения: — презентация
1 Программирование на языке Паскаль Ветвления. 2 Разветвляющиеся алгоритмы Задача. Ввести два целых числа и вывести на экран наибольшее из них. Идея решения:
Копировать в буфер обмена
Похожие презентации
Показать еще
Презентация на тему: » 1 Программирование на языке Паскаль Ветвления. 2 Разветвляющиеся алгоритмы Задача. Ввести два целых числа и вывести на экран наибольшее из них. Идея решения:» — Транскрипт:
1 1 Программирование на языке Паскаль Ветвления
2 2 Разветвляющиеся алгоритмы Задача. Ввести два целых числа и вывести на экран наибольшее из них. Идея решения: надо вывести на экран первое число, если оно больше второго, или второе, если оно больше первого. Особенность: действия исполнителя зависят от некоторых условий (если … иначе …). Алгоритмы, в которых последовательность шагов зависит от выполнения некоторых условий, называются разветвляющимися.
3 3 Вариант 1. Блок-схема начало max:= a; ввод a,b вывод max a > b? max:= b; конец да нет полная форма ветвления блок «решение» Если a = b? ?
4 4 Вариант 1. Программа max := a ; max := b ; полная форма условного оператора program qq; var a, b, max: integer; begin writeln(‘Введите два целых числа’); read ( a, b ); if a > b then begin end else begin end; writeln (‘Наибольшее число ‘, max); end.
5 5 Условный оператор if then begin end else begin end; if then begin end else begin end; Особенности: перед else НЕ ставится точка с запятой вторая часть ( else …) может отсутствовать (неполная форма) если в блоке один оператор, можно убрать слова begin и end
6 6 Что неправильно? if a > b then begin a := b; end else b := a; end; if a > b then begin a := b; end else b := a; end; if a > b then begin a := b; else begin b := a; end; if a > b then begin a := b; else begin b := a; end; if a > b then begin a := b; end; else begin b := a; end; if a > b then begin a := b; end; else begin b := a; end; if a > b then begin a := b; end else b > a begin b := a; end; if a > b then begin a := b; end else b > a begin b := a; end; begin end begin end
7 7 Вариант 2. Блок-схема неполная форма ветвления начало max:= a; ввод a,b вывод max max:= b; конец да нет b > a?
8 8 Вариант 2. Программа program qq; var a, b, max: integer; begin writeln(‘Введите два целых числа’); read ( a, b ); max := a; if b > a then max := b; writeln (‘Наибольшее число ‘, max); end. неполная форма условного оператора
9 9 Вариант 2Б. Программа program qq; var a, b, max: integer; begin writeln(‘Введите два целых числа’); read ( a, b ); max := b; if . then . writeln (‘Наибольшее число ‘, max); end. max := a; a > b
10 10 Что неправильно? if a > b then begin a := b; else b := a; if a > b then begin a := b; else b := a; if a > b then begin a := b; end; else b := a; if a > b then begin a := b; end; else b := a; if a > b then else begin b := a; end; if a > b then else begin b := a; end; if a > b then a := b; else b := a; end; if a > b then a := b; else b := a; end; a := b end a := b if b >= a then b := a; if b >= a then b := a;
11 11 Задания «4»: Ввести три числа и найти наибольшее из них. Пример: Введите три числа: Наибольшее число 15 «5»: Ввести пять чисел и найти наибольшее из них. Пример: Введите пять чисел: Наибольшее число 56
Источник: www.myshared.ru