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

Рекурсия - вычислительный процесс, направленный на решение определенной задачи таким образом, что само решение использует этот же процесс, решающий аналогичную подзадачу. В программировании под рекурсией понимают такую реализацию, в которой подпрограмма использует в своем теле вызов самой себя. Такие вызовы называют рекурсивными. Когда функция 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;

}

 

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

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

Далее создается окно с сообщениями, по следующему прототипу функции: MassagerBox PROTO hwnd: Dword, IpText: Dword, IpCaption: Dword, uType: Dword

Thwnd – хэндл родительского окна, можно считать хэндл число, представляющее окно. IpText – указатель на текст, который нудно отобразить в клиентской части окна сообщения. Указатель на текстовую ссылку == адрес этой строки. IpCaption – указатель на заголовок окна сообщения. uType устанавливает иконку, число и вид кнопок окна.

 

 

Типы данных

Все данные в программе должны быть описаны с помощью операторов объявления типа данных, имеющих следующий вид: <имя типа> <список переменных>;

Типы данных задаются ключевыми словами int (целый), long (длинный), short (короткий), unsigned (беззнаковый), char (символьный), float (действительный одинарной точности), double (действительный двойной точности), pointer (указатель), unum (перечислимый). Например, оператор int i, j; описывает переменные i и jкак целые, а оператор float t; определяет переменную t как действительную с одинарной точностью. Допустимые в языке типы данных, их размеры в битах и диапазон представления:

Тип	Размер, бит	Диапазон
unsigned char		0–255
char		-128–127
enum		-32768–32767
unsigned short		0–65535
short		-32768–32767
unsigned int		0–65535
int		-32768–32767
unsigned long		0–4294967295
long		-2147483648–2147483647
float		3.4 10^-38–3.4 10^38
double		1.7 10^-308–1.7 10^308
long double		1.7 10^-4932–1.7 10^4932
pointer		(указатели near, _cs, _ds, _es, _ss) (указатели far, huge)

Язык С поддерживает стандартные механизмы по автоматическому преобразованию одного типа данных в другой. Если в выражении при­сутствуют операнды различных типов, то они преобразуются в некоторый общий тип, при этом к каждому арифметическому операнду применяется следующая последовательность правил: char и short преобразуются в int; float преобразуется в double; если один из операндов двойной точности, то другие приводятся к двойной точности и результат будет типа double; если один из операндов типа long, то другие преобразуются в long и результат будет long; если один из операндов unsigned, то другие преобразуются в тип unsigned и результат будет иметь тип unsigned; в противном случае операнды должны быть типа int и результат будет типа int.

Преобразование типов происходит и при выполнении операции при­сваивания: значение правой части преобразуется в тип левой, при этом если преобразование идет от длинного типа к более короткому, то стар­шие разряды теряются.
40. Операции в языке C++

1. Унарные операции: 1.1. Адресные: & получение адреса операнда; * обращение по адресу или операция косвенного обращения.

1.2. Преобразования знака: - унарный минус; + унарный плюс.

1.3. Побитовые:~ инвертирования (побитового) отриц.;! логического отриц.

1.4. sizeof определение размера объекта или типа.

1.5. Увеличения и уменьшения значения: ++ инкремент, или увеличения на единицу; -- декремент, уменьшение на единицу.

1.6. Операции динамического распределения памяти: new выделения памяти; delete освобождения памяти.

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

2. Бинарные: 2.1. Аддитивные: + сложение; - вычитание.

2.2. Мультипликативные: * умножение; / деление; % получение остатка от деления целочисленных операндов (деление по модулю).

2.3.Cдвига: << левый сдвиг; >> правый сдвиг.

2.4. Поразрядные: & Поразрядная конъюнкция битовых представлений значений целочисленных операндов; | поразрядная дизъюнкция …; ^ поразрядная исключающая дизъюнкция ….

2.5.Сравнения: <,<=,>,>=,==,!= меньше, меньше равно, больше, больше равно, равно, не равно.

2.6. Логические бинарные: &&,|| и, или.

2.7. Операция присваивания: = простая форма операции присваивания.

2.8. Специальные формы операций присваивания: *=, /=, %=, +=, -=, <<=, >>=, &=, |=, ^= присвоения произведения, присвоения… и тп.

2.10. Операции обращения к компонентам класса:.* обращение к компоненте класса по имени объекта или ссылки на объект (левый операнд операции) и указателю на компоненту класса (правый операнд операции); ->* обращение к компоненте класса по указателю на объект …;:: операция доступа к компоненте класса по имени класса и имени компоненты.

2.11. Операция управления процессом вычисления значений:, запятая.

2.12. () вызов функции.

2.13. () преобразование (или приведения) типа.

2.14. [] Операция индексации.

3. Операция с тремя операндами:?: условная операция.

4. Операция typeid. Обеспечивает динамическую идентификацию типов.

41. Операторы в языке C++

Условный оператор.

if (<выражение>)<операторы1>;

[else <операторы2>;]

if, else – если, иначе. Конструкция else может отсутствовать. Если выражение – истина, то выполняется операторы1, если ложь – выполняется операторы2.

Оператор переключатель

Если необходимо выбрать один из нескольких многочисленных вариантов, то вместо if целесообразно использовать switch.

switch(<выражение>){

case<константа 1>:<операторы 1>;

case<константа n>:<операторы n>;

[default:<операторы>]

}

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

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

for(<инициализация параметра цикла>;<условие продолжение цикла>;<условие продолжения цикла>) <оператор>;

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

while(<выражение>)<оператор>;

Если выражение - true выполняется оператор, пока выражение не станет false.

Оператор с постусловием

do <оператор>;

while (<выражение>);

Сначала выполняется оператор. После проверяется выражение, если true снова выполняется оператор, пока выражение не станет false.