Класс. МУПР ОП.08 Теория алгоритмов. Методические указания по проведению практических работ по дисциплине Теория алгоритмов
 Скачать 3.39 Mb.
|
Практическая работа №9. Построение алгоритма с использованием цикла с предусловиемЦель работы: Получение навыков построения алгоритмов с использованием цикла с предусловием. Алгоритмы, которые мы составляли ранее, обладают одним общим свойством: при их выполнении каждое действие совершается один раз или вообще не совершается. Но для многих задач, решаемых на компьютере, характерно многократное выполнение отдельных участков вычислений. Вычислительные процессы, при реализации которых имеет место многократное выполнение одного или нескольких процессов вычислений, принято называть циклическими. Цикл - это алгоритмическая конструкция, в которой в зависимости от условия повторяется определённая последовательность действий. Цикл в алгоритме имеет особое значение, т.к. только его использование позволяет с помощью сравнительно коротких алгоритмов записывать длинные последовательности действий, что позволяет значительно уменьшить скорость выполнения программы. Алгоритм, предусматривающий многократное повторение одного и того же действия над новыми данными, называется циклическим. Для организации циклов можно применять условия, т.к. циклический алгоритм является частным случаем разветвляющегося. Тело цикла - это повторяющаяся последовательность действий (блок инструкций). Цикл, для которого нельзя указать число повторений, и проверка окончания которого происходит по достижению нужного условия, называется итерационным. Проверка выполнения условия может происходить до выполнения тела цикла и после него, а циклические структуры являются циклами с предусловиеми с постусловием. В цикле с предусловием, называемом еще циклом “пока”, сначала проверяется условие, а затем выполняются действия.  Цикл с предусловием может не выполниться ни разу. Решим задачу: Составить алгоритм выполнения домашнего задания по геометрии, если задано решить несколько задач.  Пример Составить алгоритм для определения наибольшего общего кратного двух целых положительных чисел, используя алгоритм Евклида (определение НОД методом вычитания). Согласно алгоритму Евклида для нахождения наибольшего общего кратного двух целых положительных чисел, нужно из большего числа вычитать меньшее до тех пор, пока они не станут равны, это число и есть наибольший общий делитель. Возьмем два числа : 4 и 11.
Таким образом, НОД чисел 4 и 11 равен 1. Блок-схема решения задачи определения НОД методом Евклида:  Задание 1. Составить алгоритм решения задачи определения НОД методом деления. (алгоритм Евклида). Большее из чисел заменяется на остаток от целочисленного деления большего числа на меньшее. Повторяется это действие до тех пор, пока остаток не станет равным нулю, второе число при этом и есть НОД. 2. Начав читать детектив с 30-й страницы, читатель подсчитал сумму номеров прочитанных за день страниц. Она оказалась равна 840. Сколько страниц за день он прочитал? 3. Весной на березе распустилось в первый день А листьев, а в каждый последующий в три раза больше, чем в предыдущий. В какой день распустится на дереве В листьев за один день? Через сколько дней на дереве будет 1000000 листьев? 4. Николай родился А см в длину. За первый год он вырос на В см. В каждый последующий год он подрастал на 17% меньше, чем в предыдущий год. Через сколько лет его рост стал больше, чем 165 см? 5. Стакан кипятка (100 градусов Цельсия) остыл за первую минуту на А градусов, а каждую последующую остывал на 15% меньше, чем в предыдущую. Через сколько минут температура воды станет ниже N градусов Цельсия? 6. Седьмому классу на практике поручено сдуть 1000 одуванчиков. Бригада мальчиков в первый день сдула А одуванчиков, а бригада девочек – в 2 раза меньше. В каждый последующий день производительность мальчиков уменьшалась на 10%, а девочек росла на 15% по сравнению с предыдущим. Через сколько дней класс выполнит норму? Сколько сделает бригада мальчиков и бригада девочек в отдельности? Дополнительные задания 1. Написать алгоритм Евклида, использующий соотношения НОД(a, b)=НОД(a mod b, b) при a >= b НОД (a, b)=НОД (a, b mod a) при b >= a 2. Написать алгоритм Евклида, использующий соотношения НОД (a, b)=НОД (a, b mod a) при b >= a 3. Даны натуральные а и b, не равные 0 одновременно. Найти d = НОД (a,b) и такие целые x и y, что d = a*x + b*y. 4. Даны натуральные а и b, не равные 0 одновременно. Найти d = НОД (a,b) и такие целые x и y, что d = a*x + b*y. 5. Даны натуральные а и b, не равные 0 одновременно. Найти d = НОД (a,b) и такие целые x и y, что d = a/x + b*y. 6. Даны натуральные а и b, не равные 0 одновременно. Найти d = НОД (a,b) и такие целые x и y, что d = a*x + b/y. 7. Написать вариант алгоритма Евклида, использующий соотношения НОД(2*a, 2*b) = 2*НОД(a,b) 8. Написать вариант алгоритма Евклида, использующий соотношения НОД(2*a, b) = НОД(a,b) при нечетном b 9. Написать бинарный алгоритм, использующий соотношения НОД(a, b)=НОД(a mod b, b) при a >= b НОД (a, b)=НОД (a, b mod a) при b >= a 10. Даны натуральные а и b, не равные 0 одновременно. Найти d = НОД (a,b) и такие целые x и y, что d = a*x + b*y, используя бинарный алгоритм. |