Алгоритм как модель деятельности 18 декабря 2013 г.

Алгоритм – это: понятное и точное предписание конкретному исполнителю совершить конкретную последовательность действий, приводящую к поставленной цели;понятное и точное предписание конкретному исполнителю совершить конкретную последовательность действий, приводящую к поставленной цели; план работы исполнителя или информационная модель.план работы исполнителя или информационная модель.

Исполнитель алгоритма Исполнитель алгоритма – это человек, животное или устройство способные выполнять определенный набор команд.Исполнитель алгоритма – это человек, животное или устройство способные выполнять определенный набор команд. Набор команд – СКИ (Система Команд Исполнителя).Набор команд – СКИ (Система Команд Исполнителя). Алгоритм составляют с ориентацией на определенного исполнителя:Алгоритм составляют с ориентацией на определенного исполнителя: …формального или неформального?

Задача 1 Выполните предложенные действия. 1.Задумайте целое число от 1 до Прибавьте к нему 2. 3.Результат умножьте на 2. 4.К полученному произведению прибавьте 3. 5.От суммы отнимите задуманное число. 6.К разности прибавьте 5. 7.От суммы отнимите задуманное число. 8.Сообщите ответ. Ответ: 12; мы выступали в роли формального исполнителя

Задача 2 Какому исполнителю под силу решить такую задачу: «Отгадай пословицу, обойдя поле ходом шахматного коня»? НА ЕШ ИЛ ГЬ ЁИ Т РК АУ Ответ: Не игла шьёт, а руки а руки A B C D E F G H Неформальный исполнитель

Задача 3 Угадай задуманное число. Игра «Угадайка»

Задача 4 Поиск НОД двух чисел.

Первый алгоритм Как-то раз древнегреческого математика Евклида спросили: - Что бы ты предпочел - два целых яблока или четыре половинки? - Конечно, четыре половинки. - А почему? Это ведь одно и то же. - Отнюдь. Выбирая два целых яблока, как я узнаю, червивые они или нет? Алгоритм Евклида – это алгоритм нахождения НОД двух целых положительных чисел

Методы решения: 1. Разложение на простые сомножители; 2. Алгоритм Евклида; Существуют различные методы нахождения НОД двух натуральных чисел:

Разложение на простые множители Порядок действий: 1. Разложить число m на простые множители. 2. Разложить число n на простые множители. 3. Выбрать все одинаковые множители чисел m и n. 4. Перемножить выбранные множители – полученное значение и будет НОД (m;n). НОД (5390; 2310) = = 2*5*7*11=770;

Рекурсивный метод – алгоритм Евклида В соответствии с этим методом НОД(m,n) вычисляется по следующему правилу: НОД(m,n) = НОД(m-n,n), если m>n, НОД(m,n-m), если n>m, m, если m=n. т.е. если d является НОД(m,n), то это же число d будет являться НОД меньшего числа из этой пары и их разности.

Блок схема алгоритма 1.Ввести натуральные M и N. 2.Если MN, то перейти к шагу 3, иначе перейти к шагу 8. 3.Если M>N, то перейти к шагу 4, иначе перейти к шагу Вычислить M=M-N. 5.Перейти к шагу 2. 6.Вычислить N=N-M. 7.Перейти к шагу 2. 8.Сообщить M. Применим алгоритм для нахождения НОД(238,544) =НОД(238, 306) = =НОД(238,68) =НОД(170,68)=НОД(102,68)=НОД(34,68)=НОД(34,34) = 34 M=238N=544

Самостоятельная работа Определите значение переменных X и Y после выполнения фрагмента алгоритма.