Re: Цікаві задачі
А відколи це [formula]\textit{k}\log(n) = O(\log(n))[/formula]? k - не фактор?
Ви не увійшли. Будь ласка, увійдіть або зареєструйтесь.
Ласкаво просимо вас на україномовний форум з програмування, веб-дизайну, SEO та всього пов'язаного з інтернетом та комп'ютерами.
Будемо вдячні, якщо ви поділитись посиланням на Replace.org.ua на інших ресурсах.
Для того щоб створювати теми та надсилати повідомлення вам потрібно Зареєструватись.
Український форум програмістів → Алгоритми та структури даних, технології → Цікаві задачі
Сторінки Попередня 1 … 8 9 10 11 12 … 20 Наступна
Для відправлення відповіді ви повинні увійти або зареєструватися
А відколи це [formula]\textit{k}\log(n) = O(\log(n))[/formula]? k - не фактор?
Знайти k-й найбільший елемент у незростальній купі (MaxHeap) за [formula]O(\log(n)).[/formula]
[formula]k \ll n.[/formula]ВІДРЕДАГОВАНО:
Оскільки більше доби відповіді немає, то відповідаю я:Необхідно k разів виконати Extract_Max, часова складність [formula]\textit{k}\log(n) = O(\log(n)).[/formula]
Так ви зразу б писали всі умови. Вчора зранку я отримав [formula]O(n\log(n))[/formula] для крайнього випадку [formula]k = n[/formula].
2 koala, Якщо [formula]k \ll n,[/formula] то ні.
2 quez, мені це питання формулювали без [formula]k \ll n,[/formula] то я спочатку так і написав, потім вже додав умову.
так як щодо [formula]\textit{k}\log k.[/formula]
Гм.. просто потрібно використати ще одну купу, а першу обходити як дерево. Тут ми вважаємо, що купа зберігається як масив.
Тобто всі елементи дерева, які є кандидатами у наступний найбільший елемент зберігаються у другій купі.
Задані два слова - початкове і кінцеве, також словник з якого можна вибирати проміжні слова. Знайти найкоротшій шлях від початкового до кінцевого слова по словах зі словника за умови, що кожен перехід повинен змінювати слово на одну букву.
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
hit->hot->...->cog
Припустімо ми маємо виливницю для певної фігури. Виймати фігуру з неї можна або переносом, або обертанням. На зображенні приклади обох. Наведіть таку двовимірну фігуру яку неможливо вийняти переносом, лише обертанням.
Теоретично, криволінійну фігуру можна звести до ∞-кутника.
В сім"ї з двома дітьми щонайменше одна дитина це хлопчик. Яка імовірність того, що друга дитина дівчинка.
---------
У відповідь на відповідь Replace додам, що це не 1/2
Можу порадити підійти систематично - розписати усі можливі виходи, розібратись які у нас є події, наприклад, щонайшенше одна дитина хлопчик - це подія, і потім вирахувати умовні ймовірності.
50%;
Які тут можуть бути умовні ймовірності? Можна якось вплинути на стать дитини,яка з'явиться/з'явилася.?:)
Десь читав про серйозну суперечку на цю тему, мов можна довести що так а можна що так. Але мені все рівно 1/2 більше до душі ніж 1/3.
Нечітко визначена умова. По-перше, не вказана ймовірність народження хлопчика/дівчини (так, вона близька до 1/2, але хлопчики все ж народжуються частіше + є ймовірність народження особи з набором хромосом XXY/X0); по-друге, не вказано, яким саме чином відбиралася родина з щонайменше одним хлопчиком (наприклад, "взяти всі родини, де є 2 дітей, і відкинути ті, де 2 дівчини" - це одна процедура, а "взяти всі родини, де є 1 хлопчик, і дочекатися народження 2-ї дитини" - зовсім інша); по-третє, невідомо, чи існує кореляція між статями дітей в родині і т.д.
Щоб леше зрозуміти відповіть - ХХ ХД ДХ ДД. Звідси й відповідь - 2/3.
2koala, щодо впливу фази місяцю, або чи не відбувалось це в Китаї, то - не присікуйтесь. Щодо "взяти всі родини, де є 1 хлопчик, і дочекатися народження 2-ї дитини" - то в умові чітко написано - "В сім"ї з двома дітьми".
Чому ви не переставляєте хлопчиків? Якщо хлопчик в парі з дівчинкою може бути старшим або молодшим, то хлопчик у парі з хлопчиком теж. І тоді відповідь стає банальнішою: ХcХм ХмХс ХcДм ХмДc, тобто 1/2.
Що я покищо додумав, то це те, що ви можете переконатись, що 2/3 все-таки правильна відповідь взявши монетку і підкинувши її 100 разів по два рази, записавши всі пари де був хоч один аверс, і потім преконатись що пар, які включають реверс серед них приблизно 2/3.
Доповнено, припустимо ви праві, тоді маємо усі варіанти такі:
ХХ
ХХ
ХД
ДХ
ДД
ДД
і виходить, що якщо першим народився хлопчик, то імовірність другого хлопчика 2/3.
Ні, якби ви писали індекси, то побачили б, що у вас молодший брат міг би народитись раніше за старшого.