Презентация по информатика на тему Алгоритмика (8 класс)

Алгоритмика

Домашнее задание Сделать ДЗ Алгоритм Исполнитель Кузнечик и прислать на почту учителю

Благодаря этой рекламе сайт может продолжать свое существование, спасибо за просмотр.

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

Алгоритмика Искусство размышлять, умение планировать свои действия, способность предусматривать различные обстоятельства и поступать соответственно с ними понадобились людям задолго до того как был изготовлен первый компьютер. Слово «алгоритм» происходит от имени средневекового ученного Махаммеда ибн Мусы аль-Хорезми (787-850), жившего в Средней Азии.

Алгоритмика В XIII веке, когда труды аль-Хорезми были переведены с арабского языка на латынь, его имя записали так: Algorithmus. А изобретали люди алгоритмы до Мухаммеда ибн Мусы? Да, например, все математики знают так называемый алгоритм Евклида (жил больше двух тысяч лет назад).

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

Старинная русская задача Волк, коза и капуста.

Старинная русская задача ЗАДАЧА: Крестьянин стоит на левом берегу с волком, козой и капустой. Ему нужно все это перевести на правый берег. Но его лодка слишком мала: он может взять только одного пассажира – либо волка, либо козу, либо капусту. И еще – если на одном берегу оставить волка и козу, то волк съесть козу, если на одном берегу оставить козу и капусту, то коза съест капусту. Только в присутствии крестьянина они не безобразничают. Как тут поступить?

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

Старинная русская задача После этого у крестьянина есть две возможности: перевезти волка, перевезти капусту. Давайте подумаем над данными вариантами…

Старинная русская задача Решение задачи в виде программы: перевези козу переправься перевези волка перевези козу перевези капусту переправься перевези козу

Старинная русская задача УПРАЖНЕНИЕ: Допустим, что крестьянин, перевезя на правый берег козу, взял не волка, а капусту. Напишите его последовательность его действий в этом случае.

Старинная русская задача Таким образом, все возможные действия крестьянина: перевези козу, переправься, перевези волка, перевези капусту. Допустимы только такие действия, перечисленные в списке, все прочие строго запрещены.

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

Исполнитель и команды Любая задача напоминает игру. Например, шахматные правила четко говорят, что позволено делать Шахматисту. Все его другие привычки (например, любит ли он капусту) никак не связаны с игрой. При этом есть одно существенное различие. Шахматисту во время игры приходится принимать собственные решения. А исполнитель не принимает никаких решений самостоятельно, он только выполняет команды, которые мы вставляем в программу.

Исполнитель ВОДОЛЕЙ Исполнителей Водолей – он занимается переливанием воды.

Исполнитель ВОДОЛЕЙ Трудно ли отмерить литр воды? Если есть литровая банка А, то команда будет состоять из одного шага: наполни А Если есть две емкости: двухлитровая банка А и трехлитровая банка В. Тогда решение задачи состоит из двух шагов: наполни В перелей из В в А

Исполнитель ВОДОЛЕЙ Команды Водолея бываю трех видов: Первый вид: наполни А (или В, С, …). Второй вид: вылей из А (или В, С). Третий вид: перелей из А в В (или из А в С и т.д.). Выпишем все команды Водолея с двумя емкостями, например с ведрами: наполни А, наполни В, вылей из А, вылей из В, перелей из А в В, перелей из В в А.

Исполнитель ВОДОЛЕЙ УПРАЖНЕНИЕ: напишите список команд для Водолея с тремя ведрами А,В,С. Сколько всего команд у вас получилось? ЗАДАЧА 1: Отмерьте 1 литр воды с помощью одной трех литровой и одной пятилитровой банки. ЗАДАЧА 1.2. Имеются 5-литровая емкость А и 8-литровая емкость В. отмерьте 1 литр воды. отмерьте 4 литра воды.

Исполнитель ВОДОЛЕЙ Домашнее задание: УПРАЖНЕНИЕ: Придумайте свой собственный вариант Водолея. Придумайте задачу для него. Опишите решение придуманной задачи.

Исполнитель ВОДОЛЕЙ

Исполнитель УДВОИТЕЛЬ Удвоитель – воображаемое устройство с экраном и двумя кнопками. На экране отображается число. В момент включения Удвоителя оно равно 0. На клавишах удвоителя написано прибавь 1 и умножь на 2. При нажатии на первую клавишу число, изображенное на экране, увеличивается на 1, а при нажатии на вторую удваивается. Удвоитель – это исполнитель с двумя с командами: прибавь 1 и умножь на 2.

Исполнитель УДВОИТЕЛЬ Попробуйте получить число 17, начинайте с 0.

Исполнитель УДВОИТЕЛЬ РЕШЕНИЕ 1: прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1 прибавь 1

Исполнитель УДВОИТЕЛЬ Решение 2: прибавь 1 умножь на 2 умножь на 2 умножь на 2 умножь на 2 прибавь 1 Какая из этих двух программ вам больше нравиться и почему?

Исполнитель УДВОИТЕЛЬ УПРАЖНЕНИЕ: Придумайте еще какую-нибудь программу для получения числа 17. ЗАДАЧА: Можно ли получить на экране любое положительное число? Поясните свой ответ. СОРЕВНОВАНИЕ: 1 называет число, все пишут программу, побеждает тот у кого минимум операций.

Исполнитель УДВОИТЕЛЬ ЗАДАЧА: Получите число 15 менее, чем за 8 шагов. Получите число 1024. На экране записано число 4, получите из него число 15, менее чем за 6 шагов.

За­да­ние 1. У ис­пол­ни­те­ля Квад­ра­тор две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:  1. вычти 3 2. воз­ве­ди в квад­рат Пер­вая из них умень­ша­ет число на экра­не на 3, вто­рая воз­во­дит его во вто­рую сте­пень. Ис­пол­ни­тель ра­бо­та­ет толь­ко с на­ту­раль­ны­ми чис­ла­ми. Со­ставь­те ал­го­ритм по­лу­че­ния из числа 4 числа 49, со­дер­жа­щий не более 5 ко­манд. В от­ве­те за­пи­ши­те толь­ко но­ме­ра ко­манд. (На­при­мер, 21211 — это ал­го­ритм: воз­ве­ди в квад­рат, вычти 3, воз­ве­ди в квад­рат, вычти 3, вычти 3, ко­то­рый пре­об­ра­зу­ет число 3 в 30.) Если таких ал­го­рит­мов более од­но­го, то за­пи­ши­те любой из них.

За­да­ние 2. У ис­пол­ни­те­ля Квад­ра­тор две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра: 1. вычти 1 2. воз­ве­ди в квад­рат Пер­вая из них умень­ша­ет число на экра­не на 1, вто­рая воз­во­дит его во вто­рую сте­пень. Ис­пол­ни­тель ра­бо­та­ет толь­ко с на­ту­раль­ны­ми чис­ла­ми. Со­ставь­те ал­го­ритм по­лу­че­ния из числа 5 числа 80, со­дер­жа­щий не более 5 ко­манд. В от­ве­те за­пи­ши­те толь­ко но­ме­ра ко­манд. (На­при­мер, 21121 — это ал­го­ритм: воз­ве­ди в квад­рат, вычти 1, вычти 1, воз­ве­ди в квад­рат, вычти 1, ко­то­рый пре­об­ра­зу­ет число 3 в 48.) Если таких ал­го­рит­мов более од­но­го, то за­пи­ши­те любой из них.

За­да­ние 3. У ис­пол­ни­те­ля Квад­ра­тор две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:  1. при­бавь 1 2. воз­ве­ди в квад­рат  Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 1, вто­рая воз­во­дит его во вто­рую сте­пень. Ис­пол­ни­тель ра­бо­та­ет толь­ко с на­ту­раль­ны­ми чис­ла­ми. Со­ставь­те ал­го­ритм по­лу­че­ния из числа 3 числа 84, со­дер­жа­щий не более 5 ко­манд. В от­ве­те за­пи­ши­те толь­ко но­ме­ра ко­манд. (На­при­мер, 11221 — это ал­го­ритм: при­бавь 1, при­бавь 1, воз­ве­ди в квад­рат, воз­ве­ди в квад­рат, при­бавь 1, ко­то­рый пре­об­ра­зу­ет число 1 в 82.) Если таких ал­го­рит­мов более од­но­го, то за­пи­ши­те любой из них.

За­да­ние 4. У ис­пол­ни­те­ля Квад­ра­тор две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра: 1. при­бавь 3 2. воз­ве­ди в квад­рат Пер­вая из них уве­ли­чи­ва­ет число на экра­не на 3, вто­рая воз­во­дит его во вто­рую сте­пень. Ис­пол­ни­тель ра­бо­та­ет толь­ко с на­ту­раль­ны­ми чис­ла­ми. Со­ставь­те ал­го­ритм по­лу­че­ния из числа 4 числа 58, со­дер­жа­щий не более 5 ко­манд. В от­ве­те за­пи­ши­те толь­ко но­ме­ра ко­манд. (На­при­мер, 22111 — это ал­го­ритм: воз­ве­ди в квад­рат, воз­ве­ди в квад­рат, при­бавь 3, при­бавь 3, при­бавь 3, ко­то­рый пре­об­ра­зу­ет число 3 в 48.) Если таких ал­го­рит­мов более од­но­го, то за­пи­ши­те любой из них.

За­да­ние 5. У ис­пол­ни­те­ля Квад­ра­тор две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра: 1. вычти 1 2. воз­ве­ди в квад­рат Пер­вая из них умень­ша­ет число на экра­не на 1, вто­рая воз­во­дит его во вто­рую сте­пень. Ис­пол­ни­тель ра­бо­та­ет толь­ко с на­ту­раль­ны­ми чис­ла­ми. Со­ставь­те ал­го­ритм по­лу­че­ния из числа 2 числа 64, со­дер­жа­щий не более 5 ко­манд. В от­ве­те за­пи­ши­те толь­ко но­ме­ра ко­манд. (На­при­мер, 11121 — это ал­го­ритм: вычти 1, вычти 1, вычти 1, воз­ве­ди в квад­рат, вычти 1, ко­то­рый пре­об­ра­зу­ет число 7 в 15.) Если таких ал­го­рит­мов более од­но­го, то за­пи­ши­те любой из них.