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

Содержание урока

§ 30. Способы записи алгоритмов

§ 31. Примеры исполнителей

§32. Оптимальные программы

Вопросы и задания

Вопросы и задания

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

2. Как можно доказать, что построенная программа для Удвоителя действительно самая короткая?

3. Какие числа можно (нельзя) получить из натурального числа N с помощью Удвоителя? Из нуля? Из отрицательного числа?

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

5. Исполнитель Калькулятор имеет команды

1. прибавь 1
2. раздели на 2

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

6. Выполните по указанию учителя задания в рабочей тетради.

Следующая страница § 30. Способы записи алгоритмов

Cкачать материалы урока

Источник

Презентация на тему «Исполнители Удвоитель, Раздвоитель, Калькулятор»

Ищем педагогов в команду «Инфоурок»

Описание презентации по отдельным слайдам:

* Исполнители Удвоитель, Раздвоитель, Калькулятор

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

* Удвоитель Исполнитель Удвоитель работает с одним числом и умеет выполнять с ним две операции (команды): 1. прибавь 1 2. умножь на 2 Программа – это последовательность номеров команд, которые нужно выполнить. Программа 12211 2 начальное число 3 6 12 13 14 1 2 2 1 1 результат Исполнитель Калькулятор

* Обратная задача (составление программы) Используя команды: 1. прибавь 1 2. умножь на 2 написать программу, которая из 3 получает 13. Ответ: 221 3 4 13 1 дерево вариантов 6 5 8 7 12 6 10 9 16 8 14 24 2 1 1 1 1 1 2 2 2 2 2 2 2 1 2 1 Исполнитель Калькулятор

* Обратная задача (решение «с конца») 13 нельзя делить на 2! 12 11 6 10 5 3 1 1 1 2 2 2 2 1 Ответ: 221 Исполнитель Калькулятор

* Удвоитель У исполнителя есть команды: 1. прибавь 1 2. умножь на 2 Задания: Какие числа можно получить из 0? Как из числа 5 получить 105? Как построить самую короткую программу для получения заданного числа N из 0? Исполнитель Калькулятор

* Раздвоитель У исполнителя есть команды: 1. вычти 1 2. раздели на 2 Задания: Какие числа можно получить из положительного числа N? Как быстрее всего получить 0 из положительного числа N? Исполнитель Калькулятор

* Исполнитель Калькулятор Исполнитель Калькулятор работает с одним числом и умеет выполнять с ним две операции (команды): 1. прибавь 2 2. умножь на 3 Программа – это последовательность номеров команд, которые нужно выполнить. Программа 12211 2 начальное число 4 12 36 38 40 1 2 2 1 1 результат Исполнитель Калькулятор

* Обратная задача (составление программы) Используя команды: 1. прибавь 2 2. умножь на 3 написать программу, которая из 3 получает 29. Ответ: 221 3 5 29 1 дерево вариантов 9 7 15 11 27 9 21 17 45 13 33 81 2 1 1 1 1 1 2 2 2 2 2 2 2 1 2 1 Исполнитель Калькулятор

* Обратная задача (решение «с конца») 29 нельзя делить на 3! 27 25 9 23 7 3 1 1 1 2 2 2 2 1 Ответ: 221 Исполнитель Калькулятор

* Ещё пример Используя команды: 1. прибавь 2 2. умножь на 3 написать программу, которая из 2 получает 15. Исполнитель Калькулятор

* Удвоитель У исполнителя есть команды: 1. прибавь 1 2. умножь на 2 Дана программа: 2112. Как можно сделать то же самое за 3 шага? Программа 2112 x 2x 2 1 1 2 2x+1 2x+2 4x+4 x+1 1 2 Исполнитель Калькулятор

* Удвоитель У исполнителя есть команды: 1. прибавь 1 2. умножь на 2 Докажите, что: любое число, меньшее 10, можно получить из 0 за 5 шагов любое число, меньшее 100, можно получить из 0 за 12 шагов Исполнитель Калькулятор

Длина оптимальной программы * 0 Минимальное число, для которого оптимальная программа содержит ровно N команд: первая команда – 1 (0 1) программа оканчивается на 1 (прибавь 1) при «обратном ходе» команды 1 и 2 чередуются Исполнитель Калькулятор

Количество программ * У исполнителя есть команды: 1. прибавь 1 2. умножь на 2 Сколько есть разных программ, с помощью которых можно из числа 1 получить число 6? Сколько есть разных программ, с помощью которых можно из числа 4 получить число 12? Сколько есть разных программ, с помощью которых можно из числа 8 получить число 18? Исполнитель Калькулятор

Табличный метод * 1. прибавь 1 2. умножь на 2 N если делится на 2! Количество программ KN: KN = KN-1 если N не делится на 2 KN = KN-1 + KN/2 если N делится на 2 K1+K1 K3+K2 K5+K3 K7+K4 K9+K5 +1 *2 для конечного числа N одна пустая! N 1 2 3 4 5 6 7 8 9 10 KN 1 2 2 4 4 6 6 10 10 14 Исполнитель Калькулятор

Задача * У исполнителя есть команды: 1. прибавь 1 2. умножь на 3 Сколько есть разных программ, с помощью которых можно из числа 4 получить число 20? KN = KN-1 если N не делится на 3 KN = KN-1 + KN/3 если N делится на 3 N 4 … 11 12 … 15 … 18 … 21 KN 1 1 1 2 2 3 3 4 4 5 N 1 2 3 4 5 6 7 8 9 10 11 12 KN 0 0 0 1 1 1 1 1 1 1 1 2 Исполнитель Калькулятор

Задача * У исполнителя есть команды: 1. прибавь 1 2. прибавь 2 2. умножь на 2 Сколько есть разных программ, с помощью которых можно из числа 4 получить число 13? Количество программ: KN = KN-1 + KN-2 если N не делится на 2 KN = KN-1 + KN-2 + KN/2 если N делится на 2 N если N делится на 2! N 4 5 6 7 8 9 10 11 12 13 KN 1 1 2 3 6 9 16 25 43 68 Исполнитель Калькулятор

* Раздвоитель (ветвление) Алгоритм: начало конец раздели на 2 вычти 1 Блок-схема: Что получится для числа: 35 44 77 88 34 22 76 44 да нет если четное то раздели на 2 иначе вычти 1 все Исполнитель Калькулятор

* Раздвоитель (циклы) Алгоритм: Что получится: 10 20 30 50 60 0 1 3 3 6 Цикл – это повторение одинаковых действий. нц 5 раз если четное то раздели на 2 иначе вычти 1 всё кц если четное то раздели на 2 иначе вычти 1 всё конец цикла тело цикла начало цикла Исполнитель Калькулятор

* Раздвоитель (циклы) начало конец раздели на 2 вычти 1 Блок-схема: да нет да нет тело цикла Исполнитель Калькулятор

нц пока положительное если четное то раздели на 2 иначе вычти 1 всё кц * Раздвоитель (циклы) Алгоритм: Задание: нарисуйте блок-схему. Сколько шагов цикла выполнится для числа 15 16 128 7 5 8 Исполнитель Калькулятор

нц пока положительное нц пока четное раздели на 2 кц вычти 1 кц * Раздвоитель (циклы) Алгоритм получения 0 из положительного числа: Задание: нарисуйте блок-схему. Исполнитель Калькулятор

нц пока положительное вычти 1 нц пока четное раздели на 2 кц кц * Раздвоитель (циклы) Алгоритм получения 0 из положительного числа: Задание: нарисуйте блок-схему. 1? 2? 3? 4? Исполнитель Калькулятор

нц пока положительное если нечетное то вычти 1 всё нц пока четное раздели на 2 кц кц * Раздвоитель (циклы) Алгоритм получения 0 из положительного числа: Задание: нарисуйте блок-схему. 1? 2? 3? 4? Исполнитель Калькулятор

Анализ блок-схем * Исполнитель Калькулятор

Анализ блок-схем * x = 13 y = 20 Исполнитель Калькулятор

Анализ блок-схем * k = 7 x1 = 21 x2 = 13 z = 21 Исполнитель Калькулятор

Анализ блок-схем * Напишите программу, в которой a, b и c вводятся с клавиатуры. Заполните таблицу: вывод «a=», a, «b=», b вывод a, b вывод a, » «, b Исходные данные Результат a b c a b 2 3 4 5 12 100 3 25 999 111 222 9999 111 222 111 100 12 5 Исполнитель Калькулятор

Анализ блок-схем * Напишите программу, в которой a и b вводятся с клавиатуры. Что она вычисляет? a:=64168 b:=82678 Исполнитель Калькулятор

Алгоритм Евклида * Евклид (365-300 до. н. э.) НОД(a,b)= НОД(a-b, b) = НОД(a, b-a) Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД. НОД (14, 21) = НОД (14, 21-14) = НОД (14, 7) НОД (1998, 2) = НОД (1996, 2) = … = 2 Пример: много шагов при большой разнице чисел: = НОД (7, 7) = 7 Надо: вычислить наибольший общий делитель (НОД) чисел a и b. Исполнитель Калькулятор

Модифицированный алгоритм Евклида * НОД(a,b)= НОД(mod(a,b), b) = НОД(a, mod(b,a)) Заменяем большее из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю. Тогда большее — это НОД. НОД (14, 21) = НОД (14, 7) = НОД (0, 7) = 7 Пример: Исполнитель Калькулятор

Алгоритм Евклида * Составить программу для вычисления НОД с помощью алгоритма Евклида и заполнить таблицу: «5»: Подсчитать число шагов алгоритма. a 64168 358853 6365133 17905514 549868978 b 82678 691042 11494962 23108855 298294835 НОД(a,b) a 64168 358853 6365133 17905514 549868978 b 82678 691042 11494962 23108855 298294835 НОД(a,b) шагов Исполнитель Калькулятор

* Конец фильма ПОЛЯКОВ Константин Юрьевич д.т.н., учитель информатики высшей категории, ГОУ СОШ № 163, г. Санкт-Петербург kpolyakov@mail.ru Использованы материалы Д. Кириенко, школа № 179, г. Москва Исполнитель Калькулятор

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

Курс повышения квалификации

Современные педтехнологии в деятельности учителя

Курс профессиональной переподготовки

Математика и информатика: теория и методика преподавания в образовательной организации

Номер материала: ДБ-1617235

Международная дистанционная олимпиада Осень 2021

Не нашли то что искали?

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Безлимитный доступ к занятиям с онлайн-репетиторами

Выгоднее, чем оплачивать каждое занятие отдельно

В Минпросвещения предложили организовать телемосты для школьников России и Узбекистана

Время чтения: 1 минута

Минпросвещения будет стремиться к унификации школьных учебников в России

Время чтения: 1 минута

В Северной Осетии организовали бесплатные онлайн-курсы по подготовке к ЕГЭ

Время чтения: 1 минута

В Осетии студенты проведут уроки вместо учителей старше 60 лет

Время чтения: 1 минута

С 2019 года закрыто более 50 детских лагерей

Время чтения: 1 минута

Путин попросил привлекать родителей к капремонту школ на всех этапах

Время чтения: 1 минута

Подарочные сертификаты

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

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

Источник

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

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

Первая из них увеличивает на 1 число на экране, вторая удваивает его.

Программа для Удвоителя — это последовательность команд. Сколько существует программ, которые число 3 преобразуют в число 26?

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n. Обозначим t(n) наибольшее кратное 2, не превосходящее n. Заметим, что мы можем получить только числа, кратные 2.

Верны следующие соотношения:

1. Если n не делится на 2, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) — прибавлением единиц.

2. Пусть n делится на 2. Тогда R(n) = R(n / 2) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 4). При n = 4: R(n) = 1 (один способ: прибавлением единицы), при n = 5: R(n) = 1. Достаточно вычислить значения R(n) для всех чисел, кратных 2 и не превосходящих 26.

R(8) = R(4) + R(6) = 1 + 2 = 3 = R(9),

R(10) = R(5) + R(8) = 1 + 3 = 4 = R(11),

R(12) = R(6) + R(10) = 2 + 4 = 6 = R(13),

R(14) = R(7) + R(12) = 2 + 6 = 8 = R(15),

R(16) = R(8) + R(14) = 3 + 8 = 11 = R(17),

R(18) = R(9) + R(16) = 3 + 11 = 14 = R(19),

R(20) = R(10) + R(18) = 4 + 14 = 18 = R(21),

R(22) = R(11) + R(20) = 4 + 18 = 22 = R(23),

R(24) = R(12) + R(22) = 6 + 22 = 28 = R(23),

R(26) = R(13) + R(24) = 6 + 28 = 34.

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

Первая из них увеличивает на 1 число на экране, вторая умножает это число на 2.

Программа для Удвоителя — это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 22?

Обозначим R(n) — количество программ, которые преобразуют число 2 в число n. Обозначим t(n) наибольшее кратное 2, не превосходящее n. Заметим, что мы можем получить только числа, кратные 2.

Верны следующие соотношения:

1. Если n не делится на 2, то тогда R(n) = R(t(n)), так как существует единственный способ получения n из t(n) — прибавлением единиц.

2. Пусть n делится на 2. Тогда R(n) = R(n / 2) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 2). При n = 4 R(n)) = 2 (два способа: прибавлением единицы и умножением на 2). Достаточно вычислить значения R(n) для всех чисел, кратных 2 и не превосходящих 22.

R(6) = R(3) + R(5) = 1 + 2 = 3 = R(7),

R(8) = R(4) + R(6) = 2 + 3 = 5 = R(9),

R(10) = R(5) + R(8) = 2 + 5 = 7 = R(11),

R(12) = R(6) + R(10) = 3 + 7 = 10 = R(13),

R(14) = R(7) + R(12) = 3 + 10 = 13 = R(15),

R(16) = R(8) + R(14) = 5 + 13 = 18 = R(17),

R(18) = R(9) + R(16) = 5 + 18 = 23 = R(19),

R(20) = R(10) + R(18) = 7 + 23 = 30 = R(21),

R(22) = R(11) + R(20) = 7 + 30 = 37.

Исполнитель Удвоитель преобразует число на экране.

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

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Удвоитель — это последовательность команд.

Сколько существует программ, для которых при исходном числе 3 результатом является число 25 и при этом траектория вычислений содержит число 11 и не содержит числа 20?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 112 при исходном числе 5 траектория будет состоять из чисел 6, 7, 14.

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

Обозначим R(n) — количество программ, которые преобразуют число 3 в число n.

Верны следующие устверждения:

Теперь можно постепенно вычислить все значения:

R(5) = R(4) = R(2) + R(3) = 0 + 1 = 1

R(9) = R(8) = R(4) + R(7) = 1 + 2 = 3

R(11) = R(10) = R(5) + R(9) = 1 + 3 = 4

4 программы для получения из числа 3 число 11, 2 программы для получения из числа 11 число 25, всего программ.

Источник

Урок 61
Алгоритмически неразрешимые задачи
(§35. Алгоритмически неразрешимые задачи)

Содержание урока

Когда задача алгоритмически неразрешима?

Когда задача алгоритмически неразрешима?

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

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

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

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

Алгоритмически неразрешимая задача — это задача, соответствующая невычислимой функции.

1 Сейчас большинство из них решено полностью или частично.

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

В начале XX века была уверенность, что такой алгоритм есть, и поэтому его упорно искали. Однако в 1970 г. советскому математику Ю. В. Матиясевичу удалось доказать, что общего алгоритма решения этой задачи не существует.

Немецкий математик Г. В. Лейбниц в XVII веке безуспешно пытался найти метод проверки правильности любых математических утверждений. Как вы знаете, почти все математические теории основаны на использовании аксиом (положений, принимаемых без доказательства), из которых выводятся все остальные утверждения (теоремы). Задача заключалась в том, чтобы разработать алгоритм, позволяющий установить, можно ли вывести формулу Б из формулы А в рамках заданной системы аксиом («проблема распознавания выводимости»).

2 Тем не менее отдельные классы теорем можно доказывать на компьютере.

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

3 Допустим, что (1) задача А неразрешима и (2) если мы можем построить алгоритм для решения задачи Б, то с его помощью можно построить алгоритм решения задачи А. Тогда задача Б тоже неразрешима.

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

Алгоритмически неразрешимые задачи встречаются не только в математике, но и в информатике, например при разработке программ. Оказывается, невозможно написать программу для машины Тьюринга (алгоритм), которая по тексту любой программы Р и её входным данным X определяет, завершается ли программа Р при входе X за конечное число шагов или зацикливается. Это так называемая проблема останова. Её неразрешимость означает, в частности, что нельзя полностью автоматизировать тестирование любых программ, поручив это компьютеру. Однако для некоторых классов алгоритмов проблему останова решить можно. Например, линейная программа, не содержащая ветвлений и циклов, всегда завершится.

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

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

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

Следующая страница Вопросы и задания

Cкачать материалы урока

Источник

Алгоритмы

Алгоритмы. Разработка алгоритма решения задачи

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

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

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

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

Базовые алгоритмические конструкции

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

Линейные алгоритмы

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

Пример

ЗАДАЧА. Разработать алгоритм вычисления гипотенузы прямоугольного треугольника по известным значениям длин его катетов a и b.

На примере данной задачи рассмотрим все три этапа разработки алгоритма решения задачи:

Этап 1. Математическое описание решения задачи.

Математическим решением задачи является известная формула:

,

где с-длина гипотенузы, a, b – длины катетов.

Этап 2. Определение входных и выходных данных.

Входными данными являются значения катетов a и b. Выходными данными является длина гипотенузы – c.

Этап 3. Разработка алгоритма решения задачи.

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

Разветвляющиеся алгоритмы

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

Пример

ЗАДАЧА. Разработать алгоритм вычисления наибольшего числа из двух чисел x и y.

Этап 1. Математическое описание решения задачи.

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

В рассматриваемом алгоритме (рис.3) имеются три ветви решения задачи:

Выбор ветви определяется значениями x и y в элементах 3 и 5, которые являются условиями, определяющими порядок выполнения элементов алгоритма. Если условие (равенство), записанное внутри символа «решение», выполняется при введенных значениях x и y, то следующими выполняется элементы 4 и 8. Это следует из того, что они соединены линией с надписью «да» и направление (последовательность) вычислений обозначена стрелочкой.

Если условие в элементе 3 не выполняется, то следующим выполняется элемент 5. Он соединен с элементом 3 линией с надписью «нет». Если условие, записанное в элементе 5, выполняется, то выполняется элементы 6 и 8, в противном случае выполняются элементы 7 и 8.

Циклические алгоритмы

Циклический алгоритм – определяет повторение некоторой части действий (операций), пока не будет нарушено условие, выполнение которого проверяется в начале цикла. Совокупность операций, выполняемых многократно, называется телом цикла.

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

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

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

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

В тело цикла входят:

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

Пример

ЗАДАЧА. Разработать алгоритм вычисления суммы натуральных чисел от 1 до 100.

Этап 1. Математическое описание решения задачи.

Обозначим сумму натуральных чисел через S. Тогда формула вычисления суммы натуральных чисел от 1 до 100 может быть записана так:

где Xi – натуральное число X c номером i, который изменяется от 1 до n, n=100 – количество натуральных чисел.

Этап 2. Определение входных и выходных данных.

Входными данными являются натуральные числа: 1, 2, 3, 4, 5, …, 98, 99, 100.

Выходные данные – значение суммы членов последовательности натуральных чисел.

Параметр цикла – величина, определяющая количество повторений цикла. В нашем случае i – номер натурального числа.

Подготовка цикла заключается в задании начального и конечного значений параметра цикла.

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

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

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

Этап 3. Разработка алгоритма решения задачи.

Введем обозначения: S – сумма последовательности, i – значение натурального числа.

Начальное значение цикла i=1, конечное значение цикла i =100, шаг цикла 1.

Источник