Слово "алгоритм" увековечило известного в далеком прошлом математика аль Хорезми, от имени которого оно и произошло. В IX веке аль Х

• 1 слайд

  Слово "алгоритм" увековечило известного в далеком прошлом математика аль Хорезми, от имени которого оно и произошло.
  В IX веке аль Хорезми сформулировал правила выполнения четырех арифметических действий.
  def: АЛГОРИТМ – однозначно трактуемая (исполнителем) процедура решения задачи, включающая конечную последовательность точно определенных шагов или операций, для выполнения которых (исполнителю) требуется конечный объем памяти и конечное время.
  Действия могут быть любыми, но всегда должны быть определены начальные условия и конечный результат.
  Для любых начальных условий, удовлетворяющих заданию на алгоритм, последний должен дать правильный результат. Это правильный алгоритм.
  

• 2 слайд

  Пирог творожный
  Начальные условия:
  * мука - 2 стакана
  * сливочное масло - 200 грамм
  * творог - 200 грамм
  * сгущенное молоко - 1 банка
  * орехи грецкие
  Собственно, алгоритм:
  1. размельчить масло
  2. тщательно растереть его с творогом
  3. добавить муку
  4. замесить тесто и оставить его на холоде на 20-30 минут
  5. проварить сгущенное молоко 20-30 мин
  6. раскатать из теста 4 коржа
  7. выпечь коржи
  8. смазать коржи горячей сгущенкой
  9. посыпать коржи орехами
  10. положить коржи один на другой
  
  Вот такой вот пирог.
  

• 3 слайд

  СФОРМИРОВАТЬ СЧЕТ
  ОПРЕДЕЛИТЬ СУММУ ПОКУПКИ
  в каждой строке счета:
  сумма = кол-во * цена
  сложить суммы по всем строкам
  ЕСЛИ СУММА ПОКУПКИ > 1000 руб. ТО
  ОПРЕДЕЛИТЬ СУММУ СКИДКИ
  определить тип клиента
  определить величину скидки в процентах
  сумма скидка = сумма покупки * процент / 100
  ОПРЕДЕЛИТЬ ИТОГ
  итог = сумма покупки - скидка
  НАПЕЧАТАТЬ СЧЕТ
  ЗАРЕГИСТРИРОВАТЬ СЧЕТ В ЖУРНАЛЕ
  
  Работаем с разными уровнями детализации =>
  уменьшаем сложность программирования и количество ошибок =>
  ускоряем разработку программ.
  Такие простые алгоритмы полезно записывать в комментариях.
  
  

• 4 слайд

  правильный результат
  ВЫВОД: Алгоритм можно написать на СТРУКТУРНОМ
  ЕСТЕСТВЕННОМ ЯЗЫКЕ, если Вы его знаете!!!!!!!
  начальные условия
  правильный алгоритм
  алгоритм
  конечный результат
  

• 5 слайд

  Один важный момент, касающийся алгоритмов: алгоритм должен быть понятен исполнителю.
  Исполнители могут быть разными –> конкретность алгоритма для исполнителя.
  Исполнителя хаpактеpизуют:
  сpеда;
  cистема команд;
  элементаpные действия; (результат выполнения команды)
  отказы.(когда команда задана при недопустимом состоянии среды)
  
  

• 6 слайд

  СВОЙСТВА алгоритма
  
  Понятность
  Дискpетность
  Опpеделенность
  Pезультативность
  Массовость
  ФОРМЫ алгоритма
  
  Словесная - рецепт, инструкция
  Графическая - блок-схема
  Псевдокоды - псевдоязык
  Программная - язык программирования
  

• 7 слайд

  Понятность для исполнителя — т.е. исполнитель алгоритма должен знать, как его выполнять.
  Дискpетность (прерывность, раздельность) — т.е. алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов).
  Опpеделенность — т.е. каждое пpавило алгоpитма должно быть четким, однозначным и не оставлять места для пpоизвола. Благодаpя этому свойству выполнение алгоpитма носит механический хаpактеp и не тpебует никаких дополнительных указаний или сведений о pешаемой задаче.
  Pезультативность (или конечность). Это свойство состоит в том, что алгоpитм должен пpиводить к pешению задачи за конечное число шагов.
  Массовость. Это означает, что алгоpитм pешения задачи pазpабатывается в общем виде, т.е. он должен быть пpименим для некотоpого класса задач, pазличающихся лишь исходными данными. Пpи этом исходные данные могут выбиpаться из некотоpой области, котоpая называется областью пpименимости алгоpитма.
  

• 8 слайд

  Почти всегда составитель алгоритма и исполнитель - разные лица. И Вам надо побеспокоиться о том, чтобы Ваш алгоритм был понятен исполнителю.
  Алгоритм может быть записан в любой форме: на естественном языке, на каком-либо символическом языке, на языке схем и т.д.
  Например, математические выражения - это тоже алгоритмы для тех кто знает математику:
  Пример:
  (2^3+4)+2*5
  Это простое выражение (алгоритм) с математического языка можно перевести на естественный (словестный) язык:
  1. возвести 2 в третью степень (получим 8)
  2. к 8 прибавить 4 (получим 12)
  3. умножить 2 на 5 (получим 10)
  4. к 12 прибавить 10 (получим 22)
  Если исполнитель - компьютер, то алгоритм записывается на языке программирования, который данный компьютер «понимает».
  

• 9 слайд

  перестановка 2-х чисел a и b
  a = a xor b
  b = a xor b
  a = a xor b
  tmp = a
  a = b
  b = tmp
  a = a + b
  b = a – b
  a = a – b
  Исключающее ИЛИ (умножение с переносом)
  xor, NEQV, ^
  a=01 b = 10
  
  01 xor 10 = 11
  11 xor 10 = 01
  11 xor 01 = 10
  

• 10 слайд

  Целесообразно перед написанием самой программы написать алгоритм ее работы, т.е. определить что и как должна делать программа без углубления в синтаксис конкретного языка программирования. Это позволяет не утонуть в деталях и видеть основной принцип работы.
  На практике наиболее распространены следующие формы представления алгоритмов:
  словесная (записи на естественном языке);
  графическая (изображения из графических символов);
  псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
  программная (тексты на языках программирования).
  
  

• 11 слайд

  Псевдокод представляет собой систему обозначений и правил,
  предназначенную для единообразной записи алгоритмов
  Основные служебные слова
  
  Общий вид алгоритма,записанного на псевдокоде:
  
  алг название алгоритма (аргументы и результаты)
  дано условия применимости алгоритма
  надо цель выполнения алгоритма
  нач описание промежуточных величин
  последовательность команд (тело алгоритма)
  кон
  Часть алгоритма от слова алг до слова нач называется заголовком,
  а часть, заключенная между словами нач и кон — телом алгоритма.
  

• 12 слайд

  В предложении алг после названия алгоритма в круглых скобках указываются:
  характеристики (арг, рез) и
  тип значения (цел, вещ, сим, лит или лог)
  всех входных (аргументы) и
  выходных (результаты) переменных.
  При описании массивов (таблиц) используется служебное слово таб,
  дополненное граничными парами по каждому индексу элементов массива.
  Примеры предложений алг:
  алг Объем и площадь цилиндра (арг вещ R, H, рез вещ V, S)
  алг Корни КвУр(арг вещ а, b, c, рез вещ x1, x2, рез лит t)
  алг Исключить элемент(арг цел N, арг рез вещ таб А[1:N])
  алг Диагональ(арг цел N, арг цел таб A[1:N,1:N], рез лит Otvet)
  
  Предложения дано и надо не обязательны.
  В них рекомендуется записывать утверждения,
  описывающие состояние среды исполнителя алгоритма, например:
  алг Число максимумов (арг цел N, арг вещ таб A[1:N], рез цел K)
  дано | N>0
  надо | К - число максимальных элементов в таблице А
  Здесь в предложениях дано и надо после знака "|" записаны комментарии.
  

• 13 слайд

  Оператор присваивания := служит для вычисления выражений и
  присваивания их значений переменным.
  Общий вид: А := В
  Для ввода и вывода данных используют команды
  ввод имена переменных
  вывод имена переменных, выражения, тексты.
  
  Для ветвления применяют команды если и выбор,
  для организации циклов — команды для и пока.
  
  Пример записи алгоритма в псевдокодах
  алг Сумма квадратов (арг цел n, рез цел S)
  дано | n > 0
  надо | S = 1*1 + 2*2 + 3*3 + ... + n*n
  нач
  цел i 
  ввод n; S:=0 
  нц для i от 1 до n   
  S:=S+i*i 
  кц 
  вывод "S = ", S
  кон
  

• 14 слайд

  Графическое описание алгоритмов выполняется с помощью блок-схем, составленных из последовательности блоков, предписывающих выполнение отдельных операций, и связей между ними.
  Правила оформления блок-схем
  внутри блоков помещается информация, поясняющая действия;
  конфигурация блоков и размеры оговорены ГОСТом;
  каждый блок снабжается номером в разрыве контура блока в левой верхней части;
  высота блока (размер a) выбирается из ряда 10, 15, 20…мм;
  ширина блока (размер b) выбирается как b=1,5a;
  в схемах, не являющихся документацией (плакаты, курсовые работы), можно увеличить ширину блока для удобства записи информации;
  ход вычислительного процесса изображается линиями связи;
  линии связи обязательно имеют стрелки, если они направлены снизу вверх или справа налево – в остальных случаях стрелки необязательны.
  Преимущества графического описания алгоритмов
  наглядность;
  читаемость;
  явное отображение управления;
  имеет стандарт изображения элементов.
  

• 15 слайд

  Типы вершин блок-схем алгоритмов
  Блок-схема – ориентированный граф, указывающий порядок исполнения команд алгоритма.
  Существует только три типа вершин.
  F
  P
  true
  false
  

• 16 слайд

  В таблице приведены наиболее часто употребляемые блоки схем алгоритмов.
  

• 17 слайд

• 18 слайд

  Следование Ветвление (выбор) Цикл
  КомпозицияАльтернативаИтерация
  IF THEN ELSE WHILE DO DO WHILE
  Принцип структурного программирования
  (Теорема Бема-Якопини) –
  логическая структура любой программы может быть выражена комбинацией из базовых структур:
  1) Следование. 2) Ветвление. 3) Цикл.
  Структурная блок схема -композиция из базовых алгоритмических структур
  Один вход - один выход
  

• 19 слайд

  Базовая структура следование. Образуется из
  последовательности действий, следующих одно за другим:
  
  Язык блок-схем
  Псевдокоды
  действие 1
  действие 2
  . . . . . . . . .
  действие n
  

• 20 слайд

  Структура ветвление существует в четырех основных вариантах:
  если условие  
  то действия
  все
  . 1. если-то
  2. если-то-иначе
  Если условие
    то действия 1
    иначе действия 2
  все
  

• 21 слайд

  3. выбор
  выбор  
  при условие1: действия1
    при условие2: действия2
    . . . . . . . . . . . .
    при условиеN: действияN все
  4. выбор-иначе
  Выбор
    при условие1: действия1
    при условие2: действия2
    . . . . . . . . . . . .
    при условиеN: действияN
    иначе действия N+1
  все
  

• 22 слайд

  Способы комбинации структур
  Путем СЛЕДОВАНИЯ структур друг за другом.
  Путем создания СУПЕРПОЗИЦИЙ – вложение одной структуры в другую.
  Признаки структурного программирования
  1. Полное исключение операторов безусловных переходов.
  2. Модульность.
  Модуль – последовательность логически связанных операций,
  оформленных как отдельная часть программы.
  Преимущества модульной структуры:
  возможность разработки программы несколькими программистами;
  простота проектирования и модификации программ;
  упрощение отладки программ: поиска и устранения ошибок;
  возможность использования готовых библиотек подпрограмм и модулей;
  лучшая читаемость программ.
  3. Детализация или декомпозиция – нисходящее проектирование программ:
  построение иерархии модулей программ;
  разбиение задач на подзадачи;
  детализация до уровня подзадач, решение которых обеспечивается за
  35 строк.
  

• 23 слайд

  Определить является ли
  натуральное число N>2
  простым ?
  2 <= k <= N-1
  и N – простое
  нет
  Выход
  да
  остатокN : k
  = 0
  N – простое
  N – не простое
  k = k+1
  да
  нет
  N – простое, k=2
  

• 24 слайд

  Алгоритм N>2 простое ?
   
  N – простое
  Перебор натур.чисел k от 2 до N-1
  Если (остаток N / k == 0 и N – простое), то
  N – не простое
  
  Определить является ли
  натуральное число N>2 простым ?
  Алгоритм не эффективен, но правилен
  

• 25 слайд

  Расширения базовых структур
  Многовариантный выбор
  

• 26 слайд

  S1
  S2
  B
  C
  T
  F
  F
  T
  Прекращение итерации цикла
   Досрочный выход из цикла