Логическа задача за процесори на космически кораб

[Fed]

Здравейте,

Представете си, че се намирате на космически кораб с [tex]n[/tex] процесора. Удря ви астероид и се развалят по-малко от [tex]\frac{n}{2}[/tex]процесора. Как с най-много [tex]n-2[/tex] въпроса можете откриете работещ процесор, като един въпрос се състои в питането какво мисли даден процесор за друг процесор (друг, т.е. без него самия). Всеки повреден процесор винаги лъже, т.е. за работещ процесор казва, че не работи и обратно, а всеки работещ винаги казва истината.

[amsara]

Imam nqkakva ideq za reshenie, no neshto ne znam kak da q formuliram,che da stane qsno.Shte se probvam da q onagledq s primeri.Nai-napred obache sledva da utochnim tova,che trqbva da razgledame dva sluchaq, v zavisimost ot vida na chisloto n - to moje da e kakto chetno,taka i nechetno.
1.Neka n e chetno chislo.Shte razgledam primer pri n=8
n=8,togava n|2=4 sa polovinata procesori.No po uslovie poveche ot polovinata rabotqt
Togava min 5 rabotqt, a 3 sa izvyn stroq
Imame pravo na n-2,toest na 8-2=6 pitaniq.Shte gi otpravim kym pyrvite poredni n-2, toest 6 procesora, kato shte gi pitame vinagi za izpravnostta na posledniq n-ti, v sluchaq 8-mi procesor.
V nai-kofti sluchaq trite razbricani procesora shte sa sred 6-te,koito razpitvame.Shte poluchim 3 polojitelni i 3 otricatelni otgovora za izpravnostta na osmiq.Toest nqmame chisleno prevyzhodstvo na polojitelnite ili otricatelnite otgovori, a ravenstvo pomejdu im.Togava razbirame,che 7 i 8 procesor sa izpravni.V ostanalite sluchai imame tyrseniq chislen preves, primerno 5 raboteshti i 1 razvalen sred sheste razpitvani,zatova neshtata stavat vednaga qsni po povod izpravnostta na posledniq.
Oh, mai ne mojah dobre da izqsnq misylta si tuk.Otivam da pomislq i vyrhu sluchaq s necheten broi procesori.

[amsara]

Dano v gorniq post e stanalo qsno kakvo imam predvid.Zashtoto sym pochti na 100% ubedena,che sym prava v razsyjdeniqta si, no syznavam che ne moga da gi obqsnq kato horata.Ideqta na gornoto e, che i v dvata sluchaq(pri mnozinstvo ili ravenstvo na opredeleni otgovori) chovek moje da razbere systoqnieto na dvata posledni procesora v redicata pri chetno n.
2.Neka razgledame sluchaq s nechetno n.Tochna polovinka nqma, imam predvid cqlo chislo. Predstaveni chrez n, broqt na razvalenite i raboteshtite procesori v nai-kofti sluchaq e (n-1)/2 razvaleni i (n-1)/2 + 1 raboteshti.Imame pravo na n-2 pitaniq.Analogichno na sluchaq pri chetniq broi procesori, shte razpitvame pyrvite n-2 procesora za izpravnostta na n-tiq.Pak imame dva sluchaq - pri ediniq procedirame po absoliutno syshtiq nachin kato pri chetnite.Samo v edin sluchai- kogato (n-1)/2 kajat che n-iq e razbrican, a ostanalite kajat che e rabotesht,neshtata ne stoqt po syshtiq nachin. Togava sys sigurnost (n-1)-iqt e v izpravnost.
Istinata e, che nai-iasno mi stana kato si vzeh za primer chislo, naprimer 9, i si nachertah tablichka s razlichnite varianti.

[allier]

Да, вярно е. Хубаво решение.

[martosss]

Аз си мисля за друг подход:
нека питаме два процесора какво мислят един за друг. Имаме две възможности:
- и двата процесора са в едно и също състояние -> и двата ще кажат, че другият работи
- двата процесора са в различно състояние -> и двата ще кажат, че другият е развален

Идеята е, че винаги и двата компютъра един за друг биха казали едно и също, тоест когато питаме 1-ви какво мисли за 2-ри, то ние по отговора автоматично се ориантираме и какво мисли 2-ри за първи.

Ще се опитаме да разделим компютрите на две групи - работещи и неработещи.
За целта хващаме за мишката 1-вият и последователно го питаме какви са всички останали без един?
След n-2 въпроса ние ще разпределим всички без последния в две категории:
-тези, за които ни е казано, че са здрави, са като номер 1, тоест те са в една група и номер 1 е в същата група;
-тези, за които ни е казано, че са развалени, са различни от номер 1.

Тогава ние ще имаме две групички:
-ако n е четно, то една от групчиките винаги ще е ?50% от броя => в нея всички компютри работят;
-ако n е нечетно, то или по-голямата групичка работят(ако е >50%), или последният работи(ако са по-равно и са по-малко от половината, примерно 3=3 при общо 7 бройки).

Идеята е, че след n-2 въпроса ще можем да разпределим както тези n-2 компютъра, така и този, с който сме задавали въпроси. С това разпределяме n-1 компютъра, с което със сигурност сме решили задачата.

Надявам се да ме разберете.
Може и да се процедира и по друг начин - всеки да пита следващият - 1-ви пита 2-ри, 2-ри пита 3-ти, ... (n-2)-ри пита (n-1)-ви, остава само един непознат, всички други се разпределят в две категории в зависимост от отговора - ако са казали, че другият работи, то те са еднакви, ако са го натопили, то те са различни.

[dgs]

Съвсем съвсем дребна бележка към написаното от martosss (даже не е бележка, а по-скоро посочване на "правописна грешка"):

Аз си мисля за друг подход:
нека питаме два процесора какво мислят един за друг. Имаме две възможности:
- и двата процесора са в едно и също състояние -> и двата ще кажат, че другият работи
- двата процесора са в различно състояние -> и двата ще кажат, че другият е развален
...

Тоя текст в цитата е по-добре (според мен) да бъде така:

нека питаме ЕДИН процесор какво мисли за ДРУГ. Имаме две възможности:
- и двата процесора са в едно и също състояние -> ще получим отговор, че другият работи
- двата процесора са в различно състояние -> ще получим отговор, че другият е развален