Линейная программа — это такая программа, в которой операторы выполняются последовательно один за другим в том порядке, в каком они записаны в программе.
Операторы для разработки линейных программ
Прежде чем составлять программу на алгоритмическом языке QBasic необходимо очень хорошо представлять структуру оператора или, как принято говорить, знать формат оператора. При описании формата обычно соблюдаются следующие правила:
- — ключевые слова QBasic пишутся так, как это указано в формате;
- — после ключевого слова обязательно ставится пробел, для того чтобы отделить его от другого ключевого слова или параметра;
- — квадратные скобки в формате показывают, что то, что находится внутри них, можно не писать, например, запись: [LET] означает, что ключевое слово LET можно не набирать на клавиатуре;
- — фигурные скобки <> указывают, на какой либо выбор, например запись означает, что можно выбрать либо запятую, либо точку с запятой;
— многоточие типа: . . означает повтор
Линейные программы
вышеприведенной конструкции оператора;
- — набранный курсивом текст показывает, что задается параметр, который должен быть определен (задан) пользователем в зависимости от решаемой задачи. Иногда параметр состоит из нескольких слов, которые специально соединены знаком подчеркивания. Соединение нескольких слов означает, что отдельные слова, поясняющие смысл параметра, образуют один параметр или объект, например, список_ переменных.
- -форматы, операторов, которые будут описаны ниже, приведены в упрощенном виде, что сделано исключительно в учебных целях. Полное описание формата в системе QBasic легко получит, если воспользоваться помощью ( кл. F1).
Оператор LET
Формат оператора:
[LET] переменная = выражение переменная-любая числовая простая переменная или переменная массива, которой присваивается значение выражения; выражение — любое числовое выражение, значение которого будет присвоено переменной. Под выражением мы будем понимать совокупность, функций, переменных, констант, соединенных знаками арифметических действий.
Назначение оператора: вычисление выражения и присвоение переменной значения выражения.
Работа оператора: яри выполнении оператора LET компьютер сначала выполняет правую часть оператора, т.е. вычисляет выражение. Полученное число присваивается переменной. Физически это означает, что число записывается в одну из ячеек памяти компьютера. Такая ячейка имеет имя переменная. Не следует забывать, что число в ячейке хранится в двоичном коде.
Рассмотрим ряд примеров записи оператора:
-переменной х присваивается значение 8;
-сначала вычисляется выражение, т.е. число 8 складывается с числом 12, получается число 20. Затем полученный результат выражения записывается в ячейку с именем хх (в двоичном коде).
Особенности записи оператора LET: как видно из описания формата ключевое слово LET можно не писать, например,
Линейные программы, Python
Такая запись предпочтительней, т.к. на набор оператора затрачивается меньше времени.
Источник: ozlib.com
Линейный алгоритм. Понятие и особенности. Блок-схема
Каждый человек на протяжении своей жизни решает множество задач разной сложности. Но даже самые простые из задач выполняются последовательно, то есть за несколько шагов. Эту последовательность можно назвать алгоритмом. Последовательности бывают разные, но начинать их изучение лучше всего с линейных.
Прежде чем приступить к рассмотрению основной темы статьи, следует сделать краткое отступление и сказать несколько слов про алгоритмический язык.
Алгоритмический язык
Представьте, что человеку, работающему за компьютером, поставлена некая вычислительная задача. В языке программирования решение этой задачи выполняется с помощью алгоритмизации. Решение предполагает: — разбиение на этапы;
— составление программы решения на алгоритмическом языке;
— отладку программы (возможны ошибки — их надо исправить);
— выполнение на ПК;
Алгоритмический язык является средством описания алгоритмов, а уже алгоритм, в свою очередь, представляет собой чёткое описание определённой последовательности действий , направленных на решение необходимой задачи.
Свойства алгоритма
— конечность . Любой алгоритм должен быть завершённым, а окончание наступает после выполнения определённого числа шагов;
— однозначность , понятность. Не допускается разных толкований, неопределённости и двусмысленности — всё должно быть чётко и ясно, а также понятно исполнителю — и правила выполнения действий линейного алгоритма, и сами действия;
— результативность . Итог работы — результат, полученный за конечное число шагов;
— универсальность , массовость. Качественный алгоритм способен решать не одну задачу, а целый класс задач, имеющих схожую постановку/структуру.
Линейная структура
Любой алгоритм составляется из ряда базовых структур. Простейшей базовой структурой является следование — структура с линейными характеристиками. Из этого можно сформулировать определение.
Линейный алгоритм — это алгоритм, образуемый командами, которые выполняются однократно и именно в той последовательности, в которой записаны. Линейная структура, по сути, проста. Записать её можно как в текстовой, так и в графической форме.
Представим, что у нас стоит задача пропылесосить ковёр в комнате. В текстовой форме алгоритм будет следующим:
— принести пылесос к месту уборки;
И каждый раз, когда нам надо будет пылесосить, мы будем выполнять один и тот же алгоритм.
Теперь поговорим про графическую форму представления.
Блок-схема
Для изображения алгоритма графически используют блок-схемы. Они представляют собой геометрические фигуры (блоки), соединённые стрелками. Стрелки показывают связь между этапами и последовательность их выполнения. Каждый блок сопровождается надписью.
Рассмотрим фигуры, которые используются при визуализации типичной линейной последовательности.
Блок начала-конца :
Блок ввода-вывода данных (отображает список вводимых и выводимых переменных):
Арифметический блок (отображает арифметическую операцию/группу операций):
Условный блок (позволяет описать условие). Алгоритмы с таким блоком используются при графической визуализации алгоритмов с ветвлением:
Условного блока нет в классическом линейном алгоритме, так как в нём, как уже было сказано ранее, все операции выполняются последовательно, то есть одна за другой. В линейном алгоритме размещение блоков выглядит следующим образом:
А вот, как решается задача по нахождению площади треугольника по формуле Герона. Здесь a, b, c – это длины сторон, S – площадь треугольника, P – периметр.
Следует обратить внимание, что запись «=» — это не математическое равенство, а операция присваивания . В результате этой операции переменная, стоящая слева от оператора, получает значение, которое указано справа. Значение не обязательно должно быть сразу определено (a = 3) — оно может вычисляться посредством выражения (a = b + z), где b = 1, a z = 2.
Примеры линейных алгоритмов
Если рассмотреть примеры решения на языке Pascal (именно этот язык до сих пор используется для изучения основ алгоритмизации и программирования), то можно увидеть следующую картину:
И, соответственно, блок-схема программы линейной структуры будет выглядеть следующим образом:
Как составить программу линейной структуры?
Порядок следующий: — определите, что именно относится к исходным данными, а также каков типы/класс этих данных, выберите имена переменных; — определите, каков тип данных будет у искомого результата, выберите название переменных (переменной); — определите, какие математические формулы связывают результат и исходные данные; — если требуется наличие промежуточных данных, определите класс/типы этих данных и выберите имена; — опишите все используемые переменные; — запишите окончательный алгоритм. Он должен включать в себя ввод данных, вычисления, вывод результатов.
На этом всё, в следующий раз рассмотрим на примерах программу разветвлённой структуры. Если же вас интересует тема алгоритмизации в контексте разработки программного обеспечения, ждём вас на профессиональном курсе OTUS!
Как работает пирамидальная сортировка выбором? Разберемся в этом 20 июля на открытом уроке в OTUS с Евгением Волосатовым, программистом с 20-летним опытом. Сортировка выбором — один из самых простых алгоритмов сортировки. Ее можно значительно ускорить, если использовать структуру данных «куча» для поиска максимального элемента за О(1) константное время.
В результате получится алгоритм пирамидальной сортировки HeapSort. На этом открытом уроке мы расскажем идею алгоритма и наглядно продемонстрируем его работу на визуальных примерах с конкретными числами. Вебинар пройдет в рамках онлайн-курса «Алгоритмы и структуры данных» и позволит познакомиться с преподавателем.
Источник: dzen.ru
Тема 9. Создание линейных программ
Все алгоритмы можно классифицировать в соответствии со следующей схемой:
В программе по линейному алгоритму команды выполняются в порядке их естественного следования в программе, нет возвратов на предыдущие команды и никакие команды не могут быть пропущены.
В программе по нелинейному алгоритму возможно нарушение порядка следования команд, переход на предыдущие, уже выполненные ранее команды, пропуск некоторых команд.
Ветвленный нелинейный алгоритм- это алгоритм, в котором некоторые команды могут быть пропущены, но возврат на предыдущие невозможен.
В программе по циклическому неветвленному алгоритму есть повторения блоков команд, возвраты на предыдущие команды.
В программе по циклическому ветвленному алгоритму возможно нарушение порядка следования команд, переход на предыдущие, уже выполненные ранее команды, пропуск некоторых команд, повторения отдельных блоков команд.
Программы с линейным алгоритмом (линейные программы) наиболее просты, поэтому начнем с создания именно таких программ.
9.1 Создание линейной программы.
Рассмотрим поэтапно написание программы, например, загружающей нули во все регистры МП.
9.1.1. Составление текста программы.
В любом текстовом редакторе создадим текстовый файл программы с расширением *.asm (вполне подойдет для этой цели встроенный редактор Norton Commander, вызываемый по клавише shift+F4).
Программа в exe-формате должна содержать сегмент стека, сегмент данных и сегмент кода.
1) Определим сегмент стека. Так как наша программа невелика, следовательно, и стек в ней может быть небольшой.
_STACK SEGMENT ‘STACK’ ; объявление сегмента стека
DB 32 DUP (‘ST’) ;стек размером 64 байта (32 повторения 2-х символов ST)
_STACK ENDS ; закрываем описание сегмента стека _STACK
2) Сегмент данных для нашей программы не нужен, т.к. операндами являются регистры и константа 0.
3) Определим сегмент кода. В сегмент кода включаются команды программы на языке Ассемблер, поэтому до этого этапа необходимо изучить команды языка Ассемблера.
_CODE SEGMENT ; Объявление сегмента кода
ASSUME SS:_STACK, CS:_CODE ; Ассоциируем сегменты и сегментные регистры
OUR_PROG PROC FAR ; описываем нашу программу как процедуру
;OUR_PROG помещаем в стек такие начальные значения, чтобы
; программа могла по завершению возвратить управление вызвавшей
; ее программе (например ОС)
PUSH DS ; поместить в регистр номер блока адреса возврата
MOV AX,0 ; обнулить регистр AX
PUSH AX ; поместить в стек нулевое смещение адреса возврата
; инициализируем адрес сегмента данных
MOV AX,_DATA ;
MOV DS,AX ; загрузка через AX указателя сегмента данных в DS
m1: MOV AX,0 ; обнуляем регистры микропроцессора по порядку
MOV BX,0
MOV CX,0
MOV DX,0
MOV SI,0
MOV DI,0
MOV BP,0
OUR_PROG ENDP ; закрываем описание процедуры OUR_PROG
_CODE ENDS ; закрываем описание сегмента кода _CODE
END m1 ; закрываем описание программы
9.1.2 Трансляция.
Трансляция программы (ассемблирование) – перевод команд Ассемблера исходного текстового asm-файла в инструкцию МП. Ассемблирование программы производится транслятором MASM.EXE или TASM.EXE. Запуск транслятора выполняется стандартно для MS DOS ,для этого необходимо в командной строке MS_DOS ввести имя транслятора, а затем указать ей имя файла, под которым вы сохранили свою программу в текстовом редакторе. Например:
MASM.EXE MYPROG.ASM
После выполнения этой программы, если Вы утвердительно ответите на соответствующие запросы, в текущем каталоге будут файл листинга трансляции *.lst и файл перекрестных ссылок *.crf (это вспомогательные файлы где будут указаны ошибки и предупреждения транслятора). В случае отсутствия ошибок создается объектный файл *.obj, который будет являться исходным для дальнейшей работы по созданию программы. В случае наличия синтаксических ошибок надо ввести исправления в asm-файл и повторить трансляцию.
Источник: studfile.net