Алгоритмы движения с заданными условиями

Фишка может двигаться по полю длины 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.

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;

}

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

Имеются 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);
}