Алгоритм. Свойства алгоритмов. Блок-схемы. Алгоритмические языки

.4. Линейный алгоритм

В основе линейных алгоритмов лежит структура «последовательность». Покажем это на примерах.

Пример 12.6

В своей книге «Арифметика» Леонтий Филиппович Магницкий привел следующий способ отгадывания задуманного двузначного числа: «Если кто задумает двузначное число, то ты скажи ему, чтобы он увеличил число десятков задуманного числа в 2 раза, к произведению прибавил бы 5 единиц, полученную сумму увеличил в 5 раз и к новому произведению прибавил сумму 10 единиц и числа единиц задуманного числа, а результат произведенных действий сообщил бы тебе. Если ты из указанного тебе результата вычтешь 35, то узнаешь задуманное число».

Представим предлагаемые JI. Ф. Магницким действия в виде алгоритма в словесной форме. В предлагаемом процессе должны участвовать два человека: загадывающий число и отгадывающий его. Поэтому алгоритмов тоже будет два.

Алгоритм для загадывающего число

1. Задумайте двузначное число.
2. Умножьте число десятков на 2.
3. К полученному произведению прибавьте 5.
4. Полученную сумму умножьте на 5.
5. К полученному произведению прибавьте 10.
6. К полученной сумме добавьте количество единиц задуманного числа.
7. Сообщите полученное число отгадывающему. Конец алгоритма

Алгоритм для отгадывающего число

1. Отнимите от сообщенного числа 35.
2. Сообщите результат. Конец алгоритма

В этих двух алгоритмах действия выполняются в том порядке, в котором записаны.

Пример 12.7

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

Для исходных данных алгоритма будем использовать следующие обозначения:
п — норма расхода продукта на человека в сутки;
k — количество участников похода;
d — количество дней.

Результат работы алгоритма (рассчитанный вес продукта) будет занесен в переменную m (рисунок 12.6).

Рис. 12.6. Алгоритм решения задачи «Вес продукта» в двух формах представления: в виде блок-схемы и в виде программы на школьном алгоритмическом языке

Приведенные ранее в п. 12.3 алгоритмы разведения костра, приготовления каши, измерения расстояния до предмета являются линейными или последовательными.

    Линейный алгоритм — алгоритм, в котором действия выполняются последовательно одно за другим.

.5. Разветвляющийся алгоритм

Вспомним сюжет из русской сказки. Царевич останавливается у развилки дороги и видит камень с надписью: «Пойдешь направо — коня потеряешь, налево — сам пропадешь…»

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

Здесь условиями, позволяющими делать выводы или влияющими на принятие решений, являются слова, расположенные между «если» и «то»:
– в первом примере — красный закат;
– во втором примере — дым;
– в третьем примере — окончание работы;
– в четвертом примере — муравейник.

Условие может принимать значение «истина», когда оно выполнено, или «ложь», когда оно не выполнено. От значения условия зависит наше дальнейшее поведение. Например, в предложении «Если закат красный, то ‘жди ветреной погоды» условие «закат красный» может быть или истинным, или ложным. Если условие истинно, то следует ждать ветреной погоды, иначе (если условие ложно) ничего о погоде сказать нельзя.

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

Рассмотрим примеры алгоритмов, содержащих анализ условия.

Пример 12.8

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

Алгоритм проверки можно записать так:

Если гриб съедобный, то положить его в котелок для варки, иначе — выбросить в костер.

В приведенной записи в зависимости от значения условия выполняется либо действие, указанное после слова «то» — положить гриб в котелок, либо другое действие, указанное после слова «иначе» — выбросить в костер. На рисунке 12.7 представлен фрагмент блок-схемы алгоритма сортировки грибов для варки супа по признаку съедобный-несъедобный.

Рис. 12.7. Алгоритм проверки грибов, в котором использована полная форма ветвления

Пример 12.9

Вы идете в гости и вам необходимо перевязать коробку с подарком красивой лентой, длина которой d. Но хватит ли этой ленты?

Представим решение этой задачи на школьном алгоритмическом языке. Исходными данными для решения этой задачи являются размеры коробки и длина ленточки. Примем для них следующие обозначения: а, b, с — соответственно длина, ширина и высота коробки; d — длина ленточки.

алг Подарок

нач вещ a,b,c,d
вывод “Введите размеры коробки” ввод а,b,с
вывод “Введите размеры ленты” ввод d
если (a b 2*c)*2 <= d то
вывод “Ленты хватит” иначе
вывод “Ленты не хватит” все кон

В примерах 12.8 и 12.9 при описании алгоритмов в виде блок- схемы и программы на школьном алгоритмическом языке использовалась конструкция «ветвление».

Различают полную и неполную форму ветвления.

При полной форме ветвления действия выполняются в обоих случаях: и при истинности, и при ложности условия. Вспомните кота из сказки А. С. Пушкина: «идет направо — песнь заводит, налево — сказку говорит ». В рассмотренных выше примерах использовалась полная форма ветвления, которой соответствует выражение
если <условие>, то <действие 1>9 иначе <действие 2>.

Неполной форме ветвления соответствует выражение
если <условие>9 то <действия>

Неполная форма предполагает отсутствие действий в случае невыполнения условия. Например: среднесуточная температура воздуха ниже 8 °С, приступить к протапливанию помещений.

На рисунке 12.8 представлен фрагмент блок-схемы алгоритма, описывающего поведение участников туристского похода, покидающих стоянку: если костер горит, то необходимо залить его водой.

Рис. 12.8. Алгоритм тушения костра, в котором используется неполная форма ветвления

Пример 12.10

Известно, что в аэропорту существуют ограничения на бесплатный провоз багажа. Если вес багажа превышает норму, то за каждый килограмм сверх нормы необходимо доплачивать. Исходными данными для решения задачи являются: v — вес багажа; vn — разрешенная норма провоза багажа; st — стоимость килограмма сверх нормы. Результат будем записывать в переменную s — сумму выплат сверх нормы.

Алгоритм «Доплата за багаж» представим на школьном алгоритмическом языке.

алг Доплата за багаж

нач вещ v, vn, st, s
вывод “введите вес багажа, норму, стоимость кг”
ввод v, vn, st
если v>vn
то s:=(v-vn)*st
вывод “Доплата составляет”, s
все
кон

На приведенных выше блок- схемах хорошо видны подобные развилки. Они создаются при помощи структуры ветвления, имеющей полную и неполную форму. Подобные алгоритмы называются разветвляющимися.

    Разветвляющийся алгоритм — алгоритм, содержащий структуру ветвления.

.6. Циклический алгоритм

Общее представление

Многие процессы в окружающем мире основаны на многократном повторении одной и той же последовательности действий.

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

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

Циклические алгоритмы могут содержать разные типы циклов. Классификация типов циклов представлена на рисунке 12.9 и подробно рассмотрена далее.

    Циклический алгоритм — алгоритм, содержащий типовую конструкцию «цикл».    Тело цикла — описание действий, повторяющихся в цикле.

Рис. 12.9. Типы циклов

Цикл с известным числом повторений

Цикл с известным числом повторений часто называют «циклом ДЛЯ». Рассмотрим примеры циклических алгоритмов с известным числом повторений.

Пример 12.11

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

Алгоритм «Упражнение для глаз»

1. Возьмите карандаш.
2. Установите его в исходное положение у кончика носа.
3. Повторите 10 раз, следя за движением карандаша:
a. Переместите карандаш на расстояние вытянутой руки;
b. Верните карандаш в исходное положение.
4. Положите карандаш. Конец алгоритма

В этом примере заранее известно число повторений. Цикл закончится, когда действия пунктов а и b повторятся 10 раз. Действия а и Ь, повторяющиеся в цикле, определяют тело цикла.

Пример 12.12

Требуется подвести итоги контрольной работы.

Исходными данными для этой задачи являются:b — балл теущего ученика;
n — количество учеников.

Расчетные данные:s — сумма баллов;
sr — средний балл.

Решение этой задачи представим на школьном алгоритмическом языке в таблице 12.3.

Таблица 12.3. Алгоритм «Итоги» на школьном алгоритмическом языке

Здесь нц, кц — служебные слова, обозначающие соответстенно начало и конец цикла.

В этом примере повторяются следующие операции:
♦ ввод оценки каждого ученика;
♦ добавление ее к общей сумме.

Эти операции составляют тело цикла. Число повторений в цикле равно количеству учащихся в классе.

Цикл с постусловием

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

Цикл с неизвестным числом повторений, в котором выход из цикла осуществляется при выполнении условия, принято называть «циклом с постусловием» или «циклом ПРИ».

Рассмотрим алгоритмы решения циклических задач с неизвестным числом повторений.

Пример 12.13

После соревнований по бегу рекомендуется измерить пульс. Измерение пульса можно описать следующим алгоритмом.

Алгоритм «Пульс»

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

Рис. 12.10. Блок-схема алгоритма «Пульс»

Пример 12.14

Требуется рассчитать время работы батарейки в часах с кукушкой, если известно, что заряда хватает примерно на 1000 звуковых сигналов «ку-ку». Однократный звуковой сигнал звучит, когда минутная стрелка показывает 30 минут. Начало каждого часа сопровождается повторением сигнала столько раз, сколько показывает часовая стрелка (от 1 до 12).

Расчетными данными для этой задачи являются:
t — обозначение текущего часа;
к — количество звуковых сигналов.

Алгоритм «Кукушка» представим на школьном алгоритмическом языке в таблице 12.4.

В этом алгоритме повторяются следующие действия:
♦ определение значения текущего часа;
♦ определение количества звуковых сигналов.

Эти действия составляют тело-цикла.

Цикл заканчивается, если количество поданных звуковых сигналов превысило 1000, что является признаком выработки ресурса батарейки.

Таблица 12.4. Алгоритм «Кукушка» на школьном алгоритмическом языке

Из рассмотренных примеров 12.13 и 12.14 видно, что цикл с постусловием имеет следующие особенности:
♦ проверка условия осуществляется в конце цикла, поэтому тело цикла выполняется хотя бы один раз;
♦ цикл заканчивается по выполнению условия.

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

Рассмотрим другой тип цикла, в котором проверка условия осуществляется в начале цикла. Для организации циклической последовательности действий и выхода из нее к другому фрагменту алгоритма используется условие, которое ставится в начале тела цикла. Цикл с неизвестным числом повторений, в котором цикл продолжается, пока выполняется условие, принято называть «циклом с предусловием» или «циклом ПОКА».

Пример 12.15

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

Алгоритм «Бочка»

1. Подойдите к бочке.
2. Если бочка неполная (есть место для воды), то перейдите к п. 3, иначе конец алгоритма.
3. Наберите ведро воды.
4. Вылейте ведро в бочку.
5. Перейдите к п. 2. Конец алгоритма

На блок-схеме (рис. 12.11) видно, что условие проверки стоит в самом начале цикла.

Рис. 12.11. Блок-схема алгоритма «Бочка»

Такой цикл получил название цикла с предусловием.

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

Пример 12.16

Требуется проверить число на симметричность (примеры симметричных чисел: 12321, 8668).

Исходными данными для этой задачи является введенное число n.

Для промежуточных вычислений будут использоваться переменные:
s — для записи цифр числа п в обратном порядке;
nl — для дублирования введенного числа п.

В алгоритме используются функции:
mod — вычисление остатка от деления на 10;
div — определение целой части числа.

Решение этой задачи представим в виде программы на школьном алгоритмическом языке в таблице 12.5.

Таблица 12.5. Алгоритм «Симметричное число» на школьном алгоритмическом языке

В этом алгоритме в цикле получается перевернутое число, которое затем сравнивается с введенным. Если они равны, то введенное число симметрично. Цикл выполняется до тех пор, пока nl при целочисленном делении на 10 не превратится в 0. Если введенное число равно 0, то цикл не выполнится ни разу, но будет выдан ответ «Число симметричное».

Из рассмотренных примеров 12.15 и 12.16 видно, что цикл с предусловием имеет следующие особенности.

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

Select caseвыражение для сравнения

   CASEусловие 1

      Группа операторов 1

  CASE условие 2

      Группа операторов 2

………….

   ELSE CASE

      Группа операторов  N

END SELECT

– если  условие 1 – истина, то выполняется блок операторов 1 и
осуществляется переход на строку программы, следующую за 
END SELECT; если условие 2 – истина,
то выполняется блок операторов 2  и осуществляется переход на
строку программы, следующую за   END SELECT
и т. д., если все условия – ложь, то выполняется блок
операторов   N  и осуществляется
переход на строку программы, следующую за 
END SELECT.

 DO 
WHILE   условие                     
   DO                                 
               WHILE 
условие

Группа операторов                         
  Группа операторов                 
   Группа операторов

LOOP                                         
           LOOP
WHILE  условие      
        WEND

– выполняет группу операторов, пока условие – истина
(такие циклы называются циклами “ПОКА”).

DO UNTIL условие                                 
DO

Группа операторов                               
  Группа операторов

LOOP                                                          LOOP
UNTILусловие

– выполняет группу операторов до выполнения
условия (такие циклы называются циклами “ДО”).

FOR Параметр=Начальное
значение TO
 Конечное значениеSTEP шаг

Группа операторов

NEXTПараметр

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

SUBИмя (формальные параметры)

  Группа операторов

END SUB

–  содержит группу операторов – процедуру; обращение к
процедуре выполняется оператором САLL.
К одной и той же процедуре можно обращаться многократно, задавая
при этом различные фактические параметры.

В
начало темы

Графический способ записи алгоритмов

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

Такое графическое представление называется схемой алгоритма или блок-схемой. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа.

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

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

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

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

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

Блок Пуск-останов используется для обозначения начала, конца, прерывания процесса обработки данных или выполнения программы.

Блок Документ предназначен для ввода-вывода данных, носителем которых служит бумага.

Действие

Для начала рассмотрим “действие” и попробуем найти причину, обеспечивающую возможность использования существующего “действия” для создания нового алгоритма.

Этой причиной является возможность повторного использования “действия” с получением тождественного результата. Только тогда разработанный с использованием этого “действия” алгоритм решения некоторой задачи будет одинаково решать эту задачу снова и снова. Мы нащупали важные законы нашего мира, в котором:

Какие признаки “действия” кроме повторимости делают возможным его использование в создании алгоритма? Что является терминальным неделимым “действием”? Чтобы ответить на этот вопрос стоит рассмотреть разные примеры “действий” из нашего опыта. Программисты встречали их много раз.

Рассмотрим, что происходит при выполнении “действия”. Например, во время падения яблока с ветки яблони на землю. В этом процессе происходит несколько изменений. Если вспомнить школьную физику и рассмотреть ситуацию в системе отсчета, привязанной к Земле, то сила гравитации вызывает изменение скорости яблока, разгоняя его. При этом в процессе отмечается еще одно важное изменение — уменьшается расстояние между яблоком и Землей.

В рамках примера процесса “Земля-Яблоко” можно отметить у “действия” следующие признаки:

Рассмотрим с этими признаками разные области и процессы, выделяя в них примеры “действий” и контролируя особенности указанных признаков в описании структуры “действия”.

Контрольные вопросы и задания

К заданию 8.1

1. Разработчик алгоритма к заданию 8.1 (рис. 8.1), введя переменную п, хотел придать алгоритму свойство массовости. Какие еще переменные следует ввести, чтобы алгоритм соответствовал этому свойству в полной мере?
2. В приведенном последовательном алгоритме порядок вывода расчетных данных можно изменять.

Какие команды в приведенных программах нельзя переставлять? Почему?
3. На блок-схеме представлены два блока вывода информации на экран. В чем их различие?
4. Запишите в тетради имена переменных, которые были использованы в процессе решения задания.

Напишите под ними значения переменных, полученные в результате тестирования.
5. Что происходит в результате выполнения блока 3 представленного алгоритма?
6. Добавьте в программу блок вычислений, определяющий, сколько экспонатов в день удастся посмотреть посетителю.

К заданию 8.2

1. Замените в программе формулу расчета катета b = a-j3 и убедитесь, что результат от этого не изменится.
2. Используя готовый каркас блок-схемы, заполните его таким образом, чтобы по новой блок-схеме вычислялись высота и площадь равнобедренной трапеции с углом при основании 45° (рис. 8.5).

Задание выполните в тетради.
3. Напишите текст программы на Кумире или другом языке для полученной блок-схемы.
4. Что надо изменить в условии задачи, чтобы расширить границы применимости алгоритма?
5. Из пояснительного рисунка видно, что а > b. Что произойдет, если при вводе а и b это соотношение будет нарушено?

К заданию 8.3

1. При расчетах радиуса и объемов используется константа 3,1415926. Что нужно изменить в программе, чтобы не набирать ее каждый раз заново?
2. В примере программы на языке Кумир тип используемых переменных описан следующим образом: вещ r, s, vshara, veil, k.

Что означает эта запись? Почему для переменных выбран такой тип?
3. В формуле вычисления объема шара используется формула V — r3. В примерах программ на разных языках она записана по-разному. Есть ли здесь ошибки? Объясните, что означают разные записи? Придумайте такой вид записи, который будет верен для всех языков.

Рис. 8.5. Чертеж для вычисления высоты и площади равнобедренной трапеции

4. Можно ли изменить последовательность операторов расчета?

Общие функции оценки сложности

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

1. C – константа (время выполнения алгоритма не зависит от входных параметров, линейные алгоритмы)
2. log(log(N))
3. log(N) – (поиск в сортированном массиве)
4. N^C, 0<C<1
5. N – линейная сложность (поиск в не сортированном массиве)
6. N*log(N)
7. N^C, C>1
8. C^N, C>1
9. N!

Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько этих функций, то уравнение можно сократить до функции, расположенной ниже в таблице. Например, O(log(N) N!)=O(N!).

Если алгоритм вызывается редко и для небольших объёмов данных, то приемлемой можно считать сложность O(N2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).

Обычно алгоритмы со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью NC можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями CN и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.

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

Википедия: Временная сложность алгоритма

Понятие алгоритма

Одним из фундаментальных понятий в информатике является понятие алгоритма. Происхождение самого термина «алгоритм» связано с математикой. Это слово происходит от Algorithmi — латинского написания имени Мухаммеда альХорезми (787 — 850), выдающегося математика средневекового Востока. В XII в. был выполнен латинский перевод его математического трактата, из которого европейцы узнали о десятичной позиционной системе счисления и правилах арифметики многозначных чисел.

В наше время понятие алгоритма трактуется шире. Алгоритм — это последовательность команд управления каким-либо исполнителем.

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

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

В разделе информатики под названием Программирование изучаются методы программного управления работой ЭВМ. Следовательно, в качестве исполнителя выступает компьютер.

Компьютер работает с величинами — различными информационными объектами: числами, символами, кодами и т.п. Поэтому алгоритмы, предназначенные для управления компьютером, принято называть алгоритмами работы с величинами.

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

Например, при решении квадратного уравнения ах2 Ьх с = 0
исходными данными являются коэффициенты а, Ь, с; результатами — корни уравнения х1, х2; промежуточным данным — дискриминант уравнения D = b2 – 4ас.

Для успешного освоения программирования необходимо усвоить следующее правило: всякая величина занимает свое определенное место в памяти ЭВМ (иногда говорят — ячейку памяти). Хотя термин «ячейка» с точки зрения архитектуры современных ЭВМ несколько устарел, однако в учебных целях его удобно использовать.

У всякой величины имеются три основных свойства: имя, значение и тип (на самом деле многие современные языки, такие как PHP или JS, обходятся без явного указания типа, интерпретируя тип переменной в зависимости от контекста операции).

На уровне команд процессора величина идентифицируется при помощи адреса ячейки памяти, в которой она хранится. В алгоритмах и языках программирования величины делятся на константы и переменные. Константа — неизменная величина, и в алгоритме она представляется собственным значением, например: 15, 34.

7, k, true и т.д. Переменные величины могут изменять свои значения в ходе выполнения программы и представляются символическими именами — идентификаторами, например: X, S2, cod15. Любая константа, как и переменная, занимает ячейку памяти, а значение этих величин определяется двоичным кодом в этой ячейке.

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

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

Типы констант определяются по контексту (т.е. по форме записи в тексте), а типы переменных устанавливаются в описаниях переменных (не во всех языках; Python, например, не имеет явного определения типа, тип переменной определяетя при первом присваивании).

Есть еще один вариант классификации данных — классификация по структуре. Данные делятся на простые и структурированные. Для простых величин (их еще называют скалярными) справедливо утверждение: одна величина — одно значение, для структурированных: одна величина — множество значений. К структурированным величинам относятся массивы, строки, множества и т.д.

Проблема

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

В результате программированию учишься по наитию. Лишь немного в этом труде помогают сборники алгоритмов, прикладных техник и шаблонов проектирования. Общая совокупность предлагаемых ими рецептов выстраивается длинным списком, и его длина грозит каждому из прочитанных приемов быть позабытым (как была забыта 53-яя личная группа в “телеге” до введения разбиения по каталогам).

Почему конкретный прием был успешен в задаче-образце? Будет ли он успешен в твоём проекте? Какие признаки проекта дают понять, что использование приёма уместно?

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

Ну, например, объяснение вреда использования метода “Copy-Paste” для развития кода. Если такие правила получится объяснить малым набором причин, их сформировавшим, то это объяснение обеспечит их запоминание и последующее использование в практике, тем самым поможет уклониться от бесчисленных грабель, разложенных тут и там.

Для компактного и полезного набора объяснений нужно:

Если обобщить, то нужны алгоритмы для написания и развития алгоритмов.

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

Стандартная структура алгоритма

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

Общий вид записи алгоритма на учебном алгоритмическом языке:

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

В следующих строках конкретизируют, какие именно переменные являются аргументами алгоритма (входными данными), а какие — его результатами (выходными данными). Для этого после служебного слова арг приводится список имен переменных–аргументов; в следующей строке после служебного слова рез приводится список имен переменных–результатов.

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

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

В первом примере алгоритм имеет название Объем_шара, один вещественный аргумент Радиус и один вещественный результат Объем. Во втором примере алгоритм под названием Choice имеет три аргумента — целые M и N и логический b, а также два результата — вещественные Var1 и Var2.

Пример алгоритма вычисления гипотенузы прямоугольного треугольника:

На вход алгоритму даются два вещественных аргумента a и b (величины катетов), результатом является вещественная переменная с (гипотенуза). Для ее расчета используется функция вычисления квадратного корня sqrt.

Строковые функции и функции
преобразования типов

 Здесь Х$ –
любая текстовая константа, переменная или выражение;
N, K,
X – числовые константы, переменные или
выражения.

Формальные исполнители алгоритма

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

Программы на языке произвольного формального исполнителя могут состоять только из элементарных команд, которые входят в его систему (которые исполнитель «понимает»).

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

■ Пример 2. Исполнитель Крот имеет следующую систему команд:

1. вперед k — продвижение на указанное число шагов вперед;
2. поворот s — поворот на s градусов по часовой стрелке;
3. повторить m [команда1 … командаN] — повторить m раз серию указанных команд.

Какой след оставит за собой исполнитель после выполнения следующей последовательности команд?

Повторить 5 [вперед 10 поворот 72]

Решение. Команда вынуждает исполнителя 5 раз повторить набор действий: пройти 10 шагов вперед и повернуть на 72° по часовой стрелке. Так как поворот происходит на один и тот же угол, то за весь путь исполнитель повернет на 5 х 72° = 360°. Поскольку все отрезки пути одинаковой длины и сумма внешних углов любого многоугольника составляет 360°, то в результате будет оставлен след в форме правильного пятиугольника со стороной в 10 шагов исполнителя.

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

■ Пример 3.  В системе команд предыдущего исполнителя Крот сформировать алгоритм вычерчивания пятиступенчатой лестницы (длина ступеньки — 10 шагов исполнителя).

Решение. За каждый шаг цикла должно происходить 4 действия: движение вперед на 10 шагов исполнителя, поворот на 90° по часовой стрелке, еще 10 шагов вперед и поворот на 90° против часовой стрелки (= 270° по часовой). В результате за один шаг цикла формируется ломаная из двух отрезков длиной 10 под прямым углом. За пять таких шагов сформируется 5–ступенчатая лестница (ломаная будет содержать 10 звеньев).

Повторить 5 [вперед 10 поворот 90 вперед 10 поворот 270]

Операторы вывода
данных

PRINTсписок вывода – служит для вывода
текстовых и числовых  данных на экран. Список для вывода
может включать в себя константы, переменные и выражения.

Константы выводятся без изменений, вместо переменных и выражений
печатаются их текущие значения. Совместно с
PRINT  удобно использовать операторы
LOCATE  COLOR. Например:

COLOR 2

LOCATE 15, 35

PRINT  “Сила =”;
F; “H”

В результате выполнения программы в центре экрана зелёным цветом
будет выведено:

 Сила = 129.81 H

BEEP- выводит звуковой сигнал.

SOUND частота, длительность – выводит звуковой сигнал
заданной длительности и частоты.

PLAY”символьное
выражение” – позволяет
создавать музыкальные фрагменты (см. справку  Qbasic).

SCREENномер- включает графический режим. Допустимые номера
режимов 1,2,8,9,12. Наилучшее качество изображения (640*480
пикселей, 16 цветов) обеспечивает  12 режим.

CLS- очищает экран.

LINE(x1,
y1)-(x2,
y2),цвет – рисует линию от точки Х1,У1 до Х2,У2 указанным
цветом.

LINE (x1,y1)-(x2,y2), цвет, b- рисует рамку с углами в точках Х1,У1 и Х2,У2 указанным
цветом.

LINE (x1,
y1)-(x2,y2), цвет, bf- рисует закрашенный прямоугольник.

PSET (x,
y),
цвет – устанавливает точку.

CIRCLE (x,
y),
радиус, цвет
– рисует окружность с центром в точке Х,У указанного цвета и
радиуса.

PAINT (x,y),
c1,c2 – выполняет заливку
начиная с точки Х,У цветом С1. Заливка ограничивается линией
цвета С2.

DRAW”символьное
выражение” – позволяет
создавать сложные рисунки (см. справку 
Qbasic).