00:01:34.268,00:01:37.268 Минко Марков: Очевидна долна граница Omega(n^2) за сортиране чрез транпсозиции 00:01:55.057,00:01:58.057 Минко Марков: транспозиция == swap(A[i], A[i+1]) 00:02:17.751,00:02:20.751 Минко Марков: Bubble sort 00:02:32.033,00:02:35.033 Минко Марков: ?? 00:02:42.028,00:02:45.028 Mario Markov: да 00:02:53.809,00:02:56.809 Irkata Wee: Еми да, защото трябва да минем през елементите 2 пъти в най-лошия случай 00:03:02.393,00:03:05.393 Trayan Gospodinov: защото има 2 for-а с по n 00:03:13.060,00:03:16.060 Trayan Gospodinov: и няма как да break-нем 00:03:19.943,00:03:22.943 George Shavov: имаме сравнение на всеки със всеки 00:03:24.843,00:03:27.843 Irkata Wee: точно това исках да кажа и аз 00:04:06.960,00:04:09.960 Христо: трябват ни 2 for цикъла и с допускане на противното няма ли да се покаже 00:04:25.079,00:04:28.079 Mario Markov: В най-лошия случай всеки елемент трябва да сравним с останалите необходени 00:04:31.777,00:04:34.777 Todor Todorov: Ако приемем, че не правим някакви безмислени работи, които просто увеличават сложността 00:05:00.851,00:05:03.851 Христо: трябва всеки да бъде сравнен в всеки елемент 00:05:03.502,00:05:06.502 Минко Марков: ИНВЕРСИИ 00:05:05.008,00:05:08.008 Mario Markov: Ок, ако знаем само за транспозициите, в най-лошия случай ще разменим всеки с всеки 00:05:05.324,00:05:08.324 Petar Angelov: ако масивът е в ненарасващ ред? 00:05:12.026,00:05:15.026 Минко Марков: ИНВЕРСИИ 00:05:28.106,00:05:31.106 Минко Марков: ?? 00:05:30.879,00:05:33.879 Христо: 1 00:06:02.032,00:06:05.032 Минко Марков: n(n-1)/2 00:06:06.659,00:06:09.659 Христо: за да сме сигурни, че сме сортирали трябва да имаме сравняване на всеки с всеки елемент 00:06:21.884,00:06:24.884 Иван Йочев: Бързо решение на зада 00:06:23.917,00:06:26.917 Иван Йочев: чата 00:06:28.684,00:06:31.684 Иван Йочев: би било с 4 сравнения 00:06:40.914,00:06:43.914 Иван Йочев: за 9 топки 00:07:19.103,00:07:22.103 Минко Марков: ?? 00:07:41.816,00:07:44.816 Yoanna Todorova: вземаме 8 от тях, ако по-тежката е сред тях правим следното: слагат се по 3 броя на везната, ако са с равно тегло - по-тежката топка е една от останалите две, тогава с още едно премерване се установява коя от тях е по-тежката. Ако везната се наклони, вземаме топките от по-тежката й страна, отделяме едната от тях, на везната слагаме другите две, отново ако са равни, по-тежката топка е онази, която не е на везната, ако са наклонени е ясно коя от двете е по-тежката. В случая, когато осемте топки ко 00:08:00.023,00:08:03.023 Ирина Куртева: аз съм я виждала 00:08:10.831,00:08:13.831 Petar Angelov: решение: вземаме произволни 6 топки, на едното блюдо слагаме произволни 3 от тях, на другото - останалите 3 ако са равни, означава, че тежката топка е измежду 3те топки, които не сме прите гляли ако не са равни, означава, че тежката топка е измежду 3те топки, които са на по- тежкото блюдо и в двата случая търсенете се свежда до намиране на тежка топка измежду 3 вземаме 1 произволна за едното блюдо и 1 за другото ако са равни, то тежката топка е тази, която не сме измерили ако една е по-тежка, то 00:08:12.432,00:08:15.432 Yoanna Todorova: В случая, когато осемте топки които сме подбрали са с равна тежест, виждайки че при поставяне на 3:3 и 1:1 няма накланяне, отново с 2 премервания виждаме че номер 9 е тази, която ни трябва 00:12:15.581,00:12:18.581 Минко Марков: ?? 00:12:18.148,00:12:21.148 Trayan Gospodinov: да 00:12:19.296,00:12:22.296 Иван-Асен Чакъров: Да 00:12:21.488,00:12:24.488 Cvetomir Cvetkov: Да 00:12:22.120,00:12:25.120 Минко Марков: ясно? 00:12:24.726,00:12:27.726 Kristian Simov: Да 00:12:26.257,00:12:29.257 Tsvetina Spasova: да 00:13:10.671,00:13:13.671 Минко Марков: може ли само 1?? 00:13:13.076,00:13:16.076 Petar Angelov: защо 2 е долна граница: нека имаме n топки: претегляне е следното нещо - вземаме x топки за първото блюдо, x за второто, и zz остават непретеглени претеглянето може да ни каже най-много следното: тежката е измежду x, x, или z в най-лошия случай ни казва, че е в най-голямото, което може да е най-малко n/3 така приложено твърдението от n=9 свеждаме веднъж до n=3 и после още веднъж до n =1 - най-малко 2 измервания 00:13:13.655,00:13:16.655 Trayan Gospodinov: ако изкараме късмет 00:13:22.893,00:13:25.893 Минко Марков: очевидно не 00:13:25.738,00:13:28.738 Katerina Koleva: аз не разбирам как свързваме топките които не са участвали в началното измерване, когато сме в средния случай 00:13:35.832,00:13:38.832 Cvetomir Cvetkov: Трябва да сме взели 2 топки и едната да е търсената 00:15:08.934,00:15:11.934 Минко Марков: ?? 00:15:14.596,00:15:17.596 Katerina Koleva: ааа, да 00:15:25.363,00:15:28.363 Katerina Koleva: да благодаря 00:17:34.325,00:17:37.325 Минко Марков: Защо не може само с едно мерене? 00:17:42.229,00:17:45.229 Иван Йочев: нечетен лрой топки 00:17:45.813,00:17:48.813 Иван Йочев: брой* 00:17:56.487,00:17:59.487 Mario Markov: Ако имаме > 3 топки става невъзможно с едно измерване 00:18:16.085,00:18:19.085 Lachezar Lubomirov: Това ни е базата 00:18:22.354,00:18:25.354 Христо: ще имаме група от топки, които няма да бъдат сравнени 00:18:42.317,00:18:45.317 Mario Markov: Защото не можем да 'изолираме' топката.. не знам как да се изкажа по-формално... ако имаме 4 топки както и да ги сложим на везната ще има 'партида' от поне 2 топки 00:18:43.608,00:18:46.608 Petar Angelov: написах по-нагоре едно предложение 00:18:44.921,00:18:47.921 Mario Markov: на везната или не на нея 00:18:58.009,00:19:01.009 Irkata Wee: 3 00:18:58.164,00:19:01.164 Cvetomir Cvetkov: > броят листа за поддървото? 00:19:00.895,00:19:03.895 Христо: 3 00:19:01.220,00:19:04.220 Mario Markov: 3 00:19:29.083,00:19:32.083 Минко Марков: колко най-много листа има кор. дърво с разклоненост 3? 00:19:44.103,00:19:47.103 Mario Markov: 3^n 00:19:44.444,00:19:47.444 Trayan Gospodinov: log3(n) горна граница ние е бройката :D 00:19:45.791,00:19:48.791 Христо: 3^h 00:19:46.001,00:19:49.001 Irkata Wee: 3^h където h е височинта 00:19:51.555,00:19:54.555 Христо: h 00:19:53.386,00:19:56.386 Irkata Wee: *височината 00:21:03.526,00:21:06.526 Минко Марков: ВСЯКО ЛИСТО ДА СЕ АСОЦИИРА с <= 1 СЪСТОЯНИЕ 00:22:25.734,00:22:28.734 Минко Марков: log_3 (n) е ДОЛНА ГРАНИЦА 00:23:18.351,00:23:21.351 Минко Марков: ясно?? 00:23:35.441,00:23:38.441 Минко Марков: За 10 топки се искат 3 мерения в най-лошия 00:23:39.085,00:23:42.085 Иван-Асен Чакъров: Да 00:23:40.798,00:23:43.798 Минко Марков: съгласни?? 00:24:06.037,00:24:09.037 Минко Марков: до 27 топки вкл долната граница е 3 00:24:34.910,00:24:37.910 Христо: ако имаме еднакви топки и само една е по-тежка, то с едно измерване можем да определим точната наредба по тегло на най-много 3 топки 00:24:35.824,00:24:38.824 Irkata Wee: ако са 27 как ще стане с 3 ? 00:24:43.668,00:24:46.668 Petra Rasheva: ясно 00:25:31.931,00:25:34.931 Irkata Wee: Ирина 00:25:35.226,00:25:38.226 Irkata Wee: да 00:28:36.647,00:28:39.647 Минко Марков: защо 24?? 00:28:37.681,00:28:40.681 Иван Йочев: да 00:28:39.807,00:28:42.807 Trayan Gospodinov: да 00:28:40.597,00:28:43.597 Katerina Koleva: да 00:29:37.497,00:29:40.497 Минко Марков: няма смисъл да започваме с различни бройки топки - защо?? 00:29:59.888,00:30:02.888 Христо: така можем да отхвърлим най-много топки с една стъпка 00:30:03.918,00:30:06.918 Trayan Gospodinov: защото не е казано колко е разликата 00:30:13.247,00:30:16.247 Иван-Асен Чакъров: Ако са различни нищо не можем да разберем 00:30:16.631,00:30:19.631 Trayan Gospodinov: може да е 10х по тежка/лека от другите 00:30:21.219,00:30:24.219 Irkata Wee: защото разликата в теглото може да дойде заради броя , а не защото там е попаднала странната 00:31:40.559,00:31:43.559 Минко Марков: ясно?? 00:31:44.715,00:31:47.715 Иван-Асен Чакъров: Да ясно 00:31:47.354,00:31:50.354 Иван Йочев: ясно 00:31:47.811,00:31:50.811 Trayan Gospodinov: да 00:31:56.675,00:31:59.675 Irkata Wee: да 00:32:04.294,00:32:07.294 Минко Марков: само 4:4 има смисъл?? 00:32:19.477,00:32:22.477 Иван Йочев: защото правим сравение и сръванието има 3 възможи резултата 00:32:31.586,00:32:34.586 Irkata Wee: 5:5 защо няма смисъл 00:32:34.234,00:32:37.234 Христо: защото ще сме сигурни, че с едно измерване ще знаем в коя група от 8 топки е странната монета 00:32:35.469,00:32:38.469 Иван Йочев: делим входа на 3 и работим върху 2 от парчетата 00:35:17.792,00:35:20.792 Минко Марков: ясно?? 00:35:29.932,00:35:32.932 Минко Марков: коренът да няма дете с >9 състояния 00:35:33.197,00:35:36.197 Минко Марков: ясно?? 00:36:02.660,00:36:05.660 Минко Марков: 3:3 00:36:38.850,00:36:41.850 Минко Марков: ясно?? 00:36:39.399,00:36:42.399 Христо: ефикасно измерване е измерване на равен брой топки по групи, а 4 е най-голямото число, което разбива всички топки на групи с равен брой топки 00:36:46.236,00:36:49.236 Irkata Wee: да 00:36:50.955,00:36:53.955 Иван-Асен Чакъров: да 00:36:57.219,00:37:00.219 Irkata Wee: да 00:36:57.364,00:37:00.364 Георги Газепов: Да 00:37:00.250,00:37:03.250 Минко Марков: чувате ли ме 00:37:01.718,00:37:04.718 George Shavov: да 00:37:25.476,00:37:28.476 Иван Йочев: след като сме направили първото сравнение как избираме топките за второто 00:37:29.805,00:37:32.805 Иван Йочев: изглеода леко произволно 00:37:38.237,00:37:41.237 Иван Йочев: изглежда* 00:37:55.130,00:37:58.130 Минко Марков: ceil ( log_3 (24) ) = 3 00:38:37.690,00:38:40.690 Irkata Wee: да 00:39:51.914,00:39:54.914 Иван Йочев: ясно 00:40:06.754,00:40:09.754 Минко Марков: 13 COIN PUZZLE 00:40:17.398,00:40:20.398 Минко Марков: ceil ( log_3 (26) ) = 3 00:41:05.108,00:41:08.108 Христо: да, защото не можем да разбием групата на групи с равен брой топки 00:41:31.111,00:41:34.111 Trayan Gospodinov: не може да направим ниво 3: да има <=3 възможности 00:41:57.461,00:42:00.461 Минко Марков: ceil ( log_3 (26) ) = 3 00:42:37.557,00:42:40.557 Минко Марков: ясно?? 00:42:42.034,00:42:45.034 Irkata Wee: тоест ако са 13 са 4 измерванията ? 00:43:42.164,00:43:45.164 Христо: ще работи ли ако кажем, че границата е log_3(2*(broq topki + 1)) 00:44:59.281,00:45:02.281 Минко Марков: comparison based sorting : A[i]