Одинадцята лекція другого сезону відбудеться 9 грудня о 18 годині у конференц-залі на третьому поверсі.
Лекцію ведуть: Brus та Lebron.
Тема: Застосування повного перебору в алгоритмічному програмуванні.
На порядку денному:
- Визначення та класифікація повного перебору.
- Оптимізація повного перебору.
- Неявні форми перебору.
Стало модно писати домашнє завдання напередодні лекції. Що ж, уже визначено домашнє завдання з основних питань лекції,
ось воно:
http://acmp.ru/index.asp?main=task&id_task=498 (повний перебір)
http://acmp.ru/index.asp?main=task&id_task=280 (повний перебір)
http://acmp.ru/index.asp?main=task&id_task=346 (оптимізація перебору)
http://acmp.ru/index.asp?main=task&id_task=371 (прекалк І роду)
http://acm.timus.ru/problem.aspx?space=1&num=1402 (прекалк І роду)
http://acm.tju.edu.cn/toj/showp3300.html (прекалк ІІ роду)
В дужках вказалі теми, що то за теми – дізнаєтесь, якщо не полінуєтесь прийти на лекцію))) Деякі із задач робляться й іншими методами, але спробуйте зробити і з використанням перебору або прекалку (хто не знає, що то таке – нехай спробує зараз здати як-небудь, а потім можна ще раз прекалком). Або ні, здайвайте різними способами, це не зашкодить.
Можливо, список задач ще доповниться, про це буде повідомлено завтра на лекції і в коментарях.
В мене є таке питання. На лекції згадали про обчислення чисел Фібоначчі через піднесення матриці в степінь. Якщо треба знайти не по модулю, то ми отримаємо довге множення і я нарахував складність N^2*logN, в той час як при додаванні отримаємо N^2. Тобто без швидкого множення додавання ефективніше. Я правий, чи я десь чогось не розумію? (Я рахував, що нам потрібно довге довжини N/3).
PrimuS, я подивився в розкладі, дифрівняння в нас з 2 курсу (з 1 семестру), це відповідь на одне з твоїх питань в процесі лекції.
PrimuS, Схоже, що складність дійсно більша… Але там багато з того N^2 насправді далеко не N і можливо навіть не прямує до нього (не впевнений, що довжина N-го числа Фібоначчі буде O(N) – це верхня оцінка) Крім того, можна в кожному розряді зберігати не 1 десяткову цифру, а 9, або взагалі числа в бінарній системі зберігати. Тоді коефіцієнт буде значно менший і хз коли множення стане повільніше за додавання. А взагалі найкращий спосіб – то перевірка! От напиши – і виклади звіт на групу =). Всім буде користь
PrimuS, провірив те, що ти згадував на лекції, про вкладеність іфок (що ми не могли гарантувати, чи дійсно можна). Ти питався, чи можна більше 7 “вкладати”.
Я спробував, 8 можна, 32 можна, 100 можна, 200 можна, 400 можна.
Далі не провіряв.
Аналогічно провірив і з циклами. Провірив, працють 8, 30, 54, 100, 136, 211, 447 вкладених цикли.
Правда, останні 2 варіанти чогось підозріло довго компілюються в студії. А в dev і різниці дуже не видно)))
Хороша оптимізація до задачі про суму квадратів, якщо перебирати останнє число – можна визначити його останню цифру “наперед” за останньою цифрою очікуваного результату (для квадратів не зовсім, для кубів – якраз так і виходить), і скоротити перебір ледь не в 10 раз.