БДИ: информатика һәм ИКТ. Отышлы уен стратегияләре

Аида ГАЙНЕТДИНОВА,
КФУның исәпләү математикасы һәм мәгълүмати технологияләр институты директоры урынбасары, информатика һәм ИКТ буенча дәүләт йомгаклау аттестациясенең предмет комиссиясе рәисе
Равил ҺАДИЕВ,
КФУның исәпләү математикасы һәм мәгълүмати технологияләр институтының өлкән укытучысы
 
Альбина ҺАДИЕВА,
Казандагы 135 нче урта мәктәпнең югары квалификация категорияле информатика укытучысы
Уен стратегияләренә караган мисаллар – БДИның 26 нчы катлаулы биремендә. Әлеге биремдә стратегияләрне дөрес ачыклаган укучы 3 балл ала.
Биремдә ике уенчы: Булат (беренче) белән Ирек (икенче), чиратлашып, каралган кагыйдәләр буенча йөри. Уенда тәмамлау һәм отучыны билгеләүче кагыйдәләр бирелә.
Без иң башта стратегияне билгели торган мисалларны карап үтик.
№26.1. Уенда n=7 төймә бирелгән. Уенчылар Булат белән Ирек, чиратлашып, берәр төймә ала. Соңгы төймәне алучы ота. Кайсысы ота: Булатмы, әллә Ирекме?
Чишү:
Уенда 7 төймә (ООООООО) бирелгән. Уенчылар сулдан уңга берәр төймә ала. Уң төймәне алганы ота. Аны «Ө» белән алмаштырабыз: ООООООӨ. Аны алыр өчен алдагы икенче төймәне алыштырырга кирәк. Шулай итеп, отышлы төймәләрне «Ө»гә алмаштырабыз: ӨОӨОӨОӨ.
Биредә инде оту өчен беренче булырга кирәклеге күренә. Булат «Ө» төймәләрен җыеп барыр, Иреккә «О» төймәләре калыр.
Бу мәсьәләдән тагын шул күренә: n так сан булса, «Ө» төймә сул якта була, һәм Булат ота.
Әгәр дә n җөп сан булса, «О» төймәсе сул якта була. Булат «Ө» төймәсен ала алмый, Ирек барлык «Ө» төймәләрен ота.
№26.2. Уенда n=7 төймә бирелгән. Уенчылардан Булат белән Ирек, чиратлашып, бер яки ике төймә ала. Соңгы төймәне алучы ота. Кайсысы ота: Булатмы, әллә Ирекме?
Чишү:
I вариант
Уенда 7 (ООООООО) төймә бирелгән. Уенчылар сулдан-уңга бер яки ике төймә ала. Уң төймәне алганы ота. Аны «Ө» төймәсенә алмаштырабыз: ООООООӨ. Аны алыр өчен алдагы өченче төймәне алырга кирәк. Чөнки сахырда  өч төймә калса, йөрүче уенчы соңгысын ала алмый. Берне алса, икәү кала: ОӨ һәм икенче уенчы аларны алып ота. Әгәр дә икене алса, бер төймә – Ө кала, һәм икенче уенчы аны ота. Шулай итеп, отышлы төймәләрне «Ө»гә алмаштырабыз: ӨООӨООӨ була. Бу очракта Булат үзенең беренче йөрешендә «Ө»не ала. Аннары Иреккә «О» төймәләре генә кала. Булат «ОӨ» я «Ө» төймәләрен ота.
Әгәр n өчкә бүленмәсә, сул як башында «Ө...» яки «ОӨ...» була. Бу очракта Булат баштан ук «Ө» төймәсен алып отып бара.
Әгәр n өчкә бүленсә, сул як башында «ООӨ...» була. Булат берничек тә «Ө» төймәсен ала алмый. Бу юлы Ирек үз йөрешендә «Ө» төймәсен алып ота.
II вариант
Бу мәсьәләне универсаль ысул белән n=6 булганда чишеп карыйбыз.
Бу уенның оту стратегиясен шулай ук таблица ярдәмендә ачыкларга була.
Иң башта уенда булган барлык хәлләр таблицасын төзибез. Анда отучы ачыклана. Аннары оту стратегиясенең таблицасын төзибез.

n	Б1	И1	Б2	И2	Б3	И3
6	≠>5	≠>4	=>3	≠>2	≠>1	=>0!И
					=>0!Б
				≠>1	=>0!Б
			≠>2	≠>1	=>0!Б
				=>0!И
		=>3	≠>2	≠>1	=>0!Б
				=>0!И
			≠>1	=>0!И
	≠>4	=>3	≠>2	≠>1	=>0!Б
				=>0!И
			≠>1	=>0!И
		≠>2	≠>1	=>0!И
			=>0!Б

 
!И – Ирек ота. !Б – Булат ота.
Чишү:
Шуннан чыгып, отышлы йөрешне – «=>» дип, ә оттырышлы йөрешне «≠>» белән билгелибез. 
Бу таблицадан Булатның отышлы беренче йөреше юклыгы, ә Ирекнең Булатның һәр йөрешенә отышлы йөреше барлыгы күренә.
Монда Булатның беренче йөрешләре оттырышлы булуы күренә. Хәзер отышлы стратегия таблицасын Ирек өчен төзибез. Бу таблицада Ирек отышлы йөрешен генә күрсәтә, ә Булат исә бөтен мөмкин булган йөрешен күрсәтергә тиеш.
 

n	Б1	И1	Б2	И2
6	5	3	2	0!И
	4		1

 
Таблица ярдәмендә чишкәндә, n зур булганда, зур мәйдан кирәк. Шуңа күрә соңгы еллардагы биремнәрдә шул таблицаның өлешен генә кулланып мәсьәлә чишәләр.
n=7 булганда. беренче уенчы бер төймә алып ота ала, чөнки 6дан уенны башлаучы оттыра. Ә Булат 7дән 6га күчсә, оту стратегиясенә ия була.
 

n	Б1	И1	Б2	И2	Б3
7	6	5	3	2	0!И
		4		1

 
№26.3. Уенда n=7 төймә бирелгән. Уенчылар Булат белән Ирек, чиратлашып, бер яки ике төймә ала. Соңгы төймәне алучы оттыра. Кайсысы ота: Булатмы, әллә Ирекме?
Чишү:
Уенда 7 төймә (ООООООО) бирелгән. Уенчылар сулдан-уңга бер яки ике төймә ала. Уң төймәне алганы оттыра. Аның алдыннан торган уенчы төймәне ота. Шул төймәне «Ө» төймәсенә алмаштырабыз: ОООООӨО. Аны алыр өчен алдагы өченче төймәне алырга кирәк. Чөнки ахырда өч төймә калса. йөрүче уенчы соңгысын ала алмый. Берне алса, икәү кала: «ОӨ».  Һәм икенче уенчы аларны алып ота. Әгәр дә икене алса, бер төймә – «Ө» кала, һәм икенче уенчы аны алып ота. Шулай итеп, отышлы төймәләрне «Ө»гә алмаштырабыз. Нәтиҗәдә «ООӨООӨО» була. Бк очракта Булат үзенең беренче йөрешендә «Ө»не ала. Иреккә «О» төймәләре генә кала. Булат «ОӨ» яисә «Ө» төймәләрен алып ота.
Бу уен №26.2 дә булган n–1 төймә булгандагы уенга ошаган.
Әгәр n–1 өчкә бүленмәсә, сул як башында «Ө...» яки «ОӨ...» була. Бу очракта Булат «Ө» төймәсен алып отып бара.
Әгәр n–1 өчкә бүленсә, сул як башында «ООӨ...». Булат берничек тә «Ө» төймәсен ала алмый. Бу очракта Ирек «Ө» төймәсен алып ота.
№26.4. Уенда n төймә бирелгән. Уенчылар Булат белән Ирек  чиратлашып, яртысына кадәр яки бер төймә алалар. Соңгы төймәне алучы ота. Өч сорауга җавап бирегез.

• 5 төймә булганда кем ота: Булатмы, әллә Ирекме?


• 6 төймә булганда кем ота: Булатмы яки Ирекме?


• 25 төймә булганда кем ота: Булатмы яки Ирекме?

Чишү:

• Таблица ярдәмендә чишәбез

N	Б1	И1	Б2	И2	Б3
5	≠>3	=>2	≠>1	=>0!И
	≠>4	=>2	≠>1	=>0!И
		≠>3	=>2	≠>1	=>0!Б

 
Ирек ота. Стратегия

N	Б1	И1	Б2	И2
5	3	2	1	0!И
	4

• Таблица ярдәмендә чишәбез

N	Б1
6	=>5
	≠>3,4

 
Монда Булат отканы күренә. Стратегия

N	Б1	И1	Б2	И2	Б3
6	5	4	2	1	0!Б
		3

• N зур булганда, таблица белән чишәргә авыр.

Биредә икенче уенчыга отышлы саннарны ачыклый торган функцияне карыйбыз.
F(k)=2, әгәр k=1, 2*F(k-1)+1, әгәр k>1
Әгәр n=F(k) ниндидер k өчен булса Ирек ота калган бирелгән төймә саннары булса, F(k) төймә калдырып, Булат ота.
Бу функция буенча n=2, 5, 11, 23, 47… булса Ирек ота. n=25 булганда Булат 2не  алып 23не калдырып ота.
№26.5. Уенда ике күч төймәләр бирелгән. Беренчесендә – 5,. икенчесендә – n (01) N нинди булганда, Булат беренче йөрешендә ота?
2) Нинди минималь N булганда һәм Булат җайсыз йөрсә, Ирек беренче йөрешендә ота?
3) N нинди булганда, Ирек бер йөрештә ота алмый, ә беренче яки икенче йөрешендә ота?
Чишү:
1)

N	Б1
5, N	6, N	N=41
	10, N	37<=n<=41
	5, N+1	N=41
	5,2*N	21<=n<=41

 
Җавап: 21<=n<=41
2) Булат нинди генә йөрешендә төймә саны 21 белән 41 арасына өләксә Ирек беренче йөрешендә ота. Бу хәл n=20 булганда була.

N	Б1	И1
5, 20	6, 20	6+40=46!И
	10, 20	10+40=50!И
	5, 21	5+42=47!И
	5, 40	5+80=85!И

Җавап: 20.
3)

N	Б1	И1	Б2	И2
5, 19	6, 19	6, 20	7, 20	7, 40!И
			6, 21	6, 42!И
	5, 20		14, 20	14, 240!И
			6, 40	6, 80!И
	10, 19	10, 38!И
	5, 38	5, 76!И

 
Җавап: 19.
№26.6. Уенда ике күч төймәләр бирелгән. Беренчесендә – 15. икенчесендә – n (01) N нинди булганда, Булат беренче йөрешендә ота?
2) Нинди минималь N булганда һәм Булат җайсыз йөрсә, Ирек беренче йөрешендә ота?
3) N нинди булганда, Ирек бер йөрештә ота алмый, ә беренче яки икенче йөрешендә ота?
Чишү:
1)

N	Б1
15, N	16, N	41>=N>=26
	30, N	12<=n<=41
	15, N+1	41>=N>=26
	15, 2*N	14<=n<=41

 
Җавап: 12<=n<=41.
2) Булат нинди генә йөрешендә төймә саны 14 белән 41 арасына өләксә Ирек беренче йөрешендә ота. Бу хәл n=11 булганда була.

N	Б1	И1	Б2
15, 10	16, 10	32+10=42!И
	30, 10	60+20=80!И
	15, 11	16, 11	32, 11!Б
		30, 11	60, 11Б
		15, 12	30, 12!Б
		15, 20	30, 20!Б
	15, 20	15, 40!И

 
Булатның оту стратегиясе

N	Б1	И1	Б2
15, 10	15, 11	16, 11	32, 11!Б
		30, 11	60, 10!Б
		15, 12	30, 12!Б
		15, 22	15, 44!Б

Җавап: 10.
3)

N	Б1	И1	Б2	И2
15, 9	16, 10	32, 10!И
	30, 9	60, 9!И
	15, 10	15, 11	16, 11	32, 11!И
			30, 11	60, 11!И
			15, 12	30, 12!И
			15, 22	30, 22!И
	15, 18	15, 36!И

 
Җавап: 9.
№26.7. Уен башында n төймә була. Уенчылар Булат белән Ирек чиратлашып өемгә берәр төймә салалар, я ике тапкыр арттыралар. Өемдә төймәне 41 дән артык булса, уен туктала. Соңгы төймә салучы ота.
1а) Ничә n булганда Булат үзенең беренче йөрешендә ота?
1б) Булат беренче йөрешендә ота алмыйча Ирек беренче йөрешенда ота торган n ны исәпләп табыгыз.
2) Булат беренче йөрешендә ота алмый торган, икенче йөрешендә ота торган ике n ны исәпләп табыгыз.
3) Ирек беренче йөрешендә ота алмый торган, икенче йөрешендә ота торган n ны исәпләп табыгыз.
Чишү:
1а)

N	Б1
N	N+1	N=41
	2*N	21<=n<=41

Җавап: 21<=n<=41
1б) n<21 булырга тиеш. Булат үз йөрешендә  N 21 белән 41 арасына эләксә, Ирек беренче йөрешендә ота.

N	Б1	И1
N=20	21	42
	40	80

 
Җавап: N=20 була.
2) Булат өемдә 20 төймә ясаса, икенче йөрешендә ота.

N	Б1	И1	Б2
N=19	20	21	42!Б
N=10		40	80!Б

 
Җавап: 19, 10
3)

N	Б1	И1	Б2	И2
N=18	19	20	21	42!И
			40	80!И
	36	72!И

 
Җавап:  18.
№26.8. Уен башында n төймә була. Уенчылар Булат белән Ирек, чиратлашып, өемгә берәр төймә сала, я ике тапкыр арттыралар. Өемдә төймәләр саны 41 дән артуга, уен туктала. Соңгы төймә салучы төймәләр санын 60 тан арттырса, оттыра.
1а) Ничә n булганда, Булат үзенең беренче йөрешендә ота?
1б) Булат беренче йөрешендә ота алмыйча, Ирек беренче йөрешендә ота торган n ны исәпләп табыгыз.
2) Булат беренче йөрешендә ота алмый, ә икенче йөрешендә ота торган ике n исәпләп табыгыз.
3) Ирек беренче йөрешендә ота алмый, ә икенче йөрешендә ота ала торган n исәпләп табыгыз.
Чишү:
1а)

N	Б1
N	N+1	N=41!Б
	2*N	21<=n<=30

 
Җавап: 21<=n<=30, яки 41.
1б) n<21, 31 белән 40 арасында булырга тиеш. Булат үз йерешендә N=40 булганда, Ирек беренче йөрешен ота.

N	Б1	И1
N=40	41	42!И
	80!И

 
Җавап: N=40 була..
2) Булат өемдә 20 төймә ясаса, икенче йөрешендә ота.

N	Б1	И1	Б2
N=39	40	41	42!Б
N=20		80!Б

 
Җавап: 39, 20.
3)

N	Б1	И1	Б2	И2
N=38	39	40	41	42!И
			80!И
	76!И

 
Җавап: 38.
№26.9. Уенда ике күч – n, m төймәләр бирелгән. Уенчылар Булат белән Ирек, чиратлашып, бер күчтән ниндидер өлешен алалар, яки ике күчтән дә бертигез.

• N=3, m=2. Кем ота?


• N=5, m=7. Кем ота?


• N=8, m=5. Кем ота?

Чишү:
Мәсьәләне ачыклау өчен таблица төзибез.
Бу юлы беренче өемдәге төймә санын исәптә тотабыз, баганалар буенча икенче өемдәгесен.

N/M	0	1	2	3	4	5	6	7	8
0	0	Б1	Б1	Б1	Б1	Б1	Б1	Б1	Б1
1	Б1	Б1	И1	Б2	Б2	Б2	Б2	Б2	Б2
2	Б1	И1	Б1	Б2	Б2	Б2	Б2	Б2	Б2
3	Б1	Б2	Б2	Б1	Б2	И2	Б3	Б3	Б3
4	Б1	Б2	Б2	Б2	Б1	Б2	Б3	И3	Б4
5	Б1	Б2	Б2	И2	Б2	Б1	Б2	Б3	Б4
6	Б1	Б2	Б2	Б3	Б3	Б2	Б1	Б2	Б3
7	Б1	Б2	Б2	Б3	И3	Б3	Б2	Б1	Б2
8	Б1	Б2	Б2	Б3	Б4	Б4	Б3	Б2	Б1

 
Таблица төзегәндә, беренче күзәнәктә 0 куябыз. Горизонталь, вертикаль, диагональ буенча Б1 – Булат беренче йөрештә оту очракларын куябыз. И1 – 0 гә иң якын ике буш  күзәнәк билгелибез. Аннары горизонталь, вертикаль, диагональ буенча буш күзәнәкләрдә Б2 һәм иң якын ике буш күзәнәктә И2 куябыз. Шулай дәвам итәбез.
Оту стратегиясе
Б1 – беренче йөрешендә ота, И1 – Булат ота алмый, Ирек беренче йөрешендә ота. Булат беренче йөрешендә ота алмый, Б1 чыга. Ирек Б1 0 гә чыга.
Б2 – Булат беренче йөрешендә ота алмый, И1гә чыга. Ирек Б1гә генә йөри ала. Булат 0 гә чыгып ота. Шулай дәвам итәбез. И2 – Булат беренче йөрешендә ота алмый, Б2гә яки Б1гә йөри. Анда Ирек 0гә, я И1гә  йөреп ота.
Шулай стратегия ачыклана.
Җавап: 1. Булат. 2. Булат. 3. Ирек.