Программирование_занятие_1

изучается:

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

Основные свойства алгоритма.

Основы программирования:

формальное исполнение алгоритма,

принципы фон Неймана,

трансляция программ.

Оформление программ:

данные и команды,

переменная и присваивание,

язык блок-схем,

язык basic,

язык pascal.

Стандартный вывод данных:

перенос строк,

форматный вывод.

Стандартный ввод данных:

команды ввода,

ввод с клавиатуры.

«Алгоритм и его свойства»

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

Понятие алгоритма трудно считать определяемым.

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

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

- Организованная последовательность действий.

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

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

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

Вопросы полноты и непротиворечивости тоже остаются открытыми.

Основные свойства алгоритмов

Почему-то в учебниках не выделяется такое свойство, как:

* ДВА СПОСОБА ИСПОЛЬЗОВАНИЯ АЛГОРИТМА

- алгоритм можно 1) записать по определенным правилам 2) исполнить

В языке BASIC имеются две отдельные команды: LIST – показать текст записи программы, RUN – исполнить программу

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

Другим свойством алгоритма является:

* НАЛИЧИЕ ИСПОЛНИТЕЛЯ

- алгоритм может быть выполнен (это система команд для кого-то или чего-то)

Исполнитель может ничего не знать о цели алгоритма.

Исполнитель должен понимать отдельные команды.

Имеет место формальность исполнения алгоритма, то есть за результат отвечает составитель, а не исполнитель алгоритма.

* РЕЗУЛЬТАТИВНОСТЬ

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

* ОДНОЗНАЧНОСТЬ

- применение алгоритма к одним и тем же данным дает один и тот же результат.

Это свойство делает понятие алгоритма похожим на понятие функции.

* ДЕТЕРМИНИРОВАННОСТЬ

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

- не допускается произвола при выборе очередного шага алгоритма,

фиксируется начальный и заключительный шаги алгоритма.

Некоторые авторы наличие начала и конца считают отдельными свойствами алгоритмов.

* МАССОВОСТЬ

- алгоритм дает решение не одной, а целого набора задач.

(Например, с помощью дискриминанта, исследуются квадратные уравнения с любыми коэффициентами.)

Считаем, что к основным свойствам алгоритмов относят: * ДВА СПОСОБА ИСПОЛЬЗОВАНИЯ АЛГОРИТМА * НАЛИЧИЕ ИСПОЛНИТЕЛЯ * РЕЗУЛЬТАТИВНОСТЬ * ОДНОЗНАЧНОСТЬ * ДЕТЕРМИНИРОВАННОСТЬ * МАССОВОСТЬ

Итак, нечто, обладающее всеми перечисленными свойствами, называем алгоритмами. Но существуют ли такие объекты?

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

Основы программирования

Позабыты хлопоты, остановлен век. Вкалывают роботы, счастлив человек! (из фильма «Приключения Электроника»)

Свойство НАЛИЧИЕ ИСПОЛНИТЕЛЯ предусматривает интереснейшую возможность, когда исполнителем будет не человек.

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

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

Вопросам записи алгоритмов уделяется огромное внимание.

Выше упоминались принципы Фон-Неймана (сформулированы в 1945 г.)

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

* Однородность памяти И данные, и команды представляются одинаково. Компьютер не различает, что находится в ячейке памяти: команда, число или текст.

* Адресность Основная память состоит из пронумерованных ячеек

* Двоичность Информация кодируется двоичным числом.

Джон(Янош) фон Нейман (1903-1957). Американский математик венгерского происхождения. Член Национальной АН США (1937). Родился в Будапеште. В 1926 г. окончил Будапештский университет. В 1927-29 гг. преподавал в Берлинском университете, в 1930-33 - в Принстонском университете. С 1933 г. - профессор Принстонского института перспективных исследований. Принимал участие в работах по созданию атомной бомбы в Лос-Аламосе. С 1954 г. член комиссии США по атомной энергетике.

Но программа, написанная по принципам, фон Неймана (язык машинного кода) очень неудобна для человека. Язык машины и язык человека оказались разными.

- Что делают люди, если их языки оказались разными?

- Правильно, приглашают переводчика.

Придуманы языки программирования – basic, pascal, c и десятки других. Эти языки достаточно близки к языкам человека и человек в состоянии выучить один или несколько таких языков. С другой стороны, для этих языков существуют алгоритмы, оформленные как программы-трансляторы, которые выполняют преобразование текста языка программирования в текст машинного кода, готового к исполнению компьютером.

Различают два вида трансляции: Интерпретация – когда из текста, по одной, выбираются команды, переводятся в машинный код и сразу выполняются. Это напоминает «устный» перевод. Переводчик всегда должен быть под рукой. Время перевода входит во время исполнения программы.

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

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

Оформление программ

С развитием компьютерной информатики все более четко выделяются

ДАННЫЕ - все объекты, с которыми может работать ЭВМ и

КОМАНДЫ - средства, которые при этом используются.

Данные, это материалы, определяют, с чем работает компьютер,

Команды, это инструменты (операторы, процедуры, функции), определяют, как поступать с данными, а иногда и с самими командами.

ДАННЫЕ = материалы бревно

КОМАНДЫ = инструменты

команды над данными топор

команды над командами точило

При работе ЭВМ данные могут менять свои значения. Для обеспечения такой возможности служат ПЕРЕМЕННЫЕ. Переменная - это выделенная для хранения определенной информации область памяти, соответственно имеет адрес начала в памяти и размер. Для удобства использования и отличий между собой переменные снабжаются ИДЕНТИФИКАТОРОМ, проще говоря каждая переменная получает ИМЯ. Информацию, хранящуюся в переменной в момент обращения к этой переменной называют ЗНАЧЕНИЕМ переменной.

Занесение значения в память называется операцией присваивания.

адрес начала и размер в памяти

| | |

+--+ память +----------+

| | |

| ПЕРЕМЕННАЯ |

| / \ |

+- имя значение – тип

(возможный диапазон значений)

Более подробно типы данных (способы хранения информации) будем разбирать на отдельном занятии

Один из способов представления алгоритмов - язык блок-схем.

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

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

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

Ввод исходной информации и вывод результатов отмечаются параллелограммами (1 вход и 1 выход)

Выделены блоки начала и конца (либо только выход, либо только вход)

Для сохранения принципа результативности (обязательное достижение единственного конца) после ветвлений требуются соединяющие узлы (2 входа 1 выход).

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

Язык блок-схем достаточно удобен для человека, но не понятен компьютеру. Компьютер понимает такой язык, как BASIC. В старых версиях, каждая команда записывалась в отдельную строку. Сейчас, через двоеточие можно записывать в одну строку несколько команд. Раньше метка-номер строки ставился у каждой строки, теперь, когда basic стал компилятором, метка обязательна только для строк, на которые выполняются ссылки. Заканчивается программа словом END. Иногда это слово писать не обязательно.

В языке basic операция присваивания оформляется знаком равенства. Под номером 50 находится команда присваивания, помещающая число 8 в память с именем Х.

10 команда 20 команда *** 50 Х=8 *** 90 команда 100 END

Еще один их известных языков – PASCAL Изначально разрабатывался как компилятор.

Текст программы начинается со слова BEGIN, заканчивается словом END и точкой. Между словами BEGIN и END размещается раздел команд. Перед словом BEGIN находится раздел описаний. В старых версиях языка, начинать текст требовалось со слова PROGRAM(input,output), с указанием имен входного и выходного устройств. В последних версиях это не обязательно. Разделителем, сигналом конца каждой команды (и не только для команд), является точка с запятой.

В языке pascal, для отличия от сравнения, при оформлении команды присваивания к знаку равенства спереди приписывается двоеточие. Читать этот парный знак следует: «переменная Х ПРИНИМАЕТ ЗНАЧЕНИЕ 8».

{ раздел описаний } begin команда; { раздел команд } команда; Х:=8; {команда присваивания} end. \ принимает значение

Стандартный вывод данных

Данные базовых типов (отметим, что в языке BASIC данные только базовых типов), и, как исключение, данные типа "строка" могут выводиться на экран командой

в языке BASIC PRINT <список;>

в языке PASCAL WRITE( <список,> )

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

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

Использование в качестве разделителя запятой, приводит к поиску в строке очередной метки табуляции и вывод информации начинается от этой метки.

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

Если после последнего элемента списка в операторе PRINT стоит разделитель, то следующий оператор PRINT продолжит вывод информации в этой же строке. Отсутствие незавершенности списка приводит к переводу строки.

в языке BASIC PRINT <список;> в языке PASCAL WRITE( <список,> ) WRITELN( <список,> )

В языке PASCAL разделитель всегда запятая, а для перевода строки в конце списка вместо процедуры WRITE( <список,> ) применяется процедура WRITELN( <список,> ).

Когда выводимая информация должна занять строго определенное место, используется Форматный вывод.

В языке BASIC, служебное слово USING определяет строку, которая будет выдана. Строка заключена в кавычки. В отведенные места внутри строки вставляются значения переменных списка. На место знаков ###.## - вставляется число, количество требуемых знаков после запятой очевидно. Применяя знаки - ,+, - можем потребовать обязательный вывод знака числа спереди или сзади. Заменив первый знак решетки на 0, – обеспечиваем заполнение нолями места перед значащими цифрами. Формат строковых значений следующий: восклицательный знак - место одного выводимого знака строки, наклонные черточки – слеши - определяют количество знаков строки (от двух и больше), амперсанд («обезьянка») & - все знаки значения.

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

writeln(pi:8:2); приведет к выводу | 3.14| (всего 8 знаков, из них 2 после запятой) Если места для вывода числовой информации недостаточно, то формат игнорируется, для целых чисел об этом сообщит появляющийся на экране знак процента.

BASIC PRINT USING" фамилия / / оценка #"; "Иванов",5

Для чисел: ###.## (можно использовать -,+,0)

Для строк: ! - один знак / / - слеши и пробелы между ними определяют количество знаков строки (два и больше) & - все знаки строки

В приведенном выше примере в 8 мест вставляются буквы фамилии «Иванов», на место решетки вставляется одна цифра 5

PASCAL (тот же результат определяет команда)

writeln(' фамилия ',fam:8,' оценка ',x:1);

формат вывода определяется знаками ’:’ writeln(pi:8:2); приведет к выводу | 3.14|

Стандартный ввод данных

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

Свойство команды ввода останавливать выполнение программы часто используется для организации задержки до нажатия клавиши «ввод» (“enter”).

В языке BASIC INPUT ""; X,Y,A$ ввод нескольких значений, разделенных запятой LINE INPUT A$ ввод одной строки знаков (включая запятые)

В языке PASCAL READLN(X,Y,A) ввод нескольких значений, разделенных пробелами.

В языке BASIC INPUT ""; X,Y,A$ ввод нескольких значений, разделенных запятой LINE INPUT A$ ввод одной строки знаков (включая запятые)

В языке PASCAL READLN(X,Y,A) ввод нескольких значений, разделенных пробелами.

Можно организовать ввод информации без дублирования на экране, используя буфер клавиатуры.

В языке BASIC имеется функция =inkey$, при исполнении которой происходит проверка наличия информации, и, если клавиша была нажата, возвращается ее значение, иначе возвращается пустая строка.

В языке PASCAL (в модуле CRT) функция проверки наличия информации в буфере клавиатуры и функция извлечения информации из буфера клавиатуры разделены, это: =keypressed, возвращает логическое значение и =readkey;, возвращает знак – какая клавиша нажата. Функция =readkey;, если буфер клавиатуры пуст, останавливает программу, пока какая-нибудь клавиша не будет нажата.

Ниже показаны, как решаются некоторые задачи средствами языков BASIC и PASCAL:

1) «если была нажата копка клавиатуры, то переменная получает значение – соответствующий знак».

2) «ждать, пока не будет нажата кнопка клавиатуры».

3) «ждать, пока не будет нажата кнопка, значение переменной – соответствующий знак».

	BASIC	PASCAL (модуль CRT
1	a$=inkey$	if keypressed then a:=readkey;
2	100 if inkey$="" then 100	repeat until keypressed;
3	100 a$=inkey$: if a$="" then 100	a:=readkey;

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

Завершение

По окончании нашего урока, вы должны знать ответы на вопросы:

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