Последние новости

YoungCoder теперь и на Stepikе. Записывайтесь: https://vk.cc/75rISy

Чтобы записаться на курс, необходимо зарегистрироваться на Степике: https://vk.cc/75rIC4

Это моя личная ссылка-приглашение на Stepik для вас. Регистрируясь по этой ссылке, записываясь на курсы и решая задачи, Вы помогаете автору данного сайта принять участие в конкурсе платформы Stepik! Подробности конкурса здесь: https://vk.cc/75rKuS

суббота, 17 августа 2013 г.

Алгоритм. Формы записи. Отличие алгоритма от программы.

Добрый день!
Сегодня мы поговорим об алгоритмах и способах их записи.
Что такое алгоритм?

Алгоритм – порядок действий, выполнив который, исполнитель (некоторое устройство или даже человек), получит решение некоторой конкретной задачи.
К алгоритмам предъявляются ряд некоторых требований.

1.   Понятность. Алгоритм должен быть понятным, человеку или устройству, которое его будет выполнять. Вспомните инструкции к технике на китайском или корейском языке.
2.   Конечность. Алгоритм должен иметь конечное число шагов. Пусть их будет два миллиона, но мы точно знаем, что выполнив все два миллиона шагов по порядку, то обязательно получим результат.
3.   Определенность. Алгоритм должен быть точным и не допускать неоднозначности в его понимании. На каждом шаге, исполнитель должен точно знать, какой шаг ему делать следующим, а не додумывать или предполагать.

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

Задача:  Дан массив целых чисел. Найти минимальный элемент в массиве.
Идея решения: Сравнить между собой все элементы и найти минимальный.

Алгоритм: (словесное описание)
1.   Принимаем в качестве минимального первый элемент предложенного массива.
2.   Начиная со второго, последовательно сравниваем каждый элемент с минимальным значением, пока не достигнем конца массива.
2.1. Если текущий элемент меньше минимального, принимаем его значение в качестве минимума.
2.2. В противном случае, переходим к следующей итерации.

Теперь представим блок-схему данного алгоритма. Имеем массив чисел arr[N], N – длина массива.

Рис 1. Блок-схема алгоритма поиска  

 

Все эти квадратики, кружочки и ромбики это не моя прихоть, а специальные обозначения. Существует даже специальный государственный документ, который определяет наклон линий, размеры этих фигур, подписи и т.д. (кому интересно поищите стандарт ЕСПД).  Я уже давно не занимался этим, и стандарты давно не читал, поэтому в тонкостях могу и ошибаться, но общий вид блок схемы правильный. К тому же соблюдать эти стандарты требуется только в официальной документации, студентов обычно не просят делать этого. Быть может, я еще подробнее остановлюсь на составлении блок-схем к алгоритмам, но пока рассмотрим основные элементы. 
Скругленные квадраты в начале и в конце обозначают начало и конец программы.
Овал – ввод или вывод данных.
В прямоугольнике записывают вычисления и присвоения.
Ромб – это условие, буквально оператор if-else. Из него две ветви одна выполняется, когда условие истинно, другая - когда ложно.
Шестигранник используется для обозначения цикл со счетчиком, хотя это и так понятно. После окончания цикла выполняется правая веточка этого значка (хотя я встречал и другие способы записи циклов).

Запись алгоритма на псевдокоде.
Вы можете встретить различные виды псевдокода, синтаксис некоторых может быть похож на синтаксис языка программирования Pascal. Я привожу здесь тот, что используется в задания типа ЕГЭ. 

Листинг 1.
АЛГ
НАЧ
ЦЕЛ N, min;
МАССИВ arr[N];
ЦЕЛ i;
min = arr[0];
НЦ  (i=0;i < N;i++)  
                 ЕСЛИ (arr[i]<min)  
                 ТО min=arr[i];
КЦ
ВЫВОД min;
КОН

Листинг 2.
#include <stdio.h>
int main(){
      int min, arr[11]={5,14,7,4,11,2,6,12,8,7,3};
      min = arr[0];
      for (int i=1; i<11; i++){
            if (arr[i]<min)
                  min = arr[i];
      }
      printf("%d\n", min);
return(0);
}

Не правда ли очень похоже? 

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

1 комментарий :

Примечание. Отправлять комментарии могут только участники этого блога.