Друга лекція другого сезону відбудеться 30 вересня о 18 годині у конференц-залі на третьому поверсі.
Лекцію ведуть: GeKa та Олександр.
Тема: Алгоритми сортування та пошуку елементів у масивах.
На порядку денному:
- Пошук елементів у масиві.
- Прості алгоритми сортування.
- Оптимальні алгоритми сортування у загальному випадку.
- Пошук k-го найменшого елементу масиву.
От блін…Трохи туповата тема… Був на ній минулого року… Думаю, з того часу нових алгоритмів не придумали
… Хоча…))))
Нє, ну і шо нового я млжу взяти для себе на тій лекції?!
Неа, ніфіга! Я тоже так думав… Того минулого року пропустив лекцію по сортуванню(якшо памятаєш – то минулого року сортування і пошук були роздулені між собою), бо думав, шо все знаю. А на пошук пішов “за компанію тупо поржать”. Але, насправді, дізнався багато нового. Ну, може не дуже багато… Але всеодно – нові знання були, а це головне!!!
А ше я дізнався КОНКРЕТНІ приклади задачок, які робляться через бінарний пошук! Насправді, таких дуже-предуже багато. І вони зовсім не ОЧЕВИДНІ!!! Насправді, бінарний пошук можна використовувати не тільки для пошуку в масиві… Є багато – пребагато інших пристосувань! До речі, згодом на TopCoder’і була задачка з цікавим “закрученим” бінарним пошуком, але я її зробив!!! А мій знайомий(приблизно такого ж рівня як я) її не зробив, бо не був на ТІЙ лекції, і навіть не уявляв, шо туда можна всунути бінарний пошук. От-так от! Так шо ходіть на лекції, навіть на найпримітивніші(на вашу думку).
Іване, це ти кому?
Взагалі, бінарка – це пошук заданого значення для функції, яка є монотонною. Якщо значення функи – це ел-и масиву, то маєм якраз випадок з масивом. Ти просто зараз знаєш, що таке бінарка, а тоді ще не знав.
Про сортування буде цікаво, бо їх є багато. І в кожного свої переваги:)
Поки мені не розкажуть алгоритм Хана – не піду з лекції!
Зробіть щось з сайтом, бо це, певно, ненормально, коли вчора я бачив пост Івана, але не бачив пост iGenius… А Іван, відповідно, бачив.
Про шо це “алгоритм Хана”?
це алгоритм сортування, в якого нульове практичне застосування (не можу знайти деталей, хіба вичитав, що для масивів до мільярда елементів він без толку) через гігантську константу, але найкраща з усіх зараз відомих сортувань асимптотика.
А я знаю хто то запостив
На правду, тупуватих тем не буває. Так може видаватися на перший погляд, що на тій чи іншій лекції ми для себе нічого не почерпнемо, але це твердження є дуже хибним. Для прикладу, давайте розглянемо гіпотетичну лекцію про елементарні операції з цілими числами, на яку майже ніхто не прийде через вищезгадані міркування. І от на лекції виникає наступне запитання. Маємо дві змінні цілого типу (знакові, 32-х бітні). Далі ми пробуємо поділити одну з них на іншу. Перерахуєте випадки коли станеться Run Time Error. Хто може відповісти на це елементарне запитання?
Shef, а який компілятор, які в нього налаштування? Певно, можна так налаштувати, що і при спробі ділення на нуль не буде рантайм давати, а просто повертатиме якусь нісенітницю.
Мені от дуже сподобалась недавно задачка на Е-олімпі, де треба вивести частку від ділення 2 цілих 32бітних чисел (націло), або error, якщо не можна ділити одне з них на інше чи результат буде за межами 32бітного знакового.
От я потратив хвилин 3-4, не менше, щоб зрозуміти причину ВА… А виявилось, що можна так поділити одне 32бітне знакове на інше 32бітне знакове, що результат не вміститься в 32бітне знакове (тепер запитання і від мене – що на що треба ділити, щоб так вийшло?).
1) коли змінна, на яку ділимо рівна 0
2) коли одна із змінних не ініціалізована
ще є?
Розкажіть мені як можна налаштувати компілятор так, що не було RTE при діленні цілих чисел.
Якщо змінна не ініціалізована, то вона все одно містить якесь значення (сміття). У загальному випадку помилки часу виконання не буде.
Поки відповідь не повна.
Кажуть в шарпі можна ділити на нуль…
Коли оголосимо дві 32-бітні змінні(типу int), то при запусках програми на машинах, де змінна int займає лише 16 біт, отримуємо ділення на нуль, якщо напишемо щось типу такого:
-2147483648/-2147483648 щось в тому плані)
Але ж ми ділимо змінну на змінну, а не константу на константу. Власне нас цікавлять при яких значення змінних (а вони обидві 32-х бітні знакові) станеться помилка часу виконання при діленні однієї з них на іншу.
#include
using namespace std;
int main()
{
int A = -2147483648;
int B = -2147483648;
cout<<A/B<<endl;
short sA = A; // а так буде при запусках на старіших машинах, де змінна int займає 16 біт
short sB = B;
cout<<sA/sB; //Runtime ERROR!
return 0;
}
Припускаю, що (-2^32)/(-1) не поміститься в той тип =)
До речі, лекція вже закінчилась. Якщо хтось не зміг на ній бути, або забув записати домашнє завдання, нагадаю:
http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1108&rid=4ca201047b952
http://acm.timus.ru/problem.aspx?space=1&num=1306
http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1087&rid=4ca254410a11f
http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1266&rid=4ca25469e95f3
http://acm.lviv.ua/fusion/viewpage.php?page_id=9&id=1312&rid=4ca2547639060
http://acm.timus.ru/problem.aspx?space=1&num=1100
AleRD,
В тебе взагалі виходить ділення 0/0, бо від приведення типу int до short залишається тільки 2 молодші байти. А старші просто втрачаються.
DixonD: “Кажуть в шарпі можна ділити на нуль…”
Брешуть =). Тільки в дійсних числах, або перехоплюючи ексепшн, або хз як перенастроївши CLR
(-2^32)/(-1) – так, саме воно, в 32бітний не влазить.
Аналогічний проклад для бідь-якої розрядності =). Завжди від”ємних чисел на 1 більше, ніж додатніх в типі даних.
LeBron,
не зразу зрозумів, що ти сказав =)
2^32 не влазить в 32-бітний інт, а -2^32 взалить =). В тому то й весь прикол тесту
Не правда!!!
-2^32 тоде не влазить…
Ага… Виправляюсь, -2^31 =). Ідея не міняється від того.
УВАГА!!!!
Тренувальний контест відбудеться в Суботу 2-го Жовтня о 18.00 на acm.lviv.ua.
Тривалість: 4 години
Кількість задач: 7
Назва: Algorithmic Programming College Season Two Practice Contest 2
Успіхів
придумайте нові задачі!!!
Не давайте ті самі)
Я шось не дуже зрозумів пошук К – го найбільшого елемента послідовності за О(N). Може хтось якось ДОпояснити
?
Для нових задач обов’язково буде організований реальний контест. А тренувальні змагання завжди проходять на вже відомих задачах. Тут основна мета – це практика, а не змагання.
Пошук к-того найбільшого – це не надто складно, на теорії. На практиці ще треба набити руку, щоб писати таке без загонів, я юзав той метод від сили 3 рази в житті.
Суть така, що можна взяти той же кусорт, але весь час розглядати тільки ту половину, де має бути наш елемент. Де він має бути – можна визначити з того, який в нього індекс:)
http://ips.ifmo.ru/courses/course1/chE/l7/index.html – ось перше зі знайдених гуглом посилань з більш-менш доступним поясненням.
Якщо ви писали вручну швидке сортування, то цей алгоритм не буде для вас складним. Якщо я не помиляюсь, то він уже є реалізований в STL, називається ‘nth_element’, але було б добре хоча б раз чи два написати самому, щоб добре його зрозуміти.
Цікаво, що на відміну від qsort він не належить до типу ‘розділяй і володарюй’, а до так званих алгоритмів ‘зменшення розміру задачі’.
Цікаво, на лекції реально не було нічого сказано про сортування підрахунком, “корзинне сортування” і всі алгоритми цього типу, чи я просто проспав цей момент?
Не було сказано, бо було мало часу на складні типи сортувань, що йшли далі…
Якщо комусь цікаво, сортування підрахунком масиву A[n] полягає у додаткового виділенні масиву b[m] цілих чисел на всі можливі значення елементів масиву A (зрозуміло, що це можна зробити тільки, коли відомо, що в масиві А є тільки числа (чи якісь інші об”єкти) з фіксованої скінченної множини, наприклад, символи від ‘я’ до ‘я’). В масиві b зберігається кількість разів, які зустрічається елемент з відповідним номером в масиві А. Потім, пройшовшись по масиву b, і виписавши всі елементи, що мають кількість більше 1, можна отримати сортований масив. Як щось не зрозуміло – питайте…
2 PostScriptum
…наприклад, символи від ‘я’ до ‘я’)…
ти, напевно, хотів написати від ’а’ до ’я’ =)
а то, якщо тільки від ’я’ до ’я’, можна все одною іфкою зробити =)
П.С.Що за корзинне сортування? Ніколи про таке не чув.
Так, хотів сказати від ‘а’ до ‘я’, хоча від ‘я’ до ‘я’ воно теж чудово працює =)).
Сортування корисне тільки тоді, коли множина допустимих значень масиву A невелика і кожне з тих значень однозначно можна ідентифікувати числом від 0 до m. Тоді складність алгоритму складає O(n+m). Зрозуміло, що коли m>>1000000, то таке сортування не має змісту (пам”яті не вистачить).
ну.. якщо може бути не більше одного однакового елемента, то вистачить. можна булеани зробити =)
Щоб ніхто не входив в оману булами – вони в багатьох середовищах займають не 1 байт, а 2 (а може й 4…). Так що в разі жорстких обмежень по пам”яті краще використовувати char (він майже завжди займає 1 байт), або взагалі працювати з бітовими полями (то ще буде на одній з наступних лекцій).