С помощью компилятора текст преобразуется в исполняемый файл. Обработка исходных файлов происходит в три этапа. Сначала файл обрабатывается препроцессором, который выполняет операторы #include, #define и еще несколько других.
Затем, на втором этапе, компилятор создает объектный файл, в котором имеются ссылки на различные системные функции и на стандартные функции языка C++.
На третьем этапе компиляции к объектному файлу подсоединяются все функции на которые он ссылается.
Основная цель многоэтапной компиляции программ – возможность компоновать программу из многих файлов. Каждый файл представляет собой законченный фрагмент программы, который может ссылаться на функции, переменные или классы, определенные в других файлах.
Исполняемая программа представляет собой непрерывный блок, который состоит из четырех частей:
-- Програмный код
--Глобальные переменные
--Куча (Heap), где хранятся динамические переменные
--Стек (stack).
В стеке хранятся:
-Адреса возврата из функций
-Значения аргументов функций
-Локальные переменные
В языке Си существует строгое правило, в соответствии с которым все переменные и функции должны быть объявлены или определены.
В программе должно быть только одно определение функции. Удобно было бы поместить Определение функции в отдельный файл, а в других файлах в начале помещать лишь объявление, прототип функции.
Пример использования указателей на функции
Последовательность действий следующая:
Создать файл point_function.cpp
Создать файл function.cpp
Создать файл function.h
Директивы препроцессора
Назначение препроцессора - обработка исходного текста программы до ее компиляции.
Препроцессор обрабатывает собственные директивы. Эти директивы задаются, как правило, в отдельной строке и начинаются с символа ’#’.
В языке C++ можно задать следующие директивы препроцессора:
· директивы компилятора #pragma, указывающие компилятору, как именно необходимо строить объектный код;
· директива включения файла #include, с помощью которой можно включить в текст программы текст из другого файла;
· директивы условной компиляции
#if, #else, #elif, #endif, #ifdef, #ifndef, defined;
· директива определения лексем #define;
· директива отмены определения #undef
Директива #include может быть записана в одном из двух форматов:
#include < имяфайла > и #include ” имяфайла ”
Первый формат позволяет включить имя файла из тех папок, которые заданы как стандартные для хранения включаемых файлов.Второй формат дает возможность записать произвольное имя файла.
Директива # define позволяет определить новые лексемы. Ее формат:
# define имялексемы [ (параметры) ] текстлексемы
Лексемы с параметрами называют макроопределениями(макросами). Такие конструкции позволяют выполнить замещение лексем по-разному, в зависимости от фактических параметров.
19.1
При решении многих задач пользуются методом сведения данной задачи к задаче, с меньшим числом предметов. Такой метод называют методом рекуррентных соотношений.
Существует класс задач, которые обладают таким свойством: вычисляя последующие значения интересующей нас величины, мы пользуемся только фиксированным числом последних значений.
Последовательности с таким свойством называют рекуррентными
Рекурсивным называется объект, который частично определяется через самого себя.
Максимальное число рекурсивных вызовов процедуры без возвратов, которое происходит во время выполнения программы, называется глубиной рекурсии .
Число рекурсивных вызовов в каждый конкретный момент времени, называется текущим уровнем рекурсии.
В общем случае любая рекурсивная процедура включает в себя некоторое множество операторов S и один или несколько операторов рекурсивного вызова.
Безусловные рекурсивные процедура приводят к бесконечным процессам, так как практическое использо-вание процедур с бесконечным самовызовом невозможно.
Такая невозможность вытекает из того, что для каждой копии рекурсивной процедуры необходимо выделял дополнительную область памяти, а бесконечной памяти не существует.
Следовательно, главное требование к рекурсивным процедурам заключается в том, что вызов рекурсивной процедуры должен выполняться по условию, которое на каком-то уровне рекурсии станет ложным.
Если условие истинно, то рекурсивный спуск продолжается. Когда оно станет ложным, спуск заканчивается и начинается поочередный рекурсивный возврат из всех вызванных на данный момент копий рекурсивной процедуры.
Формы рекурсивных процедур.
Структура рекурсивной процедуры может принимать три разные формы:
1. Форма с выполнением действий до рекурсивного вызова
(с выполнениеем действий на рекурсивном спуске).
void Rec();
{S; if (условие) Rec();};
2.Форма с выполнением действий после рекурсивного вызова
(с выполнением действий на рекурсивном возврате).
void Rec();
{if (условие) Rec(); S;};
3. Форма с выполнением действий как до, так и после рекурсивного вызова (с выполнением действий как на рекурсивном спуске, так и на рекурсивном возврате).
void Rec();
{ S1;
if (условие) Rec();
S2;}
Динамическое программирование (ДП) — это вычислительный метод для эффективного решения задач с пересекающимися подзадачами. Возникло и сформировалось в 1950-53г. благодаря работам Р.Беллмана.
Идея динамического программирования состоит в разбиении задачи на несколько независимых подзадач, решении каждой из них, а затем вычислении результата.
Для решения подзадач этот же алгоритм применяется рекурсивно или итерационно. При этом для каждой подзадачи запоми-нается вычисленный ответ, и если на каком-то шаге встретилась подзадача второй раз, то вычисления для нее не производятся.
За счет большого количества пересекающихся подзадач это значительно уменьшает время работы.
В математике существуют числа Фибоначчи. Это числа следующего вида:1; 1; 2; 3; 5;……………
Таким образом каждое следующее число получается как сумма двух предыдущих.Рекурсивное определение для чисел Фибоначчи:
Рекурсивная функция вычисления чисел Фибоначчи
int FibR(int n)
{
if ((n == 1) || (n == 2))
return 1;
else
return FibR(n - 1) + FibR(n - 2);
}
Рекурсивный НОД
int f_nod(int x,y)
{ рекурсивная функция}
{
if (y>x) return f_nod(y,x);
else if (y<=0) return x;
else return f_nod(y,x mod y);
};
Двоичный поиск элемента в упорядоченной последовательности }
void Search_bin(int *a, int l, int r,int x)
int k,p,i,j;
{ k= (l+r) / 2;
if (a[k]==x) return k;
else
{ if (a[k] <=x)
l=k+1;
else r=k-1;
return Search_bin (a,l,r,x); }}
{поиск наибольшего элемента элемента в последовательности }
int mmax (int *a, int i,int n)
{
if (i==n) mmax=a[i];
else
if ((a[i]> mmax(a,i+1) && (i==n))
mmax=a[i];
else mmax= mmax(a,i+1,n);
}
Это задача поиска наибольшей общей последовательности, (Longest Common Subsequence, LCS) которая является подпоследовательностью нескольких последовательностей (обычно двух).
Рекурсивное решение:
int lcs_length(char * A, char * B)
{
if (*A == '\0' || *B == '\0') return 0;
else if (*A == *B)
return 1 + lcs_length(A+1, B+1);
else
return
max(lcs_length(A+1,B), lcs_length(A,B+1));
}
Итерационное решение наибольшей подпоследовательности
char* getLongComSub(char *a, char *b)
{
char **max_len,*res;
max_len= (char **) malloc(strlen (a) + 1);
res= (char *) malloc(strlen (b) + 1);
for(int i = 0; i <= strlen (a); i++)
max_len[i]= (char *) malloc(strlen (b) + 1);
for(i = strlen (a)- 1; i >= 0; i--)
{
for(int j = strlen (b) - 1; j >= 0; j--)
{ if(a[i] == b[j])
{
max_len[i][j] = 1 + max_len[i+1][j+1];
}
else
{max_len[i][j] = max(max_len[i+1][j], max_len[i][j+1]);
}
}
}
k++;
i++;
j++;
//продолжение наибольшей подпоследовательности
int j,k=0;
for(i = 0, j = 0; max_len[i][j]!= 0;)
{
if(a[i] == b[j])
{
res[k]=a[i];
res[k+1]='\0';
k++; i++; j++;
}
else
{ if(max_len[i][j] == max_len[i+1][j])
i++;
else j++; } }
return res;
}
//Палиндром
#include <stdlib.h>
#include <string.h>
void insert(int c,char *A,int n)
{
int i=0;
int len=strlen(A);
int t=len;
while(t>=n)
{
A[1+t]=A[t];
--t;
}
A[n]=c;
}
void pal(char *st, int l,int r)
{
int t,i;char ch;
if (l>=r)
return;
else
if (st[l]==st[r])
pal(st,l+1,r-1);
else
// продолжение от палиндрома
if (st[l]==st[r-1])
{
ch=st[r];
insert(ch,st,l);
proc(st,l+2,r-1);
}
else
{
ch=st[l];
insert(ch,st,r+1);
proc(st,l+1,r);
} }
void main ()
{
char x[100]="12345";
proc(x, 0,5);
puts (x);
}
Алгоритмы движения с заданными условиями
Фишка может двигаться по полю длины N только вперед. Длина хода фишки не более K. Найти число различных путей, по которым фишка может пройти поле от начала до конца. Обозначим через S(i) количество различных путей, по которым фишка может пройти поле от начала до позиции с номером i. Предположим теперь, что для любого j от 1 до i известны значения величин S(j). Задача состоит в определении правила вычисления значения S(i+1), используя значения известных величин. Легко заметить, что в позицию с номером i+1 фишка может попасть из позиций i, i-1,...,i-k. Следовательно, S(i+1)=S(i)+S(i-1)+...+S(i-k). Таким образом, вычисляя последовательно значения величин S(1), S(2),..., S(N) по описанному выше правилу, получаем значение S(N), которое и указывает общее количество различных путей, по которым фишка может пройти поле от начала до позиции с номером N.
Покупка товара наибольшей стоимости
Покупатель имеет купюры достоинством A(1),...,A(n), а продавец - B(1),..,B(m). Необходимо найти максимальную стоимость товара Р, которую покупатель не может купить, потому что нет возможности точно рассчитаться за этот товар с продавцом, хотя денег напокупку этого товара достаточно.
Опишем процедуру вычисления S.
S:=0;
i:=1;
пока (i<=N) и (C[i]<=S+1)
нц
S:=S+C[i];
i:=i+1
кц
Если значение S не меньше суммарного количества денег покупателя, то покупатель может купить товар любой доступной ему стоимости, точно рассчитавшись за покупку. Иначе P=A[1]+...+A[N]-S.
Задача Иосифа Флавия
Пусть по кругу стоят n человек, начинают считать с 1-го, и каждый k-ый выбывает. Кто останется водить?
Итак, получается такая рекуррентная зависимость:
к=2:
J(n) = 1,
J(n) = 2J(n/2) - 1, если n четное,
J(n) = 2J((n - 1)/2) + 1, если n нечетное.
Пример решения задачи с циклично связным списком:
struct people{int number; people *next;};
void Step(people *&top, int k)
{
k--;
for (k; k>1; top=top->next, k--);
people *temp=top->next;
top->next=top->next->next;
top=top->next;
delete temp;
}
//Продолжение Иосифа Флавия
void main()
{
setlocale(LC_ALL,".1251"); int n, k;
cout<<"Введите количество людей в группе?\n";
cin>>n;
cout<<"Какого по счету удаляем?\n";
cin>>k;
if (k==1)
{
cout<<"В живых останется человек с номером "<<n<<endl; return;
}
people *top=new people;
top->number=1;
people *last=top;
for (int i=2; i<=n; i++)
{
people *p=new people;
p->number=i;
last->next=p;
last=p;
}
last->next=top;
for (int i=1; i<n; i++)
Step(top, k);
cout<<"В живых останется человек с номером "<<top->number<<endl;
delete top;
}
Задача о рюкзаке
Имеются m предметов с номерами от 0 до m -1, для каждого из которых известна масса в килограммах pj и стоимость cj (j = 0,1,…, m -1). Определить, какие предметы необходимо положить в рюкзак, чтобы их общая масса не превышала P кг, а общая стоимость была максимальной.
Сколько предметов каждого типа он должен положить в рюкзак, чтобы суммарная ценность снаряжения была максимальной при ограничении на массу рюкзака?
Жадный алгоритм для задачи о рюкзаке состоит в следующем:
Выбрать максимально дорогой предмет, стоимости Cmax. Упорядочить предметы по «удельной стоимости» (стоимости деленной на вес), и набивать рюкзак наиболее «удельно дорогими» предметами, пока они влезают. Пусть стоимость этого решения Cgreedy В зависимости от того, что больше, Cmax или Cgreedy, выбрать первое или второе решение.Задача укладки рюкзака сложна. Если перебирать всевозможные подмножества данного набора из k предметов, то получится решение сложности не менее чем O (2k). Мы рассмотрим решение данной задачи для случая, когда все входные данные - целочисленные, сложность которого будет O (kW). Рассмотрим следующую функцию. Пусть R(s, n) есть максимальная стоимость предметов, которые можно уложить в рюкзак максимальной вместимости n, если можно использовать только первые s предметов из заданных k. Зададим краевые значения функции R(s, n). Если s = 0, то R(0, n) = 0 для всех n (ни один предмет нельзя брать, поэтому максимальная стоимость равна 0). Если n = 0, то R(s, 0) = 0 для всех s (можно брать любые из первых s предметов, но вместимость рюкзака равна 0).
// О рюкзаке
Cоставим рекуррентное соотношение: необходимо из предметов с номерами 1,..., s составить рюкзак максимальной стоимости, чей вес не превышает n. При этом возможно два случая: когда в максимальный рюкзак включен предмет с номером s и когда предмет s не попал в максимальный рюкзак. Если предмет s не попал в максимальный рюкзак массы n, то максимальный рюкзак будет составлен только из предметов с номерами 1,..., s - 1, следовательно, A (s, n) = A (s - 1, n). Если же в максимальный рюкзак включен предмет s, то масса оставшихся предметов не превышает n - w s, а от добавления предмета s общая стоимость рюкзака увеличивается на p s. Значит, A (s, n) = A (s - 1, n - w s) + p s. Теперь из двух возможных вариантов составить рюкзак массы <= n, из предметов 1,..., s нужно выбрать:
A (s, n) = max (A (s - 1, n),
A (s - 1, n - w s) + p s.
Ханойские башни
Есть три стержня A, B, и C. На стержень A надето N дисков, наверху самый маленький, каждый следующий диск больше предыдущего, а внизу самый большой. На другие стержни дисков не надето.
Hеобходимо перенести диски со стержня A на стержень C, пользуясь стержнем B, как вспомогательным, так, чтобы диски на стержне C располагались в том же порядке, в каком они располагаются на диске A перед перемещением.
При перемещении никогда нельзя класть больший диск на меньший.
void Move(int n, char x,y,z);
//х - А y - В z - C
{ if (n==1) scanf(“ диск 1 %d -> %d“,x,y);
else
if (n>1)
{
Move(n-1,x,z,y);
printf(“диск %2d %d ->%d”,n,x,y);
Move(n-1,z,y,x);
}
Метод быстрой сортировки Хоара
Метод быстрой сортировки массива разрботан в 1962 году профессором Оксфордского университета К. Хоаром. Алгоритм состоит в том, чтобы, выбрав некоторый элемент разделяющим, переместить все элементы меньшие (или равные) его левее, а большие – правее. После этого применить тот же ход для левой части и правой части массива, если в этой части больше одного элемента. Алгоритм – рекурсивный, т.е. соответствующая процедура обращается при реализации к самой себе. Сложность алгоритма – O(n*logn) – в среднем. В худшем случае (когда после разделения на каждом шаге один из подмассивов состоит из одного элемента, а второй – из оставшихся) сложность O(n2)
void qsort(int a[], int l, int r)
{
int i = l, j = r, p;
int x = a[(l + r)/2];
while (i <= j)
{
while (a[i] < x)
++i;
while (x < a[j])
--j;
if (i <= j)
{ p = a[i]; a[i] = a[j]; a[j] = p; i++; j--; }
}
if (l < j)
qsort(a, l, j);
if (i < r)
qsort(a, i, r);
}
Рекурсивные функции сортировки
Упорядочить элементы последовательности A=(ai), i=1..n, используя рекурсивную функцию сортировки.
void rec_sort(int *a, int i, int n) // рекурсивной функция сортировки вставками
{ if (i < n)
{ int max_el = a[i], max_ind = i;
for (int j = i; j < n; ++j)
if (a[j] > max_el)
{ max_el = a[j]; max_ind = j;}
if (max_ind > i)
{ a[i] ^= a[max_ind]; a[max_ind] ^= a[i]; a[i] ^= a[max_ind];}
rec_sort(a, i+1, n);
}}
Решение комбинаторных задач: генерация k-элементных подмножеств, генерация перестановок
Генерация k-элементных подмножеств
В комбинаторике такие подмножества называют сочетаниями из n элементов по k элементов и обозначают Cnk , при программировании гораздо удобнее использовать следующие рекуррентные соотношения
Обычно генерацию всех k-элементных подмножеств проводят в лексикографическом порядке, тем более что в данном случае это не приводит ни к усложнению алгоритма, ни к увеличению его вычислительной трудоемкости. Порядок подмножеств называется лексикографическим, если для любых двух подмножеств справедливо, что ранее должно быть сгенерировано то из них, из индексов элементов которого можно составить меньшее k-значное число в n-ричной системе счисления (или в десятичной, для n < 10). Идея сведения данной задачи к задаче меньшей размерности следующая. Первым элементом подмножества может быть любой элемент, начиная с первого и заканчивая (n – k + 1)-м элементом. После того, как индекс первого элемента подмножества зафиксирован, осталось выбрать k – 1 элемент из элементов с индексами, большими, чем у первого. Далее поступаем аналогично. Когда выбран последний элемент, то мы достигли конечного уровня рекурсии и выбранное подмножество можно обработать.
