Сьома лекція другого сезону відбудеться 4 листопада о 17 годині у конференц-залі на третьому поверсі.
Лекцію ведуть: Shef та Павло.
Тема: Вступ до теорії чисел.
На порядку денному:
- Дільники натурального числа.
- Найбільший спільний дільник та найменше спільне кратне.
- Прості числа та визначення чи є число простим.
- Решето Ератосфена та оцінка складності алгоритму.
гм, я завжди про решето ератосфена думав як про чисто теоретичний математичний об’єкт, а не практичний інформатичний…
А й справді…
До речі, цікаво, а який алгоритм складніший: припустимо, прості числа менші за 300 ми знайшли і записали у змінну константою або у файл, шукаємо наступні, менші за 90000 нехай, один алгоритм полягає в тому, щоби перебирати всі числа від 301 і 90000 і перевіряти, чи вони діляться на знайдені прості числа менші за 300, звісно, якщо хоч на одне ділиться, тоді переходимо до наступного числа, інший алгоритм за решетом ератосфена, записуємо усі числа p_k * j що вони не прості, для всіх 2 <= p_k <= 300 і для деякої множини чисел A_j(k) що взагалі то кажучи, залежить від k…
Одна з найбільших переваг решета Ератосфена – відсутність складних операцій. В цьому алгоритмі немає операцій ділення і лише одна операція множення на зовнішньому циклі.
Задачі для домашньої роботи:
Супер проста проблема (http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1004&)
Остання проблема (http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1010&)
Космозаправки(http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1022&)
Новорічна математика(http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1053&)
НОД(http://www.e-olimp.com/problems/1146)
НОД и НОК(http://www.e-olimp.com/problems/1244)
Наименьшее общее кратное(http://www.e-olimp.com/problems/1243)
Розв’язок задачі Шефа:
Ми маємо зліченну кількість варіантів початкової швидкості та зліченну кількість варіантів початкової позиції. Оскільки декартів добуток зліченних множин є зліченним, то нам досить побудувати якусь бієкцію на множину натуральних чисел, і за цією бієкцією відгадувати, де машинка.
Мені найпростішим виглядає варіант перебору зі зростанням i (модуля):
(i,0..і), (i,-і..1), (-i,0..і),(-i,-і..0), тобто перебираємо пари “Початкова швидкість, початкова координата”, і для кожної пари ми можемо, за номером запиту та цими двома значеннями, визначити в якій координаті мала би бути машинка в цей момент.
В такому разі ми для довільної пари початкової швидкості й модуля відгадаємо гарантовано за час, що не перевищує квадрат більшого за модулем з 2 значень, збільшеного на 1.
-=-=-
Розв’язав у п’ятницю на лекції з дискретки, але я на новому місці проживання ще не маю доступу до Інтернету, так що виклав тільки “з поверненням додому”.
-=-=-
А є оптимальніший розв’язок? Теоретично, його не повинно існувати, але може я просто в теорії загнався)
-=-=-
А, і хто не був на лекції, сама задачка: є машинка, яка стартує з точки з цілочисельними координатами з цілочисельною швидкістю (незмінною, тобто в момент часу k машинка в координаті k*speed+start). Раз в одиницю часу можна спробувати вгадати поточне розташування машинки. Питання – чи можна гарантовано колись вгадати і як це зробити, якщо можна?
Знайшов хорошу задачку на тематику лекції, http://acm.tju.edu.cn/toj/showp3483.html
Можете провірити, чи засвоїли матеріал про кількість дільників (те, що так старався пояснити Бойко).
Хороша ідея, спробуй її розвинути. Справа в тому, що потрібно не просто один раз вгадати де знаходиться машинка, а визначити її поведінку таким чином, щоб могти ловити її коли завгодно у майбутньому. Тобто уяви собі що ти зловив машинку у якийсь момент часу, чи зможеш ти її зловити наступного?
До речі, питання до тих хто був на лекції: Чи дійсно вона була дуже простою? Можливо надалі не варто робити такий “примітивних” занять?
З одного боку лекція була відносно проста, з іншого, тести на простоту є зовсім не очевидними і не такими “простими” (хоча вони відомі майже всім “профі”), як факторизація за корінь квадратний.
Скоріше, я б сказав, що треба робити лекції більш завантаженими. Не такими, як було, коли Жека за лекцію розказав всі можливі сортування, крім, здається, підрахунку і порозрядки (і ше п’яниці і дурного:) ), бо це було вже занадто… Але на минулій було занадто мало корисної інформації, можна більше “впихнути” в той час без шкоди для сприйняття… А якщо веде Шеф, то й сумніше/нудніше від того не стане)
-=-=-
“Тобто уяви собі що ти зловив машинку у якийсь момент часу, чи зможеш ти її зловити наступного?” – ага, значить, так?.. В цілому, там виходить знов зліченна кількість варіантів, так що далі потрібно тупо перебирати… Якщо маємо момент часу, в який ми зловили машинку (а) і точку, де зловили (с), то не важливо, за якою гіпотезою ми вибирали цю точку – в реальності машинка могла мати довільну цілочислову швидкість.
Далі перебір за швидкістю (0, -1, 1, -2, 2, -3, 3…), для кожної швидкості можем встановити гіпотетичну початкову координату (яка мала б бути, щоб в момент а машинка була в с при такій швидкості), і від неї відштовхуватись – маючи координату, швидкість і час, знаходим очікувану позицію машинки, і так поки не вгадаєм.
Так, чекаємо на повну версію розв’язку задачі про машинку!
перебираємо по н від 0 до нескінченності, вкладений цикл по м від 0 до н (початкова координата і швидкість). Для кожної пари (н,м) розглядаєм 4 випадки: (н,м), (-н,м), (н,-м), (-н,-м). Для кожного випадку визначаємо гіпотетичну координату, як н+к*м, де к – кількість часу, що пройшла від початку відліку. Тоді ми гарантовано зловим машинку не пізніше, ніж коли розглядатимем пару, яка відповідає її дійсним даним. Але може статись, що ми зловимо її і раніше. Тому після того, як вперше зловили машинку, потрібно перебирати знову. Тепер у нас уже одна невідома, оскільки швидкість можна виразити через початкову координату (якщо зловили в момент к в точці а, то початкова координата н=а-к*м, перебираючи по м від 0 до нескінченності (за принципом (м), (-м)), вираховуємо координату, в якій мала би бути машинка в цей момент, як н+(к’-к)*м, замінивши н маємо
а-к*м+(к’-к)*м=а+к’*м (де к’ – момент часу, який ми розглядаємо, к – момент, в який ми зловили машинку вперше, а – точка, де зловили).
Якщо хоч раз зловимо машинку ще раз, значить ми гарантовано розглядаємо правильну пару (н,м), отже, далі за цією парою можна в довільний момент ловити машинку.
-=-=-
З.І. Вибачайте, влом було розкладки перемикати весь час)
На жаль (чи на щастя), розв’язок є не повністю вірним. Хто знайде помилку? Достатньо просто навести приклад коли наведений алгоритм не буде працювати.
А, ще така дописка, що провірку, якщо це потрібно, треба доповнювати симетричною (до н,м симетрична м,н), бо інакше ми ніколи не потрапим на пару, скажімо, (0,1).
Зрозуміло, що в разі рівних параметрів симетричної не треба)
Добре, тоді розкажи детальніше що ти будеш робити коли вперше впіймаєш машинку.
Буду перевіряти всі швидкості по черзі (0, 1,-1, 2,-2,3,-3,4,-4…), для кожної вибираючи координату, де повинна бути машинка в цей момент (множимо часову різницю на швидкість і на стільки зміщаємось від точки першого “попадання”), і ставлячи потрібний запит.
Коли вдруге зловлю машинку – все, це вже правильна відповідь.