Главные вкладки
Основы алгоритмизации и программирования
Материалы к занятиям
Скачать:
| Вложение | Размер |
|---|---|
 1_algoritmy.pptx | 475.85 КБ |
| 2_osnovnye_algoritmich_konstruktsii.pptm | 190.81 КБ |
| 3_usloviya.pptx | 319.64 КБ |
| 4_reshenie_zadach.pptx | 90.37 КБ |
| 5_tsikl_algoritm.pptx | 144.61 КБ |
Предварительный просмотр:
Подписи к слайдам:
АЛГОРИТМ - понятное и точное предписание исполнителю совершить последовательность действий, направленных на достижение указанной цели или на решение поставленной задачи
Абдулла Мухаммед аль-Хорезми (783 - 850гг.) Algorithmi 825 год
ИСПОЛНИТЕЛЬ - это что-то или кто-то, способный выполнить действия , предписываемые алгоритмом
ИСПОЛНИТЕЛИ АЛГОРИТМОВ НЕФОРМАЛЬНЫЕ: ФОРМАЛЬНЫЕ: Человек животные Робот-манипулятор Техническое устройство (бытовые приборы) Компьютер
СИСТЕМА КОМАНД ИСПОЛНИТЕЛЯ ( СКИ) – совокупность команд, которые данный исполнитель может выполнить.
Обрабатываемые данные - величины Входные Промежуточные Выходные (аргументы) (результаты) Исходные данные, известные перед выполнением задачи Результат решения задачи
ВЕЛИЧИНЫ Х АРАКТЕРИЗУЮТСЯ: именем типом значением - обозначение и место в памяти - множество допустимых значений и множество применимых операций к ней, значение в ячейке
Постоянная Переменная (константа) Не изменяется и не может быть изменено ВЕЛИЧИНА Значение меняется в ходе выполнения алгоритма
СВОЙСТВА АЛГОРИТМОВ Понятность Дискретность Однозначность Массовость Результативность Конечность
ПОНЯТНОСТЬ Алгоритм составляется только из команд, входящих в СКИ.
ДИСКРЕТНОСТЬ Алгоритм разбит на отдельные элементарные действия (шаги).
ОДНОЗНАЧНОСТЬ Каждое действие однозначно понятно исполнителю и не может быть истолковано неопределенно.
МАССОВОСТЬ Алгоритм, разработанный для решения некоторой задачи, должен быть применим для решения задач этого типа при всех допустимых значениях исходных данных
РЕЗУЛЬТАТИВНОСТЬ (ИЛИ КОНЕЧНОСТЬ) Выполнение алгоритма должно приводить к результату за конечное число шагов
СПОСОБЫ ЗАПИСИ АЛГОРИТМА Словесный Графический Программный
Словесная форма – естественный язык Последовательность шагов, которые выполняются исполнителем, записывается в форме нумерованного списка. Пример : Переход улицы: Остановись на тротуаре. Посмотри налево. Если транспорта нет, то иди до середины улицы и остановись, иначе выполняй п. 2. Посмотри направо. Если нет транспорта, то иди до противоположного тротуара, иначе выполняй п. 4.
БЛОК-СХЕМА - графическое представление алгоритма. Она состоит из функциональных блоков, которые выполняют различные назначения (ввод/вывод, начало/конец, вызов функции и т.д.).
Условные графические обозначения в схемах алгоритмов Наименование Обозначение Пуск-останов Процесс
Наименование Обозначение Решение Ввод-вывод Модификация Соединители Комментарии Текст комментария
ПЕРЕХОД УЛИЦЫ Начало Подойти к переходу Дождаться зеленого света Перейти улицу Конец
Предварительный просмотр:
Подписи к слайдам:
№2 Алгоритм должен обязательно выполнятся за конкретное (определенное) число шагов.
№3 Если задачу можно разбить на отдельные шаги (действия), то для нее можно составить алгоритм.
№4 Строгая последовательность конечного числа действий является алгоритмом.
№5 Для любых задач можно разработать алгоритм.
№6 Алгоритмизация – обязательный этап для решения задачи с использованием компьютера.
№7 Свойство «дискретность» указывает на возможность разбиения алгоритма на отдельные шаги.
№8 «Дискретность» является необязательным свойством алгоритма.
№9 Свойство «результативность» указывает на получение результата за конечное число шагов.
№10 «Массовость» является желательным свойством алгоритма.
Основные алгоритмические конструкции
ЛИНЕЙНЫЙ АЛГОРИТМ - описание действий, которые выполняются однократно в заданном порядке
В своей книге «Арифметика» Леонтий Филиппович Магницкий привел следующий способ отгадывания задуманного двузначного числа: «Если кто задумает двузначное число, то ты скажи ему, чтобы он увеличил число десятков задуманного числа в 2 раза, к произведению прибавил бы 5 единиц, полученную сумму увеличил в 5 раз и к новому произведению прибавил сумму 10 единиц и числа единиц задуманного числа, а результат произведенных действий сообщил бы тебе. Если ты из указанного тебе результата вычтешь 35, то узнаешь задуманное число» Представить предлагаемые действия в виде алгоритма
РАЗВЕТВЛЯЮЩИЙСЯ АЛГОРИТМ- алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
вопрос, на который можно однозначно ответить «да» или «нет» УСЛОВИЕ –
ЕСЛИ Мы надеваем тёплую одежду, ЕСЛИ на улице холодно Мы идём в магазин за хлебом, ЕСЛИ хлеб весь съели Мы берём на улицу зонтик, ЕСЛИ погода пасмурная
УСЛОВИЕ ДА НЕТ ?
Мячик красный? Снег белый? Кто спрятался в корзине? Сколько будет 3+2? Мы пойдём гулять? У домика есть труба? На какой вопрос можно ответить «ДА» или «НЕТ»?
КОМАНДА ВЕТВЛЕНИЯ ИМЕЕТ ПОЛНУЮ (1) ИЛИ СОКРАЩЕННУЮ ФОРМУ(2) 1 Серия 1 Условие Серия 2 Да Нет Да Нет Условие Серия 1 2
Настроение хорошее? Позвонить другу Погулять ДА НЕТ НАЧАЛО КОНЕЦ ДА НЕТ ДА НЕТ Пример разветвляющегося алгоритма
По данной блок-схеме в словесном описании алгоритма расставить номера шагов Шаг 1. Вводим Х. Переходим к шагу … Шаг 2. Если Х >= 18, то записываем «призывник» и переходим к шагу …, иначе к шагу … Шаг 3. Записываем «допризывник». Переходим к шагу … Шаг 4. Задача окончена начало конец Х Х >= 18 допризывник призывник Да Нет
Составить алгоритм проверки грибов, в котором использована полная форма ветвления Представьте в виде блок-схемы поведение кота из сказки А. С. Пушкина: «идет направо — песнь заводит, налево — сказку говорит» Если среднесуточная температура воздуха ниже +8 °С, то приступить к протапливанию помещений
Сколько вариантов ? ?
Предварительный просмотр:
Подписи к слайдам:
Сложные условия в разветвляющихся алгоритмах
простые сложные Условия
Простое условие Включает в себя два числа, две переменных или два арифметических выражения, которые сравниваются между собой Например: 5 >4; x * y=3+8. Условие, содержащее один знак сравнения, называется простым
Сложные условия При решении задач возникает необходимость объединения двух или более условий в одно условие. Для этого используются логические связки: или, и, не .
Сложное условие Последовательность простых условий, объединенных между собой знаками логических операций И , ИЛИ Например: ( 10 >0) И (8>9); (x=10) ИЛИ (x>=0).
Логические связки Логическая связка И используется, когда все условия выполняются одновременно. Логическая связка ИЛИ используется, когда достаточно выполнения хотя бы одного из нескольких условий. НЕ – отрицание условия.
происходит замена знаков отношения на противоположные по схеме : < ↔ ≥ > ↔ ≤ = ↔ ≠ Логическое отрицание
Запишите отрицание X < 10 B = -2 C >= 0 D 33 H > J N <= 88
Запишите в виде сложного условия а < b < c а b < c а b c
X лежит вне отрезка [ a , b ]; X принадлежит отрезку [ a , b ] или отрезку [ c , d ]; K является трехзначным числом; Какое из чисел a , b , c является меньшим; Есть ли среди чисел a , b , c взаимно противоположные; Равны ли треугольники со сторонами a1, b1, c1 и a2, b2, c2 ; Заданное натуральное число N является двузначным и кратно К . Запишите в виде условия
( x < a ) и ( x > b ); (( x > =a ) и ( x < =b )) или (( x > =c ) и ( x < =d )); ( k > 99) и ( k < 1000); ( c < a ) и ( b > a ); ( a=-b ) или ( a=-c ) или ( b=-c ); (a1= a2 ) и ( b1 = b2 ) и ( c1 =c 2 ); Ответы:
Укажите логическое выражение, определяющее полуотрезок (-1;3 ] 1 . ( x <=3) и ( x >-1) 2 . ( x <3) или не ( x >-1) 3 . (x>=-1) и (x<3)
Записать логическое выражение, при значении истинности которого точка на координатной плоскости с координатами X и Y лежит внутри единичной окружности с центром в начале координат. 1 1 -1 0 Y X Решение: Из геометрических соображений понятно, что для всех точек, лежащих внутри единичной окружности, будет истинным значение следующей логической функции: ( X 2 +Y 2 ) <1
Записать условие, по которому точка с координатами (X, Y) принадлежит заштрихованной области
Предварительный просмотр:
Подписи к слайдам:
Если ты, мечтой томим, Знаешь слово Элоим , Муху странную бери, Муху в банку посади, С банкой по полю ходи, За приметами следи. Если муха чуть шумит, Под ногою медь лежит, Если усиком ведет, К серебру тебя зовет. Если хлопает крылом, Под ногами злата ком. (Н. Заболоцкий “Царица мух”)
Найдите ошибки в предложенной блок-схеме: 3 начало конец Действие 1 Действие 2 Действие 3 Действие 1 Действие 2 Действие 3 Начало Конец
Найдите ошибки в предложенной блок-схеме: Ввод а, в Р=х-у Вывод S Начало Конец Ввод х , у Р=х-у Вывод Р Начало Конец
Найдите ошибки в предложенной блок-схеме: 5 Ввод а условие Действие Начало Конец Ввод а Действие Условие Начало Конец Да Нет
х 5 -2 0 у 30 6 10 6 Ввод х Х <0 У=8+Х У= 4Х+10 Вывод у да нет Начало Конец
Составить блок-схему Требуется определить тип треугольника по двум введенным углам. При выполнении задания необходимо учесть ситуации некорректного ввода данных, например: 90, 90 или 120, 80. 7
Предварительный просмотр:
Подписи к слайдам:
Какие формы ветвления вы знаете ?
p вход нет да выход вход выход к Как выглядит блок-схема полного(неполного) ветвления ? вход выход .. .. p вход выход 1) 2) 3) 4)
Пример 1 : имеется коробка карандашей, надо поточить все карандаши в этой коробке. точить 1-ый карандаш точить 2-ой карандаш точить 3-ий карандаш точить 4-ый карандаш точить 5-ый карандаш точить 6-ой карандаш взять карандаш точить карандаш В коробке есть карандаш? нет да начало конец начало конец
Циклические алгоритмы
Алгоритм, предусматривающий многократное повторение одного и того же действия над новыми данными, называется циклическим
Цикл с постусловием ; Цикл с предусловием; Цикл с параметром . Различают три вида циклов:
Пример 1 : имеется коробка карандашей, надо поточить все карандаши в этой коробке. взять карандаш точить карандаш В коробке есть карандаш ? нет да начало конец
Цикл с постусловием р s вход выход нет да Особенности : 1) тело цикла расположено до проверки условия 2) цикл выполняется хотя бы 1 раз
Пример 2 : собирай грибы, пока в корзине есть место. есть место ? собирай грибы да нет начало конец
Цикл с предусловием р s вход выход нет да Особенности : 1) тело цикла расположено после проверки условия 2) цикл может ни разу не выполниться
Пример 3 : описать процесс обучения в школе. Учебный год начало конец К:=1 до 11
цикл с параметром вход Тело цикла выход нет да Особенности : 1) число повторений цикла известно заранее или может быть вычислено От нач. знач до конечного значения
Составьте блок-схему по предложенному словесному алгоритму
Алгоритм «Пульс» Удобно положите левую руку ладонью вверх. Два пальца правой руки положите на запястье левой руки. Заметьте положение секундной стрелки. Сосчитайте очередной удар. Посмотрите на часы. Если секундная стрелка прошла полный круг, то закончите действия, иначе перейдите к п. 4. Конец алгоритма
Алгоритм «Упражнение для глаз» Возьмите карандаш. Установите его в исходное положение у кончика носа. Повторите 10 раз, следя за движением карандаша: a . Переместите карандаш на расстояние вытянутой руки; b . Верните карандаш в исходное положение. Положите карандаш. Конец алгоритма
Алгоритм «Бочка» Подойдите к бочке. Если бочка неполная (есть место для воды), то перейдите к п. 3, иначе конец алгоритма. Наберите ведро воды. Вылейте ведро в бочку. Перейдите к п. 2. Конец алгоритма
Исходными данными для этой задачи являются: b — балл текущего ученика; n — количество учеников. Расчетные данные: s — сумма баллов; sr — средний балл. Требуется подвести итоги контрольной работы