|
Тема |
Re: Ако е за имане... [re: Пaлячo] |
|
Автор | Пoнaзнaйвaщ (Нерегистриран) | |
Публикувано | 14.10.05 17:14 |
|
|
ре вече е отговорил в едно изречение, но все пак и аз да си напиша:
100% сигурност си я имаш.
Не се иска гаранция, че в първият етап всички обикновени са минали(то даже само минаването им не върши работа - трябва и да са преброени). И да са и да не са преброени фаза2 си започва. Ако са преброени чудесно, ако не са за това си има зацикляне на фазите с по 300 дена. Когато успеят да се преброят тогава. То и резултатите от симулацията показват от 2300 до 8234(това разбира се горна граница няма, но само веднъж видях нещо към 10 000 и нещо) дена. Щом има резултати над 3500(2000+1500), то явно, че са минавали няколко пъти през фаза1 и фаза2.
С един преброител(без помощници) в 2 бита информация може се съдържа(всъшност това е една от оптимизациите на ре, коят е приложима тука):
1)вече е избран преброител
2)още не е избран преброител
Който влезе първи за втори път става преброител. Тези, които са влизали докато е било "още не е избран преброител" се считат за преброени и след избирането на преброител нищо не правят.
Разбира се за тази фаза - "избиране на преброител" трябва да се отдели време(и всеки да знае предварително колко е тази фаза): повече от 100 дена очевидно е безмислено, а дали да е 100 дена или по-малко е въпрос на калкулации.
Относно оптимизации на йерархичният модел на преброяване виж какво е писал ре. С включването и на лидера да брои обикновените затворници през първата фаза намалява средното време при мене с още 100 дена и се стига до към 3600. Другата оптимизация за избирането на лидер динамично не съм я пробвал, но той твърди, че се сваля до 3500.
Разбира се си прав, че за да са възможни оптимизациите трябва всеки да е наясно в кой пореден ден излиза. Относно всеки ден да изкарват точно по един затворник - условие 3 ми се струва, че е гарант за това.
|
| |
|
|
|