Визначити об’єм невитеклої води, якщо
a) Тіло опускається повністю у воду, потім піднімається;
Після підйому вода залишиться тільки у внутрішньому заглибленні, над елементом А(2,2)=1.
Об'єм води дорівнює 1.
b) У позицію (i0,j0) виливається об'єм води V.
Для реалізації цього алгоритму нам знадобиться структура даних "черга". Черга у програмуванні, як і черга у магазині, має початок і кінець. Якщо приходить новий елемент, він стає наприкінці черги, якщо потрібно взяти елемент із черги, він береться з її початку. Чергу представлятимемо у вигляді масиву. Нехай у нас є індекс першого – BEG та останнього FIN елементів черги (якщо черга порожня, то BEG=FIN+1; спочатку ж BEG=1, FIN=0).
Чергу опишемо так: var Queue = array [1 ... MaxQ] of element;
Тут MaxQ - максимальне число елементів у черзі, element якийсь тип даних. У задачі нижче як element можна взяти такий type element = record x: byte; y: byte; end; де element - це запис, що складається з x-ової та y-ової координати елемента матриці A=array[0..M+1,0..N+1] of integer. Індекси матриці приймають таке значення через те, що ми обрамлятимемо матрицю нульовими елементами (так буде простіше перевіряти виливання за край фігури).
З чергою можна проводити операції:
вставка в чергу InQueue,
видалення із черги OutQueue.
Procedure InQueue (x : element);beginFIN:=FIN+1; Queue[FIN]:=x; end; Procedure OutQueue (var x: element); beginx: = Queue [BEG]; BEG:=BEG+1;
Знаходимо максимальний елемент D у матриці A. Поки всі елементи в матриці A не дорівнюватимуть D, повторюємо наступну послідовність дій:
а) Знаходимо в матриці мінімальний ненульовий елемент z (якщо їх кілька, то беремо будь-який з них) і заносимо його в чергу(Черга спочатку порожня). Якщо це мінімальний ненульовий елемент z=D, то СТОП.
Спочатку вважаємо, що p=D - мінімальний граничний елемент області, заповненої елементами зі значенням z.
Фрагмент програми пошуку:
Сумарний отриманий об'єм води і шуканий.
Обрамлення матриці, згадане вище, може виглядати наступним чином: матриця [1..N, 1..M] облямовується нулями так: вводяться додаткові нульові 0-й і (N+1)-ий рядки і 0-й і (M+ 1) стовпці
var A: array[0..N+1,0..M+1] of byte;for i:=1 to N do beginA[i,0]:=0; A [i, M + 1]: = 0; 0; A[N+1,j]:=0;end;
Завдання №23
Ханойські вежі
Є три стрижні A, B, і C. На стрижень A надіто N дисків, нагорі найменший, кожен наступний диск більший за попередній, а внизу найбільший. На інші стрижні дисків не надіто. Необхідно перенести диски зі стрижня A на стрижень C, користуючись стрижнем B як допоміжним, так, щоб диски на стрижні C розташовувалися в тому ж порядку, в якому вони розташовуються на диску A перед переміщенням.
Під час переміщення ніколи не можна класти більший диск на менший.
Рекурсивний метод
Для того, щоб перекласти всю піраміду, треба спочатку перекласти все, що вище найбільшого диска, з першого на допоміжний стрижень, потім перекласти це найбільший диск з першого на третій стрижень, а потім перекласти піраміду, що залишилася, з другого на третій стрижень, користуючись першим стрижнем, як допоміжним.
дана процедура переносить N дисків зі стрижня A на стрижень C
користуючись B як допоміжним, дотримуючись правил
процедура "Перенести" (A, B, C, N)
// Якщо диск лише один, то требайого перенести безпосередньо
зняти диск зі стрижня A та покласти на стрижень C;
повернення з процедури;
// Переносимо всі диски, крім найбільшого зі стібня
// A на стрижень B
// Переносимо найбільший диск зі стрижня A на стрижень C
зняти диск зі стрижня A та покласти на стрижень C;
// Переносимо всі диски зі стрижня B на стрижень C поверх
// Найбільшого диска
повернення з процедури;
кінець процедури "Перенести";
procedure Solve (n: integer; a, b, c: Char);
Writeln('Перемістити диск зі стрижня', a, 'на стрижень',b);
Нерекурсивний метод
Стрижню, на якому диски знаходяться на початку, дамо номер 0; стрижня, на який їх треба перенести - номер 2; і, відповідно, стрижню, що залишився - номер 1. Нехай всього дисків N. Занумеруємо диски в порядку збільшення радіуса числами 0,1,2. N-1. Як відомо, завдання вирішується за 2 N-1 ходи. Занумеруємо ходи числами 1,2. 2 N-1. Будь-яке натуральне число i представимо у вигляді i=(2t+1)*2 k , де t і k - цілі (тобто як добуток непарного числа на деякий ступінь двійки). Так ось, на i-му ході переноситься диск номер k зі стрижня номер ((-1) N-k * t mod 3) на стрижень номер ((-1) N-k * (t + 1) mod 3).
Хід k(диск) t Со_стрижня Hа_стрижень Стрижні