181

Re: Цікаві задачі

А відколи це [formula]\textit{k}\log(n) = O(\log(n))[/formula]? k - не фактор?

182

Re: Цікаві задачі

Yola написав:

Знайти 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].

183

Re: Цікаві задачі

2 koala, Якщо [formula]k \ll n,[/formula] то ні.
2 quez, мені це питання формулювали без [formula]k \ll n,[/formula] то я спочатку так і написав, потім вже додав умову.

так як щодо [formula]\textit{k}\log k.[/formula]

184

Re: Цікаві задачі

Гм.. просто потрібно використати ще одну купу, а першу обходити як дерево. Тут ми вважаємо, що купа зберігається як масив.

Тобто всі елементи дерева, які є кандидатами у наступний найбільший елемент зберігаються у другій купі.

185

Re: Цікаві задачі

Задані два слова - початкове і кінцеве, також словник з якого можна вибирати проміжні слова. Знайти найкоротшій шлях від початкового до кінцевого слова по словах зі словника за умови, що кожен перехід повинен змінювати слово на одну букву.

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

hit->hot->...->cog

186

Re: Цікаві задачі

Пишу елементарні функції, одна для двох слів знаходить відстань, інша, використовуючи першу, будує граф із списку. Гуглю алгоритм пошуку найкоротшого шляху в графі, реалізовую або підключаю.

Подякували: Yola, Arete2

187 Востаннє редагувалося Yola (19.07.2015 09:51:46)

Re: Цікаві задачі

Припустімо ми маємо виливницю для певної фігури. Виймати фігуру з неї можна або переносом, або обертанням. На  зображенні приклади обох. Наведіть таку двовимірну фігуру яку неможливо вийняти переносом, лише обертанням.

Post's attachments

Untitled.png 11.24 kb, 221 downloads since 2015-07-19 

188

Re: Цікаві задачі

щось такого роду?

https://www.dropbox.com/s/nt75jamtdeqfucg/fg.jpg?dl=1

Подякували: koala1

189

Re: Цікаві задачі

А так, щоб це був многокутник?

190 Востаннє редагувалося P.Y. (20.07.2015 12:20:07)

Re: Цікаві задачі

Теоретично, криволінійну фігуру можна звести до ∞-кутника.

191

Re: Цікаві задачі

якось так.

Post's attachments

uncastable_with_translation.png 27.41 kb, 239 downloads since 2015-07-20 

192 Востаннє редагувалося Yola (14.11.2015 10:15:46)

Re: Цікаві задачі

В сім"ї з двома дітьми щонайменше одна дитина це хлопчик. Яка імовірність того, що друга дитина дівчинка.

---------

У відповідь на відповідь Replace додам, що це не 1/2  :P

Можу порадити підійти систематично - розписати усі можливі виходи, розібратись які у нас є події, наприклад, щонайшенше одна дитина хлопчик - це подія, і потім вирахувати умовні ймовірності.

193

Re: Цікаві задачі

Прихований текст

1/2?

194 Востаннє редагувалося VTrim (14.11.2015 10:45:17)

Re: Цікаві задачі

50%;
Які тут можуть бути умовні ймовірності? Можна якось вплинути на стать дитини,яка з'явиться/з'явилася.?:)

195

Re: Цікаві задачі

Десь читав про серйозну суперечку на цю тему, мов можна довести що так а можна що так. Але мені все рівно 1/2 більше до душі ніж 1/3.

196 Востаннє редагувалося koala (14.11.2015 10:51:13)

Re: Цікаві задачі

Нечітко визначена умова. По-перше, не вказана ймовірність народження хлопчика/дівчини (так, вона близька до 1/2, але хлопчики все ж народжуються частіше + є ймовірність народження особи з набором хромосом XXY/X0); по-друге, не вказано, яким саме чином відбиралася родина з щонайменше одним хлопчиком (наприклад, "взяти всі родини, де є 2 дітей, і відкинути ті, де 2 дівчини" - це одна процедура, а "взяти всі родини, де є 1 хлопчик, і дочекатися народження 2-ї дитини" - зовсім інша); по-третє, невідомо, чи існує кореляція між статями дітей в родині і т.д.

Якщо ж довільно припустити

що існує рівна кількість родин з комбінаціями старша/молодша дитина ХХ, ХД, ДХ та ДД (остання не обов'язково), і взяті всі, крім останньої - то очевидно, що 2/3.

Подякували: leofun011

197 Востаннє редагувалося Yola (14.11.2015 11:00:15)

Re: Цікаві задачі

Щоб леше зрозуміти відповіть - ХХ ХД ДХ ДД. Звідси й відповідь - 2/3.

2koala, щодо впливу фази місяцю, або чи не відбувалось це в Китаї, то - не присікуйтесь. Щодо "взяти всі родини, де є 1 хлопчик, і дочекатися народження 2-ї дитини" - то в умові чітко написано - "В сім"ї з двома дітьми".

198 Востаннє редагувалося quez (14.11.2015 11:41:46)

Re: Цікаві задачі

Чому ви не переставляєте хлопчиків? Якщо хлопчик в парі з дівчинкою може бути старшим або молодшим, то хлопчик у парі з хлопчиком теж. І тоді відповідь стає банальнішою: ХcХм    ХмХс    ХcДм    ХмДc, тобто 1/2.

Подякували: Yola, leofun012

199 Востаннє редагувалося Yola (14.11.2015 12:07:15)

Re: Цікаві задачі

quez написав:

Чому ви не переставляєте хлопчиків? Якщо хлопчик в парі з дівчинкою може бути старшим або молодшим, то хлопчик у парі з хлопчиком теж. І тоді відповідь стає банальнішою: ХcХм    ХмХс    ХcДм    ХмДc, тобто 1/2.

Що я покищо додумав, то це те, що ви можете переконатись, що 2/3 все-таки правильна відповідь взявши монетку і підкинувши її 100 разів по два рази, записавши всі пари де був хоч один аверс, і потім преконатись що пар, які включають реверс серед них приблизно 2/3.

Доповнено, припустимо ви праві, тоді маємо усі варіанти такі:
ХХ
ХХ
ХД
ДХ
ДД
ДД

і виходить, що якщо першим народився хлопчик, то імовірність другого хлопчика 2/3.

200 Востаннє редагувалося quez (14.11.2015 14:56:13)

Re: Цікаві задачі

Ні, якби ви писали індекси, то побачили б, що у вас молодший брат міг би народитись раніше за старшого.