Понятие алгоритма: рекурсивные функции, системы текстовых замен.

Стр 1 из 2Следующая ⇒

Понятие алгоритма: рекурсивные функции, системы текстовых замен.

Алгоритм — конечная последовательность действий, приводящих к результату.

Терминистический — для любой последовательности шагов алгоритма, он заканчивается

за конечное число шагов.

Детерминированный — независимо от количества шагов результат определяется однозначно.

Детерминистический — нет никакой последовательности в выборе следующего шага.

Свойства алгоритма:

1.Конечность 2.Определенность 3.Результативность 4.Массовость

5.Состоит из конечного числа шагов 6.Эффективность

Алгоритм Евклида — Находит НОД двух чисел (вычитает наиб. и наим. и сравнивает)

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

1) Оператор рекурсии строит рекурсивную функцию следующим образом: значение искомой функции при нулевом значении главного дополнительного аргумента считать значением функции f1, а для последующего значения главного дополнительного аргумента значение функции f2. Для предыдущего значения ГДА и для значения ВДА, совпадающего со значением искомой функции на предыдущем шаге: f(0)=f1; f(i)=fi(i, f(i)); Пример (для функции f(x)=x-1):

f:: =R {φ 0, ψ 2, 1(x, y), x(y)}

f (0)=y0=0

f(1)=f2(0, 0)= ψ 2, 1(0, 0)=0

f(2)= f3(0, 0)= ψ 2, 1(1, 0)=1

2)Оператор подстановки и суперпозиции: Сначала вычисляются значения f1 и f2 и используют как аргумент для вычисления функции F: Ʈ (y)=λ (λ (y))=λ (y’)=y’’

3)Оператор минимизации или построения по первому нулю.

f:: =μ {f1, y}; f(x1,..xn)= μ {f1(x1,..xn, y), y}

Замена s-> t применение правила v-> w, если есть слова a, v, w, z ЄV*, такие что справедливо: s=a*v*z; t=a*w*z

Системы счисления, переводы чисел из одной позиционной системы в другую.

Система счисления — совокупность правил наименований и записи числа.

Позиционные/Непозиционные — значение цифры числа зависит/не зависит от ее положения.

1. 2-> 10 2. 8-> 10. 3. 10-> 2 4. 2-> 8 5. 8-> 2 6. 8-> 16.

Понятие подпрограммы, функции, возвращающей/не возвращающей значение в

С/С++, описание и использование.

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

Назначение:

1)Позволяет избегать дублирования программы, делает ее короче.

2)Делает структуру программы четкой и более понятной.

3)Подпрограммы позволяют расширять языки программирования, добавив новые

функции, операции, операторы, процедуры.

Функция — именованная последовательность описаний и операторов, выполняющая какое-либо законченное действие. Может принимать параметры возвращать значения.

Пример.

Функция возвращающая сумму 2-х чисел:

#include < iostream>

Using namespace std;

Int sum(int x, int y){return x+y; }

Int main() {int a=5, b=6, c; C=sum(a, b); Cout< < ”sum=”< < c< < endl; Cout< < ”sum=”< < sum(a, b);

Return 0; }

В С\С++ используется один тип подпрограмм — функция, но они могут выдавать один результат и тогда обращение к ним — указатель функции и в этом случае обращение-операнд, и когда несколько результатов и выходные параметры-результаты, а в С — это функции не возвращающие значение.

Пример.

#include < stdio.h>

Void p (int k(по значению), int *d(по адресу указатель))

{ Int j; *d=1; For (j=2; j< =k; j++) *d=*d*j; Return; }

Передача параметров в подпрограмму, параметры входные и выходные, параметры, передаваемые по значению и по адресу.

Формальные — Параметры, указанные в описании программы.

Фактические — В обращении к программе.

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

2)Выходные (получают значения в подпрограмме, передаются по адресу)

Пример: #include< iostream.h>

# include< conio.h>

Void fun f(int I; int *j; int & h){ i++; (j*)++; k++; };

int main() {int i=1; j=2; k=3; cout< < ”ijk/n”; cout< < i< < “ “< < j< < “ “< < k< < “/n”;

fun(i, & j, k); cout< < i< < “ “< < j< < “ “< < k< < “/n”; return 0; }

I j k

1 2 3

1 3 4

Использование подпрограмм, параметры формальные, локальные, глобальные, обращения к подпрограммам, фактические параметры.

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

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

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

Достоинства подпрограмм: 1) Избежание дублирования одинаковых частей программы. 2) Делает структуру программы более четкой и понятной. 3) Отдельные подпрограммы можно хранить в отдельных файлах. 4) позволяет расширить язык программирования. 5) позволяет повторно использовать раннее разработанные программы.

Формальные — параметры, указанные в описании подпрограммы.

Фактические — указанные в обращении к ней

Локальные — все величины, описанные в подпрограмме, область действия - тело ф-ии.

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

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

7.Рекурсивные подпрограммы, примеры рекурсивных функций в С/С++.

Рекурсия — вызов функции из нее же самой, непосредственно.

Глубина рекурсии — количество вложенных вызовов функции или процедуры.

Функция Рекурсивная — если она вызывает сама себя в качестве вспомогательной.

Подпрограмма Рекурсивная — если содержит обращение к самой себе.

n! =1 при n=0 и n! =1*2*3*...*n при n> 0 – итерационное(итеративное) определение

n! =1 при n=0 и n! =(n-1)! *n при n> 0 — рекурсивное определение

Рекурсия Прямая — подпрограмма обращается сама к себе.

Рекурсия Косвенная — несколько подпрограмм обращается друг к другу.

#include < iostream> using namespace std;

unsigned long F(short n)//рекурсивный метод

{ if (n==0 || n==1) return 1; //нерекурсивная ветвь

//шаг рекурсии — повторный вызов функции с другим параметром.

return n*F(n-1); } int main() { short n; cout< < ”n=”; cin> > n;

unsigned long f=F(n); //нерекурсивный вызов функции F

cout< < n< < ”! =”< < f< < endl; return 0; }

Очередь, реализация очереди массивом.

Очередь — линейный список, где все включения производится с одной стороны, а исключения и всякий доступ с другой; абстрактная структура данных, работающая по принципу FIFO. Доступ возможен с двух концов, существуют 2 переменные: head и tail.

Можно описать с помощью массива:

Const int n=100; float Queue[n], x; int head, tail;

Основные операции:

1)Инициализация очереди. Пусть head=0, tail=0. Head указывает на 1-ый элемент в очереди, tail – на последний или на 1-ю свободную ячейку. Сначала tail head чтобы не переполнить массив, присвоить tail значение 1 и заполнять очередь с начала массива, т.о. закольцованная структура. Чтобы отличить пустую ячейку от непустой, оставляем 1 ячейку свободной. Если пуста, то head=tail, если полна, то head = tail+1.

2) Взятие элементов. If (head == tail) cout< < ”Очередь пуста”; else {x=Queue[head];

head=head+1; if (head == n) head = 0; }

3) Добавление элемента. r=tail +1; if (r==n) r=0; if (r==head) cout< < ”Очередь полна”;

else {Queue[tail] = x; tail = r; }

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

Графическое представление очереди: имеет две точки доступа. Head – для удаления элементов, tail – для добавления элементов. Описание: struct tqueue{int inf; tqueue*next};

1)Инициализация очереди: head=NULL, tail=NULL;

2)Добавление элемента в очередь: r=new tqueue; r-> inf=x; r-> next=NULL; if(head==NULL) {head=r; tail=r; }; else{tail-> next=r; tail=r};

3)Взятие элемента из очереди: if(head! =NULL) {r=head; x=head-> inf; head=head-> next; delete r; }/*удаление первого элемента. r - указатель на 1-ый элемент. (r=NULL).*/

4)Освобождение динамической памяти, занятой очередью:

void clear_queue(tqueue*& head) {tqueue *r; while(head! =NULL) {r=head; head=head-> next; delete r; }; }

Основные понятия ООП: абстракция, инкапсуляция, полиморфизм.

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

Абстрагирование — метод решения задачи, при котором объекты разного рода объединяются общим понятием, а затем сгруппированные сущности рассматриваются как элементы единой категории.

Инкапсуляция — объединение данных с функциями, предназначенными для манипулирования этими данными в новом типе — КЛАССЕ.

Полиморфизм — многоформенность в С++; механизм, позволяющий использовать одинаковые имена для сходных по смыслу действий и методов, относящихся к различным объектам. Это означает, что один и тот же метод выполняется по разному для различных объектов.

Формат команды и директивы на Ассемблере.Примеры команд и директив.

Ассемблер — язык программирования низкого уровня => программа на нем должна пройти 3 этапа обработки.

Команда состоит из 4-х полей:

[< имя> [: ]]< код операции> [< операнды> ][; комментарии]

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

[: ] - метка внутренняя. Код операции определяет какое действие должен выполнить процессор.

Поле < операнды> содержит адреса данных или данные, участвующие в операции и местоположение результатов через “, ”.

JMP M1: команда безусловной передачи на команду с меткой М1

M1: MOV AX, BX; пересылка содержимого регистра BX в регистр AX.

Директива: [< имя> ]< код псевдо операции> < операнды> [; коменты] Код псевдооперации определяет назначение директивы. Операндов мб различное кол-во и для одной директивы. M1 DB 1, 0, 1, 0, 1; директива DB определяет 5 байтов в памяти и заполняет их 0 или 1, причем адрес первого байта М1. M2 Dv?,?,?; 3 байта ничем не заполнены, адрес первого М2. Proc; директива начала процедуры Endp; директива конца процедуры Segment; директива начала сегмента Ends директива конца сегмента.