Студопедия

КАТЕГОРИИ:

АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

ТО,ЧТО НАПИСАНО НИЖЕ БЫЛО В ПРАКТИЧЕСКОЙ ПО АЛГОРИТМИЗАЦИИ.




Массив представляет собой фиксированное количество упорядоченных однотипных компонент, снабженных индексами. Он может быть одномерным и многомерным. Чтобы задать массив используется зарезервированное слово array, после которого следует указать тип индекса (индексов) компонент (в квадратных скобках) и далее после слова of – тип самих компонент :

 

type < имя типа > = array < тип индекса > of < тип компонент > ;

 

Пример 1. 

type Arr = array [ 1 . . 3 ] of real ;

       { массив из 3 вещественных чисел }

       Matrix = array [ 1 . . 3 , 1 . . 2 ] of integer ;

       { двумерный массив целых чисел, состоящий из 3 строк и 2 столбцов }

 

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

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

Так, для введенных выше типов можно задать, например, следующие переменные и константы:

Var             M1 , M2 : Arr ;

                   Matr : Matrix ;

Const M3 : Arr = ( 1 , 2 , 3 );

                   Mat : Matrix = ( ( 1, 2 ) , ( 3 , 4 ) , ( 5 , 6 ) ) ;

Последняя константа соответствует следующей структуре :

       1                 2

3 4

       5                 6

 

Массив можно вводить непосредственно и при определении соответствующих переменных или типизированных констант. Например :

Var             M1 , M2 : array [ 1 . . 3 ] of real ;

                   Matr : array [ 1 . . 3 , 1. . 2 ] of integer ;

Здесь определены те же массивы, что и в предыдущем примере.

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

M1 [ 2 ] – обращение ко второму элементу массива М1,

Matr [X , Y] – обращение к элементу, который расположен на пересечении строки X и столбца Y и т. д.

Одному массиву можно присвоить значение другого массива , но только идентичного типа.

 

Одномерный массив: Двухмерный массив:

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

For i:=1 to n do begin     write ( ‘ a1[ ‘ , i , ’ ]= ’ );      readln ( a1[ i ] ) ; еnd ;   For i:=1 to n do for j:=1 to m do begin   write( ‘ a2[‘, i , ’ , ’ , j ,’ ]= ’ ) ;    readln ( a [ i , j ] ) ; end ;  

Вывод на экран

For i:=1 to n do begin       writeln ( a1[ i ]) ; end.     For i:=1 to n do begin for j:=1 to m do           write ( a2[i , j]);                     writeln ;       end ;

 

 

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 5

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

 

 

Отрица́ние — унарная операция над суждениями, результатом которой является суждение «противоположное» исходному. Обозначается знаком перед или чертой над суждением. Конъю́нкция — логическая операция, по своему применению максимально приближённая к союзу "и". Дизъю́нкция —логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу». Импликация — бинарная логическая связка, по своему применению приближенная к союзам «если… то…». Импликация записывается как посылка следствие; применяются также стрелки другой формы и направленные в другую сторону (остриё всегда указывает на следствие). Эквивалентность — отношение между высказываниями. Законы де Мо́ргана (правила де Мо́ргана) — логические правила, связывающие пары дуальных логических операторов при помощи логического отрицания. not (P and Q) = (not P) or (not Q), not (P or Q) = (not P) and (not Q). Обычная запись этих законов в формальной логике: Если существует операция логического умножения двух и более элементов, операция «и» — (A&B), то для того, чтобы найти обратное от всего суждения ~(A&B), необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, операцией «или» — (~A+~B). Закон работает аналогично в обратном направлении: ~(A+B) = (~A&~B).

 

 

2. Шинные формирователи. Функционирование. Схема ШФ К580ВА86 и временная диаграмма его работы. Параметры ШФ.

 

Шинные формирователи (ШФ), называемые также приемопередатчиками, шинными драйверами или магистральными вентиль - буферами, включаются между источником информации и шиной. Они усиливают сигналы по мощности при работе на шину, отключают источник информации от шины, когда он не участвует в обмене, формируют при необходимости требуемые уровни сигналов логической 1 или 0. ШФ различаются разрядностью и передачей сигналов в прямом или инверсном виде.

Шина А принимает данные от МП или передает их ему, шина В связана с магистралью, на которую передает инф. или с которой принимает ее.

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

Функционирование ШФ подчиняется условиям указанным в таблице:

ШФ формирует уровни выходных напряжений (U) соответствующего «1» не меньше 2.4 В и «0» не более 0.5 В. 

 

3. Сортировка. Дать определение понятия сорти­ровка, привести различные методы сортировки. Описать сортировку выбором и обменом. Описать алгоритм би­нарного поиска и поиска перебором.

 

 

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

 

Методы сортировки:

Сортировка вставками

Сортировка выбором

3. Сортировка обменом

Сортировка выбором.

Формально его можно описать следующим образом.

На i - м шаге ( i = 1, ..., N — i ):

выбираем из элементов с индексами от i до N максимальный элемент;

меняем местами найденный максимальный и элемент А [i], на i-м месте оказывается максимальный элемент из еще неотсортированной части массива.

После выполнения N—1-го шага в позиции A [N] будет находиться самый маленький элемент массива.

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

 

Запишем алгоритм сортировки выбором:

нц для i от 1 до N — 1 

       K : = i 

       max : = A [ i ]

       нц для j от i + 1 до N

                   если A [ i ] > max

       то max : = A [ j ]

                              K : = j

                   все

       кц

A [ K ] : = A [ i ]

A [ i ] : = max

кц

 

Внутренний цикл ДЛЯ j ОТ i + 1 ДО N является алгоритмом поиска максимального алгоритма среди элементов с номерами от i+1 до N. Рассмотрим работу данного метода на массиве

А = {0, 1, 9, 2, 4, 3, 6, 5}.

Максимальный элемент будем подчеркивать.

1) 0, 1, 9, 2, 4, 3, 6, 5

2) 9, 1, 0, 2, 4, 3, 6, 5

3) 9, 6, 0, 2, 4, 3, 1, 5

4) 9, 6, 5, 2, 4, 3, 1, 0

5) 9, 6, 5, 4, 2, 3, 1, 0

6) 9, 6, 5, 4, 3, 2, 1, 0

7) 9, 6, 5, 4, 3, 2, 1, 0

8) 9, 6, 5, 4, 3, 2, 1, 0

 

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

На первом шаге для нахождения максимального элемента необходимо (N—1) сравнение, на втором (N—2), на третьем (N—3), ..., на последнем шаге —одно сравнение. Найдем сумму:

N – 1 + N – 2 + N – 3 + . . . + 1 = N ( N – 1 ) / 2 = ( N2 — N ) / 2 .

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

Количество перестановок элементов равно (N—1). Это количество определяется внешним циклом ДЛЯ.

 

Сортировка обменом

Рассмотрим еще один метод сортировки, который формально можно описать так:

На i-м шаге (i = 1, ..., N — 1 ) выполняем:

1. Сравниваем первые два элемента. Если первый меньше второго, то меняем их местами.

2. Сравниваем второй и третий, третий и четвертый, .... N—i и N — i + 1, при необходимости меняя элементы местами. Самый маленький окажется на i-м месте в массиве.

После первого шага самый маленький элемент массива помещается на N-e место. Массив будет отсортирован после просмотра, в котором участвуют только первый и второй элементы.

Название метода «сортировка обменом» определяется тем, что алгоритм основывается на обмене местами двух элементов массива.

Описанный метод сортировок обменом называют также пузырьковой сортировкой.

 

Алгоритм метода сортировки обменом:

нц  для i от 1 до N — 1

       нц  для j от 1 до N — i

                   если A [ j ] < A [ j + 1 ]

                   то   x : = A [ j ]

                              A [ j ] : = A [ j + l ]

                              A [ j + l ] : = x 

                   все

       кц

кц

 

Рассмотрим его на примере того же массива A = {0, 1, 9, 2, 4, 3, 6, 5}.

1) 1, 9, 2, 4, 3, 6, 5, 0

2) 9, 2, 4, 3, 6, 5, 1, 0

3) 9, 4, 3, 6, 5, 2, 1, 0

4) 9, 4, 6, 5, 3, 2, 1. 0

5) 9, 6, 5, 4, 3, 2, 1, 0

6) 9, 6, 5, 4, 3, 2, 1, 0

7) 9, 6, 5, 4, 3, 2, 1, 0

Число сравнений в данном алгоритме равно также (N 2 - N ) / 2.

При каждом сравнении возможна перестановка двух элементов в массиве. Поэтому количество перестановок (в худшем случае) будет равно количеству сравнений, т. е. (N2—N)/2.

* На последних двух проходах в приведенном выше примере массив не менялся. Заметим, что если на каком-то шаге алгоритма элементы массива уже упорядочены, то при последующих проходах по массиву перестановки больше выполняться не будут. Следовательно, как только количество выполненных на последнем проходе перестановок станет равным 0, алгоритм можно заканчивать.

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

 

Р : = « Истина »

К : = N — 1

нц пока Р = « Истина »

       Р : = « Ложь »

       R : = K

       нц для j от 1 до R

                   если A [ j ] < A [j + 1]

                   то   x: = A [ j ]

                              A [ j ] : = A [ j + l ]  

                              A [ j + l ] : = x 

                              Р : = «Истина»

                              K : = j 

                   все

       кц

кц

 

В приведенном фрагменте переменная Р логического типа используется для определения, были перестановки или нет, а переменная К — для хранения индекса последнего обмена. Переменная R является границей, на которой заканчивается просмотр.

Поиск перебором

Чтобы найти какие-то данные в неупорядоченном массиве,

применяется алгоритм простого перебора элементов.

Следующая функция возвращает индекс заданного элемента массива.

Её аргументы: массив с первым индексом 0, количество элементов

в массиве и искомое число. Если число не найдено, возвращается -1.

function SearchPer (Arr : array of Integer; n, v : Integer) : Integer;

var

i : Integer;

begin

Result := -1;

for i := 1 to n do

if Arr [i] = v then begin

Result := i;

Exit;

end;

end;

 

Бинарный поиск

При поиске в упорядоченном массиве можно применить гораздо

более быстрый метод поиска - бинарный.

Суть его в следующем: В начале переменная Up указывает на самый

маленький элемент массива (Up := 0), Down - на самый большой

(Down := n, где n - верхний индекс массива), а Mid - на средний.

Дальше, если искомое число равно Mid, то задача решена; если число меньше Mid,

то нужный нам элемент лежит ниже среднего, и за новое значение Up принимается Mid + 1;

и если нужное нам число меньше среднего элемента, значит, оно расположено

выше среднего элемента, и Down := Mid - 1. Затем следует новая итерация цикла,

и так повторяется до тех пор, пока не найдётся нужное число, или Up не станет больше Doun.

function SearchBin (Arr : array of Integer; v, n : Integer) : Integer;

var

Up, Down, Mid : Integer;

Found : Boolean;

begin

Up := 0; Down := n;

Found := False; Result := -1;

repeat

Mid := Trunc ((Down - Up) / 2) + Up;

if Arr [Mid] = v then

Found := True

else

if v < Arr [Mid] then

   Down := Mid - 1

else

   Up := Mid + 1;

until (Up > Down) or Found;

if Found then

Result := Mid;

end;

 

 

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 6

1. Перечислите способы описания функций алгебры логики, приведите примеры. Опишите структуру таблиц истинности логических функций от 2-х, 3-х и 4-х переменных. Приведите пример построения таблицы истинности для логической функции F(A,B,C,D)=

 

Табличный способ. При этом способе функция задается в виде таблицы истинности, представляющей собой совокупность всех комбинацийвходных переменных (левые столбцы) и соответствующих им значений функции (правый столбец). Таблица истинности содержит 2n строк, n +m столбцов (количество входов n+количество выходовm). Например: пусть требуется задать функцию двух переменных, т.е. дискретное устройство на два входа и на один выход, следовательно, число столбцов = 2+1, а число строк = 4. Словесно-аналитический способ задания функции алгебры логики. При этом способе функция задается в виде аналитического выражения. В левой части высказывания указывается действие управляемого привода (или исполнительного устройства), а в правой части- условие, при котором выполняется это действие. Графические способы. Для графического описания логических взаимодействий можно использовать разные способы, предлагаемые стандартом IEC 848: шаговая, временная диаграмма, логические функциональные схемы, функциональный план. Математическое представление алгебры логики. Элементарные логические действия можно представить с помощью специальных или арифметических символов (AND:Ù, · ;OR: Ú, +; NO:a`), обозначающих логические действия. Используя законы алгебры логики, возможны преобразования математических выражений логических функций. Представление логического взаимодействия в электротехнике. Логические взаимодействия сигналов возможно реализовать через определенное соединение контактов. Существует язык программирования, который использует логические свойства соединения контактов.

A B C D F
0 0 0 0 1
0 0 0 1 0
0 0 1 0 1
0 0 1 1 1
0 1 0 0 1
0 1 0 1 0
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 0
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 0
1 1 1 0 1
1 1 1 1 1

 

2. Опишите состав регистра флагов процессора. На примере команды ADD AX, 9A74h (где AX←8E35h) раскройте назначение флагов состояния. Объясните назначение флагов управления состоянием процессора.

 

Регистр флагов эквивалентен регистру слова состояния процессора других вычислительных систем. Этот регистр содержит информацию о текущем состоянии процессора. Рассматривают его не как единое целое, а как набор 16-ти отдельных битов, каждый из которых указывает на определенный факт. Он включает 6 флагов состояний и 3 флага управления состоянием CPU.

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

 

 

        OF DF IF TF SF ZF   AF   PF   CF

15   14 13 12   11 10  9    8   7   6   5   4    3 2   1     0

 

Флаги состояния процессора:

 

CF — устанавливается в 1 при переносе из/заёме в (при вычитании) старший значащий бит результата и показывает наличие переполнения в беззнаковой целочисленной арифметике. Также используется в длинной арифметике

PF — устанавливается в 1, если младший значащий байт результата содержит чётное число единичных (ненулевых) битов.

AF — устанавливается в 1 при переносе и заёме из бита 3 результата.

ZF — устанавливается в 1, если результат равен нулю.

SF — равен значению старшего значащего бита результата, который является знаковым битом в знаковой арифметике.

OF – флаг переполнения. Устанавливается в 1, если происходит переполнение разрядной сетки при обработке операндов со знаком. Такая ситуация возникает в случае выхода результата за пределы допустимого диапазона для чисел со знаком.

Управляющий флаг

Флаг направления (DF, бит 10 в регистре флагов) управляет строковыми инструкциями (MOVS, CMPS, SCAS, LODS и STOS): установка флага заставляет уменьшать адреса (обрабатывать строки от старших адресов к младшим), обнуление заставляет адреса увеличивать. Инструкции STD и CLD соответственно устанавливают и обнуляют флаг DF.

Системные флаги

IF — обнуление этого флага запрещает отвечать на маскируемые запросы на прерывание.

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

ПРИМЕР

 Пример походу с подвохом, т.к. не сказано знаковые или незнаковые операнды. Рассмотрим две ситуации.

А) Операнды беззнаковые. Тогда:

8E35                                   1000 1110 0011 0101

+ 9A74                                 +1001 1010 0111 0100

128A9                                1 0010 1000 1010 1001

CF — 1, т. к. произошло переполнение

PF —.1, т. к. в младшем бите четное кол – во единиц

AF — 0, т. к. переноса из 3 в 4 бит не было

ZF — 0, т. к. результат не равен 0

SF — 0

OF – ? (не определяем)

 

Б) Операнды знаковые. Тогда:

 

1)Т.к. оба числа отрицательные (1 в старшем бите) получаем обратный код:

 10000

- 8E35

 71CB

 

10000

-9A74

 658C

 

2)Складываем полученные операнды

 

71CB                                  0111.0001.1100.1011

658C                                   0110.0101.1000.1100

D757                                   1101.0111.0101.0111

 

3)Т.к. в старшем байте 1, то мы получили дополнительный код отрицательного числа. Найдем его модуль.

 

-10000

  D757

28A9

Ответ: -28A9h или - 1240910

Для установки флагов смотрим шаг 2 в двоичной системе

CF — не рассматриваем(знаковые операнды)

PF —.0, т. к. в младшем бите нечетное кол – во единиц

AF — 1, т. к. был перенос из 3 в 4 был

ZF — 0, т. к. результат не равен 0

SF — 1

OF – 1, т. к. произошло переполнение

 

3. Среда программирования Delphi. Дать понятие о визуаль­ном программировании, особенно­стях разработки программ под WINDOWS. Рассказать об основных эле­ментах среды программирования Delphi. Описать визуальные компоненты, палитру компонен­тов. Рассказать о структуре приложения в Delphi, способах запуска, создания, сохранения проекта. Описать объект TForm, его характеристики.

 

В КОНСПЕКТЕ

 

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 7

 

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

 

В КОНСПЕКТЕ

 

2. Приведите структурную схему CPU i8086. Опишите состав и назначение устройства сопряжения с шиной и устройства обработки.

 

В КОНСПЕКТЕ

 

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

 

 










Последнее изменение этой страницы: 2018-04-12; просмотров: 481.

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