Bikák és tehenek 1987 gém e
Bikák és tehenek
Játsszák kettő. Minden megfogan négyjegyű szám különböző számjegy, amelynek meg kell kitalálni partner (az első helyen, és lehet 0). Az természetesen az, hogy a kitaláló kéri egy bizonyos számot, és a négy különböző számokat. Ha fogant, és hívott számok összesített számadatok, hogy álljon el ugyanazon a helyen, a helyzet az úgynevezett „bika” (a továbbiakban: „b”). Ha a teljes számok, de ezek különböző helyeken, hogy a „tehén” (amelyet „a”).
Válaszul a haladás, a partner zagadchik összehasonlítja a számot a neve, és jelenti az összes „bikák” és a „tehén”. Például, ha fogant 5239 és elemzi 2735 lesz a válasz „1 ökör 2 tehén (2 * 16). 3. ábra létezik mind a számok, és ugyanazon a helyen (16), 2. és 5. ábrán, közös, de különböző helyeken (2k), 7. és 9. nem gyakori.
Lépni, és kap választ, jós kivonatok néhány információt azok fogant, és végső soron határozza meg. A játék véget ér abban a pillanatban, amikor a következő munkája során választ kap 46, azaz a több tervet talált. Az a játékos, aki kitalálja a számot gyorsabb ellenfél.
Íme egy példa. A lépések és válaszok lesz írva a táblázatban. 1.
Tegyük fel, hogy a partner fogant szám 3594, hogy meg kell kitalálni. Az első természetesen az 1568 választ adott 16. Ez azt jelenti, hogy ezekben az átgondolt csak egy számjegyet a fenti, és állt a helyén. Megpróbáljuk kitalálni, hogy anélkül, hogy vonzza még - a félreértések elkerülése végett - a többi számok. Tegyen egy másik folyamán 1586 A 16 azt mondja, hogy a helyén van egy szám 1 vagy 5. Most jön a harmadik során a 1658, és a válasz 1k mutatja. hogy gondolni egy számot a második helyen 5 és az 1, 6, 8, ez nem az. Progress in 2570 megpróbálja kideríteni a rendelkezésre álló számok 2., 7. és 16. 0. A válasz nagyon sikeres - ezeket a számokat a kívánt szám nem. Tehát egyértelmű, hogy a terv a számok száma 3, 4, 5, 9, és a második helyen - 5. Végezze el a következő során 4539. A 16 3k azt jelenti, hogy fogant az egyik szám - 3594 vagy 9543. Ha az első számjegy 3, majd 9 csak a harmadik, és ha az első 9, majd a 3 - csak a negyedik. Természetesen a 3594 és 46 válasz vezetett bennünket, hogy a cél; 16 3k válasz azt jelentené, hogy a tervezett száma 9543, ebben az esetben a párt tovább fog tartani a pályán.
A bemutatott példában látható. 1 ksbzh választott titkosítási. Az első alkalommal során zchszh egy teljes mérkőzés (x) és a szín (ek) nem volt a helyén. Így, CU válasz (a régi 16 1k). A második fogás chbb választ. A harmadik - bbchch (azonosították mind a négy színben), a negyedik - chchchch. A játéknak akkor van vége. A párt tartott négy mozog. Általában, mint láttuk, a testület célja a tíz mozog - (csak nagyon tapasztalatlan játékosok nem illik ebbe a keretbe).
Bár a leírás vesz el sok helyet, sőt a válasz megfogalmazott néhány másodperc.
Tehát, a „bikák és tehenek” van 5040 különböző szám, ami lehet, és úgy gondolja, hogy tud járni. És hány különböző válaszokat? Mindegyik felsorolt második oszlopában. 2, a 14 (nyilvánvalóan lehetetlen választ 1k 36). A vízszintes vonal egy táblázatban osztva az eseteket, amelyekben megtalálható mind a négy számjegyét, három számjegy, kettő, egy és egyik sem. A harmadik oszlop mutatja a számok száma, amely biztosítja a megfelelő válasz, hogy az első lépést. A legkellemesebb válasz, persze, 46 azonnal véget ér a játék. Amint látjuk, a legváltozatosabb lehetséges számok az 1k válasz - 1440.
Természetesen a játék kimenetelét, azaz a lépések számát, amelyekre kitalálni a számos terv, bizonyos mértékig függ az ügyben. De sok meghatározzuk, és a művészet játszik. Ez felveti azt a kérdést: mit értünk a készség a játék a „bikák és tehenek”? Végtére is, még egy kezdő játékosnak az első lépés lehet kitalálni véletlenszerűen gondolni egy számot, de ez még mindig nem beszél, hogy képes.
Tegyük fel, hogy A és B játékos játszott mérkőzés a három párt. A játékos mind a három játékot kitalálta száma Partner 5 fordulattal. B játékos két részletben sejtette száma 4 ütemű, és az egyik 9. Ki játszik a jobb? B játékos nyerte meg a meccset a pontszám 2: 1, de ez az összes stroke ő tovább. Ha például a sakkban a győzelem önmagában is fontos, függetlenül attól, hogy tart a párt, a „bikák és tehenek” csak találgatás sebesség, ütések száma ténylegesen eltöltött, és az eredmény a játék.
A két legérdekesebb megközelítést az erejét a játék a „bikák és tehenek.” Jelöli li. löketszám, amelyre a játékos kitalálja a számra i (i fut 1-5040). Bemutatjuk két jellemző a hatalmát játék „bikák és tehenek”:
A játékban az emberek mindig könnyű kitalálni, hogy ki az erősebb. A másik dolog, amikor a számítógépek. Minden játék stratégia formálása egy algoritmus, akkor lehetséges, hogy kiszámítja a száma Lave és Lmax, ezért feltételeitől függően, hogy melyik számítógépes program erősebb.
Érdemes megjegyezni, hogy a játék a kérdéses tárgy egy nagyon érdekes kutatási a számítógépen. Elég annyit mondani, hogy az írás egy programot a „bikák és tehenek” egyike volt a világ legnagyobb szakértője az amerikai programozó D. Knuth. Hazánkban számos eredményeket ezen a területen már kapott egy csoport diák a Department of Kibernetikai MISA élén docens M. Gendler.
A „bikák és tehenek” néhány évvel ezelőtt hallgatói által MISA stratégiát dolgoztak ki, amely biztosítja a találgatás akárhány hét stroke és azt találták, hogy Lmax ≥6. De ahhoz, hogy lezárja a határokat nem sikerült. Csak a közelmúltban, és a segítségével egy nagyon ötletes kombinatorikus gondolkodás és finom használatát gép képességeit, azt állapították meg, hogy az Lmax = 7 Más szóval, a játék épül egy algoritmus a „bikák és tehenek”, amely lehetővé teszi, hogy megtalálja az ismeretlen számot hét stroke, és bebizonyította, hogy a hat utas stratégia nem létezik.
Egyébként a fenti példában az elején a terv az volt, hogy rátaláljon a szám hét stroke (bár a példa viselt akadémiai jellegű, és nem célja, hogy játsszon optimálisan).
Nézzük több fél (pontosabb azt mondani, a sakk terminológiát - végződések vagy vázlatok) képviseli formájában feladatokat. Miután megvizsgálták őket, akkor kap egy jól illusztrálja a finomságok a játék a „bikák és tehenek.” Minden esetben meg kell vizsgálni, ha az ellenség válaszol az első fogás - számának meghatározására 1234 - egybeesik az egyik első öt a táblázatban. 2. Ha a válasz 46 párt tart csak egy fordulattal, és mind a többi négy esetben, adjuk el a játék, ami garantálja találgatás fogant a legkevesebb mozog. Más szóval, sok mozog, hogy pontosan tudjuk kitalálni a számot az ellenség, bármi legyen is az, de kisebb számban, nem tudjuk mindig szerencsés - a kód nem kerül nyilvánosságra.
Fél 1. Az első lépés 1234 ellenfél válaszolt 2b 2k. Mi az a legkisebb számú mozog garantált találgatás fogant?
Könnyen belátható, hogy csak hat szám fogant válaszul az első természetesen a 1234 tud válaszolni 2k 2b (táblázat. 3. Az első oszlop), és bármelyik pillanatban folyamán legalább három közülük fog adni ugyanazt a választ.
A második játék során 1356 (helyett 5. és 6. ábrák lehetne tenni, és mások, a különböző 1, 2, 3, 4). Minden lehetséges válaszok a második oszlop a táblázatban. Válasz 2b közvetlenül határozza meg a számos terv - 1324-ben (válaszul számos egyéb), 1b 1k válasz hagy két lehetőséget, és a válasz 2k - három. A harmadik ciklus 3256 (figyelembe véve a második) teszi teljesen egyértelmű - mind az öt számot adni a különböző jelöltek egy pár választ. A kötőjel a táblázatban. 3. (és minden további táblázatok) azt jelenti, hogy a megfelelő megoldás „reakció”, hogy ez egy adott számú minket nem igazán érdekel. Így a negyedik kurzus garantált válaszidő 4b, és a párt nem tart tovább, mint négy mozog.
Egy tipikus és elég nyilvánvaló tévedés, hogy sokan, akik véghez ezt a segítségével a számok játék, amelyek csak a számjegyek 1, 2, 3, 4. A logika egyszerű - ha valamennyi számok ismertek, akkor miért csatlakoztatni az új? Ez a megközelítés azonban fogant, hogy garantálja a szám határozza meg az ötödik sebesség (4b válasz).
Fél 2. Ugyanez a kérdés, hogy az első játék, de a válasz az első lépés 1b 3k.
Az első lépés 1234-nyolc számot adhat választ 1b 3k (fülre. 4). Mindenesetre a második során legalább az egyik a négy
szám adja ugyanazt a választ, és hogy tisztázza a helyzetet, kell két további fejlődéshez. A második fogás 1256 vannak osztva két csoportra; Az első csoportnak (válasz 1b 1k) tette a harmadik során a 1563 és a számok a második csoport (a válasz 2k) - Stroke 2564. után, hogy van két pár szám az egyes csoportokban igénylő újabb stroke-ot, és egy negyedik tanfolyam 1564 teljesen tisztázni a képet. Így a második fél nem tart tovább, mint öt részeket.
Fél 3. Ugyanez a kérdés, mint az előző két játék, de a válasz az első fogás 4k.
Válaszul az első természetesen a 1234 kilenc számban adhat választ 4k (fülre. 5). A második során 3102 dekódolja a két szám, és a fennmaradó hét oszt két csoportra oszlanak, amelyek közül az egyik úgy dönt, szélütés 4153, és a többi - 2456. A negyedik stroke-befejezi a rész (4b fogadja válasz).
Fél 4. Ugyanez a kérdés, mint az előző három játékot, de a válasz az első lépés a 3b.
3b válasz az első természetesen az 1234 adja a 24-es számot. Sőt, a három számjegy lehet rögzíteni a helyére négyféleképpen, mint a negyedik, hat lehetőség van: O, 5, 6, 7, 8, 9, összesen 4 * 6 = 24 lehetőség. Érdekes, hogy megtalálja, hogy a számos terv között 24 számot a szállítás nem azonos számú agyvérzés, hány nyolc szám a második játék.
Tekintsük az asztalra. 6. a. Az első négy sor, és a jelentése bármelyik számjegy 8, 9, 0. Tehát itt képviseli mind a 24 lehetőséget. Tegyen egy másik során 1567. A tölgyfalevelekkel a választás három megoldatlan számok, melyek jó harmadik pedig 8934 (fülre. 6. b). Válaszul 26 játszhatnak 1506 (6. táblázat). És ha a válasz 1k - 5634 (. Táblázat 6 g).
Kilenc számokat választ a 16. táblázat. 6, és kialakuljon az asztalra. 6 g (ismét, és hogy az egyik három érték - 8, 9, 0). A harmadik ciklus 3564 osztja őket három egyenlő csoportot, a negyedik tanfolyam számát azonosítják, és az ötödik teljes játékot haladás (4b válasz). Még mindig van hat számot, az alsó sorban a táblázat. 6, írd külön (fülre. 6 e). És ez a hat nem érti, hogy két további szélütés. Tehát ismét a párt nem tart tovább, mint öt stroke.
Az eredmények minden említett fél táblázatban foglaltuk össze. 7. A szigorú bizonyítás azt a tényt, hogy minden esetben kevesebb agyvérzés nem fogjuk hagyni.
Bontott példák azt mutatják, hogy egy okos játék a „bikák és tehenek” megköveteli a kényes matematikai számítás.