Jedinstveni državni ispit iz informatike 26 zadataka riječi. Teorija igara. Pronalaženje pobjedničke strategije

Najteži dio ovog problema je ispravno i logično pisanje rješenja.

Dakle, hajde da počnemo pokušavajući da razumemo stanje.

  1. Imamo dvije gomile kamenja i dva igrača: prvog (Petya) i drugog (Vanya).
  2. Igrači se izmjenjuju.
  3. Tokom poteza, možete dodati jedan kamen na bilo koju gomilu ili udvostručiti broj kamenja u gomili.
  4. Čim se na hrpi nađu 73 ili više kamenčića, igra se završava.
  5. Onaj koji zadnji ode pobjeđuje.

Važne napomene

  1. U nekim zadacima ćemo napraviti stablo partija. To smo dužni da uradimo prema uslovu samo u zadatku 3. U zadatku 2 mi nije obavezan napravi party drvo.
  2. U svakom od zadataka nije dovoljno samo reći ko ima pobjedničku strategiju. Također ga morate opisati i navesti mogući broj koraka koji će biti potrebni za pobjedu.
  3. Strategiju nije dovoljno nazvati pobjedničkom. Treba dokazati da to vodi do pobede. Čak i očigledne izjave zahtijevaju dokaze.

Vježba 1.

Razmotrimo sada zadatak 1. U hrpama je (6, 33) kamenja (prvi dio zadatka 1) i (8, 32) kamenja (drugi dio zadatka 1). Moramo odrediti koji igrač ima pobjedničku strategiju. Drugim riječima, koji igrač, ako se igra pravilno, sigurno će pobijediti, bez obzira na postupke protivnika.

Ovdje i dalje ćemo rješenje podijeliti na dva dijela. Prvo će biti preliminarno objašnjenje (nema potrebe da se to piše u Jedinstvenom državnom ispitu), a zatim - "formalna odluka", odnosno ono što treba napisati na samom obrascu Jedinstvenog državnog ispita.

Diskusija.

Zamislimo: prvi igrač očigledno ne može pobijediti u jednom potezu, jer šta god da uradi, ukupan broj neće biti 73. "Najveća" akcija koju može da uradi je da udvostruči broj kamenčića u drugoj hrpi, čineći ih 66. Ali (6, 66) je 72 kamena, a ne 73. To znači da se prvi jasno može osvojiti u jednom potezu ne mogu. Međutim, drugi je prilično sposoban. Prvi potencijalno može izvršiti četiri radnje: dodati 1 prvoj hrpi, udvostručiti broj kamenja na prvoj hrpi, dodati 1 drugoj hrpi, udvostručiti broj kamenja na drugoj hrpi. Da vidimo kuda ovo vodi:

  • (6.33) -> (7.33). U ovom slučaju, drugi igrač može udvostručiti broj kamenčića u drugoj hrpi. Dobijamo (7, 66). Ukupno - 73. Dakle, drugi pobjeđuje.
  • (6.33) -> (12, 33). U ovom slučaju, drugi igrač može udvostručiti broj kamenčića u drugoj hrpi. Dobijamo (12, 66). Ukupno - 78. Dakle, drugi pobjeđuje.
  • (6.33) -> (6.34). U ovom slučaju, drugi igrač može udvostručiti broj kamenčića u drugoj hrpi. Dobijamo (6, 68). Ukupno - 74. Dakle, drugi pobjeđuje.
  • (6.33) -> (6.66). U ovom slučaju, drugi igrač može udvostručiti broj kamenčića u drugoj hrpi. Dobijamo (6, 132). Ukupno - 138. Dakle, drugi pobjeđuje.

Ukupno: bez obzira kako se prvi igrač ponaša, drugi će pobijediti u jednom potezu.

Rješava slično sa (8.32).

Formalno rješenje zadatka 1.

Drugi igrač ima pobjedničku strategiju. Dokažimo to i pokažimo ovu strategiju. Da bismo to učinili, napravit ćemo partijsko stablo za svaku od početnih pozicija. U stablu igre ćemo naznačiti stanje obje gomile u formatu (a,b), gdje je a broj kamenčića u prvoj hrpi, b broj kamenčića u drugoj hrpi. Kada se prvi igrač okrene, razmotrit ćemo četiri moguće opcije za njegovo ponašanje: dodati 1 na prvu gomilu, udvostručiti broj kamenčića na prvoj hrpi, dodati 1 na drugu gomilu, udvostručiti broj kamenčića na drugoj hrpi. Za drugog igrača ćemo naznačiti po jedan potez koji vodi do pobjede. Poteze ćemo prikazati u obliku strelica, pored kojih pišemo I u slučaju prvog poteza i II u slučaju drugog poteza.

Stablo igre za početnu poziciju (6, 33).

Stablo igre za početnu poziciju (8, 32).

Prema stablu igre, bez obzira na poteze prvog, drugi uvijek ima pobjedničku strategiju koja mu omogućava pobjedu u jednom potezu, opisanu u stablima (zbirovi nakon Vanjinih poteza su, s lijeva na desno, 73, 80 , 74 i 136, redom). Štaviše, prema stablu igre, drugi igrač može pobijediti u tačno jednom potezu.

Zadatak 2

Formalno rješenje

Razmotrimo početni položaj (6,32). Imajte na umu da je blizu (6,33) iz zadatka 1. U zadatku 1 smo saznali da na poziciji (6, 33) pobjeđuje drugi, i to u jednom potezu. Ovaj uslov se može preformulisati: u poziciji (6.33) nalazi se onaj ko pobedi u jednom potezu Ne hoda (odnosno hoda drugi). Ili, drugim riječima, onaj koji se kreće gubi u jednom potezu.

U poziciji (6.32) prvi pobjeđuje u dva poteza. Dokažimo to. Na svom prvom potezu, Petya dodaje +1 na drugu gomilu. Tako se dobija pozicija (6.33). Kako smo ranije saznali, na poziciji (6,33) gubi onaj koji se kreće. U našem slučaju to će biti Vanjin potez. Stoga će Vanja izgubiti u jednom potezu. U ovom slučaju, Petya će morati napraviti ukupno dva poteza: prvi (dodati 1 kamen na drugu gomilu) + drugi potez u skladu sa Party Tree u zadatku 1, djelujući prema Vanjinoj strategiji.

Slično u poziciji (7, 32). Svojim prvim potezom Petya dodaje +1 kamen na prvu gomilu i dobija poziciju (8, 32). U ovoj poziciji, prema istom rezonovanju, gubi onaj koji se kreće. To će biti Vanjin potez, pa će Vanja izgubiti. Petyina pobjednička strategija je sljedeća: Petya dodaje +1 kamen na prvu gomilu, a zatim slijedi Vanyinu strategiju iz zadatka 1.

Slično u poziciji (8, 31). Svojim prvim potezom Petya dodaje +1 kamen na drugu gomilu i dobija poziciju (8, 32). U ovoj poziciji, prema istom rezonovanju, gubi onaj koji se kreće. Biće Vanjinog poteza, pa će Vanja izgubiti. Petyina pobjednička strategija je sljedeća: Petya dodaje +1 kamen na drugu gomilu, a zatim slijedi Vanyinu strategiju iz zadatka 1.

Zadatak 3

Diskusija

Imajte na umu da je iz situacije (7, 31) vrlo lako završiti ili u situacijama (8, 31) i (7, 32), u kojima, prema prethodnom zadatku, pobjeđuje onaj koji se kreće, ili u situaciji ( 14, 31) i (7, 62), u kojima onaj koji se kreće može pobijediti u jednom potezu udvostručavajući broj kamenčića u drugoj hrpi. Tako se ispostavlja da Vanja mora imati pobjedničku strategiju. Štaviše, može pobijediti i u 2 poteza (prva dva slučaja) i u jednom potezu (druga dva slučaja).

Formalno rješenje

U početnoj poziciji (7, 31), Vanja pobjeđuje u jednom ili dva poteza. Dokažimo to. Da bismo to uradili, napravićemo stablo svih strana.

Stablo svih igara za početnu poziciju (7, 31).

Prema stablu svih igara, Vanya pobjeđuje ili u jednom potezu (ako je Petya udvostručio broj kamenčića u prvoj ili drugoj hrpi) ili u dva poteza (ako je Petya povećao broj kamenova u prvoj ili drugoj hrpi za 1) .

Dakle, na početnoj poziciji (7, 31) Vanja ima pobedničku strategiju, a Vanja će pobediti u jednom ili dva poteza.

Evgenij Smirnov

IT stručnjak, nastavnik informatike

Lekcija je obuhvatila analizu zadatka 26 Jedinstvenog državnog ispita iz informatike: dat detaljno objašnjenje i rješenje zadatka za 2017. godinu


26. zadatak - “Teorija igara, traženje pobjedničke strategije” – karakteriziran je kao zadatak visokog stepena složenosti, vrijeme za izvršavanje - cca 30 minuta, maksimalni rezultat - 3

* Neke slike i primjeri stranica preuzeti su iz prezentacijskih materijala K. Polyakova

Teorija igara. Pronalaženje pobjedničke strategije

Da biste riješili zadatak 26, morate zapamtiti sljedeće teme i koncepte:

    Pobjednička strategija

  • da bi se u jednostavnim igrama pronašla dobitna strategija, dovoljno je koristiti metodu nabrajanja svih mogućih opcija za poteze igrača;
  • za rješavanje problema najčešće se za to koristi 26 zadataka način gradnje drveta;
  • ako se iz svakog čvora stabla protežu dvije grane, tj. moguće opcije za poteze, onda se takvo stablo zove binarni(ako postoje tri opcije za nastavak sa svake pozicije, stablo će biti ternarno).

    • Osvajanje i gubljenje pozicija

  • sve pozicije u jednostavne igre podijeljeni na dobitke i poraze;
  • pobednička pozicija– ovo je pozicija u kojoj će igrač koji napravi prvi potez sigurno pobijediti bez obzira na to šta protivnik uradi, osim ako ne pogriješi; kaže se da ovaj igrač ima pobednička strategija- algoritam za odabir sljedećeg poteza, koji mu omogućava da pobijedi;
  • ako je igrač koji napravi prvi potez unutra gubljenje pozicije, onda će sigurno izgubiti osim ako njegov protivnik ne pogriješi; u ovom slučaju se kaže da ovaj igrač ima nema pobedničke strategije; Dakle, opšta strategija igre je da svojim potezom stvorite gubitnu poziciju za vašeg protivnika;
  • pobjedničke i izgubljene pozicije karakteriziraju kako slijedi:
  • pozicija iz koje svi mogući potezi vode do pobjedničkih pozicija – gubljenje;
  • pozicija iz koje barem jedan od sljedećih mogućih poteza vodi u gubitnu poziciju - pobjeda, a strategija igrača je da pretvoriti igru ​​u gubitnu(za protivnika) pozicija.

    • Ko će pobijediti sa strateški ispravnom igrom?

  • da bi se odredilo koji će igrač pobijediti sa strateški ispravnom igrom, potrebno je odgovoriti na pitanja:
  • Može li bilo koji igrač pobijediti, bez obzira na poteze drugih igrača?
  • Šta igrač sa pobjedničkom strategijom mora učiniti na svom prvom potezu da bi mogao pobijediti, bez obzira na akcije igrača?

Pogledajmo primjer:

Igra: ima 5 šibica na hrpi; igraju dva igrača koji se naizmjenično vade šibice sa hrpe; uslov: u jednom potezu možete ukloniti 1 ili 2 šibice; Pobjednik je onaj koji ostavi 1 šibicu na hrpi


Rješenje:

odgovor: sa pravilnom igrom (strategijom igre), prvi igrač će pobijediti; Da bi to učinio, potrebno mu je samo ukloniti jedan meč svojim prvim potezom.

Rješavanje 26 Jedinstvenih ispitnih zadataka iz informatike

Analiza zadatka 26 Jedinstvenog državnog ispita iz informatike 2017 FIPI opcija 5 (Krylov S.S., Churkina T.E.):

Dva igrača, Paša i Valja, igraju sledeću igru. Ispred igrača je gomila kamenja. Igrači se izmjenjuju Paša pravi prvi potez jedan dvaput. Na primjer, ako imate gomilu od 7 kamenčića, u jednom potezu možete dobiti gomilu od 14 ili 8 kamenčića. Svaki igrač ima neograničen broj kamenja da napravi potez.

Igra se završava kada broj kamenčića na hrpi postane najmanje 28 . Ako u isto vrijeme nema više od 44 kamenje, pobjednik je igrač koji je napravio posljednji potez. U suprotnom, njegov protivnik postaje pobjednik. Na primjer, ako je na hrpi bilo 23 kamena, a Pasha udvostruči broj kamenčića na hrpi, onda će se igra završiti i Valya će biti pobjednik. U početnom trenutku u gomili je bilo S kamenja, 1≤ S ≤ 27.

Vježba 1
a) Na kojim vrijednostima broja S Može li Paša pobijediti u jednom potezu? Navedite sve takve vrijednosti i Pašine odgovarajuće poteze.
b) Koji igrač kada ima pobjedničku strategiju S = 26, 25, 24? Opišite pobjedničke strategije za ove slučajeve.

Zadatak 2
S = 13, 12? Opišite relevantne pobjedničke strategije.

Zadatak 3
Koji igrač kada ima pobjedničku strategiju S=11? Konstruirajte stablo svih mogućih igara ovom pobjedničkom strategijom (u obliku slike ili tabele). Na rubovima stabla označite ko se kreće; u čvorovima - broj kamenja na poziciji.


✍ Rješenje:

Za detaljno objašnjenje zadatka 26 Jedinstvenog državnog ispita pogledajte video:

Analiza zadatka 26 Jedinstvenog državnog ispita iz informatike 2017 (jedna od opcija prema diplomcu):

Petya i Vanya igraju igru: postoji skup riječi, morate dosljedno imenovati slova ovih riječi. Pobjednik je igrač koji imenuje posljednje slovo bilo koje riječi iz seta. Petya ide prva.

Na primjer, postoji skup riječi (Vuk, Računarstvo, Strašno); za dati skup riječi, Petya može imenovati slovo svojim prvim potezom IN, I ili WITH. Ako Petya odabere pismo IN, tada će Vanya pobijediti (sljedeći potezi: Petya - IN, Vania - O, Petar - L, Vania - TO).

Vježba 1
A) Date 2 riječi (skup slova) ( IKLMNIKLMNH, NMLKINMLKI). Odredite dobitnu strategiju.

B) Date 2 riječi ( TRITRITRI...TRI, RITARITARITARITARITA...RITA). U prvoj riječi 99 slova, u drugom 164 . Odredite dobitnu strategiju.

Zadatak 2
Potrebno je zamijeniti dva slova iz seta artikala 1A u riječi najkraće dužine tako da je dobitna strategija drugi igrač. Objasnite pobjedničku strategiju.

Zadatak 3
S obzirom na skup riječi ( Vrana, Vuk, Wave, Derivat, Prokhor, Proso). Koji igrač ima pobjedničku strategiju? Obrazložite svoj odgovor i napišite stablo svih mogućih igara za pobjedničku strategiju.


✍ Rješenje:

* Za Vanju se prikazuju samo strateški potezi
**Crveni krug znači pobjedu

Za više detalja o rješavanju zadatka riječi pogledajte video tutorijal:

Rješenje 26. Demo verzija Jedinstvenog državnog ispita iz informatike 2018:

Dva igrača, Petya i Vanya, igraju sljedeću igru. Ispred igrača je gomila kamenja. Igrači se izmjenjuju, Petya pravi prvi potez. U jednom potezu, igrač može dodati na gomilu jedan kamena ili povećati broj kamenja u gomili dvaput. Na primjer, ako imate gomilu od 15 kamenčića, u jednom potezu možete dobiti hrpu od 16 ili 30 kamenčića. Svaki igrač ima neograničen broj kamenja za poteze.

Igra se završava kada se poveća broj kamenčića na hrpi najmanje 29. Pobjednik je igrač koji je napravio zadnji potez, odnosno prvi koji je dobio gomilu u kojoj će biti 29 ili više kamenja. U početnom trenutku u gomili je bilo S kamenja, 1 ≤ S ≤ 28.

Reći ćemo da igrač ima pobjedničku strategiju ako može pobijediti bilo kojim potezom protivnika. Opisati igračevu strategiju znači opisati koji bi potez trebao napraviti u svakoj situaciji na koju može naići pri različitim igrama od protivnika. Opis pobjedničke strategije ne radi to uključuju poteze igrača koji igra po ovoj strategiji koji za njega nisu bezuslovno dobitni, tj. ne pobjeđivati ​​bez obzira na igru ​​protivnika.

Vježba 1
A) Navedite takve vrijednosti broja S za koje Petya može pobijediti u jednom potezu.
b) Navedite vrijednost S tako da Petya ne može pobijediti u jednom potezu, ali za svaki potez koji Petya napravi, Vanja može pobijediti svojim prvim potezom. Opišite Vanjinu pobjedničku strategiju.

Zadatak 2
Navedite dvije takve vrijednosti S za koje Petya ima pobjedničku strategiju i:
— Petya ne može pobijediti u jednom potezu;
- Petya može pobijediti svojim drugim potezom, bez obzira kako se Vanja kreće.
Za date vrijednosti S, opišite Petitovu pobjedničku strategiju.

Zadatak 3
Navedite vrijednost S na kojoj:
— Vanja ima pobedničku strategiju koja mu omogućava da pobedi prvim ili drugim potezom u bilo kojoj Petjinoj igri;
— Vanja nema strategiju koja će mu omogućiti da bude zagarantovana pobeda na prvom potezu.

Za datu vrijednost S, opišite Vanjinu pobjedničku strategiju. Konstruirajte stablo svih mogućih igara ovom pobjedničkom strategijom (u obliku slike ili tabele). Na rubovima stabla označite ko se kreće; u čvorovima - broj kamenja u poziciji

Stablo ne bi trebalo sadržavati igre koje su nemoguće ako pobjednički igrač implementira svoju pobjedničku strategiju. Na primjer, kompletno stablo igre nije tačan odgovor na ovaj zadatak.


✍ Rješenje:
    Vježba 1.
  • a) Petya može pobijediti ako S = 15, … 28
15, ..., 28 - dobitne pozicije iz prvog poteza
  • b) Vanya može pobijediti prvim potezom (bez obzira kako Petya igra), ako postoji S=14 kamenje. Tada će nakon Petjinog prvog poteza na hrpi biti 15 ili 28 kamenčića. U oba slučaja, Vanya udvostručuje gomilu i pobjeđuje u jednom potezu.
    • S = 14 Petya: 14 + 1 = 15 pobjednička pozicija (vidi tačku a). Vanya Petya pobjeđuje: 14 * 2 = 28 pobjednička pozicija (vidi tačku a). Vanya osvaja 14 - gubi poziciju

    Zadatak 2.

  • Moguće vrijednosti S: 7, 13. U ovim slučajevima Petya očito ne može pobijediti prvim potezom. Međutim, može dobiti gomilu od 14 kamenčića: u prvom slučaju udvostručavanjem, u drugom dodavanjem jednog kamena. Ovaj stav je razmatran u stavu 1b. U njemu igrač koji će se pomaknuti (sada Vanya) ne može pobijediti, ali će njegov protivnik (to jest Petya) pobijediti na svom sljedećem potezu.
    • S = 7 Petya: 7 * 2 = 14 izgubljena pozicija (vidi tačku 1 b). Petya osvaja S = 13 Petya: 13 + 1 = 14 gubi poziciju (vidi tačku 1 b). Petya osvaja 7, 13 - osvajanje pozicija iz drugog poteza

    Zadatak 3.

  • Moguće vrijednosti S: 12. Nakon Petjinog prvog poteza, na hrpi će biti 13 ili 24 kamena. Ako ih ima 24 na hrpi, Vanya će udvostručiti broj kamenčića i pobijediti prvim potezom. Situacija kada je 13 kamenčića u gomili obrađena je u paragrafu 2. U ovoj situaciji, igrač koji će krenuti (sada je to Vanya) pobjeđuje svojim drugim potezom.
    • S = 12 Petya: 12 + 1 = 13 Vanya: 13 + 1 = 14 gubi poziciju (vidi tačku 1 b). Vanya pobjeđuje sekunda u pokretu!

    Tabela prikazuje stablo mogućih igara (i samo njih) za Vanjinu opisanu strategiju. Konačne pozicije (u njima Vanya pobjeđuje) su podvučene. Na slici je isto stablo grafički prikazano.


    Stablo svih mogućih igara sa Vanjinom strategijom:

    *crveni krug znači pobjedu

    Rani ispit iz informatike 2018, opcija 1. Zadatak 26:

    Dva igrača, Paša i Vasja, igraju sledeću igru. Ispred igrača je gomila kamenja. Igrači se izmjenjuju Paša pravi prvi potez. U jednom potezu, igrač može dodati na gomilu jedan ili četiri kamen ili povećati broj kamenja u gomili pet puta. Igra završava kada se broj kamenčića hrpa postaje najmanje 69.
    Pobjednik je igrač koji je napravio zadnji potez, odnosno prvi koji je dobio gomilu koja sadrži 69 ili više kamenčića. U početnom trenutku u gomili je bilo S kamenja, 1 ≤ S ≤ 68.

    Vježba 1.
    A) Navedite sve vrijednosti broja S za koje Pasha može pobijediti u jednom potezu. Opravdajte da su sve tražene vrijednosti S pronađene i označite pobjednički potez za svaku određenu vrijednost S.

    b) Navedite vrijednost S tako da Pasha ne može pobijediti u jednom potezu, ali sa bilo kojim Pašinim potezom Vasya može pobijediti svojim prvim potezom. Opišite Vasjinu pobjedničku strategiju.

    Zadatak 2. Navedite 2 takve vrijednosti S za koje Pasha ima pobjedničku strategiju, a Pasha ne može pobijediti u jednom potezu i može pobijediti svojim drugim potezom, bez obzira na to kako se Vasya kreće. Za svaku datu vrijednost S, opišite Pašinu pobjedničku strategiju.

    Zadatak 3. Navedite barem jednu vrijednost S za koju Vasya ima dobitnu strategiju koja mu omogućava da pobijedi prvim ili drugim potezom u bilo kojoj Pašinoj igri, a Vasya nema strategiju koja će mu omogućiti pobjedu prvim potezom. Za određenu vrijednost S, opišite Vasjinu pobjedničku strategiju. Konstruirajte stablo svih mogućih igara s ovom Vasyinom pobjedničkom strategijom (u obliku slike ili tablice).


    ✍ Rješenje:
      1.
      A) S ≥ 14. Ako je broj kamenčića u gomili 14 ili više, Paša treba da poveća njihov broj pet puta i tako dobije 70 ili više kamenčića.
    S ≥ 14 pobjedničkih pozicija

    b) S=13. Pasha može napraviti 14, 17 ili 65 kamenčića na svom prvom potezu, nakon čega Vasya povećava broj pet puta, dobijajući 70, 85 ili 325 kamenčića u gomili.

    S = 13 Pasha 1. potez: 13 + 1 = 14 Pasha 1. potez: 13 + 4 = 17 Pasha 1. potez: 13 * 5 = 65 Vanja 1. potez: * 5 = S ≥ 14 Vanja pobjeđuje 13 - gubi poziciju

    2. S = 9, 12. Za ove slučajeve, paša treba dodati 4 kamena na gomilu od 9 kamenova, ili 1 kamen na gomilu od 12, i dobiti gomilu od 13 kamenčića.
    Nakon toga igra se svodi na strategiju opisanu u paragrafu 1b.

    S = 13 Pasha 1. potez: 9 + 4 = 13 Pasha pobjeđuje Pasha 1. potez: 12 + 1 = 13 Pasha osvaja 9, 12 - dobitne pozicije iz drugog poteza

    3. S=8. Svojim prvim potezom Pasha može napraviti broj kamenčića u gomili 9, 12 ili 40. Ako Pasha poveća broj za pet puta, tada Vasja pobjeđuje svojim prvim potezom, povećavajući broj kamenčića za pet puta.
    Za slučaj kamenja 9 i 12, Vasya koristi strategiju naznačenu u klauzula 2.

    S = 8 Pasha 1. potez: 8 + 1 = 9 Vanja pobjeđuje (vidi tačku 2) Pasha 1. potez: 8 + 4 = 12 Vanya pobjeđuje (vidi tačku 2) Pasha 1. potez: 8 * 5 = 40

    Pogledajte video za rješenje zadatka 26:

    Simulator Jedinstvenog državnog ispita iz informatike 2018, test verzija 1. Zadatak 26 (Krylov S., Ushakov D.):

    jedan kamen ili . Igra se završava u trenutku kada postane ukupan broj kamenčića u hrpama najmanje 73.
    Pobjednik je igrač koji je napravio posljednji potez, tj. prvi koji će dobiti takav položaj da će gomile sadržavati 73 kamena ili više.

    Vježba 1.
    (6, 33), (8, 32) naznačiti koji igrač ima pobjedničku strategiju. U svakom slučaju, opišite pobjedničku strategiju; objasnite zašto ova strategija vodi do pobjede i naznačite najveći broj poteza koji bi pobjednik mogao trebati da dobije ovom strategijom.

    Zadatak 2.
    Za svaku od početnih pozicija (6, 32), (7, 32), (8, 31) naznačiti koji igrač ima pobjedničku strategiju.

    Zadatak 3.
    Za početnu poziciju (7, 31) naznačiti koji igrač ima pobjedničku strategiju. Napravite stablo svih mogućih igara sa pobjedničkom strategijom koju ste naveli. Zamislite drvo kao sliku ili sto.


    ✍ Rješenje:

    Video rješenje zadatka 26 sa dvije hrpe:


    26_6: Analiza zadatka 26 sa web stranice K. Polyakova (br. 31):

    Dva igrača, Petya i Vanya, igraju sljedeću igru. Ispred igrača su dvije gomile kamenja. Igrači se izmjenjuju, Petya pravi prvi potez. U jednom potezu, igrač može dodati na jednu od gomila (po svom izboru) dva kamena ili udvostručiti broj kamenja u gomili. Da bi napravio poteze, svaki igrač ima neograničen broj kamenčića. Igra se završava u trenutku kada postane ukupan broj kamenčića u hrpama najmanje 44.
    Pobjednik je igrač koji je napravio posljednji potez, tj. prvi koji je postigao takav položaj da će gomile sadržavati 44 ili više kamena.

    U početnom trenutku u prvoj hrpi je bilo 5 kamena, u drugoj hrpi – S kamenje; 1 ≤ S ≤ 38.
    Vježba 1.
    Na čemu S: 1a) Petya pobjeđuje prvim potezom; 1b) Vanja pobjeđuje prvim potezom?

    Zadatak 2.
    Navedite jednu vrijednost S, pod kojim Petya može pobijediti svojim drugim potezom.

    Zadatak 3.
    Navedite vrijednost S na kojoj Vanya pobjeđuje svojim prvim ili drugim potezom.


    ✍ Rješenje:

    5 + 20*2 = 45 (>44) * 5 - broj kamenja u prvoj gomili, ne menja se u skladu sa uslovom

  • Shodno tome, sve vrijednosti veliki 20 rezultiraće većim brojem 44 . Naznačimo to u tabeli. + znači osvajanje pozicije od prvog poteza:


    • Odgovor 1 a): S= (Na Jedinstvenom državnom ispitu objasnite poteze, na primjer: (5; 20) -> (Petitov potez) -> (5; 40); 40 + 5 = 45)

    Zadatak 1 b):

  • Pošto će Vanya ići drugi, potrebno je promijeniti broj kamenja u prvoj hrpi. Dakle, razmotrimo situacije u kojima bi Petya mogla napraviti prvi korak (7;S) i u (10;S). Naznačimo hoće li se ove pozicije osvojiti jednim potezom: npr (7;19) osvajanje pozicije jer igrač će napraviti potez (7;38) i pobijedit će (7 + 38 = 45). Shodno tome, sve pozicije su dobitne (7; više od 19). Analizirajmo tabelu, povećavajući broj kamenčića u prvoj hrpi i tražeći pobjedničke pozicije u jednom potezu:

  • Sljedeća logika rezonovanja: Vanja može pobijediti svojim prvim potezom, dok Petya svojim prvim potezom može preći na pobjedničke pozicije samo od prvog poteza (u +). Označimo ove pozicije, uzimajući u obzir da je ovo Petyin prvi potez, a broj kamenja u prvoj hrpi trebao bi biti 5. Pronađene pozicije će gubiti pozicije (-):

  • Nalazimo jedinu takvu vrijednost - (5; 19). One. S = 19.

    • Odgovor 1 b): S=19 (Na Jedinstvenom državnom ispitu objasnite poteze, na primjer: (5; 19) -> (Petini potezi): (5;21),(5;28);(7;19);(7;28). Vanja će pobediti svuda sledećim potezom, vidi prethodni pasus)

    Zadatak 2:

  • Imajte na umu da su u tabeli svi rezultujući "uglovi" izgubljene pozicije (od 1. poteza): to jest, ako se igrač nađe u takvoj poziciji, onda može preći samo na pobjedničke pozicije (tj. protivnik pobijedit će sljedećim potezom):

  • Logika rasuđivanja: Petya će moći pobijediti svojim drugim potezom kada prvim potezom završi u gubitnoj poziciji, tj. će dovesti protivnika u situaciju gubitka. Ove vrijednosti su: S = 16, 17 ili 18. Nazovimo ove pozicije dobitnim iz drugog poteza (2+):

    • Odgovor 2: S = 16, 17 ili 18

    Zadatak 3:

  • Naznačimo u tabeli i pozicije koje su dobitne od n-tog poteza: kada igrač može prebaciti protivnika u izgubljenu poziciju:

  • Naznačimo i izgubljene pozicije iz drugog poteza: igrač koji se nađe u takvoj poziciji može se kretati samo na pobjedničke pozicije (tada će protivnik pobijediti):

  • Logika rasuđivanja: Vanja može pobijediti svojim prvim ili drugim potezom, kada Petya može pogoditi prvim potezom samo bilo na pobjedničku poziciju iz prvog poteza (+), ili na pobjedničku poziciju iz drugog ili n-og poteza (2+). Ovo je pozicija na S = 14:


    • Odgovor 3: S=14 (Na ispitu objasniti poteze, pozivajući se na objašnjenja iz prethodnih paragrafa)

    Analiza 26 zadatka USE 2017 iz informatike iz demonstracije. Ovo je zadatak iz drugog dijela visokog nivoa težine. Predviđeno vrijeme za završetak zadatka je 30 minuta. Maksimalan broj bodova za izvršenje zadatka je 3.

    Provjereni elementi sadržaja:
    — Sposobnost da se napravi stablo igre prema datom algoritmu i opravda pobjednička strategija.

    Zadatak 26

    Dva igrača, Paša i Valja, igraju sledeću igru. Ispred igrača je gomila kamenja. Igrači se kreću redom, Pasha pravi prvi potez. U jednom potezu, igrač može dodati na gomilu jedan kamena ili povećati broj kamenja u gomili dvaput. Na primjer, ako imate gomilu od 15 kamenčića, u jednom potezu možete dobiti hrpu od 16 ili 30 kamenčića. Svaki igrač ima neograničen broj kamenja za poteze.
    Igra se završava u trenutku kada broj kamenčića u hrpi postane najmanje 20. Ako istovremeno nema više od 30 kamenčića u gomili, tada se igrač koji je napravio posljednji potez smatra pobjednikom. U suprotnom, njegov protivnik postaje pobjednik. Na primjer, ako je na hrpi bilo 17 kamenčića, a Pasha udvostruči broj kamenčića na hrpi, onda će se igra završiti i Valya će biti pobjednik. U početnom trenutku bilo je na gomili S kamenje, 1 ≤ S ≤ 19.

    Reći ćemo da igrač ima pobednička strategija, ako može pobijediti bilo kojim potezom protivnika. Opisati igračevu strategiju znači opisati koji bi potez trebao napraviti u svakoj situaciji na koju može naići u različitim igrama protivnika.

    Dovršite sljedeće zadatke.
    1. a) Na kojim vrijednostima broja S Može li Paša pobijediti u jednom potezu?
    Navedite sve takve vrijednosti i Pašine odgovarajuće poteze.
    b) Koji igrač kada ima pobjedničku strategiju S = 18, 17, 16?
    Opišite pobjedničke strategije za ove slučajeve.
    2. Ko od igrača kada ima pobjedničku strategiju S= 9,8? Opišite relevantne pobjedničke strategije.
    3. Ko od igrača kada ima pobjedničku strategiju S= 7? Konstruirajte stablo svih mogućih igara ovom pobjedničkom strategijom (u obliku slike ili tabele). Na rubovima stabla označite ko se kreće; u čvorovima - broj kamenja na poziciji.

    1. a) Paša može pobijediti ako S= 19 ili S= 10, 11, 12, 13, 14, 15. Sa S= 19 U prvom potezu, jedan kamen se mora dodati na gomilu, sa naznačenim preostalim vrijednostima S potrebno je udvostručiti broj kamenja.

    b) Kada S= 16, 17 ili 18 udvostručavanje broja kamenova nema smisla, jer nakon takvog poteza protivnik pobjeđuje. Stoga možemo pretpostaviti da je jedini mogući potez dodavanje jednog kamena na gomilu.

    At S= 18 nakon takvog Pašinog poteza, na gomili će biti 19 kamena. U ovoj poziciji pobjeđuje hodač (tj. Valya). (vidi tačku 1a): at S= 18 Pasha (igrač koji mora ići prvi) gubi.

    Vali ima pobjedničku strategiju.

    At S= 17, nakon što Paša prvim potezom doda jedan kamen, na gomili će biti 18 kamenčića. U ovoj poziciji, hodač (tj. Valya) gubi (vidi gore): at S= 17 Pasha (igrač koji mora prvi krenuti) pobjeđuje. Paša ima pobedničku strategiju.

    At S= 16 Valya ima pobedničku strategiju. Zaista, ako Pasha udvostruči broj kamenčića u svom prvom potezu, tada gomila postaje 32 kamena, a igra se odmah završava pobjedom Valija. Ako Paša doda jedan kamen, tada gomila postaje 17 kamenčića. Kao što već znamo, u ovoj poziciji pobjeđuje igrač koji se mora pomaknuti (tj. Valya).

    U svim slučajevima pobjeda se postiže činjenicom da prilikom svog poteza igrač sa pobjedničkom strategijom mora dodati jedan kamen na gomilu.

    Moguće je nacrtati stabla svih mogućih strana za određene vrijednosti S.
    Druga mogućnost je (1) istaći da udvostručavanje hrpe nema smisla i (2) reducirati slučaj sekvencijalno S= 18 po slučaju S= 19, slučaj S= 17 – povodom S= 18, itd.

    2. Kada S= 9 ili 8 Pasha ima pobedničku strategiju. Sastoji se od udvostručavanja broja kamenčića u gomili i dobijanja gomile koja će imati 18 odnosno 16 kamenčića. U oba slučaja, igrač koji napravi potez (sada Valya) gubi (vidi tačku 1b).

    3. Kada S= 7 Valya ima pobedničku strategiju. Nakon Pašinog prvog poteza, gomila može imati 8 ili 14 kamenčića. U obje ove pozicije, igrač koji napravi potez (sada Valya) pobjeđuje. Dešava se S= 8 razmatrano u tački 2, slučaj S= 14 recenziranih u tački 1a.

    Tabela prikazuje stablo mogućih igara za Valijevu opisanu strategiju. Konačne pozicije (Valja pobjeđuje u njima) su podvučene. Na slici je isto drvo prikazano grafički (oba načina prikazivanja stabla su prihvatljiva).

    Drvo svih mogućih igara pod Valjinom strategijom. Znak >> označava pozicije na kojima igra završava.

    Dva igrača, Pasha i Vova, igraju sledeću utakmicu. Ispred igrača je gomila kamenja. Igrači se kreću redom, Pasha pravi prvi potez. U jednom potezu, igrač može dodati 1 kamen ili 10 kamenčića na gomilu. Na primjer, ako imate gomilu od 7 kamenčića, u jednom potezu možete dobiti hrpu od 8 ili 17 kamenčića. Svaki igrač ima neograničen broj kamenja za poteze. Igra se završava kada broj kamenčića u hrpi postane najmanje 31. Pobjednik je igrač koji je napravio zadnji potez, odnosno prvi koji je dobio hrpu koja sadrži 31 ili više kamenčića.

    U početku je u gomili bilo S kamenja, 1 ≤ S ≤ 30.

    Rješenje.

    1. a) Paša može pobijediti ako je S = 21, ..., 30. Sa manjim vrijednostima S, u jednom potezu nemoguće je dobiti gomilu sa više od 30 kamenčića. Pasha treba samo da poveća broj kamenova za 10. Za S 1. b) Vova može pobijediti na prvi potez (bez obzira kako Pasha igra) ako gomila u početku sadrži S = 20 kamenova. Tada će nakon Pašinog prvog poteza na gomili biti 21 kamen ili 30 kamenčića. U oba slučaja, Vanya povećava broj kamenova za 10 i pobjeđuje u jednom potezu.

    2. Moguće vrijednosti S: 10, 19. U ovim slučajevima Paša očito ne može pobijediti prvim potezom. Međutim, on može dobiti gomilu od 20 kamenčića (na S=10 povećava broj kamenčića za 10; na S=19 dodaje 1 kamen). Ovaj stav je razmatran u stavu 1 b. U njemu igrač koji će krenuti (sada je to Vova) ne može pobijediti, ali će njegov protivnik (odnosno Pasha) pobijediti na sljedećem potezu.

    3. Moguća vrijednost S: 18. Nakon Pašinog prvog poteza, na hrpi će biti 19 ili 28 kamenčića. Ako je na hrpi 28 kamenčića, Vova će povećati broj kamenčića za 10 i vi igrate prvim potezom. Situacija kada je 19 kamenčića u gomili obrađena je u paragrafu 2. U ovoj situaciji, igrač koji će krenuti (sada je to Vova) pobjeđuje svojim drugim potezom.

    Gost 26.05.2014 12:31

    Tačka 3. Ali šta je sa situacijom kada je u početku 9 kamenja na gomili. Nakon Pašinog poteza, kamenčići postaju ili 10 ili 19, Vasja završava do 20 i dalje prema tački 1.b.

    Konstantin Lavrov

    Da, 9 je takođe tačan odgovor. Dovoljno je navesti barem jednu tačnu vrijednost.

    Dva igrača, Pasha i Vova, igraju sledeću utakmicu. Ispred igrača je gomila kamenja. Igrači se kreću redom, Pasha pravi prvi potez. U jednom potezu, igrač može dodati 1 kamen ili 10 kamenčića na gomilu. Na primjer, ako imate gomilu od 7 kamenčića, u jednom potezu možete dobiti hrpu od 8 ili 17 kamenčića. Svaki igrač ima neograničen broj kamenja za poteze. Igra se završava kada broj kamenčića na hrpi postane najmanje 41. Pobjednik je igrač koji je napravio posljednji potez, odnosno prvi koji je dobio hrpu koja sadrži 41 ili više kamenčića.

    U početku je u gomili bilo S kamenja, 1 ≤ S ≤ 40.

    Reći ćemo da igrač ima pobjedničku strategiju ako može pobijediti bilo kojim potezom protivnika. Opisati igračevu strategiju znači opisati koji bi potez trebao napraviti u bilo kojoj situaciji na koju se može susresti različitim igrama od neprijatelja.

    Dovršite sljedeće zadatke. U svim slučajevima obrazložite svoj odgovor.

    1. a) Navedite sve takve vrijednosti broja S za koje Paša može pobijediti u jednom potezu. Opravdajte da su sve tražene vrijednosti S pronađene i označite pobjedničke poteze.

    b) Navedite vrijednost S tako da Paša ne može pobijediti u jednom potezu, ali svakim Pašinim potezom Vova može pobijediti svojim prvim potezom. Opišite Vovinu pobjedničku strategiju.

    2. Navedite dvije vrijednosti S za koje Pasha ima dobitnu strategiju, a Pasha ne može pobijediti u jednom potezu, ali može pobijediti svojim drugim potezom, bez obzira kako se Vova kreće. Za date vrijednosti S, opišite Pašinu pobjedničku strategiju.

    3. Navedite vrijednost S za koju Vova ima pobjedničku strategiju koja mu omogućava da pobijedi u prvom ili drugom potezu kad god Pasha igra, ali Vova nema strategiju koja će mu omogućiti pobjedu u prvom potezu. Za navedenu vrijednost S, opišite Vovinu pobjedničku strategiju. Konstruirajte stablo svih mogućih igara ovom Vovinom pobjedničkom strategijom (u obliku figure ili tabele). Na rubovima stabla označite ko se kreće, a na čvorovima - broj kamenja u hrpi.

    Rješenje.

    1. a) Paša može pobijediti ako je S = 31, ..., 40. Sa manjim vrijednostima S ne može se dobiti hrpa sa više od 40 kamenčića u jednom potezu. Dovoljno je da Paša poveća broj kamenčića za 10. Sa S b) Vova može pobijediti na prvi potez (bez obzira kako Pasha igra) ako u početku ima S = 30 kamenčića u gomili. Tada će nakon prvog Pašinog poteza na gomili biti 31 kamen ili 40 kamenčića. U oba slučaja, Vanya povećava broj kamenova za 10 i pobjeđuje u jednom potezu.

    2.  Moguće vrijednosti S: 20, 29. U ovim slučajevima Paša očigledno ne može pobijediti prvim potezom. Međutim, on može dobiti gomilu od 30 kamenčića (pri S = 20 povećava broj kamenčića za 10; pri S = 29 dodaje 1 kamen). Ovaj stav je razmatran u stavu 1. b). U njemu igrač koji će krenuti (sada je to Vova) ne može pobijediti, a njegov protivnik (to jest, Pasha) će pobijediti na sljedećem potezu.

    3. Moguća vrijednost S: 28. Nakon Pašinog prvog poteza, na hrpi će biti 29 ili 38 kamenčića. Ako je na hrpi 38 kamenčića, Vova će povećati broj kamenčića za 10 i igrate na prvi potez. Situacija, kada je 29 kamenčića na gomili, govori se u paragrafu 2. U ovoj situaciji, igrač koji će krenuti (sada je to Vova) pobjeđuje svojim drugim potezom.

    Tabela prikazuje stablo mogućih igara za Vovinu strategiju opisanu gore. Konačne pozicije (u njima Vova pobjeđuje) su podvučene. Na slici je isto stablo prikazano grafički (oba načina predstavljanja stabla su prihvatljiva).

    Dva igrača, Petya i Vanya, igraju sljedeću utakmicu. Ispred njih su dvije gomile kamenja, od kojih se u prvoj nalaze 2, au drugoj - 3 kamena. Svaka igra-ro-ka nema-ogran-no-chen-ali puno kamenja. Igrači hodaju oko-re-di, prvi potez je de-la-et Petya. Pokret se sastoji u tome da igrač ili uklanja broj kamenčića na nekoj hrpi, ili dodaje 4 kamena na neku hrpu. Igra se završava u trenutku kada je ukupan broj kamenčića u dvije hrpe najmanje 31. Ako je u trenutku završetka igre ukupan broj kamenčića u dvije hrpe najmanje 40, onda je Petya pobijedila, u suprotnom je pobijedila Vanya. Ko si ti-ig-ry-va-et u nedostatku greške-boch-noy igre obje igre-ro-kov? Koji bi trebao biti prvi potez vas-ig-ry-va-yu-sche-go-ro-ka? Obrazložite odgovor.

    Rješenje.

    Vanya pobjeđuje.

    Da biste to dokazali, razmotrite nepotpuno stablo igre, dizajnirano u obliku tablice, gdje svaka ćelija sadrži parove brojeva odvojenih zarezom. Ovi brojevi odgovaraju broju kamenčića u svakoj fazi igre u prvoj i drugoj hrpi, respektivno.

    Tabela sadrži sve moguće poteze za prvog igrača. To pokazuje da za bilo koji potez prvog igrača, drugi ima potez koji vodi do pobjede.

    Dva igrača, Petya i Vasya, igraju sljedeću igru. Ispred njih leže dvije gomile kamenja, od kojih prva sadrži 2, a druga - 1 kamen. Svaki igrač ima neograničen broj kamenja. Igrači se izmjenjuju, Petya ide prvi. Potez je da igrač ili poveća broj kamenčića u nekoj hrpi za 3 puta, ili doda 3 kamena na neku gomilu. Pobjeđuje igrač nakon čijeg poteza ima najmanje 24 kamena u jednoj od hrpa. Ko pobjeđuje kada igra bez grešaka? Koji bi trebao biti prvi potez pobjedničkog igrača?

    Obrazložite svoj odgovor.

    Rješenje.

    Petya pobjeđuje; svojim prvim potezom mora utrostručiti broj kamenčića u drugoj hrpi. Da biste to dokazali, razmotrite nepotpuno stablo igre, dizajnirano u obliku tablice, gdje svaka ćelija sadrži parove brojeva odvojenih zarezom. Ovi brojevi odgovaraju broju kamenčića u svakoj fazi igre u prvoj i drugoj hrpi, respektivno.

    Tabela sadrži sve moguće opcije za Vasyine poteze. To pokazuje da sa svakim odgovorom Petya ima potez koji vodi do pobjede.

    Dva igrača, Petya i Vanya, igraju sljedeću igru. Ispred igrača je gomila kamenja. Igrači se izmjenjuju, Petya pravi prvi potez. U jednom potezu, igrač može dodati jedan kamen na gomilu ili povećati broj kamenčića u gomili pet puta. Na primjer, ako imate gomilu od 10 kamenčića, u jednom potezu možete dobiti gomilu od 11 ili 50 kamenčića. Svaki igrač ima neograničen broj kamenja za poteze.

    Igra se završava onog trenutka kada broj kamenčića na hrpi postane veći od 100. Pobjednik je igrač koji je napravio posljednji potez, odnosno prvi koji je dobio gomilu koja sadrži 101 ili više kamenčića.

    U početku je u gomili bilo S kamenja, 1 ≤ S ≤ 100.

    Za igrača se kaže da ima pobjedničku strategiju ako može pobijediti bilo kojim potezom svog protivnika. Opisati igračevu strategiju znači opisati koji bi potez trebao napraviti u bilo kojoj situaciji na koju se može susresti različitim igrama od neprijatelja.

    Dovršite sljedeće zadatke. U svim slučajevima obrazložite svoj odgovor.

    1. a) Za koje vrijednosti broja S Petya može pobijediti svojim prvim potezom? Navedite sve takve vrijednosti i Petitov pobjednički potez.

    b) Navedite vrijednost S tako da Petya ne može pobijediti u jednom potezu, ali za svaki potez koji Petya napravi, Vanja može pobijediti svojim prvim potezom. Opišite Vanjinu pobjedničku strategiju.

    2. Navedite dvije vrijednosti S za koje Petya ima pobjedničku strategiju, a Petya ne može pobijediti prvim potezom, ali Petya može pobijediti svojim drugim potezom, bez obzira na to kako se Vanja kreće. Za date vrijednosti S, opišite Petitovu pobjedničku strategiju.

    3. Navedite vrijednost S tako da Vanja ima pobjedničku strategiju koja mu omogućava da pobijedi prvim ili drugim potezom u bilo kojoj igri Petya, a da istovremeno Vanya nema strategiju koja će mu omogućiti pobjedu s prvim pokret.

    Za datu vrijednost S, opišite Vanjinu pobjedničku strategiju. Konstruirajte stablo svih mogućih igara s Vanjinom pobjedničkom strategijom. Predstavite ga u obliku figure ili tabele. Za svaku ivicu stabla označite ko čini potez; za svaki čvor naznačite broj kamenja na poziciji.

    Rješenje.

    1. a) Petya može pobijediti ako je S = 21, ..., 100. Sa manjim vrijednostima S, u jednom potezu nemoguće je dobiti gomilu sa više od 100 kamenčića. Dovoljno je da Petya poveća broj kamenja za 5 puta. Kada je S 1. b) Vanya može pobijediti prvim potezom (bez obzira kako Petya igra), ako u početku ima S = 20 kamenčića u gomili. Tada će nakon Petjinog prvog poteza biti 21 kamen ili 100 kamenčića u gomili. U oba slučaja, Vanya povećava broj kamenova 5 puta i pobjeđuje u jednom potezu.

    2. Moguće vrijednosti S: 4, 19. U ovim slučajevima Petya očigledno ne može pobijediti prvim potezom. Međutim, on može dobiti gomilu od 20 kamenčića (sa S = 4, povećava broj kamenčića za 5 puta; sa S = 19, dodaje 1 kamen). Ovaj stav je razmatran u stavu 1 b). U njemu igrač koji će se pomaknuti (sada Vanya) ne može pobijediti, ali će njegov protivnik (to jest Petya) pobijediti na svom sljedećem potezu.

    3. Moguća vrijednost S: 18. Nakon Petjinog prvog poteza, na hrpi će biti 19 ili 90 kamenčića. Ako je na hrpi 90 kamenčića, Vanya će povećati broj kamenčića 5 puta i pobijediti prvim potezom. Situacija kada je 19 kamenčića u gomili obrađena je u paragrafu 2. U ovoj situaciji, igrač koji će krenuti (sada je to Vanya) pobjeđuje svojim drugim potezom.

    Tabela prikazuje stablo mogućih igara za Vanjinu strategiju opisanu gore. Konačne pozicije (u njima Vanya pobjeđuje) su podvučene. Na slici je isto stablo prikazano grafički (oba načina prikazivanja su prihvatljiva).


    Uradite testove za ove zadatke

    Otvaramo pretplatu na interaktivne simulatore za pripremu za Jedinstveni državni ispit iz informatike 2016.

    Svako sa novčanikom Visa, MasterCard, Yandex.Money, pa čak i sa pozitivnim stanjem na svom mobilnom telefonu, može naručiti 60 jedinstvenih interaktivnih animacija za pripremu za Jedinstveni državni ispit iz informatike 2016. bez napuštanja računala

    Simulator za zadatak br. 26 demo verzije Jedinstvenog državnog ispita 2015.
    u informatici i IKT metodom "Brda i rupe".

    Najjednostavnije rješenje za problem 26 ili stari C3
    u informatici i informaciono-komunikacionim tehnologijama pomoću vizuelne metode “Brda i rupe”.

    Primjer rješavanja problema u slučaju povećanja kamenja u hrpi na dva načina: “+1” i “*2”

    Dva igrača, Petya i Vanya, igraju sljedeću igru. Ispred igrača je gomila kamenja. Igrači se izmjenjuju, Petya pravi prvi potez. U jednom potezu, igrač može dodati jedan kamen na gomilu ili udvostručiti broj kamenčića na hrpi. Na primjer, ako imate gomilu od 15 kamenčića, u jednom potezu možete dobiti hrpu od 16 ili 30 kamenčića. Svaki igrač ima neograničen broj kamenja za poteze. Igra se završava kada broj kamenčića na hrpi postane najmanje 22. Pobjednik je igrač koji je napravio zadnji potez, odnosno prvi koji je dobio hrpu koja sadrži 22 ili više kamenčića.
    U početku je u gomili bilo S kamenja, 1<= S <=21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
    Dovršite sljedeće zadatke. U svim slučajevima obrazložite svoj odgovor.

    1. a) Navedite sve takve vrijednosti broja S za koje Petya može pobijediti u jednom potezu. Opravdajte da su sve tražene vrijednosti S pronađene i označite pobjednički potez za svaku određenu vrijednost S.
    b) Navedite vrijednost S tako da Petya ne može pobijediti u jednom potezu, ali za svaki potez koji Petya napravi, Vanja može pobijediti svojim prvim potezom. Opišite Vanjinu pobjedničku strategiju.

    2. Navedite dvije takve vrijednosti S za koje Petya ima pobjedničku strategiju, i
    – Petja ne može da pobedi u jednom potezu, i
    – Petya može pobijediti svojim drugim potezom, bez obzira na to kako se Vanja kreće.
    Za svaku datu vrijednost S, opišite Petyinu pobjedničku strategiju.

    3. Navedite vrijednost S, pri kojoj:
    – Vanja ima pobedničku strategiju koja mu omogućava da pobedi prvim ili drugim potezom u bilo kojoj Petjinoj igri, i
    – Vanja nema strategiju koja će mu omogućiti da bude zagarantovana pobeda na prvom potezu.
    Za datu vrijednost S, opišite Vanjinu pobjedničku strategiju.
    Konstruirajte stablo svih mogućih igara s ovom Vanjinom pobjedničkom strategijom (u obliku slike ili tablice). Na rubovima stabla označite ko se kreće; na čvorovima označite broj kamenja u hrpi.

    Pitanje 1a.
    Radeći unazad od “pobjede” određujemo granice početne pobjedničke pozicije: 22 – 1 = 21 I 22/2 = 11
    Za bilo koji broj koji se nalazi unutar ovog raspona vrijedi sljedeći unos: max0*2>= 22 ili max0*2 > 21 (zaokružite ovaj raspon na vrhu i označite ga kao max0, što će značiti početnu dobitnu poziciju ili pobjedu u jednom potezu)

    1a) Petya pobjeđuje svojim prvim potezom na 11<= S <= 21. Для этого достаточно число камней в куче увеличить вдвое и их всегда получится более 21.

    Pitanje 1b. Da biste odgovorili na ovo pitanje, morate pronaći pozicije, nazovimo ih min0 , od kojih svi mogući potezi vode do početne pobjedničke pozicije, koju smo označili kao max0 . Obrnuto određujemo “sumnjive” pozicije na min0 :
    11/2=? nije potpuno podijeljena, dakle, takva pozicija ne postoji. Ostaje samo S= 11-1=10
    (ali za sada je ovo samo nagađanjemin0 , pa crtamo "jama" dvije karakteristike, što će značiti - ne zaboravite na postojanje 2 moguća poteza koje ćete morati provjeriti!)

    Provjeravamo pretpostavku za S = 10 na min0. Ova provjera će poslužiti kao odgovor na pitanje 1b
    Kada je S = 10, Petya ima 2 poteza s kojima ne može pobijediti u jednom potezu, ali sa bilo kojim Petjinim potezom, Vanja može pobijediti svojim prvim potezom:
    Svaki Petyin potez “10+1=11” ili 10*2=20 vodi Vanjinoj početnoj pobjedničkoj poziciji, koja, udvostručivši broj kamenčića u hrpi, dobije 22 ili 40, što je više od 21 i Van će pobediti
    Stoga, dole ocrtavamo poziciju S = 10 punom linijom ( nacrtati rupu) - min0 (početni gubitak ili gubitak za 1. okret):

    Odgovor na pitanje 1b. može biti ovako: Sa S = 10, Petya ima 2 poteza sa kojima ne može pobijediti, ali sa bilo kojim Petjinim potezom, Vanja može pobijediti svojim prvim potezom. Svaki Petyin potez “10+1=11” ili “10*2=20” vodi Vanju na početnu pobedničku poziciju, koji, udvostručavajući broj kamenčića u gomili, dobija 22 ili 40, što je više od 21, a Vanja pobjeđuje

    Pitanje 2. Da bi Petya bio zagarantovan da pobedi na svom drugom potezu, tj. bio na poziciji max0 , nakon Vanjinog poteza, treba mu njegov prvo kreći se" stavi Vanju u rupu" Jasno je da takvih pozicija može biti dva, čije vrijednosti nalazimo obrnuto i obavezno provjerite...
    Prva sumnjiva pozicija "10-1=9"

    S=9. Provjerimo ovu poziciju da osiguramo pobjedu!
    Da je Petya igrao davanje, napravio bi potez "9*2 = 18" , ali on treba da pobijedi, tako da odbacujemo ovaj potez. Ostaje samo "9+1 = 10", Ivanya je unutra “jama” - što dovodi Petju do pobjede u svom drugom potezu, bez obzira na to kako Vanja izađe!

    Druga "sumnjiva pozicija" 10/2 = 5

    S=5. Provjerimo ovu poziciju da osiguramo pobjedu! pokret "5+1=6" , odlaže igru, tako da je ne razmatramo (odbacite)
    Ostaje samo "5*2=10", Ivanya je unutra "jama" -što dovodi Petya do pobjede u svom drugom potezu, bez obzira kako Vanya ide!

    Odgovor 2 može biti:

    Sa S = 5 i 9, Petya ne može pobijediti prvim potezom, ali može pobijediti drugim potezom, a za to mu je potrebno samo napraviti potez “5*2 = 10” sa pozicije S = 5, i time poslati Vanja na početnu gubitnu poziciju ili sa pozicije S = 9 pošalji je u istu poziciju potezom “9+1=10”

    Pitanje 3. Vanya mora pobijediti, stoga mora biti na vrhu max0, to znači da Petya sigurno mora završiti min0, gdje ići "zatvorit će" Vanja iz max1, Sve što treba da uradimo je da pronađemo pozicije sa kojih bi Petya sigurno ušao max1
    Pronalazimo „sumnjive“ pozicije do kojih bi Petya mogla dovesti max1 koristeći istu obrnutu:
    9-1=8
    9/2=? 9 nije deljivo sa 2 - nestaje
    5-1=4
    5/2=? 5 sa 2 nije deljivo - nestaje
    Nalazimo da je takvo "sumnjivo" Postoje samo dvije pozicije, ali ih još uvijek treba provjeriti!

    S=8. Hajde da proverimo ovu poziciju da vidimo da li će Petya sigurno izgubiti!
    Petyin potez je 8+1=9 i Vanya pobjeđuje svojim drugim potezom
    Petyin potez je 8*2=16 i Vanja pobjeđuje svojim prvim potezom
    S=4. Hajde da proverimo ovu poziciju da vidimo da li će Petya sigurno izgubiti!
    Petjin potez je 4+1=5 i on bi izgubio, ali sa ove pozicije Petja ima koristi od poteza 4*2=8, pri čemu Vanja upada u „rupu“ i gubi. Ali moramo pronaći Vanjinu pobjedničku strategiju, tako da isključimo poziciju S=4 iz kandidata i dobijemo konačnu "slika":

    3. Na poziciji S = 8 – Vanja nema strategiju koja će mu omogućiti da dobije prvim potezom, pošto njegova pobeda zavisi od Petjinog poteza, tako da Vanja ima strategiju da pobedi ili prvim ili drugim potezom: Ako Petja odabere potez “+1”, gomila postaje 9 kamenčića i Vanya pobjeđuje u 2. potezu (vidi odgovor na pitanje 2). Ako Petya odabere potez “*2”, Vanya pobjeđuje svojim prvim potezom, udvostručavajući broj kamenčića u gomili.

    Slika koju smo dobili iznad može se lako ponovo nacrtati u stablo igre tako što ćete prvo označiti izgubljene poteze crvenim linijama (debela linija je „ kratki udar" ili " +1 ", i tanak - " dugo" ili " *2 ") i zeleno - pobjednički. (crvene debele linije mogu se povući s grbama prema gore, koje će se poklapati sa smjerom "kratkih" grana stabla divljači)

    Konačna strateška slika Petitove pobjede može izgledati ovako:

    Ostale metode za rješavanje problema ove vrste možete pronaći ovdje -