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

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

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

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

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

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

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

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

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

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

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

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

12 Блок схема алгоритма 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

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