1.История развития языков программирования.
Fortran—первый язык программирования высокого уровня, имеющий транслятор. Создан в период с 1954 по 1957 год группой программистов под руководством Джона Бэкуса в корпорации IBM Название Fortran является аббревиатурой от FORmula TRANslator, то есть, переводчик формул. Фортран широко используется в первую очередь для научных и инженерных вычислений.
Pascal — высокоуровневый язык программирования общего назначения. Один из наиболее известных языков программирования, широко применяется в промышленном программировании, обучении программированию в высшей школе, является базой для большого числа других языков. Был создан Никлаусом Виртом в 1968-69 годах (опубликован в 1970 году) Паскаль был создан как язык для обучения процедурному программированию (хотя, по словам Вирта, язык нельзя считать только учебным, поскольку язык, непригодный для написания реальных программ, для обучения использоваться не должен). Название языку дано в честь выдающегося французского математика, физика, литератора и философа Блеза Паскаля.
Algol—применяемый при составлении программ для решения научно-технических задач на ЭВМ. Разработан комитетом по языку высокого уровня IFIP в 1958—1960 гг. (Алгол-58, Алгол-60); усовершенствован в 1964—1968 гг. (Алгол 68). Алгол относится к языкам высокого уровня и позволяет легко переводить алгебраические формулы в программные команды.
Си—стандартизированный процедурный язык программирования, разработанный в начале 1970-х годов сотрудниками Томпсоном и Ритчи.Си был создан для использования в операционной системе UNIX. С тех пор он был портирован на многие другие операционные системы и стал одним из самых используемых языков программирования. Он является самым популярным языком для создания системного программного обеспечения. Его также часто используют для создания прикладных программ.
2.Стадии разработки программного обеспечения.
В процессе своей разработки продукт может проходить следующие стадии :
Пре-альфа-начальная стадия разработки—не всё доработано
Альфа—Стадия добавления новых функциональных возможностей. Программа доработана можно давать для ознакомления
Бета—Стадия активного бета-тестирования и отладки. Программы этого уровня могут быть использованы другими разработчиками программного обеспечения для испытания совместимости. Тем не менее программы этого этапа могут содержать достаточно большое количество ошибок.
Гамма или релиз-кандидат — Стадия-кандидат на то, чтобы стать стабильной. Программы этой стадии прошли комплексное тестирование, благодаря чему были исправлены все найденные критические ошибки. Но в то же время, существует вероятность выявления ещё некоторого числа ошибок, незамеченных при тестировании.
Релиз или RTM —Стабильная версия программы и готовая к применению.
3.Основные этапы обработки информации и решения задачи на ЭВМ.
При разработке программы выделяют следущие этапы:
1.постановка задачи(определение целей,определение требований ко времени,к объёму ресурсов…)
2.проектирование программы(определить метод расчёта,сценарий,вид данных)
3.разработка алгоритмов(разработать детали проекта…)
Св-ва алгоритма:
1.дискретность-расчлинение описания на отдельные элементарные действия
2.детерминированность-на одинаковых исходных данных алгоритм всегда должен давать одинаковые результаты
3.массовость-алгоритм должен работать на однотипных данных
4.кодирование-записывают на алгорит-м языке.
5.отладка и тестирование-устранение ошибок
4 Понятие алгоритма и способы его описания.
Алгоритм–конечная последовательность команд исполнителю, направленная на достижение определённой цели.
Способы описания алгоритмов.
-словесный;
-с использованием псевдокода;
-с помощью формул, таблиц;
- графический(схемы).
6.Типы алгоритмов.
Тип алгоритма определяется характером решаемой (в соответствии с его командами) задачи.
Типовые конструкции алгоритмов:
-Линейная.
-Циклическая.
-Разветвляющаяся.
Линейный(все команды должны выполнятся последовательно в порядке их записи,не могут повторятся или быть пропущены)
Циклический – описание действий или группы действий, которые должны повторяться указанное число раз или пока не выполнено заданное условие.
Разветвляющийся – алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
7. Базовые структуры, применяемые при создании алгоритмов.
Переменная - это область оперативной памяти, занимающая несколько ячеек и имеющая свое имя. Переменная обладает следующими свойствами:
1.переменная хранит не более 1 значения;
2.переменная способна хранить значения только одного и того же типа;
3.переменная хранит значение до тех пор, пока в нее не поместят новое значение, при этом предыдущее содержимое переменной стирается;
4.значение переменной может быть вызвано для использования сколько угодно раз без изменения оригинала;
5.к началу выполнения программы содержимое переменной считается неопределенным; ячейки памяти, отведенные под переменную путем ее описания, заполняются значениями в ходе выполнения программы с помощью оператора присваивания;
8. Алфавит языка Турбо-Паскаль включает буквы латинского алфавита: от a до z и от A до Z, арабские цифры: от 0 до 9, специальные символы: _ + - * / = , . : ; < > ( ) [ ] { } ^ @ $ #, пробел "_" и управляющие символы с кодами от #0 до #31.
Используются также служебные (зарезервированные) слова, например:and, array, begin, case, const, constructor, destructor,do, else, end, file, for, function, if, inline, interface, while, with, xor
При написании программы применяются:
константы - данные, значения которых не изменяются в программе;
переменные - данные, могущие изменяться при выполнении программы;
выражения - константы, переменные и обращения к функциям, соединенные знаками операций;
операторы - специальные символы и слова, выполняющие действия;
функции, процедуры и модули - отдельные программные блоки, имеющие имена и подключаемые к основной программе.
Общая структура программ на языке Паскаль
Program имя программы;
Uses Список используемых модулей
Label Список меток из основного блока программы
Const Определение констант программы
Type Описание типов
Var Описание переменных
Procedure Текст процедуры
Function Текст функции
Begin
Основной блок программы
(раздел операторов)
End.
9.Типы переменных, используемых в Турбо Паскале.
Простые:вещественный,строковый,целый,логический,символьный,порядковый…
Структкрированные:массив,запись,множество,файловый.
Вещественные Целые типы
Single 4 Byte 1
Real 6 Shortint 1
Duble 8 Word 2
Integer 2
Longint 4
Логический тип Переменные могут принимать значения: False(ложь) или True (истина).
Символьный тип Переменные могут принимать значения одного из символов с кодами от #0 до #255, т. е. допускаются буквы русского алфавита и символы псевдографики.
Строковый тип Переменная задается набором символов, заключенных в кавычки.
Массив - упорядоченные данные одного типа, состоящие из переменных (элементов массива). Элементы массива имеют свой порядковый номер (индекс) и значение. Массив может быть многомерным (без ограничения), но занимать не более 65520 байт.
Тип диапазон и перечислимый тип задаются программистом.
Файлы - именованная область внешней памяти ЭВМ, содержащая различные данные. Длина файла ограничена доступной дисковой памятью. Файлы могут быть текстовые, типизированные и нетипизированные
Записи - вводимый программистом тип, определяемый как структура данных разного типа, cодержащая названия полей с указанием их типов, расположенных между служебными словами Record и End
10.Условный оператор, оператор выбора..
if <условие> then Begin <Блок операторов 1> End else Begin <Блок операторов 2> End;
And(И)–возвращает значение истина если все объединяемые им условия верны, и ложь если это не так.
Or(ИЛИ)–возвращает значение ложь если все объединяемые им условия ложны, и – истина если это не так.
Xor(СТРОГОЕ ИЛИ)–возвращает значение истина если объединяемые им условия различны по значению и ложь, если они одинаковы.
Условия с этими операциями называют составными.
Not – отрицание одного условия.
Выражение 1 Выражение 2 And Or Xor
True True True True False
True False False True True
False True False True True
False False False False False
ОПЕРАТОР CASE … OF … END Case <выражение 1> Of Значение 1: оператор1;
Значение 2: оператор2;…Значение n: операторn;else оператор;
Между Case и Of находится выражение (называемое селектором), значение которого может принимать одно из перечисленных в списках значений
11.Операторы организации циклов.
Цикл с предусловием —цикл, который выполняется пока истинно некоторое условие, указанное перед его началом.
while <условие> do begin <тело цикла> end;
Цикл с постусловием —цикл, в котором условие проверяется после выполнения тела цикла. В языке Паскаль этот цикл реализует оператор repeat..until;
repeat <тело цикла> until <условие>
Цикл со счётчиком — цикл, в котором некоторая переменная изменяет своё значение от заданного начального значения до конечного значения с некоторым шагом, и для каждого значения этой переменной тело цикла выполняется один раз.
FOR v := b TO e BY s DO
... тело цикла
END
12.Итерационные алгоритмы и программы.
Итерационные алгоритмы(пошаговые)алгоритм в котором на каждом шаге используется одна и та же формула, выраженная через значения, полученные на предыдущих шагах алгоритма.
13.Структурные типы данных. Одномерные массивы. Способы описания. Базовые алгоритмы обработки одномерных массивов.
1. Структурные типы данных
К структурным типам относятся: массивы, записи, множества и файлы.
Массив - совокупность однородных элементов, обращение к которым выполняется с помощью индексов.
Одномерный массив.
Структурная схема массива
8 |
4 |
7 |
3 |
2 |
Массив А. |
Описание массивов
1. Неявный способ.
Type
<имя типа> = ARRAY [<тип индекса> ] OF <тип элементов >
VAR <имя переменной> : <имя типа>;
в разделе Type описывается тип массива, который будет использоваться в программе, то есть его размер и тип элементов, в разделе VAR для переменных которые будут содержать массив указывается новый тип.
2. Явный способ
VAR <имя переменной > : ARRAY [<тип индекса>] OF <тип элементов >
в разделе VAR сразу указываются переменные, которые будут иметь тип – массив. Если необходимо создать массивы разных типов или разных размеров, то их описывают отдельно.
14.Структурные типы данных. Двумерные массивы. Способы описания.
По своей структуре аналогичны таблицам. Каждый элемент характеризуется номером строки и номером столбца. Например: А[3,8] – элемент из массива А находящийся в 3 строке и 8 столбце.
Описание аналогично одномерным массивам, но необходимо указывать два типа индексов, разделяя их запятой. Например,
A: ARRAY [1..5, 1..10] of integer;– описание двумерного массива из 5 строк и 10 столбцов.
Для обработки двумерного массива используются вложенные циклы For. Первый цикл – внешний изменяет номер строки. Второй – внутренний изменяет номер столбца.
15. Подпрограммы. Глобальные и локальные переменные.
Переменные, описанные в разделе описаний подпрограммы, называются ее локальными переменными. Переменные же, описанные вне подпрограммы, называются глобальными по отношению к ней.
Если имя локальной переменной совпадает с именем глобальной переменной, то локальная переменная скрывает глобальную, так что к глобальной переменной нельзя обратиться внутри подпрограммы
Подпрограмма — поименованная или иным образом идентифицированная часть компьютерной программы, содержащая описание определённого набора действий. Подпрограмма может быть многократно вызвана из разных частей программы.
Виды подпрограмм:
Функция — это подпрограмма специального вида, которая, кроме получения параметров, выполнения действий и передачи результатов работы через параметры имеет ещё одну возможность — она может возвращать результат.
Процедура — это любая подпрограмма, которая не является функцией.
16.Пользовательские процедуры. Заголовок и тело процедур, классификация параметров. Вызов процедур. Особенности их использования
Описание процедуры начинается с заголовка, который является обязательным. Заголовок состоит из служебного слова Procedure, за которым следуют имя процедуры
Раздел описаний процедуры подобен разделу описаний основной программы, и может состоять из разделов меток, констант, типов, переменных и, в свою очередь, процедур и функций. В языке Паскаль допускается отсутствие раздела описаний.
Раздел операторов заключается в операторные скобки BEGIN и END, причём после END в отличие от основной программы ставится точка с запятой.
Вызывается процедура по её имени, например:
PRIM(Список_параметров);
Параметры.
Для реализации алгоритма подпрограмме могут понадобиться некоторые данные из основной программы. Обработав эти данные, подпрограмма возвращает результат основной программе, если в этом есть необходимость. Передавать информацию из основной программы в подпрограмму и наоборот мы можем только через переменные, которые носят специальное название — формальные параметры.
Те, через которые данные только поступают в подпрограмму, называют параметры-значения. Те, через которые данные возвращаются в основную программу из процедуры, называют параметры-переменные.
Параметры-переменные (результат работы процедуры) отличаются от параметров-значений тем, что перед ними стоит служебное слово Var.
При каждом обращении к процедуре мы должны поместить в параметры некоторые значения. Эти значения называются фактическими параметрами.
Фактические параметры — это параметры (данные), которые передаются процедуре при ее вызове.
17.Пользовательские функции. Заголовок и тело функций, классификация параметров. Вызов функций. Особенности их использования.
Если подпрограмма имеет только один выводимый параметр (результат), то её можно оформить в виде функции.
Заголовок функции состоит из слова Function, за которым указывается имя функции, затем в круглых скобках записывается список формальных параметров, далее ставится двоеточие и указывается тип результата функции.
В теле функции обязательно должен быть хотя бы один оператор присваивания, в левой части которого стоит имя функции, а в правой — ее значение. Иначе значение функции не будет определено.
Function Имя[(Список формальных параметров)]: Тип результата;
Раздел описаний
Begin
Раздел операторов — тело функции, в котором обязательно должен быть оператор присваивания: Имя_функции:=значение
End;
Вызывается функция по её имени с указанием фактических параметров. При этом вызов функции можно делать непосредственно внутри выражения, подобно тому, как используются стандартные встроенные функции, например, квадрат — SQR(X).
18. Метод пошаговой детализации последовательного уточнения разработки алгоритмов. Особенности использования массивов в качестве параметров.
При написании программы вся задача рассматривается как единственное предложение (вершина), выражающее общее назначение программы. Так как вершина редко отображает достаточное количество деталей, на основании которых можно написать программу, то поэтому надо начинать процесс детализации. Вершина разделяется на ряд более мелких задач в том порядке, в котором эти задачи должны выполнятся. В результате получим первую детализацию. Далее каждая из подзадач разбивается на подзадачи, принадлежащие второму уровню детализации. Программист завершает процесс нисходящей разработки с пошаговой детализацией, когда алгоритм настолько детализирован, чтобы его можно было бы преобразовать в программу.
Достоинства метода пошаговой детализации:
* Сохраняется концептуальная целостность программы: от сложного к простому.
* Проектирование программы, кодирование, проверку и документирование можно делать параллельно.
* В каждый момент времени (даже в начале разработки) имеется работающий вариант программы.
Особенности использования массивов в качестве параметров.
При использовании процедур с параметрами для описания формальных параметров в заголовке требуется наименование типа параметров, поэтому , используя переменную m как переменную “массив”, необходимо для нее самостоятельное описание ее типа mas в основной программе, для чего используется раздел TYPE.
19. Организация библиотек. Модули пользователя. Структура Unit-a.
Модуль - это автономно компилируемая программная единица, включающая в себя различные компоненты раздела описаний (типы, константы, переменные, процедуры )
Модули представляют собой прекрасный инструмент для разработки библиотек прикладных программ и мощное средство модульного программирования. Важная особенность модулей заключается в том, что компилятор Турбо Паскаля размещает их программный код в отдельном сегменте памяти. Максимальная длина сегмента не может превышать 64 Кбайта, однако количество одновременно используемых модулей ограничивается лишь доступной памятью, что дает возможность создавать весьма крупные программы.
Модуль имеет следующую структуру:
UNIT<имя>; -зарезервированное слово (единица); начинает заголовок модуля
INTERFACE –
<интерфейсная часть>
IMPLEMENTATION
<исполняемая часть>
BEGIN
<инициирующая часть>
END.
20.Стандартные модули
В Турбо Паскале имеется восемь стандартных модулей, в которых содержится большое число разнообразных типов, констант, процедур и функций.
Модуль SYSTEM.
В него входят все процедуры и функции стандартного Паскаля,модуль SYSTEM подключается к любой программе независимо от того, объявлен ли он в предложении USES или нет, поэтому его глобальные константы, переменные и подпрограммы считаются встроенными в Турбо Паскаль.
Модуль PRINTER.Делает доступным вывод текстов на матричный принтер. В нем определяется файловая переменная LST типа TEXT, которая связывается с логическим устройством PRN.
Модуль CRT. С помощью входящих в модуль подпрограмм можно перемещать курсор в произвольную позицию экрана, менять цвет выводимых символов и окружающего их фона, создавать окна.
Модуль GRAPH. С помощью подпрограмм, входящих в модуль GRAPH, можно создавать разнообразные графические изображения и выводить на экран текстовые надписи стандартными или разработанными программистом шрифтами.
Модуль DOS.В модуле собраны процедуры и функции, открывающие доступ программам к средствам дисковой операционной системы MS- DOS.
Модуль OVERLAY.-Он необходим при разработке громоздких программ с перекрытиями.
21.Символьные переменные и строки. Организация, размещение в памяти, процедуры и функции обработки строк.
Значением символьного типа (Char) является множество всех символов ПК. Каждому символу приписывается целое число в диапазоне 0...255.
ORD(X) – возвращает порядковый номер значения выражения X.
PRED (X) - возвращает предыдущее значение порядкового
SUCC (X) - возвращает следующее значение порядкового типа, которое соответствует порядковому номеру ORD(X) +1, т.е.
UPCASE(CH) - функция типа CHAR; возвращает прописную букву, если СН -строчная латинская буква, в противном случае возвращает сам символ СН
Для кодировки используется код ASCII ( американский стандартный код для обмена информацией). Это 7-битный код, т.е. с его помощью можно закодировать лишь 128 символов в диапазоне от 0 до 127. В то же время в 8-битном байте, отведенном для хранения символа в Турбо Паскале, можно закодировать в два раза больше символов в диапазоне от 0 до 255.
COPY(ST, INDEX, COUNT) - функция типа STRING; копирует из строки ST COUNT символов, начиная с символа с номером INDEX.
DELETE (ST, INDEX, COUNT) - процедура; удаляет СОUNT символов из строки ST, начиная с символа с номером INDEX.
INSERT (SUBST, ST, INDEX) - процедура; вставляет подстроку SUBST в строку ST, начиная с символа с номером INDEX.
LENGTH (ST) - функция типа INTEGER; возвращает длину строки ST.
22.Множества. Организация, процедуры и функции обработки.
Множества - это наборы однотипных логически связанных друг с другом объектов. Количество элементов, входящих в множество, может меняться в пределах от 0 до 256 (множество, не содержащее элементов, называется пустым). Именно непостоянством количества своих элементов множества отличаются от массивов и записей.
Два множества считаются эквивалентными тогда и только тогда, когда все их элементы одинаковы, причем порядок следования элементов в множестве безразличен.
Описание типа множества имеет вид:
<имя типа> = SET OF <баз.тип>
Здесь <имя типа> - правильный идентификатор;
SET, OF - зарезервированные слова (множество, из);
<баз.тип> - базовый тип элементов множества, в качестве которого может использоваться любой порядковый тип, кроме WORD, INTEGER, LONGINT.
Над множествами определены следующие операции:
* пересечение множеств; результат содержит элементы, общие для обоих множеств;
+ объединение множеств; результат содержит элементы первого множества, дополненные недостающими элементами из второго множества:
- разность множеств; результат содержит элементы из первого множества, которые не принадлежат второму:
= проверка эквивалентности; возвращает TRUE, если оба множества эквивалентны;
<> проверка неэквивалентности; возвращает TRUE, если оба множества неэквивалентны;
<= проверка вхождения; возвращает TRUE, если первое множество включено во второе;
>= проверка вхождения; возвращает TRUE, если второе множество включено в первое;
23.Записи. Организация, процедуры и функции обработки.
Запись-структура данных, состоящая из фиксированного числа компонентов, называемых полями записи. В отличие от массива, компоненты (поля) записи могут быть различного типа. Чтобы можно было ссылаться на тот или иной компонент записи, поля именуются.
Структура объявления типа записи такова:
<имя типа> = RECORD <сп.полей> END
Здесь <имя типа> - правильный идентификатор;
RECORD, END - зарезервированные слова (запись,конец);
<сп.полей> - список полей; представляет собой последовательность разделов записи, между которыми ставится точка с запятой.
Каждый раздел записи состоит из одного или нескольких идентификаторов полей, отделяемых друг от друга запятыми. За идентификатором (идентификаторами) ставится двоеточие и описание типа поля (полей)
Чтобы упростить доступ к полям записи, используется оператор присоединения WITH:
WITH <переменная> DO <оператор>
Здесь WITH, DO - ключевые слова (с, делать);
<переменная> - имя переменной типа запись, за которым, возможно, следует список вложенных полей;
<оператор> - любой оператор Турбо Паскаля.
24.Методы сортировки. Сортировка пузырьковым методом. Сортировка выбором
Имеется три способа сортировки массивов:
- сортировка обменом;
- сортировка выбором;
- сортировка вставкой.
Сортировка пузырьковым методом.
Наиболее известной является сортировка пузырьковым методом.Однако, эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок.
Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов.
Сортировку пузырьковым методом называют квадратичным алгоритмом, поскольку время его выполнения пропорционально квадрату числа сортируемых элементов. Сортировка большого числа элементов пузырьковым методом потребует очень много времени, т.к. время выполнения сортировки находится в квадратичной зависимости от числа элементов массива.