А. В. Володько

ДЕТАЛИ
[+/-]

Виджеты

Виджеты<bs-widget-edit>

Требуемые страницы
Кто в сети?
Материал из Wiki Лицея
Перейти к: навигация, поиск

Изучаем алгоритмы

Алгоритмы и исполнители

Все, что бы мы ни делали, имеет какую-то цель. Не всегда ее удается достигнуть, но для того чтобы это было возможно необходимо как следует сформулировать желаемый для себя результат, а потом продумать четкий план его достижения. Часто план сформулирован в виде предписаний или инструкций.

Алгоритм – понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящую к достижению результата.

 Исполнитель – тот объект или субъект, для управления которым составлен алгоритм.
Характеристики исполнителя:

  • СКИ — система команд исполнителя – вся совокупность команд, которые исполнитель умеет выполнять.
  • среда – обстановка, в которой функционирует исполнитель.

Свойства алгоритма:

  • Понятность – алгоритм должен быть составлен только из команд, входящих в СКИ.
  • Дискретность (детализация) – алгоритм разбивается на отдельные элементарные шаги, которые могут быть исполнены при помощи СКИ.
  • Однозначность (определенность или детерминированность) – каждый шаг алгоритма имеет единственность толкования выполнения действия и порядка их выполнения.
  • Результативность (конечность) – выполнение алгоритма должно приводить к результату за конечное число шагов.
  • Массовость – возможность применения алгоритма к классу однотипных задач, различающихся исходными данными.

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

Способы записи алгоритмов.

На практике наиболее распространены следующие формы представления алгоритмов:

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

Система программирования КуМир

КуМир (Комплект Учебных МИРов) - система программирования, предназначенная для поддержки начальных курсов информатики и программирования в средней и высшей школе.

Сайт: http://www.niisi.ru/kumir/ и http://lpm.org.ru/kumir2/

В системе КуМир используется школьный алгоритмический язык с русской лексикой и встроенными исполнителями Робот и Чертёжник.

При вводе программы КуМир осуществляет постоянный полный контроль ее правильности, сообщая на полях программы об всех обнаруженных ошибках.

При выполнении программы в пошаговом режиме КуМир выводит на поля результаты операций присваивания и значения логических выражений. Это позволяет ускорить процесс освоения азов программирования.

В простейшем случае программа на КуМире выглядит так:

алг Первый
нач
. 
кон

После «алг» (алгоритм) пишется имя алгоритма, между «нач» (начало) и «кон» (конец) пишутся команды алгоритма. При написании автоматически создаются отступы вначале строки, это делает программу более наглядной, удалять или пытаться сделать отступ самим не надо.

Приведенный алгоритм «Первый» не будет ничего делать, т. к. между «нач» и «кон» у него нет  команд.

Вот пример уже работоспособного алгоритма:

алг Площадь прямоугольника
нач
. вещ длина, ширина, площадь
. вывод "введите значения длины и ширины прямоугольника"
. ввод длина, ширина
. площадь := длина * ширина
. вывод "Площадь прямоугольника равна ", площадь
.кон

Его уже можно запустить на выполнение, он запросит у пользователя значения длины и ширины, вычислит и напечатает результат вычислений...

Простые команды

Эти команды используются практически во всех алгоритмах.

  • команда описания переменных
  • команда присваивания
  • команды ввода-вывода

Величины в алгоритмах

Для запоминания информации в памяти используют величины.

Компьютер работает с информацией, хранящейся в его памяти. Отдельный информационный объект (число, символ, строка, таблица и пр.) называется величиной.

Величины в программировании, как и в математике, делятся на переменные и константы. Значение константы остается неизменной в течении всей работы программы, значение переменной величины может изменяться.

У каждой переменной есть имя, тип и текущее значение.

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

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


В именах можно использовать:

  • буквы (русские и латинские, прописные и строчные)
  • цифры
  • два специальных знака: @ _

Примеры возможных имен: m, x2, площадь, погода на завтра, Ноябрь 7, Седьмое ноября, дом_57б.

Также будьте внимательны при использовании имен, одинаково выглядящих на русском языке и записанных латинскими буквами. Переменные "x" (икс) и "x" (хэ) - это разные переменные.

Типы переменных

Существуют три основных типа величин, с которыми работает компьютер: числовой, символьный и логический.

Тип величины определяет какие значения она может принимать и какие действия с ней можно выполнять. В зависимости от типа переменной в памяти компьютера будет выделена определенная область. В КуМире числовые типы бывают двух видов: целочисленные и вещественные.

Числовые типы

  • цел - целые числа от -2147483647 до 2147483647
  • вещ - действительные числа от -1.797693 × 10308 до 1.797693 × 10308

Текстовые типы

  • сим - один любой символ
  • лит - строка символов

Описание переменных

Для того чтобы компьютер мог работать с величиной, нужно указать тип и имя величины, например «цел n». Такое указание называется описанием величины.

алг
нач

цел а, б вещ частное
...
кон

Команда присваивания

Для того чтобы запомнить или изменить значение величины есть специальная команда — команда присваивания, которая записывается в виде:

имя величины := выражение
Например:
частное := а/б
с:= div(а,б)
k:= sqrt(a)

Команда вывода

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

вывод "тексты", имена величин, выражения, нс

Обратите внимание:

  • текстовые сообщения берутся в кавычки;
  • имена переменных и выражения перечисляются через запятую без кавычек;
  • нс - команда перехода на новую строку

Команда ввода

Позволяет вводить с клавиатуры значения переменных перечисленных в этой команде

ввод а, б

Примеры простых алгоритмов и практическое задание

Алгоритм сложения двух чисел

сложение.png


Алгоритм нахождения суммы цифр двузначного числа

сумма цифр двузначного числа

Задания

  1. Напишите алгоритм нахождения суммы цифр трехзначного числа
  2. Даны длины сторон прямоугольника. Найти его периметр и длину диагонали.
  3. Задачи для тренировки
  4. Задачи на целочисленное деление

Ветвление

Структура полного и неполного ветвления. Блок-схемы. Сложные условия (использование и, или, не)

Решение задачи нахождение наибольшего из трех чисел двумя способами:

с использованием сначала полного ветвления, а затем неполного ветвления

с использованием двух неполных ветвлений

2015-04-06 16-22-15 макс 1.kum - Кумир.png
2015-04-06 16-25-06 макс 2.kum - Кумир.png

Практические задания

Задачи для самостоятельного решения

Задачи на ветвление по уровням сложности

Циклы

Циклическим называется алгоритм, в котором некоторая часть операций (тело цикла — последовательность команд) выполняется многократно. Однако слово «многократно» не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма, является нарушением требования его результативности — получения результата за конечное число шагов.Если количество повторений заранее известно, то такой цикл называется арифметическим (или циклом с параметром). Если количество повторений для цикла заранее неизвестно, то такой цикл называется итерационным.

Цикл с параметром или Цикл для

цикл "для"
-
нц для i от i1 до i2

 . тело цикла (последовательность действий)
кц

В первой строке (заголовке цикла - нц) в неявной форме задано количество повторений команд тела цикла:

i – параметр цикла, переменная целого типа, которая в процессе выполнения команды последовательно пробегает множество значений, начиная с i1 до i2 с шагом 1.
 Если i1 = i2, то тело цикла выполнится один раз для i = i1.
 Если же i1 > i2, то тело цикла не выполнится ни разу

Договоренности:
* В теле цикла нельзя использовать команды, изменяющие значение параметра цикла, так как это приведет к ошибке исполнения цикла.
* После окончания цикла значение параметра использовать нельзя, так как оно считается неопределенным.

Цикл с предусловием или Цикл пока

факториал.jpg

Задачи, решаемые с использованием циклических алгоритмов

  • Вычисление факториала целого положительного числа.
  • Возведение целого числа в натуральную степень.
  • Подсчет количества цифр в введенном целом произвольном числе.
  • Нахождение суммы чисел вводимых с клавиатуры.

Задачи для самостоятельной работы

1. Задачи на циклы по уровням сложности

2. Домашнее задание на циклы