15.10.2020

Deschidem un abonament la simulatoare interactive pentru a ne pregăti pentru USE 2016 în informatică

Toți cei care au un portofel Visa, MasterCard, Yandex.Money și chiar un sold pozitiv pe telefonul mobil, pot comanda 60 de animații interactive unice pentru a se pregăti pentru examenul de stat unificat 2016 în informatică, fără să se ridice de pe computer.

Simulator pentru problema nr. 26 a versiunii demo a USE 2015
în informatică și TIC prin metoda „Hills and Pits”

Cea mai simplă soluție la problema 26 sau la vechiul C3
în informatică și TIC folosind metoda vizuală „Dealuri și gropi”

Un exemplu de rezolvare a problemei în cazul creșterii pietrelor într-o grămadă î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 se alternează, Petya face prima mișcare. Într-o singură mișcare, jucătorul poate adăuga o piatră la grămadă sau poate dubla numărul de pietre din grămadă. De exemplu, având o grămadă de 15 pietre, într-o singură mișcare puteți obține o grămadă de 16 sau 30 de pietre. Fiecare jucător are un număr nelimitat de pietre pentru a face mișcări. Jocul se termină în momentul în care numărul pietrelor din grămadă devine cel puțin 22. Câștigătorul este jucătorul care a făcut ultima mișcare, adică primul care primește grămada, în care vor fi 22 sau mai multe pietre.
În momentul inițial, erau pietre S în grămadă, 1<= S <=21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Finalizați următoarele sarcini. În toate cazurile, justificați-vă răspunsul.

1. a) Indicați toate aceste valori ale numărului S pentru care Petya poate câștiga într-o singură mișcare. Justificați că ați găsit toate valorile S necesare și indicați mutarea câștigătoare pentru fiecare valoare S specificată.
b) Indicați valoarea lui S, la care Petya nu poate câștiga într-o singură mutare, dar pentru orice mutare, Petya poate câștiga cu prima sa mutare. Descrieți strategia câștigătoare a lui Vanya.

2. Indicați două astfel de valori ale lui S pentru care Petya are o strategie câștigătoare și
- Petya nu poate câștiga într-o singură mișcare și
- Petya poate câștiga cu a doua sa mutare, indiferent de modul în care se mișcă Vanya.
Pentru fiecare valoare specificată a lui S, descrie strategia câștigătoare a lui Petit.

3. Specificați valoarea S la care:
- Vanya are o strategie câștigătoare care îi permite să câștige la prima sau a doua mutare în orice joc Petya și
- Vanya nu are o strategie care să-i permită să câștige cu o primă mișcare garantată.
Pentru valoarea indicată a lui S, descrie strategia câștigătoare a lui Vanya.
Construiți un copac al tuturor jocurilor posibile cu această strategie câștigătoare a lui Vanya (sub forma unei imagini sau a unei mese). Pe marginile copacului, indicați cine face mișcarea, în noduri - numărul de pietre din grămadă.

Întrebarea 1a.
Prin mișcarea inversă de la „victorie” definim limitele poziției inițiale de câștig: 22 – 1 = 21 și 22/2 = 11
Pentru orice număr din acest interval, următoarea notație este validă max0 * 2\u003e \u003d 22 sau max0 * 2\u003e 21 (schițăm această gamă de sus și o desemnăm ca max0, ceea ce va însemna poziția inițială de câștig sau câștig într-o singură mișcare)

1a) Petya câștigă cu prima mișcare la 11<= S <= 21. Для этого достаточно число камней в куче увеличить вдвое и их всегда получится более 21.

Întrebarea 1b. Pentru a răspunde la această întrebare, trebuie să găsiți poziții, să le numim condiționat min0 , din care toate mișcările posibile conduc la poziția inițială de câștig, marcată de noi ca max0 ... În mișcarea inversă, determinăm pozițiile „suspectate” pe min0 :
11/2=? nedivizat în totalitate, prin urmare, nu există o astfel de poziție. Rămâne doar S \u003d 11-1=10
(dar până acum acest lucru este doar un presupusmin0 așa că desenăm "Groapă" două caracteristici, ceea ce va însemna - nu uitați de existența a 2 mișcări posibile, care trebuie verificate!)

Verificați ipoteza pentru S \u003d 10 la min0. Această verificare va servi drept răspuns. la întrebarea 1b
Cu S \u003d 10, Petya are 2 mutări, pe care nu le poate câștiga într-o singură mutare, dar pentru orice mutare Petya Vanya poate câștiga cu prima sa mutare:
Orice mișcare a lui Petit "10 + 1 \u003d 11" sau 10 * 2 \u003d 20 duce la poziția câștigătoare inițială a lui Vanya, care, după ce a dublat numărul de pietre din grămadă, primește 22 sau 40, adică mai mult de 21 și vanya va câștiga
Prin urmare, conturăm poziția S \u003d 10 în partea de jos cu o linie continuă ( desenați o groapă) - min0 (pierdere inițială sau pierdere pentru prima mutare):

Răspuns la întrebarea 1b. poate fi așa: Cu S \u003d 10, Petya are 2 mișcări pe care nu le poate câștiga, dar pentru orice mișcare Petya Vanya poate câștiga cu prima sa mutare. Orice mișcare a lui Petya "10 + 1 \u003d 11" sau "10 * 2 \u003d 20" îl conduce pe Vanya la poziția inițială de câștig, care, după ce a dublat numărul de pietre din grămadă, primește 22 sau 40, adică peste 21, iar Vanya câștigă

intrebarea 2... Pentru ca Petya să poată câștiga la a doua mișcare, adică a ajuns pe poziție max0 , după mutarea lui Vanya, are nevoie de a lui primul mutare " pune-l pe Vanya într-o groapă". Este clar că astfel de poziții pot fi două, ale căror valori se găsesc în sens invers și trebuie verificate ...
Prima poziție suspectă „10-1 \u003d 9”

S \u003d 9. Să verificăm această poziție pentru o victorie garantată!
Dacă Petya ar juca un cadou, el ar fi făcut o mișcare „9 * 2 \u003d 18”,dar trebuie să câștige, așa că renunțăm la această mișcare. Rămâne doar „9 + 1 \u003d 10”,iar Vanya este în "Pit" - ceea ce îl conduce pe Petya să câștige cu a doua mișcare, indiferent de modul în care pleacă Vanya!

A doua „poziție suspectă” 10/2 = 5

S \u003d 5. Să verificăm această poziție pentru o victorie garantată! Accident vascular cerebral „5 + 1 \u003d 6”,întârzie jocul, deci nu îl considerăm (aruncați)
Rămâne doar „5 * 2 \u003d 10”,iar Vanya este în „Groapă” -ceea ce îl conduce pe Petya să câștige cu a doua mișcare, indiferent de modul în care pleacă Vanya!

Răspunsul 2 ar putea fi astfel:

Cu S \u003d 5 și 9, Petya nu poate câștiga cu prima mișcare, dar poate câștiga cu a doua mișcare și pentru aceasta este suficient pentru el să facă mișcarea "5 * 2 \u003d 10" din poziția S \u003d 5, trimitând astfel Vanya în poziția inițială de pierdere sau din poziția S \u003d 9 trimite-l în aceeași poziție cu mișcarea „9 + 1 \u003d 10”

Întrebarea 3... Vanya trebuie să câștige, prin urmare, el trebuie să fie în vârf max0, asta înseamnă că Petya trebuie să fie cu siguranță în min0, unde este "Plantă" Vanya din max1, rămâne pentru anam să găsească astfel de poziții din care ar cădea cu siguranță Petya max1
Găsim poziții „suspecte” care pot duce la Petya max1 folosind aceeași backtrack:
9-1=8
9/2 \u003d? 9 nu este divizibil cu 2 - dispare
5-1=4
5/2 \u003d? 5 nu este divizibil cu 2 - dispare
Găsim că așa "Suspicios"există doar două poziții, dar totuși trebuie verificate!

S \u003d 8. Să verificăm această poziție pentru pierderea garantată a Petit!
Mutarea lui Petit este 8 + 1 \u003d 9, iar Vanya câștigă cu a doua mutare
Mutarea lui Petit este 8 * 2 \u003d 16, iar Vanya câștigă cu prima mutare
S \u003d 4. Să verificăm această poziție pentru pierderea garantată a Petit!
Mișcarea lui Petya 4 + 1 \u003d 5 și ar fi pierdut, dar din această poziție mișcarea lui Petya 4 * 2 \u003d 8 este profitabilă, astfel Vanya cade în „gaură” și pierde. Dar trebuie să găsim strategia câștigătoare a lui Vanya, așa că excludem poziția S \u003d 4 din candidați și obținem finala "Imagine":

3. În poziția S \u003d 8 - Vanya nu are o strategie care să-i permită să câștige cu o primă mutare garantată, deoarece victoria sa depinde de mutarea lui Petya, așa că Vanya are o strategie pentru a câștiga fie la prima, fie la a doua mutare: Dacă Petya alege „+1” , sunt 9 pietre în grămadă și Vanya câștigă la mișcarea 2 (vezi răspunsul la întrebarea 2). Dacă Petya alege „* 2”, Vanya câștigă cu prima mișcare, dublând numărul de pietre din grămadă.

Desenul obținut mai sus poate fi redesenat cu ușurință în arborele jocului, marcând anterior mișcările pierdute cu linii roșii (linia groasă este „ accident vascular cerebral scurt"sau" +1 ", Și slab -" mult"sau" *2 ») Și verde - câștigător. (se pot trasa linii groase roșii, care vor coincide cu direcția ramurilor „scurte” ale arborelui de joc)

Imaginea strategică finală a câștigului lui Petya ar putea arăta astfel:

Alte metode pentru rezolvarea problemelor de acest tip pot fi găsite aici -

În această sarcină, cea mai dificilă parte este să scrieți soluția corect și logic.

Deci, să începem prin a încerca să înțelegem starea.

1. Avem două grămezi de pietre și doi jucători: primul (Petya) și al doilea (Vanya).
2. Jucătorii se alternează.
3. În timpul unei ture, puteți fie să adăugați o piatră la oricare dintre grămezi, fie să dublați numărul de pietre din grămadă.
4. De îndată ce există 73 sau mai multe pietre în total, jocul se termină.
5. Cel care a mers ultima a câștigat.

Notite importante

1. Vom construi un copac de petrecere în unele sarcini. Suntem obligați să facem acest lucru în conformitate cu condiția numai în Task 3. În Task 2 noi nu trebuie construiește un copac de petreceri.
2. În fiecare dintre sarcini, nu este suficient să spunem pur și simplu cine are strategia câștigătoare. De asemenea, este necesar să o descrieți și să indicați numărul posibil de pași care vor fi necesari pentru a câștiga.
3. Nu este suficient să apelezi la o strategie câștigătoare. Trebuie sa dovedică duce la câștig. Chiar și declarațiile evidente necesită dovezi.

Exercitiul 1.

Luați în considerare sarcina 1. În grămezi - (6, 33) pietre (prima parte a sarcinii 1) și (8, 32) pietre (a doua parte a sarcinii 1). Trebuie să stabilim care dintre jucători are o strategie câștigătoare. Cu alte cuvinte, care dintre jucători, cu jocul corect, va câștiga cu siguranță, indiferent de acțiunile adversarului.

În continuare, vom împărți soluția în două părți. În primul rând, va exista o explicație preliminară (nu este necesar să o scrieți în examenul de stat unificat) și apoi - o „decizie formală”, adică ceea ce trebuie să scrieți în examenul de stat unificat.

Discuţie.

Să ne gândim: primul jucător, evident, nu poate câștiga într-o singură mișcare, pentru că orice ar face, nu vor fi în total 73. Cea mai mare acțiune pe care o poate face este să dubleze numărul de pietre din a doua grămadă, făcându-le 66. Dar (6, 66) este de 72 de pietre, nu de 73. Deci, prima va câștiga evident într-o singură mișcare nu poti. Cu toate acestea, al doilea este destul de capabil. Primul poate face patru lucruri: adăugați 1 la prima grămadă, dublați numărul de pietre din prima grămadă, adăugați 1 la a doua grămadă și dublați numărul de pietre din a doua grămadă. Să vedem unde duce acest lucru:

• (6,33) -\u003e (7,33). În acest caz, al doilea jucător poate dubla numărul de pietre din a doua grămadă. Primim (7, 66). În total - 73. Deci câștigă al doilea.
• (6,33) -\u003e (12, 33). În acest caz, al doilea jucător poate dubla numărul de pietre din a doua grămadă. Primim (12, 66). În total - 78. Deci câștigă al doilea.
• (6,33) -\u003e (6,34). În acest caz, al doilea jucător poate dubla numărul de pietre din a doua grămadă. Primim (6, 68). În total - 74. Deci câștigă al doilea.
• (6,33) -\u003e (6,66). În acest caz, al doilea jucător poate dubla numărul de pietre din a doua grămadă. Primim (6, 132). În total - 138. Aceasta înseamnă că al doilea câștigă.

Total: indiferent de comportamentul primului jucător, al doilea va câștiga într-o singură mișcare.

Soluția cu (8.32) este similară.

Soluție formală la problema 1.

Al doilea jucător are o strategie câștigătoare. Să dovedim acest lucru și să arătăm această strategie. Pentru a face acest lucru, vom construi un copac lot pentru fiecare dintre pozițiile de pornire. În arborele petrecerilor, vom indica starea ambelor grămezi în format (a, b), unde a este numărul de pietre din prima grămadă, b este numărul de pietre din a doua grămadă. Pe parcursul primului jucător, vom lua în considerare patru opțiuni posibile pentru comportamentul său: adăugați 1 la prima grămadă, dublați numărul de pietre din prima grămadă, adăugați 1 la a doua grămadă și dublați numărul de pietre din a doua grămadă. Pentru cel de-al doilea jucător, vom indica o mișcare care duce la câștig. Mișcările vor fi afișate sub formă de săgeți, lângă care scriem I în cazul primei mișcări și II în cazul celei de-a doua mișcări.

Arborele de petrecere pentru poziția inițială (6, 33).

Arborele lotului pentru poziția inițială (8, 32).

Conform arborelui jocurilor, indiferent de mișcările primei, a doua are întotdeauna o strategie câștigătoare care îi permite să câștige într-o singură mutare, descrisă în copaci (sumele după mutările lui Vanya sunt 73, 80, 74 și 136, de la stânga la dreapta, respectiv). Mai mult, conform arborelui de joc, al doilea jucător poate câștiga exact într-o singură mișcare.

Tema 2

Soluție formală

Luați în considerare poziția inițială (6.32). Rețineți că este aproape de (6,33) din Sarcina 1. În Sarcina 1 am aflat că în poziția (6, 33) a doua câștigă și într-o singură mișcare. Această condiție poate fi reformulată: în poziția (6.33), câștigătorul într-o singură mutare este cel care nu merge (adică merge al doilea). Sau, cu alte cuvinte, cel care umblă pierde dintr-o singură mișcare.

În poziția (6,32) primul câștigă în două mutări. Să dovedim. Cu prima sa mutare, Petya adaugă +1 la a doua grămadă. Astfel, se obține poziția (6,33). După cum am aflat mai devreme, în poziția (6.33), cel care se mișcă pierde. În cazul nostru, va fi mișcarea lui Vanya. Prin urmare, Vanya va pierde într-o singură mișcare. În acest caz, Petya va trebui să facă în total două mișcări: prima (adăugați 1 piatră la cea de-a doua grămadă) + a doua mutare în conformitate cu Arborele de petrecere din Task 1, urmând strategia lui Vanya.

În mod similar în poziția (7, 32). Petya, la prima sa mutare, adaugă +1 piatră la prima grămadă, obținând poziția (8, 32). În această poziție, după același raționament, cel care umblă pierde. Va fi mișcarea lui Vanya, așa că Vanya va pierde. Strategia câștigătoare a lui Petya este după cum urmează: Petya adaugă +1 piatră la prima grămadă, apoi urmează strategia lui Vanya din Task 1.

În mod similar în poziția (8, 31). Petya, cu prima sa mutare, adaugă +1 piatră la a doua grămadă, obținând poziția (8, 32). În această poziție, după același raționament, cel care umblă pierde. Va fi mișcarea lui Vanya, așa că Vanya va pierde. Strategia câștigătoare a lui Petya este următoarea: Petya adaugă +1 piatră la cea de-a doua grămadă, apoi urmează strategia lui Vanya din Task 1.

Tema 3

Discuţie

Rețineți că din situația (7, 31) este foarte ușor să intrați fie în situațiile (8, 31) și (7, 32), în care, conform sarcinii anterioare, câștigă cel care merge, fie în situație (14, 31) și (7, 62), în care cel care merge poate câștiga într-o singură mișcare prin dublarea numărului de pietre din a doua grămadă. Astfel, se dovedește că Vanya ar trebui să aibă o strategie câștigătoare. Mai mult, el poate câștiga atât în \u200b\u200b2 mutări (primele două cazuri), cât și într-o singură mutare (al doilea două cazuri).

Soluție formală

În poziția inițială (7, 31) Vanya câștigă în una sau două mutări. Să dovedim. Pentru a face acest lucru, să construim un copac al tuturor părților.

Arborele tuturor părților pentru poziția de plecare (7, 31).

Conform arborelui tuturor părților, Vanya câștigă fie într-o singură mișcare (dacă Petya a dublat numărul de pietre din prima sau a doua grămadă), fie în două mutări (dacă Petya a mărit numărul de pietre din prima sau a doua grămadă cu 1).

Astfel, în poziția inițială (7, 31) Vanya are o strategie câștigătoare, în timp ce Vanya va câștiga într-una sau două mișcări.

Evgeny Smirnov

Expert IT, profesor de informatică

Doi jucători, Pașa și Vova, joacă următorul joc. Există o grămadă de pietre în fața jucătorilor. Jucătorii se alternează, Pașa face prima mișcare. Într-o singură mișcare, jucătorul poate adăuga 1 piatră sau 10 pietre la grămadă. De exemplu, având o grămadă de 7 pietre, într-o singură mișcare puteți obține o grămadă de 8 sau 17 pietre. Fiecare jucător are un număr nelimitat de pietre pentru a face mișcări. Jocul se termină în momentul în care numărul de pietre din grămadă devine cel puțin 31. Câștigătorul este jucătorul care a făcut ultima mișcare, adică primul care primește grămada care conține 31 sau mai multe pietre.

În momentul inițial, existau pietre S în grămadă, 1 ≤ S ≤ 30.

Decizie.

1. a) Pașa poate câștiga dacă S \u003d 21, ..., 30. Pentru valori mai mici ale lui S, într-o singură mișcare, nu puteți obține o grămadă cu mai mult de 30 de pietre. Este suficient ca Pașa să mărească numărul de pietre cu 10. Cu S 1. b) Vova poate câștiga cu prima mișcare (indiferent de modul în care joacă Pașa), dacă inițial sunt S \u003d 20 de pietre în grămadă. Apoi, după prima mișcare a lui Pașa, vor fi 21 de pietre sau 30 de pietre în grămadă. În ambele cazuri, Vanya crește numărul de pietre cu 10 și câștigă într-un singur rând.

2. Valorile posibile ale lui S: 10, 19. În aceste cazuri, Pașa, evident, nu poate câștiga cu prima mișcare. Cu toate acestea, poate obține o grămadă de 20 de pietre (la S \u003d 10, crește numărul de pietre cu 10; la S \u003d 19, adaugă 1 piatră). Această poziție este discutată la punctul 1 b. În el, jucătorul care se va mișca (acum este Vova) nu poate câștiga, iar adversarul său (adică Pașa) va câștiga următoarea mutare.

3. Valoarea S posibilă: 18. După prima mișcare a lui Pașa, vor fi 19 sau 28 de pietre în grămadă. Dacă există 28 de pietre în grămadă, Vova va crește numărul de pietre cu 10 și te vei juca cu prima ta mișcare. Situația în care există 19 pietre în grămadă a fost rezolvată la pasul 2. În această situație, jucătorul care se va mișca (acum este Vova) câștigă cu a doua sa mutare.

un musafir 26.05.2014 12:31

Punctul 3. Dar ce zici de situația când sunt inițial 9 pietre în grămadă. După ce mișcările lui Pașa devin 10 sau 19, Vasya termină până la 20 și mai departe conform paragrafului 1.b.

Konstantin Lavrov

Da, 9 este și răspunsul corect. Este suficient să indicați cel puțin o valoare corectă.

Doi jucători, Pașa și Vova, joacă următorul joc. Există o grămadă de pietre în fața jucătorilor. Jucătorii se alternează, Pașa face prima mișcare. Într-o singură mișcare, jucătorul poate adăuga 1 piatră sau 10 pietre la grămadă. De exemplu, având o grămadă de 7 pietre, într-o singură mișcare puteți obține o grămadă de 8 sau 17 pietre. Fiecare jucător are un număr nelimitat de pietre pentru a face mișcări. Jocul se termină în momentul în care numărul pietrelor din grămadă devine cel puțin 41. Jucătorul care a făcut ultima mișcare este considerat câștigător, adică primul jucător care primește grămada care conține 41 sau mai multe pietre.

În momentul inițial, existau pietre S în grămadă, 1 ≤ S ≤ 40.

Vom spune că un jucător are o strategie câștigătoare dacă poate câștiga cu mișcările oricărui adversar. A descrie strategia unui jucător înseamnă a descrie ce mișcare ar trebui să facă în orice situație pe care ar putea să o întâmpine într-un joc diferit al adversarului.

Finalizați următoarele sarcini. În toate cazurile, justificați-vă răspunsul.

1. a) Indicați toate aceste valori ale numărului S, la care Pașa poate câștiga într-o singură mișcare. Justificați că s-au găsit toate valorile necesare ale lui S și indicați mișcările câștigătoare.

b) Indicați valoarea lui S. la care Pașa nu poate câștiga într-o singură mișcare, dar pentru oricare dintre mișcările Pașa, Vova poate câștiga cu prima sa mutare. Descrieți strategia câștigătoare a lui Vova.

2. Indicați două valori ale lui S pentru care Pașa are o strategie câștigătoare, iar Pașa nu poate câștiga într-o singură mutare, dar poate câștiga cu a doua sa mutare, indiferent de modul în care se mișcă Vova. Pentru valorile date de S, descrie strategia câștigătoare a lui Pașa.

3. Indicați valoarea lui S la care Vova are o strategie câștigătoare care îi permite să câștige la prima sau a doua mutare în orice joc al Pașei, dar Vova nu are o strategie care să-i permită să câștige la prima mutare. Pentru valoarea indicată a lui S, descrie strategia câștigătoare a lui Vova. Construiți un copac al tuturor jocurilor posibile cu această strategie câștigătoare a lui Vova (sub forma unei imagini sau a unei mese). Pe marginile copacului indică cine face mișcarea, în noduri - numărul de pietre din grămadă.

Decizie.

1. a) Pașa poate câștiga dacă S \u003d 31, ..., 40. Cu valori mai mici de S, într-o singură mișcare, nu puteți obține o grămadă care conține mai mult de 40 de pietre. Este suficient ca Pașa să crească numărul de pietre cu 10. Dacă S b) Vova poate câștiga cu prima mișcare (indiferent de modul în care joacă Pașa), dacă inițial sunt S \u003d 30 de pietre în grămadă. Apoi, după prima mișcare a Pașei, vor fi 31 de pietre sau 40 de pietre în grămadă. În ambele cazuri, Vanya crește numărul de pietre cu 10 și câștigă într-un singur rând.

2. Valorile posibile ale lui S: 20, 29. În aceste cazuri, Pașa, evident, nu poate câștiga cu prima mișcare. Cu toate acestea, poate obține o grămadă de 30 de pietre (la S \u003d 20 crește numărul de pietre cu 10; la S \u003d 29 adaugă 1 piatră). Această poziție este discutată la punctul 1. b). În el, jucătorul care se va mișca (acum este Vova) nu poate câștiga, iar adversarul său (adică Pașa) va câștiga următoarea mutare.

3. Valoarea S posibilă: 28. După prima mișcare a lui Pașa, vor fi 29 sau 38 de pietre în grămadă. Dacă există 38 de pietre în grămadă, Vova va crește numărul de pietre cu 10 și te vei juca cu prima ta mișcare. Situația în care sunt 29 de pietre într-o grămadă este rezolvată la pasul 2. În această situație, jucătorul care se va deplasa (acum este Vova) câștigă cu a doua sa mutare.

Tabelul prezintă un arbore de posibile jocuri pentru strategia descrisă de Vova. Pozițiile finale (în care câștigă Vova) sunt subliniate. Figura arată același arbore într-o formă grafică (sunt admise ambele moduri de afișare a unui arbore).

Doi jucători, Petya și Vanya, joacă următorul joc. În fața lor sunt două grămezi de pietre, în prima dintre care sunt 2, iar în a doua - 3 pietre. Fiecare joc-ro-ka nu este-limitat-chen-ci o mulțime de pietre. Jocul-ro-ki merge pe rând, prima mișcare este de-la-et Petya. Mișcarea este că jucătorul fie am-și-wa-este numărul de pietre dintr-o grămadă, fie adaugă 4 pietre la o grămadă. Jocul este finalizat în acel moment în care numărul total de pietre din cele două grămezi devine de cel puțin 31. Dacă în momentul finalizării jocului suma totală numărul de pietre din două grămezi nu este mai mic de 40, apoi ai jucat Petya, altfel - Vanya. Cine ești tu-joc-ry-va-e când ambii jucători joacă fără greșeli? Care ar trebui să fie prima mișcare a jocului you-game-ry-va-yu-shch-go? Justificați răspunsul.

Decizie.

Vanya câștigă.

Pentru dovadă, luați în considerare un arbore de joc incomplet, proiectat sub forma unui tabel, în care fiecare celulă conține perechi de numere separate printr-o virgulă. Aceste numere corespund numărului de pietre din fiecare etapă a jocului din prima și a doua grămadă, respectiv.

Tabelul conține toate opțiunile posibile pentru mișcările primului jucător. Se vede din aceasta că pentru orice mișcare a primului jucător, al doilea are o mișcare care duce la victorie.

Doi jucători, Petya și Vasya, joacă următorul joc. În fața lor sunt două grămezi de pietre, în prima dintre care sunt 2, iar în a doua - 1 piatră. Fiecare jucător are un număr nelimitat de pietre. Jucătorii se transformă pe rând, Petya merge primul. Miscarea constă în faptul că jucătorul fie mărește de 3 ori numărul pietrelor dintr-o grămadă, fie adaugă 3 pietre la o grămadă. Un jucător câștigă, după a cărui rundă există cel puțin 24 de pietre într-una din grămezi. Cine câștigă jucând fără erori? Care ar trebui să fie prima mișcare a jucătorului câștigător?

Justificați răspunsul.

Decizie.

Petya câștigă, cu prima sa mișcare, trebuie să tripleze numărul de pietre din a doua grămadă. Pentru dovadă, luați în considerare un arbore de joc incomplet, proiectat sub forma unui tabel, în care fiecare celulă conține perechi de numere separate printr-o virgulă. Aceste numere corespund numărului de pietre din fiecare etapă a jocului din prima și a doua grămadă, respectiv.

Tabelul conține toate variantele posibile ale mișcărilor lui Vasya. Se poate vedea din acesta că, pentru oricare dintre răspunsurile sale, Petya are o mișcare care duce la victorie.

Doi jucători, Petya și Vanya, joacă următorul joc. Există o grămadă de pietre în fața jucătorilor. Jucătorii se alternează, Petya face prima mișcare. Într-o singură mișcare, jucătorul poate adăuga o piatră la grămadă sau poate crește numărul de pietre din grămadă de cinci ori. De exemplu, având o grămadă de 10 pietre, într-o singură mișcare puteți obține o grămadă de 11 sau 50 de pietre. Fiecare jucător are un număr nelimitat de pietre pentru a face mișcări.

Jocul se termină în momentul în care numărul pietrelor din grămadă devine mai mare de 100. Câștigătorul este jucătorul care a făcut ultima mișcare, adică primul jucător care a primit grămada care conține 101 sau mai multe pietre.

În momentul inițial, existau pietre S în grămadă, 1 ≤ S ≤ 100.

Se spune că un jucător are o strategie câștigătoare dacă poate câștiga la mișcările oricărui adversar. A descrie strategia unui jucător înseamnă a descrie ce mișcare ar trebui să facă în orice situație pe care ar putea să o întâmpine într-un joc diferit al adversarului.

Finalizați următoarele sarcini. În toate cazurile, justificați-vă răspunsul.

1. a) La ce valori ale lui S poate câștiga Petya cu prima mutare? Indicați toate aceste valori și mișcarea câștigătoare a lui Petit.

b) Indicați valoarea lui S, la care Petya nu poate câștiga într-o singură mutare, dar pentru orice mutare, Petya poate câștiga cu prima sa mutare. Descrieți strategia câștigătoare a lui Vanya.

2. Indică două valori ale lui S pentru care Petya are o strategie câștigătoare, iar Petya nu poate câștiga cu prima sa mutare, dar Petya poate câștiga cu a doua sa mutare, indiferent de modul în care se mișcă Vanya. Pentru valorile indicate de S, descrie strategia câștigătoare a lui Petit.

3. Indicați valoarea lui S pentru care Vanya are o strategie câștigătoare care îi permite să câștige la prima sau a doua mutare în orice joc al lui Petya și, în același timp, Vanya nu are o strategie care să-i permită să câștige la prima mutare.

Pentru valoarea indicată a lui S, descrie strategia câștigătoare a lui Vanya. Construiți un copac al tuturor jocurilor posibile cu această strategie câștigătoare de către Vanya. Prezentați-l sub forma unei imagini sau a unui tabel. Pentru fiecare margine a copacului, indicați cine face mișcarea, pentru fiecare nod - numărul de pietre în poziție.

Decizie.

1. a) Petya poate câștiga dacă S \u003d 21, ..., 100. Pentru valori mai mici ale lui S, într-o singură mișcare este imposibil să obții o grămadă cu mai mult de 100 de pietre. Este suficient ca Pete să mărească numărul de pietre de 5 ori. Cu S 1. b) Vanya poate câștiga cu prima mișcare (indiferent de modul în care joacă Petya), dacă inițial există S \u003d 20 pietre în grămadă. Apoi, după prima mișcare a lui Petit, vor fi 21 de pietre sau 100 de pietre în grămadă. În ambele cazuri, Vanya mărește numărul de pietre de 5 ori și câștigă într-o singură mișcare.

2. Valorile posibile ale lui S: 4, 19. În aceste cazuri, Petya evident nu poate câștiga cu prima mișcare. Cu toate acestea, poate obține o grămadă de 20 de pietre (cu S \u003d 4, crește numărul de pietre de 5 ori; cu S \u003d 19, adaugă 1 piatră). Această poziție este discutată la punctul 1 b). În el, jucătorul care se va mișca (acum este Vanya) nu poate câștiga, iar adversarul său (adică Petya) va câștiga următoarea mutare.

3. Posibilă valoare S: 18. După prima mișcare a lui Petit, vor fi 19 sau 90 de pietre în grămadă. Dacă există 90 de pietre în grămadă, Vanya va crește numărul de pietre de 5 ori și va câștiga la prima sa mutare. Situația în care sunt 19 pietre în grămadă a fost rezolvată la pasul 2. În această situație, jucătorul care se va muta (acum este Vanya) câștigă cu a doua sa mutare.

Tabelul prezintă un copac al posibilelor jocuri pentru strategia descrisă a lui Vanya. Pozițiile finale (în care Vanya câștigă) sunt subliniate. În figură, același arbore este prezentat sub formă grafică (ambele metode de reprezentare sunt acceptabile).

Faceți un test cu privire la aceste sarcini

Complexitate : înalt.
Timpul estimat al soluției : 20 de minute
Subiect: Bazele matematice ale programării. Algoritmi.
Subtema: Jocuri și strategii
Ce este verificat: Cunoașterea conceptelor de bază legate de analiza jocului cu informații complete. Abilitatea de a identifica pozițiile câștigătoare și pierdute.
Cum ar putea arăta o misiune? De exemplu, astfel: Se oferă o descriere a jocului a doi jucători cu informații complete. Este necesar să se determine pozițiile în care jucătorul specificat în condiție are o strategie câștigătoare care îi permite să câștige garantat în numărul specificat de mutări.

Cum se analizează o problemă.
O analiză bună a fost făcută de K.Yu. Polyakov în articolul „Unified State Exam: New Strategies (Task C3)” [Primul septembrie. Informatică. 2013, ianuarie. P. 22-27]. Articolul conține multe sarcini pentru soluții independente. Există o singură inexactitate în articol: arborele descris la pagina 25 se numește arborele „opțiuni de joc posibile”. În contextul articolului, este clar despre ce este vorba. Dar atunci când analizăm articolul cu elevii, este mai bine să clarificăm: arborele posibilelor opțiuni pentru joc cu strategia aleasă a lui Vanya. De obicei arborele posibilelor variante ale jocului (sau pur și simplu arborele jocului) se numește arborele reprezentând toate jocurile posibile. Adică, sunt luate în considerare toate mișcările posibile ale lui Vanya și nu numai mișcările corespunzătoare unei anumite strategii.

Cometariu. Activitatea C3-2013 combină ideile sarcinilor C3-2011 și C3-2012. Continuitatea din C3-2012 poate fi văzută din analiza lui K.Yu. Polyakov. A se vedea, de asemenea, defalcarea C3-2012