Быстрый поиск

Шпаргалка: Вопросы и ответы к экзаменам В-1

(1999)

1. Алгоритм. Свойства алгоритма. Способы записи алгоритма

(общ.) Алгоритм – это система формальных правил однозначно приводящая к решению поставленной задачи.

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

Свойства:

А) Дискретность - алгоритм состоит из отдельных пунктов или шагов

Б) Определённость - каждый шаг алгоритма должен быть строго сформулирован.

(иметь точный смысл)

В) Связанность - на каждом следующем шаге используются результаты предыдущего.

Г) Конечность – алгоритм должен завершаться после конечного числа шагов

Д) Результативность – алгоритм должен приводить к получению конечных результатов

Е) Массовость – пригодность для решения широкого класса задач.

Ж) Эффективность – применение а. должно давать какой бы-то положительный временной результат (временной)

Способ записи:

А) Словесно-формульный

Б) Структурная схема и алгоритм (ССА)

В) Спец. языки (алгоритмические и псевдокоды)

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

Г) Графический способ

2. Линейные и разветвляющиеся алгоритмы. Cтруктурные схема алгоритмов. Правила выполнения.

CCA- при записи в виде структурной схемы алгоритм представляется графически в виде последовательности блоков выполняющих определённые функции и блоки соединяются линиями возможно со стрелками. Внутри блоков операции. Блоки нумеруются по порядку. По способу организации алгоритмов ССА блоки делятся на линейные, разветвляющиеся и циклические.

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

Начало—ряд операторов—конец.

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

3. Циклические алгоритмы. Классификация. Вычисление сумм, произведений.

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

Циклы по числу повторений делятся на циклы с заданным числом повторений и итерационные.

ЦИКЛЫ

ЗАДАННОЕ ЧИСЛО ИТЕРАЦИОННЫЕ

СО СЧЁТЧИКОМ УПР. УСЛОВИЕМ

ПОСТ. УСЛОВИЕ ПРЕДУСЛОВИЕ

Общее замечание: вход только в начало цикла, а выход вследствие окончания цикла, оператором GOTO, процедурами прерхода и выхода, находящимся в теле цикла.

4. Циклические алгоритмы. Итерационные циклы. Вложенные циклы.

Циклы по числу повторений делятся на циклы с заданным числом повторений и итерационные.

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

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

5. Массивы. Алгоритмы обработки массивов. Процедура BREAK

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

Пример: В[2] означает второй элемент массива В.

Пусть имеется некоторая последовательность величин 1, 2, 4, 8, 3. Все элементы этой последовательности имеют одно имя А. Отличаются они друг от друга индексами, например, A[1]=1, A[2]=2, A[3]=4, A[5]=8, A[6]=3.

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

Количество индексов в обозначении элемента массива определяет размерность массива. Массив может быть одномерным (один индекс S[4]), двумерным (два индекса N[2,4]), трех мерным (три индекса Y[2,4,1]) и т.д.

Массив описывается в разделе описания переменных, при этом описание массива включает описание типа массива (тип его элементов, т.е. какие значения они могут принимать) и типа индексов. Например, массив вещественного типа с именем vector может быть описан следующим образом:var vector: array [1..50] of real

Это описание означает, что одномерный массив vector имеет 50 элементов типа real со значениями индекса 1,2, ...,50. Элементы этого массива будут иметь обозначения: vector[1], vector[2], ..., vector[50]

Двумерный массив matrix, с целочисленными компонентами можно определить следующим образом:

var matrix [1..10,1..15] of integer

Двумерный массив часто называют матрицей. Первый индекс этого массива (номер строки матрицы) принимает значения из отрезка 1..10, а второй (номер столбца) - из отрезка 1..15. Компоненты массива могут иметь обозначения: matrix[1,5], matrix[8,8], matrix[i,j] и т.п.

Примеры:

program p2;

var matrix: array [1..3, 1..4] of integer;{ определяется двумерный массив в 3 строки и 4 столбца с именем matrix}

i, j: integer;

begin

for i:=1 to 3 do

for j:=1 to 4 do

read(matrix[ i, j]); {заполнение двумерного массива на 3 строки и 4 столбца}

for i:=1 to 3 do

begin

writeln;

for j:=1 to 4 do write(matrix[ i, j]);{вывод элементов двумерного массива в виде таблицы}

end;

6. Структуризация. Восходящее программирование. Проектирование алгоритма перевода чисел из одной системы счисления в другую (2,8,10,16).

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

7. Нисходящее программирование. Проектирование алгоритма выполнения арифметических операций (+,-,*,/) над числами с пл. точкой.

При нисходящем программировании сверху вниз сначала разрабатывается общая структурная схема алгоритма, а затем разрабатываются этапы её детализации (структурирование).

8. Язык TURBO PASCAL. Алфавит языка. Идентификаторы TURBO PASCAL.

ТП – единство двух самостоятельных начал компилятора и инструментов програмной оболочки. Это мощная современная процедурная система программирования

Алфавит: буквы латинского от a до z, знак _.(если не char A = a)

Цифры – арабские 0-9, спец. символы +-*/=.,:;<>[]{}()^&$@#%!

Пробелы (ASCII от 0 до 32) ограничители идентификаторов

Зарезервированные слова и параметры (не используются в качестве идентификаторов). Стандартные директивы absolute, assembler, external, far, forward, near и т.д. .

Идентификаторы: имена констант, var’ных, меток , типов, obg-ов, процедур, функций(могут иметь произвольную длину, но значат только первые 63 символа, начинаются только с буквы или цифры).

9. Оператор условного перехода IF. Составной и пустой операторы.

IF<условие >THEN<операторы> ELSE <операторы>;

10. Оператор цикла со счетчиком.

FOR <идентификатор>:=<начальное состояние >TO<конечное состояние > DO<оператор>

FOR <идентификатор>:=<начальное состояние >DOWNTO<конечное состояние > DO<оператор>

11. Оператор цикла с предусловием.

Цикл ДО

WHILE<условие>DO<оператор>

12. Оператор цикла с постусловием.

Цикл ПОКА

REPEAT

Оператор;

UNTIL<условие>;

13. Подготовка и отладка программ в среде TurboPascal.

Меню run

Run- запуск на исполнение

Step over-пошаговое исполнение программы

Trace into- пошаговое исполнение программы только подпрограммы выполняются оператор за оператором

Go to cursor – выполнение до курсора

Program reset- завершение процесса отладки

Parameters- окно для ввода параметров для отладки

Меню compile

Compile- компиляция файла, находящегося в активном окне редактирования.

Make – условная компиляция изменённых модулей в ЕХЕ файл

Build- безусловная компиляция многомодульной программы с созданием ЕХЕ файла

Target…-выбор в окне таргет целевой платформы для приложения

Primary file…-открывает окно для указания главного файла, компилируемой программы.

Меню Debug:

Breakpoints- установка точек условного и безусловного перехода

Call stack – показывает процедуры выполнявшиеся ранее.

Watch – окно значений переменных

Output – окно результатов работы программы

User screen – просмотр результатов включая графику

Evaluate/ modify.. – окно изменения значений выражений

Add watch – окно значений и переменных вовремя отладки

Add breakpoint.. – окно установки точек прерывания программы

14. Константы в TURBO PASCAL (целые, вещественные, 16-ричные, логические, символьные, строковые константы, конструктор множества)

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

Целые числа: от –2147483648 до 2147483647

Вещественные числа: (экспоненциальная часть) 3.14E5

16-ричное число: $(код 36 в ASCII) $00000000- $F…$F(8)

Логическая константа: True, False.

Символьная константа: любой символ в ‘ ‘, либо указатель внутри кода #83=’S’

Конструктор множества - список элементов множества в [].

[1,2,3,4],[red, blue],[true, false]. В ТП разрешается объявление констант

const a=12/343;

15. Типизированные константы.

Типизированные константы фактически являются переменными со статическим классом памяти. В отличие от простых констант, в описании типизированных указывается как значение константы, так и её тип.

Существуют типы:

Константа, константа-адрес, константа-массив, константа-запись, константа-объект, константа-множество.

Указательный тип:

Type ptr = ^integer;

Conct intptr:ptr=nil;

Структурированный тип:

1 массив (array)

2 множество (set of 1..4)

3 запись (record)

4Объектного типа (object)

16. Оператор присваивания. Приоритет операций. Стандартные функции.

<имя переменной>:=<выражение>;

арифметические логические отношения прочие

1 NOT @-адресное преобразование

2 *,/,DIV,MOD AND,SHL,SHR

3 +,- OR, XOR

4 <;>;=; IN

Для повышения приоритета используются ( ).

Стандартные функции ТП.

ABS(X ) SQR(X) SQRT(X) TRUNG(X) ROUND(X)

COS(X) SIN(X) TG(X) ARCTANG(X) EXP(X)

LN(X) PRED(X) SUCE(X) ORD(X) CHR(X)

ODD(X) INT(X) FRAG(X) +,-,*,/ (X)DIV(Y)

MOD(X) NOT AND OR XOR

= < > I_SHL_J I_SHR_J

17. Операторы и функции безусловного перехода (goto, continue, exit, halt).

EXIT; - выход из программы или подпрограммы

HALT(COD);- (COD) – необязательный параметр, определяет код

HALT; - безусловная остановка программы

ERRORLEVEL; - вниз

BREAK; - досрочный выход из цикла

CONTINUE; - прерывает выполнение текущей операции в цикле, передаёт управление следующему оператору

18. Структуры простой и сложной программ в Турбо-Паскале.

PROGRAM<имя программы >;

USES<имя модуля>;

TYPE<раздел типов>;

LABEL<метки>;

CONST<константы>;

VAR<переменные и их типы>;

FUNCTION<имя функции>(имя переменной: тип)

BEGIN

операторы

END;

PROCEDURE<имя процедуры>( параметры)

BEGIN

операторы

END;

BEGIN

Текст основной программы

END.

19. Подпрограммы. Применение. Структура описания. Отличие процедуры от функции.

Самостоятельные, законченные фрагменты программы, оформленные особым образом, снабжённые именем – называются подпрограммами

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

Подпрограммы используются:

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

2. В сложных программах при модульном проектировании.

Подпрограммы делятся на процедуры и функции

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

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

Тело подпрограммы состоит из раздела описаний и раздела операторов.

Структура: PROCEDURE<имя процедуры >;

FUNCTION<имя функции>(параметр: тип);

USES<модули>;

LABEL<метки>;

CONST<константы>;

TYPE<типы>;

VAR<переменные>;

BEGIN

Тело подпрограммы

END;

20. Вложенные подпрограммы. Принципы локализации имен (локальные и глобальные переменные).

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

Если какая либо программа использует некоторые переменные подпрограммы,

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

21. Вызов подпрограмм (формальные и фактические параметры).

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

Пример:

PROCEDURE<имя>[(<формальные параметры>)];

FUNCTION<имя>[(<формальные параметры>)]:<тип>

Сразу за заголовками может следовать одна стандартных директив: ASSEMBLER <тело подпрограммы на ассемблере>, EXTERNAL<объявление внешней подпрограммы>, FAR, FORWARD, INLINE<встроенные машинные инструменты>, INTERRUPT,NEAR.

PROCEDURE SB(a: real<формальный параметр>);

Фактические параметры – это глобальные переменные подставленные в формальные

ТИП ФАКТ=ТИП ФОРМ.