13 Рекурсивный вычислительный процесс.

Рекурсия-процедура, вызывающая сама себя. Когда функция A в своем теле вызывает только одну рекурсивную функцию (саму себя), то это простая рекурсии. Косвенной рекурсия - это явление, когда рекурсивные функции вызывают друг друга (например, функция А вызывает B, а функция B вызывает A).

Прямая рекурсия	Косвенная рекурсия
void A(){ Операторы; A(); Операторы; }	void A(){ Операторы; B(); Операторы; } void B(){ Операторы; A(); Операторы; }

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

Факториал

Самый простой пример рекурсивного решения - задача о вычислении факториала.. Здесь нужно определить некоторую функцию F(n), которая будет вычислять значение n! через саму себя. В данном случае воспользуемся рекуррентной формулой:

F(n) = F(n-1)*n. условие выхода: если n<2, то ответ равен 1. Таким образом, в тех случаях, когда n<2, функция не будет себя вызывать, что будет гарантировать выход из рекурсии.

//Вычисление факториала

int F(int n)

{

if n<2 then return 1;

else return F(n-1)*n;

}

14 Программирование для операционной системы WINDOWS.

В windows есть два типа программ: GUI-приложения и консольные приложение. Консольные программы похожи на DOS-программы, они выполняются в поле подобном DOS. Большинство используемых программ – это GUI-приложения, у них есть графический интерфейс для взаимодействия с пользователем. Это сделано, созданием окон. Почти все, что видно в Windows это окна. Сначала создается родительскоеокно, а затем его дочерние окна (контролы) такие, как окна редактирования, статистические контролы , кнопки и.т.д. Каждое окно имеет имя класса. Для родительского окна определяется собственный класс. Для контролов можно использовать стандартные классы окон (такие как EDIT, STATIC, BUTTON). Далее создается окно с сообщениями, по следующему прототипу функции: MassagerBox PROTO hwnd: Dword, IpText: Dword, IpCaption: Dword, uType: Dword Thwnd – хэндл родительского окна, можно считать хэндл число, представляющее окно. IpText – указатель на текст, который нудно отобразить в клиентской части окна сообщения. Указатель на текстовую ссылку == адрес этой строки . IpCaption – указатель на заголовок окна сообщения. uType устанавливает иконку, число и вид кнопок окна.

МПТ 1. Микропроцессорная система (МПС) представляет собой функционально законченное изделие, состоящее из одного или нескольких устройств, главным образом микропроцессорных. Микропроцессорная система может рассматриваться как частный случай электронной системы, предназначенной для обработки входных сигналов и выдачи выходных сигналов. В качестве входных и выходных сигналов при этом могут использоваться аналоговые сигналы, одиночные цифровые сигналы, цифровые коды, последовательности цифровых кодов. Внутри системы может производиться хранение, накопление сигналов (или информации), но суть от этого не меняется. Если система цифровая (а микропроцессорные системы относятся к разряду цифровых), то входные аналоговые сигналы преобразуются в последовательности кодов выборок с помощью АЦП, а выходные аналоговые сигналы формируются из последовательности кодов выборок с помощью ЦАП. Обработка и хранение информации производятся в цифровом виде. Характерная особенность традиционной цифровой системы состоит в том, что алгоритмы обработки и хранения информации в ней жестко связаны со схемотехникой системы. То есть изменение этих алгоритмов возможно только путем изменения структуры системы, замены электронных узлов, входящих в систему, и связей между ними. Естественно, это практически невозможно сделать в процессе эксплуатации, обязательно нужен новый производственный цикл проектирования, изготовления, отладки всей системы. Именно поэтому традиционная цифровая система часто называется системой на «жесткой логике». Системы на «жесткой логике» хороши там, где решаемая задача не меняется длительное время, где требуется самое высокое быстродействие, где алгоритмы обработки информации предельно просты. А универсальные, программируемые системы хороши там, где часто меняются решаемые задачи, где высокое быстродействие не слишком важно, где алгоритмы обработки информации сложные.

2. Микропроцессор - процессор, выполненный в виде одной либо нескольких взаимосвязанных интегральных схем. Микропроцессор состоит из цепей управления, регистров, сумматоров, счетчиков команд и очень быстрой памяти малого объема. Некоторые микропроцессоры дополняются сопроцессорами, расширяющими возможности микропроцессоров и набор выполняемых команд. Микропроцессор, как и любой другой процессор, является устройством, предназначенным для обработки или передачи данных. Он часто не имеет памяти, средств ввода-вывода данных. Эти задачи решаются внешними (по отношению к микропроцессору) интегральными схемами. Размеры слов, с которыми работают микропроцессоры, все время растут. Все больше используются 32- и 64-разрядные микропроцессоры. Последние позволяют резко увеличивать адресуемую память и размер файлов, с которыми работают. Это, в свою очередь, увеличивает быстродействие микропроцессоров. В тех случаях, когда память и средства ввода-вывода размещаются на той же подложке интегральной схемы, что и микропроцессор, последний превращается в микрокомпьютер. Микроконтроллер является специализированным микрокомпьютером, применяемым для управления различными устройствами. Например, принтерами, терминалами, аппаратами передачи данных. Микроконтроллеры нередко выпускаются сериями по несколько миллионов штук. Создание микропроцессоров позволяет уменьшить стоимость и размеры технических средств обработки информации, увеличить их быстродействие, снизить энергопотребление. Первый микропроцессор корпорации Intel 4004 на четырех кристаллах появился в 1971 г. Микропроцессор имел 4-битовую шину, адресуемую память 4,5 Кбит и выполнял 45 команд. Сейчас микропроцессоры выпускаются многими производителями. На их основе создается подавляющее число компьютеров. Некоторые микропроцессоры могут быть дополнены сопроцессорами, расширяющими возможности первых и набор выполняемых команд. Микропроцессор является основным компонентом микрокомпьютера. Простейшие микропроцессоры используются в компьютерных карточках (пластиковая карточка со встроенными в нее микропроцессором, программным обеспечением и энергонезависимым запоминающим устройством). Наряду с универсальными производятся специальные микропроцессоры, которые выполняют ограниченный набор функций, но они дешевле и потребляют меньше электроэнергии.

3. Типы адресации и система команд. Все команды, выполняемые процессором, образуют систему команд процессора. Структура и объем системы команд процессора определяют его быстродействие, гибкость, удобство использования. Всего команд у процессора может быть от нескольких десятков до нескольких сотен. Система команд может быть рассчитана на узкий круг решаемых задач (у специализированных процессоров) или на максимально широкий круг задач (у универсальных процессоров). Коды команд могут иметь различное количество разрядов (занимать от одного до нескольких байт). Каждая команда имеет свое время выполнения, поэтому время выполнения всей программы зависит не только от количества команд в программе, но и от того, какие именно команды используются.Способы адресации: 1)Регистровая : Add R4,R3 - Требуемое значение в регистре 2)Непосредственная или литеральная: Add R4,#3 - Для задания констант 3)Базовая со смещением: Add R4,100(R1) - Для обращения к локальным переменным 4)Косвенная регистровая: Add R4,(R1) - Для обращения по указателю или вычисленному адресу 5)Индексная: Add R3,(R1+R2) - Иногда полезна при работе с массивами: R1 - база, R3 – индекс 6)Прямая или абсолютная: Add R1,(1000) - Иногда полезна для обращения к статическим данным 7)Косвенная: Add R1,@(R3) - Если R3-адрес указателя p, то выбирается значение по этому указателю 8)Автоинкрементная: Add R1,(R2)+ - Полезна для прохода в цикле по массиву с шагом: R2 - начало массива 9)Автодекрементная: Add R1,(R2)- - Аналогична предыдущей.Обе могут использоваться для реализации стека 10)Базовая индексная со смещением и масштабированием: Add R1,100(R2)[R3] - Для индексации массивов.

4. Структура процессора. Для выполнения команд в структуру процессора входят внутренние регистры, арифметико-логическое устройство (АЛУ, ALU — Arithmetic Logic Unit) , мультиплексоры, буферы, регистры и другие узлы. Работа всех узлов синхронизируется общим внешним тактовым сигналом процессора. То есть процессор представляет собой довольно сложное цифровое устройство (рис. 1.4).

Рис. 1.4.  Пример структуры простейшего процессора.

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

5. Программный обмен информацией является основным в любой микропроцессорной системе. Он предусмотрен всегда, без него невозможны другие режимы обмена. В этом режиме процессор является единоличным хозяином (или задатчиком, Master) системной магистрали. Все операции (циклы) обмена информацией в данном случае инициируются только процессором, все они выполняются строго в порядке, предписанном исполняемой программой. Процессор читает (выбирает) из памяти коды команд и исполняет их, читая данные из памяти или из устройства ввода/вывода, обрабатывая их, записывая данные в память или передавая их в устройство ввода/вывода. Путь процессора по программе может быть линейным, циклическим, может содержать переходы (прыжки), но он всегда непрерывен и полностью находится под контролем процессора. Ни на какие внешние события, не связанные с программой, процессор не реагирует. Все сигналы на магистрали в данном случае контролируются процессором.

6. Обмен по прерываниям используется тогда, когда необходима реакция микропроцессорной системы на какое-то внешнее событие, на приход внешнего сигнала. В случае компьютера внешним событием может быть, например, нажатие на клавишу клавиатуры или приход по локальной сети пакета данных. Компьютер должен реагировать на это, соответственно, выводом символа на экран или же чтением и обработкой принятого по сети пакета. Этот режим предпочтительно применять при управлении в режиме реального времени, при коротких импульсных сигналов которые можно пропустить во время программного опроса.

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