- •Понятие алгоритма: рекурсивные функции, системы текстовых замен.
- •Системы счисления, переводы чисел из одной позиционной системы в другую.
- •Передача параметров в подпрограмму, параметры входные и выходные, параметры, передаваемые по значению и по адресу.
- •Использование подпрограмм, параметры формальные, локальные, глобальные, обращения к подпрограммам, фактические параметры.
- •Статические и динамические переменные, динамическая память, работа с динамическими переменными.
- •Понятие линейного связного списка, типы списков, представление стека с помощью массива, пример использования стека.
- •Использование динамических переменных для представления и работы со стеком.
- •Очередь, реализация очереди массивом.
- •Очередь, представление и реализация основных операций с помощью динамических переменных.
- •Реализация основных операций со списком: добавление, удаление, поиск.
- •Деревья, основные операции над деревьями, представление дерева массивом.
- •Двусвязные линейные списки, построение и обход бинарного дерева.
- •Операции поиска и удаления в бинарном дереве.
- •Понятие графа, представление графа на эвм.
- •Представление графа списком инцидентности, алгоритм обхода графа в глубину.
- •Представление графа списком списков, алгоритм обхода графа в ширину.
- •Технологии программирования, концепции, заложенные в ооп.
- •Основные понятия ооп: абстракция, инкапсуляция, полиморфизм.
- •Понятие объекта, его состояние и поведение, классы, определение класса и объявление класса.
- •Статические, дружественные и виртуальные поля и методы, особенности их использования.
- •Абстрактные классы, их назначение и использование.
- •Понятие области видимости: общие, личные, защищённые и опубликованные поля и методы объекта.
- •Указатель this и перегрузка методов.
- •Использование классов, различные способы инициализации.
- •Использование классов, работа с массивами и указателями на обьекты.
- •Наследование, пример использования наследования.
- •Конструкторы и деструкторы, их назначение и использование.
- •Архитектура пк, основные функциональные устройства и их назначение.
- •Мп с точки зрения программиста, регистры общего назначения.
- •Оперативная память, понятие исполняемого и физического адреса, сегментные регистры.
- •Регистр флажков, его назначение и использование.
- •Форматы данных и форматы команд, машинный формат двухадресной машины.
- •Адресация операндов, способы адресации, примеры команд с различными способами адресации.
- •Понятие команды и директивы в Ассемблере, формат команды и директивы.
- •Структура программы на Ассемблере с использованием стандартных директив сегментации.
- •Основные элементы языка Ассемблер: имена, константы, переменные, выражения.
- •Директивы определения данных и памяти, примеры.
- •Команда прерывания, команды работы со стеком.
- •Упрощённые директивы сегментирования, структура программы с использованием точечных директив, пример программы.
- •Этапы выполнения Ассемблерной программы на эвм, понятие com-файла.
- •Различие между exe - и com – файлами, требования, предъявляемые к исходному модулю, предназначенному для создания com – файла, примеры программ.
- •Понятие структурного программирования, этап проектирования – композиция и декомпозиция, понятие статической и динамической структуры программы, спецификация программы.
- •Понятие частичной и полной корректности программы, правила вывода – общий вид, правила консеквенции.
- •Правила вывода для операторов: пустого, присваивания, составного.
- •Правила вывода для операторов ветвления.
- •Правила вывода циклов с предусловием и посусловием.
Передача параметров в подпрограмму, параметры входные и выходные, параметры, передаваемые по значению и по адресу.
Параметры, указанные в описании программы – формальные, а в обращении к программе – фактические.
Формальные делят на входные (должны быть известны до обращения подпрограмме, могут передаваться и по значению, и по адресу, Мб выражения( в том числе константы, переменные))и на выходные (получают значения в подпрограмме и могут использоваться в вызывающей программе, передаются только по адресу)
Пример: #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
Параметр I передавался по значению и значение его не изменилось, j по адресу с помощью указателя, следовательно для передачи в ф-ию адреса фактического параметра используется операция взятия адреса, а в теле ф-ии для работы с таким параметром надо использовать разыменование. Параметр k передан с помощью ссылки, следовательно в заголовке стоит амперсанд, в ф-ию передается адрес амперсанда.
Использование подпрограмм, параметры формальные, локальные, глобальные, обращения к подпрограммам, фактические параметры.
Подпрограмма – отдельная структурная единица, имеющая собственное имя и реализующая вспомогательный алгоритм, который неоднократно используется в основной программе или другой подпрограмме с различными значениями некоторых величин, называемых параметрами.
Для того чтобы использовать подпрограмму, ее необходимо описать, а затем в нужном месте основной программы или другой подпрограммы обратиться к ней с конкретными значениями параметров.
Описать подпрограмму – значит выбрать для нее имя, определить величины, от которых будет зависеть вычисление подпрограммы в различных точках обращения
и записать последовательность операторов, реализующих вспомогательный алгоритм.
Достоинства использования подпрограмм
Позволяет избегать дублирования одинаковых частей программы, делая ее короче, но увеличивая время ее выполнения (за счет передачи параметров, обращения к подпрограмме, возврату из нее)
Делает структуру программы более четкой и понятной (основная программа записана более кратко, использование подпрограммы более эффективно с точки зрения разработки, отладки, модификации программы). Отдельные подпрограммы, модули, можно хранить в отдельных файлах, т.е. отдельно друг от друга.
Позволяет расширить язык программирования, добавив в него новые функции, операции и операторы-процедуры. Для любого языка программирования создана большая библиотека стандартных подпрограмм и программист, разрабатывая сложный программный продукт, создает, по сути, собственную библиотеку подпрограмм, которые затем можно использовать для разработки других проектов.
Позволяет повторно использовать ранее разработанные программы.
Параметры, указанные в описании подпрограммы, называются формальными, а указанные в обращении к ней – фактическими.
Все величины, описанные в подпрограмме, а так же формальные параметры являются локальными величинами, областью их действия является только тело функции. При обращении к функции в стеке выделяется память под все локальные величины, записываются значения регистров процессора, а также адрес возврата из подпрограммы – адрес команды, которая должна выполниться следующей после выхода из подпрограммы
При выходе из подпрограммы этот участок стековой памяти очищается, это значит, что значения локальных величин не сохраняются между обращениями к одной и той же подпрограмме.
Если значение какого-то локального параметра необходимо сохранить между вызовами, то этот параметр нужно описать статически (static int n=0). Такая статическая переменная сохраняется не в стеке, а в сегменте данных и инициализируется один раз при первом обращении к подпрограмме.
Глобальные параметры описываются вне функций, в том числе и вне main, поэтому они видны во всех функциях программы и могут использоваться для передачи данных между всеми функциями. Если имена глобальных и локальных параметров совпадают, то внутри функций локальные переменные «заменяют» глобальные, а после выхода из функции значение глобальной переменной восстанавливается. Однако с помощью операции доступа к области видимости (::) можно получить доступ к одноименной глобальной переменной.
Рекурсивные подпрограммы, примеры рекурсивных функций в С/С++
Рекурсия - вызов функции (процедуры) из неё же самой, непосредственно. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Рекурсивной называют функцию, если она вызывает сама себя в качестве вспомогательной.
Подпрограмма называется рекурсивной, если она содержит обращение к самой себе.
Функцию называют рекурсивной, если она вызывает сама себя в качестве вспомогательной
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;
}