1. Задача Иосифа Флавия

Пусть по кругу стоят 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;

}

1. Задача о рюкзаке

Имеются m предметов с номерами от 0 до m-1, для каждого из которых известна масса в килограммах p_j и стоимость c_j (j = 0,1,…,m-1). Определить, какие предметы необходимо положить в рюкзак, чтобы их общая масса не превышала P кг, а общая стоимость была максимальной. Сколько предметов каждого типа он должен положить в рюкзак, чтобы суммарная ценность снаряжения была максимальной при ограничении на массу рюкзака?

Жадный алгоритм для задачи о рюкзаке состоит в следующем: Выбрать максимально дорогой предмет, стоимости C_max . Упорядочить предметы по «удельной стоимости» (стоимости деленной на вес), и набивать рюкзак наиболее «удельно дорогими» предметами, пока они влезают. Пусть стоимость этого решения C_greedy В зависимости от того, что больше, C_max или C_greedy, выбрать первое или второе решение.Задача укладки рюкзака сложна. Если перебирать всевозможные подмножества данного набора из k предметов, то получится решение сложности не менее чем O(2^k). Мы рассмотрим решение данной задачи для случая, когда все входные данные - целочисленные, сложность которого будет 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(n²)

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 элементов и обозначают C_n^k , при программировании гораздо удобнее использовать следующие рекуррентные соотношения

Обычно генерацию всех k-элементных подмножеств проводят в лексикографическом порядке, тем более что в данном случае это не приводит ни к усложнению алгоритма, ни к увеличению его вычислительной трудоемкости. Порядок подмножеств называется лексикографическим, если для любых двух подмножеств справедливо, что ранее должно быть сгенерировано то из них, из индексов элементов которого можно составить меньшее k-значное число в n-ричной системе счисления (или в десятичной, для n < 10). Идея сведения данной задачи к задаче меньшей размерности следующая. Первым элементом подмножества может быть любой элемент, начиная с первого и заканчивая (n – k + 1)-м элементом. После того, как индекс первого элемента подмножества зафиксирован, осталось выбрать k – 1 элемент из элементов с индексами, большими, чем у первого. Далее поступаем аналогично. Когда выбран последний элемент, то мы достигли конечного уровня рекурсии и выбранное подмножество можно обработать.