Фундаментальні комп’ютерні алгоритми

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Про предмет

Викладач: Франчук Олег Васильович

Лекції

Лекція №1: Алгоритмічні системи

Задачі

1. Селянський алгоритм множення. Реалізувати операцію добутку двох натуральних чисел, використовуючи лише операції суми, цілочисельного ділення на 2 та множення на 2.
2. У відрізку з цілочисельними координатами кінців, порахувати кількість точок відрізка, що мають цілочисельні координати.
3. В послідовності цілочисельних величин існує лише одне число для якого не має пари (парою вважаються два однакових значення). За один прохід знайти це число. Приклад послідовності: -3, 10, 1, 15, -3, 15, 1. Число без пари тут 10.
4. Вивести на екран десяткове представлення дробу $\frac{p}{q}, (p<q)$ до k-го знаку після крапки. $k\le1000$.

Лекція №2: Обчислювальна геометрія на площині

4. Відстань від точки до прямої

а) Для загального рівняння

Поняття орієнтованої та неорієнтованої відстані

Задачі

1. Визначити, чи буде собою контур (крива), заданий чотирма точками A,B,C,D, чотирикутником?
2. Чи є чотирикутник ABCD опуклим?
3. Чи належить точка P(x₀,y₀) трикутнику ABC?
4. Задача про павука та муху: Є кімната (прямокутний паралелепіпед), відомі її виміри: довжина l_x, ширина l_y, висота l_z(вони цілочисельні). На одній вертикальній стінці сидить павук(П), а на протилежній до нього муха(М). Визначити, яку найкоротшу відстань треба пройти павуку, щоб дістатися до мухи?. Павук може ходити по стінах, стелі та підлозі.

Лекція №6: Ігрові задачі

Види ігрових задач

Виділяють два основних види ігрових задач:

• з повною інформацією
• з неповною інформацією

Гра Баше

Умова 

Є n предметів. На кожному кроці можна забрати не більше, ніж k предметів (k < n), тобто h предметів, $1 \le h \le k$. Виграє той, хто забирає останній предмет.

Роздуми 

У кінці після нашого ходу повинно залишитись k + 1 предметів.

Розв'язання 

Для того, щоб завжди вигравати, треба на кожному ході брати кількість, яка задовольняє умові: $n\,\bmod\,(k+1)= 0$

Гра Нім

Умова 

Є k рядків, у кожному з яких n_i предметів (у загальному випадку $n_i\ne n_j$). Можна брати будь-яку кількість предметів з одного рядка (навіть весь рядок). Виграє той, хто забере останній рядок.

Розв'язання 

Виписуємо кількості предметів у стовпчик, записуємо їх двійкове представлення, рахуємо порозрядну XOR-суму. Якщо, сума дорівнює нулю, то ми програємо, якщо сума не дорівнює нулю, то є шанс виграти. Для цього робимо XOR з сумою (загальною) та рядком, шукаємо рядок, з якого можна забрати предмет - тоді сума буде дорівнювати нулю. Загальна сума у кінці ходу має бути рівна нулю.

Завдання

1. Є дві купки монет. З них можна забирати монети за наступними правилами:

• беремо 1 монету з будь-якої купки
• беремо по одній монеті з кожної купки
• беремо 2 монети з будь-якої купки

Виграє той, хто ходить останнім.
2. Варіація гри Нім. Поле з n стовпців, m рядків. З одного боку стовпчик з чорних баранів (позиція першого гравця). З іншого стовпчик білих баранів. Барани можуть ходити наступним чином: іти вперед доки не підійшли до баранів суперника (на будь-яку кількість клітинок), іти назад(на будь-яку кількість клітинок), якщо є вільні клітинки. Програє той, у кого закінчилися ходи.