Сьома лекція третього сезону відбудеться 3 листопада о 18 годині у конференц-залі на третьому поверсі.
Лекція містить матеріал підвищеної складності.
Лекцію ведуть: Jarlax та Shef.
Тема: Ряди Фарея та дерева Штерна-Броко.
На порядку денному:
- Основні означення.
- Теорема Піка.
- Властивості рядів Фарея.
- Бінарний пошук по дереву Штерна-Броко.
Класно!)
Хочу ще почути лекцію підвищеної складності по факторизації.
А ще мені цікаво, як працює в Java BigInteger.nextProbablePrime().
Відгукніться хтось, чи є плани на розгляд цих питань?
А ще цікаво було б почути як зробити задачу 1255 з Тімуса ( http://acm.timus.ru/problem.aspx?space=1&num=1255 ) за О(1) складності. Бо сам я зробив за О(n*k) але там на форумі багато говориться про алгоритм О(1).
“А ще мені цікаво, як працює в Java BigInteger.nextProbablePrime().”
Сорси Java доступні в неті, я пробігся по них, там цей метод працює так:
до поточного числа додають постійно 2 і перевіряють чи є це число складним, спочатку тупо, чи ділиться на 3, 5, 7 і до 41, потім ще якісь примітивні перевірки робляться, а потім сама кульмінація перевірок – застосовується 2 методи перевірки на простість
http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test
вроді так.
Дякую, спробую закодити.
А як щодо інших питань?
Можна організувати лекцію підвищеної складності по факторизації. Всі свої побажання стосовно тем майбутніх лекцій прошу залишати в коментарях.
А чи пробував Ти сам розв’язати задачу 1255 за О(1)?
Задачки по темі:
http://projecteuler.net/problem=192
http://projecteuler.net/problem=198
http://acm.tju.edu.cn/acm/showp2798.html
http://acm.hdu.edu.cn/showproblem.php?pid=2432
http://www.spoj.pl/problems/MATHS/
http://acm.uva.es/p/v104/10408.html
http://acm.uva.es/p/v100/10077.html
Ну шо за запитання, Шеф?
Звісно пробував. Тобто, думав над цим, проте нічого так і не придумав.
Лекція по факторизації – це було б чудово.
3-є твердження мало бути дещо по інакшому сформульоване:
якщо a/b і c/d – два сусіди в ряді Ферея порядку max(b, d), і дріб p/q має сусідами a/b i c/d в деякому ряді, то p/q = (a+c)/(b+d).
В 4-у твердженні дійшли до того, що якщо a/b і c/d сусіди в ряді порядку n, то наступний елемент p/q може бути записаний як (kc – a)/(kd – b). При чому, для будь-якого цілого додатнього k, (kc – a)/(kd – b) > c/d.
Розглянемо тепер різницю (kc – a)/(kd – b) – ((k+1)c – a)/((k+1)d – b). В її чисельнику після скорочення вийде bc – ad, що за 2-ю властивістю рівне 1. Звідки випливає, що (kc – a)/(kd – b) > ((k+1)c – a)/((k+1)d – b). Таким чином, зі зростанням k дріб (kc – a)/(kd – b) спадає. Звідси, найближче до c/d значення в ряді порядку n досягатиметься при k = floor((n+b)/d).