Понятие алгоритма: рекурсивные функции, системы текстовых замен.
Алгоритм — конечная последовательность действий, приводящих к результату.
Терминистический — для любой последовательности шагов алгоритма, он заканчивается
за конечное число шагов.
Детерминированный — независимо от количества шагов результат определяется однозначно.
Детерминистический — нет никакой последовательности в выборе следующего шага.
Свойства алгоритма:
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 директива конца сегмента.
Понятие алгоритма: рекурсивные функции, системы текстовых замен.
Алгоритм — конечная последовательность действий, приводящих к результату.
Терминистический — для любой последовательности шагов алгоритма, он заканчивается
за конечное число шагов.
Детерминированный — независимо от количества шагов результат определяется однозначно.
Детерминистический — нет никакой последовательности в выборе следующего шага.
Свойства алгоритма:
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