Cea mai simplă soluție a problemei 26 sau a vechiului C3
pe știința informaticii și TIC prin metoda vizuală "Hills and holes"
Un exemplu de rezolvare a unei probleme în cazul creșterii pietrelor în heap în două moduri, "+1" și "* 2"
Doi jucători, Petya și Vanya, joacă următorul joc. Există o grămadă de pietre în fața jucătorilor. Jucătorii merg pe rând, prima mișcare este făcută de Petya. Într-o mișcare, un jucător poate adăuga o piatră în grămadă sau poate mări cantitatea de pietre din grămadă de două ori. De exemplu, având o grămadă de 15 pietre, puteți obține o grămadă de 16 sau 30 de pietre într-o mișcare. Fiecare jucător pentru a face mișcări, există un număr nelimitat de pietre. Jocul se termină în momentul în care numărul de pietre în grămadă devine nu mai puțin de 22. Câștigătorul este jucătorul care a făcut ultima mutare, care este primul pentru a obține o grămadă, care este de 22 sau mai multe pietre.
La momentul inițial, în piatră erau pietre S, 1 <= S <=21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Finalizați următoarele sarcini. În toate cazurile, justificați răspunsul dvs.
1. a) Indicați toate aceste valori ale numărului S la care Petya poate câștiga într-o singură rundă. Justificați că ați găsit toate valorile necesare ale lui S și indicați mutarea câștigătoare pentru fiecare valoare specificată a lui S.
b) Specificați o valoare S pentru care Petya nu poate câștiga într-o mișcare, dar Petey Vanya poate câștiga cu prima sa mișcare. Descrieți strategia câștigătoare a lui Vani.
2. Specificați două astfel de valori ale lui S pentru care Petit are o strategie câștigătoare și
- Petya nu poate câștiga într-o mișcare, și
- Petya poate câștiga cu a doua mutare, indiferent de modul în care Vanya va merge.
Pentru fiecare valoare specificată de S, descrie strategia câștigătoare a lui Petit.
3. Specificați valoarea lui S, la care:
- Vanya are o strategie câștigătoare, care îi permite să câștige prima sau a doua mișcare cu orice joc Petit și
- Vanya nu are o strategie care să-i permită să câștige în primul rând.
Pentru valoarea specificată a lui S, descrie strategia câștigătoare a lui Vani.
Construiți un copac al tuturor loturilor posibile cu această strategie câștigătoare Vani (sub forma unei imagini sau a unui tabel). Pe marginea arborelui indicați cine face mutarea, în noduri - numărul de pietre în heap.
Întrebarea 1a.
Înapoi de la "victorie" determinăm limitele poziției câștigătoare inițială: 22 - 1 = 21 și 22/2 = 11
Pentru orice număr situată în limitele acestui interval, următoarea intrare este valabilă * max0 2> sau max0 = 22 * 2> 21 (încercuiască interval de sus și denotă-l kakmax0, ceea ce va însemna poziția inițială sau premiul câștigător pentru fiecare accident vascular cerebral)
1a) Petya câștigă prima mișcare la 11 <= S <= 21. Для этого достаточно число камней в куче увеличить вдвое и их всегда получится более 21.
Întrebarea 1b. Pentru a răspunde la această întrebare, trebuie să găsim poziții, să le numim în mod condiționat min0. din care toate mișcările posibile conduc la poziția inițială câștigătoare, marcată de noi ca max0. În schimb, determinăm pozițiile "suspecte" pe min0:
11/2 =? nu există o astfel de poziție. Ramane doar S = 11-1 = 10
(Dar până acum doar predpolagaemyymin0, asa ca am trage „Groapă“ două trăsături care ar însemna - nu uitați despre cele 2 mutarile posibile care vor trebui să fie sigur de a verifica)
Verificăm ipoteza pentru S = 10 cu min0. Acest test va servi drept răspuns la întrebarea 1b
La S = 10, Petya are 2 mișcări pe care nu le poate câștiga într-o mișcare, dar Petey Vanya poate câștiga cu prima sa mișcare:
Orice accident vascular cerebral Petit „10 + 1 = 11“, sau 10 * 2 = 20 sunt în poziția câștigătoare inițială Vanea că prin dublarea numărului de roci într-un teanc, primește 22 sau 40, care este mai mult de 21, iar victoria va giruetă
Prin urmare, poziția S = 10 din partea de jos cu o linie solidă (trageți o groapă) - min0 (pierderea sau pierderea inițială pentru prima mișcare):
Răspunsul la întrebarea 1b. poate fi urmatorul: La S = 10, Petya are 2 mutari pe care nu le poate castiga, dar Petey Vanya poate castiga cu prima miscare. Orice accident vascular cerebral Petit „10 + 1 = 11“ sau „10 * 2 = 20“ conduce la poziția inițială câștigătoare Vanea că prin dublarea numărului de roci într-un teanc, primește 22 sau 40, mai mult de 21 de victorii si Vanya
Întrebarea 2. Pentru ca Petya să câștige în a doua rundă, i. E. a fost în poziția max0. după mutarea lui Vanya, are nevoie de prima mutare "de a pune Vanya într-o groapă". Este clar că pot exista două astfel de poziții. valorile pe care le găsim în sens invers și neapărat verificăm ...
Prima poziție suspectă este "10-1 = 9"
S = 9. Să verificăm această poziție cu privire la garanția victoriei!
Dacă Petya ar fi jucat un pariu, ar fi făcut mișcarea "9 * 2 = 18", dar trebuie să câștige, astfel încât această mișcare este eliminată. Rămâne doar "9 + 1 = 10", iar Vanya este în "groapă" - ceea ce îl face pe Petya să câștige a doua mișcare indiferent de coborârea lui Vanya!
A doua poziție "suspectă" 10/2 = 5
S = 5. Să verificăm această poziție cu privire la garanția victoriei! Mișcarea "5 + 1 = 6" strânge jocul, deci nu este considerat (aruncat)
Rămâne doar o „5 * 2 = 10“, iar Vania este în „bine“ - ceea ce conduce la un câștig Petia al doilea curs, indiferent de modul în care vine Vania!
Dacă S = 5 și 9, Petru nu poate câștiga prima cursă, dar el poate câștiga un al doilea accident vascular cerebral și în acest scop este suficient din poziția S = 5 pentru a face o mutare „5 * 2 = 10“, trimite-se astfel Vanea poziția pierde primară sau poziția S = 9 trimite-o în aceeași poziție cu mișcarea "9 + 1 = 10"
Întrebarea 3. Vanya ar trebui să câștige, prin urmare, el trebuie să fie pe MAX0 sus, acest lucru înseamnă că Petru trebuie să fie neapărat în min0, unde a „plantat“ Vania de la max1, dar noi încă găsim astfel de poziții, dintre care Petru ar lovi cu siguranta max1
Gasim pozitiile "suspecte" care pot duce Petya la max1 cu acelasi drum de intoarcere:
9-1 = 8
9/2 =? 9 pe 2 nu este împărțită - scade
5-1 = 4
5/2 =? 5 pe 2 nu este divizat - scade
Aflăm că există doar două astfel de poziții "suspecte", dar trebuie încă verificate!
S = 8. Să verificăm această poziție pentru pierderea garantată a lui Petit!
Misiunea lui Petit este 8 + 1 = 9 și Vanya câștigă a doua mișcare
Mișcarea lui Petit este 8 * 2 = 16 și Vanya câștigă prima mișcare
S = 4. Să verificăm această poziție pentru pierderea garantată a lui Petit!
Accident vascular cerebral Petit 4 + 1 = 5 și el s-ar fi pierdut, dar această poziție este avantajoasă Pete accident vascular cerebral 4 * 2 = 8, prin aceasta Vanea cade în „groapă“ și pierde. Dar trebuie să găsim o strategie câștigătoare pentru Vanya, astfel încât poziția S = 4 este exclusă de la reclamanți și obținem "imaginea" finală:
3. Poziția S = 8 - Vanea nu este o strategie care îi va permite să câștige o primă mișcare garantat de la victoria sa depinde de progresul Petit, de ce Vania are o strategie pentru a câștiga fie primul sau al doilea curs: Dacă Petru alege un curs de „+1“ , în halda devin 9 pietre și Vanya câștigă la a doua mișcare (a se vedea răspunsul la întrebarea 2). Dacă Petya alege miscarea "* 2", Vanya câștigă prima mișcare, dublând numărul de pietre din grămadă.
Am obținut figura de mai sus poate aspira să fie ușor se mută de joc copac, linii roșii marcate în prealabil pierde (linie îngroșată - „accident vascular cerebral scurt“ sau „+1“, și subțire - „lung“ sau „* 2“), și verde - câștigătoare. (linii groase roșii pot fi trase cu humps în sus, care va coincide cu direcția ramurilor copacului "scurt" ale jocului)
În fine, imaginea strategică a câștigătorului Petit poate arăta astfel:
Cu alte metode de rezolvare a problemelor de acest tip pot fi găsite aici - arată
Trimiteți-le prietenilor: