Как составить алгоритм программы для начинающих

Is this article up to date?

Была ли эта статья полезной?

Итак, опустив долгие и нудные восхваления Паскаля, которые так любят публиковать в своих статьях редакторы многих сайтов, приступим непосредственно к самому основному – к программированию.

В школах, как правило, изучение Паскаля начинают с решения простейших задач путем составления различных алгоритмов или блок-схем, которое многие так часто игнорируют, считая никому не нужной ерундой. А зря. Я, как и любой другой человек, хоть немного соображающий в программировании (не важно где – в Паскале, Си, Дельфи), могу уверить Вас – умение правильно и быстро составлять схемы является фундаментом, основой программирования.

Блок-схема — графическое представление алгоритма. Она состоит из функциональных блоков, которые выполняют различные назначения (ввод/вывод, начало/конец, вызов функции и т.д.).

Существует несколько основных видов блоков, которые нетрудно запомнить:

Сегодняшний урок я решила посвятить не только изучению блок-схем, но также и изучению линейных алгоритмов. Как Вы помните, линейный алгоритм — наипростейший вид алгоритма. Его главная особенность в том, что он не содержит никаких особенностей. Как раз это и делает работу с ним простой и приятной.

Задача №1: «Рассчитать площадь и периметр прямоугольника по двум известным сторонам».

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

Составим алгоритм решения подобных задач:

1) Прочитать задачу.
2) Выписать известные и неизвестные нам переменные в «дано». (В задаче №1 к известным переменным относятся стороны: a, b ;к неизвестным — площадь S и периметр P)
3) Вспомнить либо составить необходимые формулы. (У нас: S=a*b; P=2*(a+b))
4) Составить блок-схему.
5) Записать решение на языке программирования Pascal.

Запишем условие в более кратком виде.

Дано: a, b

Найти: S, P

Блок-схема:

Структура программы, решающей данную задачу, тоже проста:

• 1) Описание переменных;
• 2) Ввод значений сторон прямоугольника;
• 3) Расчет площади прямоугольника;
• 4) Расчет периметра прямоугольника;
• 5) Вывод значений площади и периметра;
• 6) Конец.

А вот и решение:

Program Rectangle;
Var a, b, S, P: integer;
Begin
write('Введите стороны прямоугольника!'); 
readln(a, b);
S:=a*b;
P:=2*(a+b);
writeln('Площадь прямоугольника: ', S);
write('Периметр прямоугольника: ', P);
End.

Задача №2: Скорость первого автомобиля — V1 км/ч, второго – V2 км/ч, расстояние между ними S км. Какое расстояние будет между ними через T часов, если автомобили движутся в разные стороны? Значения V1, V2, T  и S задаются с клавиатуры.

Решение осуществляем, опять же, следуя алгоритму. Прочитав текст, мы переходим к следующему пункту. Как и во всех физических или математических задачах, это запись условий задачи:

Дано: V1, V2, S, Т
Найти: S1

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

Формула, используемая для решения нашей задачи, выглядит следующим образом:

S1=(V1+V2)*T+S

Следующий пункт алгоритма – блок-схема:

А также решение, записанное в Pascal :

Program Rasstoyanie;
Var V1, V2, S, T, S1: integer; {Ввод }
begin
write('Введите скорость первого автомобиля: '); 
readln(V1);
write('Введите скорость второго автомобиля: '); 
readln(V2);
write('Введите время: '); 
readln(T);
write('Введите расстояние между автомобилями: '); 
readln(S);
S1:=(V1+V2)*T+S;
writeln('Через ', t,'ч. расстояние ', S1,' км.');
End.

Вам может показаться, что две эти программы правильны, но это не так. Ведь сторона треугольника может быть 4.5, а не 4, а скорость машины не обязательно круглое число!  А Integer — это только целые числа. Поэтому при попытке написать во второй программе другие числа выскакивает ошибка:

Чтобы решить эту проблему вам надо вспомнить какой тип в Pascal отвечает за нецелые числа. В этом уроке мы рассматривали основные типы. Итак, это вещественный тип — Real.  Вот, как выглядит исправленная программа:

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

Алгоритмизация и программирование являются
одной из трудных для понимания учащимися тем в
предмете информатика, а при наличии дефицита
часов, выделяемых на изучение предмета, перед
учителем встает довольно сложная задача «Как
познакомить хотя бы с основами программирования
всех учащихся, в том числе и непрофильных
классов?». Между тем, как мы видим и в новых
стандартах и в демо-версии ЕГЭ по информатике эта
тема занимает существенное место. Предлагаемые
ниже материалы помогают познакомить ребят с
основными алгоритмическими конструкциями и
реализацией их на языке программирования
Паскаль и дать начальное представление о языке.
Заинтересовавшиеся учащиеся могут в дальнейшем
продолжить изучение языка программирования на
спецкурсе.

Предлагаю задания к трем урокам: по линейному
алгоритму, ветвлению и циклам. Типы переменных и
структура программы на Паскале рассматриваются
на предыдущих уроках.

Начальная подготовка учащихся.

• Знание основных алгоритмических конструкций:
  линейный алгоритм, ветвление, цикл.
• Знание основных типов переменных.
• Знание структуры программы на Паскале.

Ход урока.

Перед каждым уроком учитель раскладывает на
столах «Папки ученика», в которых находятся
листы с заданиями, таблица «Реализация элементов
блок – схемы алгоритма на языке Паскаль»,
«Алгоритм создания программы по шаблону» и
другой справочный материал. Если
предполагается создание программы по шаблону,
т.е. ученики редактируют уже имеющуюся программу,
то соответствующий файл *.pas с текстом программы
должен находится на жестком диске в
соответствующем каталоге.

Для знакомства с реализацией алгоритмической
конструкции средствами языка используется сайт http://schools.keldysh.ru/gym1522/inform/pascal/ (см. Приложение1)

Обсуждается задание, проговаривается сценарий,
составляется блок-схема алгоритма.

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

В качестве заданий на ветвление и циклы взяты
задачи по физике, так как программирование
изучается на уроках интегрированного с физикой
курса «Компьютерное моделирование физических
процессов и явлений» в 9 классе.

Описание приложений.

• Адрес сайта «Паскаль для начинающих» — http://schools.keldysh.ru/gym1522/inform/pascal/ Немного
  сокращенный вариант находится в архиве (Приложение1.zip). Сайт выполнен
  с использованием флэш-технологии, позволяет в
  анимационной форме дать начальное представление
  о языке Паскаль 7.0 Для демонстрации надо
  разархивировать в каталог на жестком диске.
  Главная страница сайта – index.html
• Тексты программ для создания программ по
  шаблону – файлы Приложение2.pas и Приложение3.pas. Их
  надо переименовать в Shablon1.pas и Shablon2.pas и поместить
  в соответствующий каталог на диске.

Использованная литература дана в Приложении 1
на сайте в разделе «ссылки».

Реализация элементов блок – схемы
алгоритма на языке Паскаль.

Линейный алгоритм. Простейшая
программа (ввод/вывод данных, вычисление суммы,
разности, произведения и частного двух чисел).

Для выполнения задания можно использовать
приведенный ниже текст программы или заранее
подготовленный учителем файл Shablon1.pas (файл Приложение2.pas) с текстом
программы, который находится в каталоге CLASS (там
же находятся личные папки учащихся). Ученик
проставляет вместо вопросительных знаков
необходимые операторы и служебные слова.
Комментарии в фигурных скобках поясняют, что
необходимо сделать. Программа состоит из двух
частей. В первой части программы демонстрируется
использование операторов ввода и вывода, во
второй, после комментария {ЗАДАНИЯ}, ученику надо
самому записать необходимые операторы,
используя приведенную выше блок-схему и
комментарии в программе. Алгоритм создания
программы по шаблону дан ниже.

Текст программы по линейному
алгоритму

PROGRAM P1;

{Объявление переменной S для ввода имени, надо
указать тип переменной — строковый}

VAR S: ???? ;

{Объявление переменных A и B для ввода чисел,
надо указать тип переменных — целые числа со
знаком}

VAR A,B: ???? ;

{Объявление переменной C для вывода результата,
надо указать тип переменной — все действительные
числа}

VAR C: ???? ;

{Начало раздела инструкций}

BEGIN

{Оператор вывода на экран сообщения (просьба
ввести имя)}

WRITE (‘Введите свое имя’);

{Оператор ввода данных (значение переменной S =
имя пользователя)}

READLN (S);

{Вывод на экран сообщения (приглашения к работе)
– слово «Привет» и значение переменной S
(введенное пользователем имя)}

WRITELN (‘Привет, ‘, S);

{ЗАДАНИЯ:}

{1)Запишите оператор вывода на экран
приглашения к вводу 2 чисел (переменные A и В)}

???????

{2) Запишите оператор ввода для переменных A и В}

???????

{3) Запишите оператор присваивания для
вычисления значения переменной С (сумма,
разность, произведение, частное двух чисел)}

C:=?????;

{4) Запишите оператор вывода на экран результата
вычислений (сумма (разность, произведение,
частное) = <значение переменной>}

????????

{Конец программы, конец раздела инструкций}

END.

Ветвление. Моделирование
равномерного прямолинейного движения двух тел.

Текст программы на ветвление

PROGRAM P2;

{Объявление переменных V1, V2 и V для значений
скоростей, тип переменных — целые числа со знаком
}

VAR V1, V2, V: ??? ;

{Объявление переменных A1 и A2 для значений
направлений, значения переменных — символы}

VAR A1, A2: ??? ;

{Начало раздела инструкций}

BEGIN

{Оператор вывода на экран сообщения (просьба
ввести скорость первого тела)}

WRITE (‘Введите скорость 1 тела’);

{Оператор ввода данных (значение переменной V1)}

READLN (V1);

{Тоже для второго тела}

?????????????

?????????????

{Аналогично осуществить ввод направлений
движения}

WRITE (‘Введите направление 1 тела’ );

READLN (A1);

?????????????

?????????????

{Условный оператор: проверка условия
равенства значений переменных A1 и A2}

IF A1 = A2 THEN V := V1 — V2 ELSE V := V1 + V2;

{Определение модуля вектора ABS – функция
вычисление абсолютной величины}

V:=ABS(V);

{Оператор вывода на экран результата
вычислений }

????????

{Конец программы, конец раздела инструкций}

END.

Текст программы находится в файле Приложение3.pas (в кодировке MS
DOS). Его надо переименовать в Shablon2.pas и можно
использовать при создании программы по шаблону
(см. алгоритм ниже).

Алгоритм создания программы по
шаблону.

1. Войти в систему программирования Turbo Pascal 7.0.

2. Открыть файл ShablonK.pas (K — номер шаблона):

2.1. File -> Open

2.2. Перейти в каталог CLASS (в списке Files
выбрать ..)

2.3. Выбрать файл ShablonK.pas (K — номер шаблона)

2.4. Подтвердить выбор (Open)

3. Выполнить задание, заменяя ????.

4. Сохранить файл в своем каталоге:

4.1. (File -> Save as)

4.2. Убедится, что находитесь в своем каталоге
(нижняя строчка)

4.3. Ввести имя файла

4.4. Подтвердить сохранение (Ok)

5. Запустить программу (Run -> Run или Ctrl+F9)

6. При наличии ошибок, внести изменения в
программу и повторить пункт 5.

7. Просмотреть результат выполнения программы (Debug
User Screen или Alt+F5)

8. Сохранить файл (File -> Save или F2)

9. Выйти из системы программирования (File ->
Exit или Alt+X)

Для циклического алгоритма уже текст программы
не дается. Учащиеся должны сами составить
программу по блок – схеме.

Циклы. Моделирование
равноускоренного движения.

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

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

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

Первое знакомство

Я начал программировать, когда ещё учился в средней школе. А первые шаги делал, создавая калькуляторы и светофоры на Visual Basic. Позже освоил HTML и Java. В то время я разрабатывал настольные и веб-приложения. Я просто писал хоть какой код, о внутренней логике и не задумывался.

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

Из программиста в разработчики

Изучение структур данных и алгоритмов стало поворотным пунктом в моём понимании компьютерного программирования: теперь я думал больше как инженер-разработчик, а не как программист. Почему я так говорю? Приведу несколько примеров.

Пример 1: алгоритмы сортировки

Представьте, что мы делаем приложение для интернет-магазина. Нам надо, чтобы пользователи могли просматривать товары в порядке возрастания цены. Для этого товары нужно отсортировать по цене. Будь я начинающим программистом, добавил бы цены в массив (или список) с записью их индексов и просто вызвал бы встроенный в массив метод sort(). Что на самом деле происходит внутри метода sort()? Когда я раньше делал приложения, я об этом и понятия не имел.

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

Различают следующие алгоритмы сортировки:

• сортировка вставками;
• сортировка выбором;
• быстрая сортировка;
• сортировка пузырьком;
• сортировка слиянием.

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

Пример 2: синтаксический анализ математических выражений

При вводе какого-нибудь математического выражения в калькулятор или в ячейку электронной таблицы, например MS Excel, оно автоматически вычисляется, и мы получаем ответ. Вы когда-нибудь задумывались о том, как это выражение высчитывается? А вот нам пришлось разработать программное обеспечение для работы с электронными таблицами и реализовать парсер выражений. Именно тогда я узнал о популярном алгоритме сортировочной станции. В нём используется очередь для хранения значений и стек для хранения операторов. Я узнал о реальных приложениях, в которых применяются такие структуры данных, как очереди и стеки (изучал их на курсе по структурам данных и алгоритмам), и понял лежащую в их основе логику. Меня так и распирала гордость оттого, что удалось самостоятельно реализовать алгоритм сортировочной станции, хотя таких реализаций тогда было уже полным-полно. 😃

Пример 3: списки, множества и словари

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

Всё это примеры из моего опыта, иллюстрирующие переход от мышления программиста к мышлению инженера-разработчика. Когда я делал выбор в пользу более подходящей структуры данных или более быстрого алгоритма, происходило значительное улучшение производительности моего кода.

С чего начать?

Изучаем концепции программирования

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

Осваиваем алгоритмы и их принципы работы

Помимо материалов моего курса, я занимался также по учебнику «Алгоритмы: построение и анализ» Томаса Х. Кормена, Чарльза Э. Лейзерсона, Рональда Ривеста и Клиффорда Штайна. Можно начать с самых азов:

• анализа временной и пространственной сложности;
• терминов “O” большое и “o” малое;
• рекурсии;
• базовых структур данных, таких как массивы, матрицы, связные списки, стеки, очереди, деревья и т. д.;
• основных алгоритмов, таких как алгоритмы поиска и сортировки.

Анализ временной и пространственной сложности  —  это очень важная тема, которую необходимо освоить, чтобы анализировать алгоритмы. Затем можно перейти к более продвинутым алгоритмам, таким как алгоритмы на графах.

Самое важное  —  чётко понимать, что происходит внутри алгоритма. Раньше я брал простые примеры и применял алгоритм, чтобы посмотреть, что происходит на каждом его шаге. Проработка примеров помогала мне лучше понять, что происходит в алгоритме, причём мне никогда не приходилось эти алгоритмы запоминать. Если меня попросят написать псевдокод для алгоритма, я смогу легко связать его с примером и проработать его, вместо того чтобы запоминать каждый шаг.

Погружаемся в код с головой

На курсе нам предлагалось реализовать различные структуры данных с нуля, используя основные их операции. Например, двоичные деревья поиска (BST) в C++ с операциями вставки, удаления, поиска, обхода с предварительной выборкой, обхода с отложенной выборкой и обхода с порядковой выборкой. Приходилось создавать класс BST и реализовывать все эти операции в виде функций. Предлагалось даже сравнивать время выполнения определённых операций с различными размерами наборов данных. Это был отличный опыт. Я многому научился благодаря этим занятиям и стал лучше разбираться в операциях. Такой учебный процесс с практическими заданиями помог мне лучше понять концепцию алгоритмов.

Можно начать программировать с языков, поддерживающих ООП. Это легко с очень простыми в освоении языками:

• C++
• Java
• Python

Для новичков один из этих языков будет в самый раз.

Ресурсы для обучения

Онлайн-курсы

Можно заниматься дистанционно на:

1. Coursera: специализация «Алгоритмы», специализация «Структуры данных и алгоритмы», «Алгоритмы, часть I», «Алгоритмы, часть II».
2. MIT Open Courseware: «Введение в алгоритмы».
3. Академия Хана: «Алгоритмы».
4. Udacity: «Введение в алгоритмы», «Введение в структуры данных и алгоритмы», «Структуры данных и алгоритмы», «Введение в алгоритмы для студентов», «Вычислимость, сложность и алгоритмы».
5. edX: «Алгоритмы: дизайн и анализ, часть 1», «Алгоритмы: дизайн и анализ, часть 2», «Алгоритмы и структуры данных», «Алгоритмы: дизайн и техники», «Алгоритмы: дизайн и анализ», «Графовые алгоритмы».

и многие другие платформы. Для лучшего понимания можно попробовать приведённые там упражнения.

Средства интерактивной визуализации алгоритмов

Кроме того, можно попробовать платформы визуализации алгоритмов:

1. Визуализация структуры данных.
2. Визуализатор алгоритмов.
3. VisuAlgo.
4. Визуальное отображение алгоритмов сортировки| Toptal.
5. Анимированные алгоритмы.
6. Визуализации и визуальное отображение алгоритма.

Они доступны в Интернете и понимают пошаговый механизм работы алгоритмов.

Упражнения на закрепление

Освоив азы, можно переходить к практическим занятиям, закрепляя пройденный материал в упражнениях. Вот платформы, на которых собраны очень хорошие задачи самых разных уровней сложности:

1. «Проект Эйлер».
2. HackerRank.
3. CodeChef.
4. Coderbyte.
5. Exercism.
6. Codewars.
7. LeetCode.

Чем больше практики, тем лучше понимание. Закрепление учебного материала в упражнениях  —  это хороший способ узнать, как изученные теории можно применить в решении задач.

Подводя итоги

Резюмируем статью списком из десяти рекомендаций для тех, кто приступает к изучению алгоритмов:

1. Начинайте с изучения основ.
2. Сформируйте чёткое понимание того, что происходит в алгоритме.
3. Прорабатывайте шаги алгоритма с примерами.
4. Обстоятельно разберитесь в анализе сложности.
5. Попробуйте самостоятельно реализовывать алгоритмы.
6. Записывайте всё важное, чтобы вернуться к этому в будущем.
7. Занимайтесь дистанционно на онлайн-курсах платформ для обучения.
8. Следите за онлайн-лекциями, опубликованными известными университетами.
9. Закрепляйте пройденный материал в упражнениях.
10. Если среди упражнений вам попались трудные задачи, не расстраивайтесь. После завершения упражнения можно будет почитать специальную инструкцию и понять, где вы застряли.

Дополнительные материалы для чтения

Если хотите узнать больше о структурах данных и алгоритмах, то можете ознакомиться со следующими статьями:

Заключение

Не забывайте о том, что путь к совершенству  —  практика!

Надеюсь, для вас эта статья была полезной и познавательной. 

Спасибо за внимание.

Читайте также:

• Алгоритмы поиска, которые должен знать каждый специалист по обработке и анализу данных
• Алгоритмы машинного обучения простым языком. Часть 1
• 10 Графовых алгоритмов

Читайте нас в Telegram, VK и Яндекс.Дзен

---

Перевод статьи Vijini Mallawaarachchi: How to be Good at Algorithms?