1. Ука­жи­те ко­ли­че­ство вер­ных не­ра­венств среди пе­ре­чис­лен­ных:

 

10101010₂ > 252₁₀;

10101010₂ > 9F₁₆;

10101010₂ > 252₈.
По­яс­не­ние.

Пе­ре­ве­дем все числа в де­ся­тич­ную си­сте­му счис­ле­ния.

 

10101010₂ = 170₁₀,

9F₁₆ = 9·16 + 15 = 159₁₀,

252₈ = 2·64 + 5·8 + 2 = 170₁₀.

 

По­лу­чив­ши­е­ся не­ра­вен­ства: 170>252; 170>159; 170>170. Из них верно толь­ко одно.

 

Ответ:1

 

2. Ло­ги­че­ская функ­ция Fзадаётся вы­ра­же­ни­ем:

 

(¬x ∧ y) ∨ (y ∧ z).

 

На ри­сун­ке при­ведён фраг­мент таб­ли­цы ис­тин­но­сти функ­ции F, со­дер­жа­щий все на­бо­ры ар­гу­мен­тов, при ко­то­рых функ­ция F ис­тин­на.

Опре­де­ли­те, ка­ко­му столб­цу таб­ли­цы ис­тин­но­сти функ­ции F со­от­вет­ству­ет каж­дая из пе­ре­мен­ных x, y, z.

 

Перем. 1	Перем. 2	Перем. 3	Функ­ция
???	???	???	F
0	1	0	1
0	1	1	1
1	1	1	1

 

В от­ве­те на­пи­ши­те буквы x, y, z в том по­ряд­ке, в ко­то­ром идут со­от­вет­ству­ю­щие им столб­цы (сна­ча­ла буква, со­от­вет­ству­ю­щая пер­во­му столб­цу, затем буква, со­от­вет­ству­ю­щая вто­ро­му столб­цу, и т. д.) Буквы в от­ве­те пи­ши­те под­ряд, ни­ка­ких раз­де­ли­те­лей между бук­ва­ми ста­вить не нужно.

При­мер. Пусть за­да­но вы­ра­же­ние x → y, за­ви­ся­щее от двух пе­ре­мен­ных x и y, и таб­ли­ца ис­тин­но­сти:

 

Перем. 1	Перем. 2	Функ­ция
???	???	F
0	0	1
0	1	0
1	0	1
1	1	1

 

Тогда 1-му столб­цу со­от­вет­ству­ет пе­ре­мен­ная y, а 2-му столб­цу со­от­вет­ству­ет пе­ре­мен­ная x. В от­ве­те нужно на­пи­сать: yx.

По­яс­не­ние.

Вы­ра­же­ние рав­ня­ет­ся 1, если хотя бы одна из двух ско­бок равна 1. Пер­вая скоб­ка при­ни­ма­ет 1 при двух на­бо­рах зна­че­ний пе­ре­мен­ных: (0, 1, 0), (0, 1, 1). Вто­рая при­ни­ма­ет 1 также при двух на­бо­рах зна­че­ний пе­ре­мен­ных: (0, 1, 1), (1, 1, 1). Два на­бо­ра из четырёх сов­па­ло, итого имеем три на­бо­ра: (0, 1, 0), (0, 1, 1), (1, 1, 1). Из на­бо­ра с еди­ни­ца­ми вы­во­дов о по­ряд­ке пе­ре­мен­ных не сде­лать, в осталь­ных двух y оба раза 1, x оба раза 0. На­хо­дим в таб­ли­це такие столб­цы. По­лу­ча­ем, что нуж­ный по­ря­док: x, y, z.

Ответ:xyz

 

3. Между че­тырь­мя мест­ны­ми аэро­пор­та­ми: ВОС­ТОРГ, ЗАРЯ, ОЗЕР­НЫЙ и ГОРКА, еже­днев­но вы­пол­ня­ют­ся авиа­рей­сы. При­ведён фраг­мент рас­пи­са­ния перелётов между ними:

 

Аэро­порт вы­ле­та	Аэро­порт при­ле­та	Время вы­ле­та	Время при­ле­та
Вос­торг	Горка	13:10	17:15
Озер­ный	Заря	13:00	14:30
Озер­ный	Вос­торг	12:10	14:20
Горка	Озер­ный	11:15	15:30
Вос­торг	Озер­ный	12:35	14:50
Заря	Озер­ный	12:30	14:20
Вос­торг	Заря	10:30	12:15
Заря	Горка	14:40	16:45
Горка	Заря	15:15	17:20
Озер­ный	Горка	14:30	16:20

 

Пу­те­ше­ствен­ник ока­зал­ся в аэро­пор­ту ВОС­ТОРГ в пол­ночь (0:00). Опре­де­ли­те самое ран­нее время, когда он может по­пасть в аэро­порт ГОРКА.

 

1) 13:10

2) 16:20

3) 16:45

4) 17:15

По­яс­не­ние.

За­ме­тим, что есть пря­мой рейс из аэро­пор­та ВОС­ТОРГ в аэро­порт ГОРКА (13-10 — 17-15).

 

Можно ле­теть с одной пер­есад­кой: ВОС­ТОРГ-ЗАРЯ (10-30 — 12-15). ЗАРЯ-ГОРКА (14-40 — 16-45). На пе­ре­сад­ку у пу­те­ше­ствен­ни­ка есть 2 часа 25 минут.

 

Пере­сад­ку в аэро­пор­ту ОЗЕР­НЫЙ до аэро­пор­та ГОРКА или до аэро­пор­та ЗАРЯ осу­ще­ствить нель­зя, т. к. самолёт ВОС­ТОРГ-ОЗЕР­НЫЙ (12-35 — 14-50), при­ле­та­ет позже, чем от­прав­ля­ют­ся со­от­вет­ству­ю­щие рейсы(время вы­ле­та 13-00 и 14-30 со­от­вет­ствен­но).

 

Воз­мо­жен также рейс с двумя пе­ре­сад­ка­ми: ВОС­ТОРГ-ЗАРЯ (10-30 — 12-15), ЗАРЯ-ОЗЁРНЫЙ (12-30 — 14-20), ОЗЁРНЫЙ-ГОРКА (14-30 — 16-20). Время на пе­ре­сад­ку на каж­дом про­ме­жу­точ­ном пунк­те не менее 10 минут.

 

Самое раннее время при­­б­ытия 16-20 минут.

 

Ответ:2

 

 

 

 

 

 

 

4. В фраг­мен­те базы дан­ных пред­став­ле­ны све­де­ния о род­ствен­ных от­но­ше­ни­ях. На ос­но­ва­нии при­ведённых дан­ных опре­де­ли­те, сколь­ко всего вну­ков и вну­чек есть у Кар­пец Д. К.

 

Таб­ли­ца 1 ID Фа­ми­лия_И.О. Пол 866 Кар­пец Д.К. Ж 867 Ко­ро­тич Б.Ф. М 879 Ле­меш­ко В.А. Ж 885 Месхи К.Г. М 900 Сер­дюк Л.А. Ж 904 Пет­рик А.И. М 911 Ко­ро­тич А.Б. Ж 932 Пет­рик П.А. Ж 938 Ко­ро­тич И.Б. М 949 Фо­мен­ко Г.Р. Ж 970 Сер­дюк А.П. М 995 Кор­тич Т.И. Ж 1017 Кор­тич П.И. М 1026 Му­хи­на Р.Г. Ж 1041 Гейко М.А. Ж 1056 Сер­дюк П.А. М

Таб­ли­ца 2 ID_Ро­ди­те­ля ID_Ре­бен­ка 866 911 866 938 867 911 867 938 911 879 911 1041 904 900 938 995 938 1017 949 995 949 1017 970 879 970 1041 904 932 1026 900 1026 932

По­яс­не­ние.

Из пер­вой таб­ли­цы опре­де­ля­ем, что id Кар­пец Д. К. — 866.

Из вто­рой опре­де­ля­ем, что та­ко­му id со­от­вет­ству­ют id 911 и 938.

Из вто­рой опре­де­ля­ем, что id 911 со­от­вест­ву­ют id 879 и 1041, а id 938 — 995 и 1017.

 

Итого, у Кар­пец Д. К. 4 внука с id 879, 1041, 995 и 1017.

 

Ответ:4

 

5. По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко 4 буквы К, О, Р, А; для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, до­пус­ка­ю­щий од­но­знач­ное де­ко­ди­ро­ва­ние. Для букв Р, А, К ис­поль­зу­ют­ся такие ко­до­вые слова:

 

Р: 000, А: 10, К: 01.

 

Ука­жи­те такое ко­до­вое слово для буквы О, при ко­то­ром код будет до­пус­кать од­но­знач­ное де­ко­ди­ро­ва­ние. Если таких ко­до­вых слов не­сколь­ко, ука­жи­те то, у ко­то­ро­го мень­шая длина.

 

1) 1

2) 0

3) 11

4) 001

 

 

По­яс­не­ние.

Для того, чтобы код можно было од­но­знач­но де­ко­ди­ро­вать, не­об­хо­ди­мо, чтобы вы­пол­ня­лось усло­вие Фано: ни­ка­кое ко­до­вое слово не долж­но яв­ля­ть­ся на­ча­лом дру­го­го ко­до­во­го слова.

Ва­ри­ант «1» не удо­вле­тво­ря­ет усло­вию Фано. Ва­ри­ант «0» — не удо­вле­тво­ря­ет. Ва­ри­ант «11» удо­вле­тво­ря­ет усло­вию Фано. Ва­ри­ант «001» удо­вле­тво­ря­ет усло­вию Фано.

Вы­би­рая из четвёртого и тре­тье­го ва­ри­ан­та, оста­нав­ли­ва­ем­ся на тре­тьем, по­сколь­ку он ко­ро­че.

 

Ответ:3

 

 

6. У ис­пол­ни­те­ля Квадр две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

 

1. при­бавь 1,
2. воз­ве­ди в квад­рат.

 

Пер­вая из этих ко­манд уве­ли­чи­ва­ет число на экра­не на 1, вто­рая — воз­во­дит в квад­рат. Про­грам­ма для ис­пол­ни­те­ля Квадр — это по­сле­до­ва­тель­ность но­ме­ров ко­манд.

 

На­при­мер, 22111 — это про­грам­ма

 

воз­ве­ди в квад­рат

воз­ве­ди в квад­рат

при­бавь 1

при­бавь 1

при­бавь 1

 

Эта про­грам­ма пре­об­ра­зу­ет число 3 в число 84.

 

За­пи­ши­те про­грам­му для ис­пол­ни­те­ля Квадр, ко­то­рая пре­об­ра­зу­ет число 5 в число 2500 и со­дер­жит не более 6 ко­манд. Если таких про­грамм более одной, то за­пи­ши­те любую из них.

По­яс­не­ние.

Не любое число яв­ля­ет­ся квад­ра­том це­ло­го числа, по­это­му, если мы пойдём от числа 2500 к числу 5, тогда од­но­знач­но вос­ста­но­вим про­грам­му. По­лу­чен­ные ко­ман­ды будут за­пи­сы­вать­ся спра­ва на­ле­во.

 

1) Число 2500 яв­ля­ет­ся квад­ра­том числа 50, сле­до­ва­тель­но, оно было по­лу­че­но с по­мо­щью опе­ра­ции 2.

 

2) Число 50 не яв­ля­ет­ся квад­ра­том, зна­чит, оно было по­лу­че­но с по­мо­щью опе­ра­ции 1. От­ни­мем от него 1 и по­лу­чим число 49.

 

3) Число 49 яв­ля­ет­ся квад­ра­том 7, зна­чит, оно было по­лу­че­но опе­ра­ци­ей 2.

 

4) Два раза от­ни­мем от 7 еди­ни­цу и по­лу­чим ис­ход­ное число 5. Мы толь­ко что при­ме­ни­ли два раз опе­ра­цию, об­рат­ную опе­ра­ции 1.

 

Ответ: 11212.

 

 

 

 

 

 

 

7. В элек­трон­ной таб­ли­це Excel от­ра­же­ны дан­ные по про­да­же не­ко­то­рого штуч­но­го то­ва­ра в тор­го­вых цен­трах го­ро­да за че­ты­ре ме­ся­ца. За каж­дый месяц в таб­ли­це вы­чис­ле­ны сум­мар­ные про­да­жи и сред­няя по го­ро­ду цена на товар, ко­то­рая на 2 рубля боль­ше цены по­став­щи­ка дан­но­го то­ва­ра.

 

 

 

 

ТЦ	Ян­варь		Фев­раль		Март		Ап­рель
	Про­да­но, штук	Цена, руб.	Про­да­но, штук	Цена, руб.	Про­да­но, штук	Цена, руб.	Про­да­но, штук	Цена, руб.
Эдель­вейс	5	14	1	17	5	15	4	15
По­ку­поч­ка	6	13	2	16	6	11	4	14
Ко­ше­лек	2	17	5	14	4	15	1	18
Сол­неч­ный	8	12	7	13	7	11	7	13
Про­да­но всего	21		15		22		16
Сред­няя цена	14		15		13		15

 

Из­вест­но, что весь по­сту­пив­ший от по­став­щи­ка в те­ку­щем ме­ся­це товар ре­а­ли­зу­ет­ся в этом же ме­ся­це.

В каком ме­ся­це вы­руч­ка по­став­щи­ка дан­но­го то­ва­ра была мак­си­маль­на?

По­яс­не­ние.

Найдём вы­руч­ку за про­да­жи в тор­го­вых цен­трах на каж­дый месяц. В том ме­ся­це, где она мак­си­маль­на, по­став­щик также по­лу­чил наи­боль­шую при­быль.

 

Ян­варь: 21 * 14 = 294,

Фев­раль: 15 * 15 = 225,

Март: 22 * 13 = 286,

Ап­рель: 16 * 15 = 240.

 

Наи­боль­шая при­быль в ян­ва­ре.

 

8. Опре­де­ли­те, что будет на­пе­ча­та­но в ре­зуль­та­те ра­бо­ты сле­ду­ю­ще­го фраг­мен­та про­грам­мы:

 

var n, s: integer;

begin

    n := 3;

    s := 0;

    while n <= 7 do begin

        s := s + n;

        n := n + 1

    end;

    write(s)

end.

По­яс­не­ние.

Цикл while вы­пол­ня­ет­ся до тех пор, пока ис­тин­но усло­вие n <= 7, т. е. пе­ре­мен­ная n опре­де­ля­ет, сколь­ко раз вы­пол­нит­ся цикл.

 

За­пи­шем по­сле­до­ва­тель­но зна­че­ния s и n:

 

s 0 3 7 12 18 25

n 3 4 5  6   7   8

 

 

Цикл вы­пол­нит­ся пять раз (так как дей­ствие n := n + 1 стоит в конце цикла, сле­до­ва­тель­но, для n=8 дей­ствие s := s + n не будет вы­пол­нять­ся).

 

9. До­ку­мент объёмом 6 Мбайт можно пе­ре­дать с од­но­го ком­пью­те­ра на дру­гой

двумя спо­со­ба­ми.

А. Сжать ар­хи­ва­то­ром, пе­ре­дать архив по ка­на­лу связи, рас­па­ко­вать.

Б. Пе­ре­дать по ка­на­лу связи без ис­поль­зо­ва­ния ар­хи­ва­то­ра.

При этом:

• ско­рость пе­ре­да­чи дан­ных по ка­на­лу связи со­став­ля­ет 2²²бит в се­кун­ду;
• объём сжа­то­го ар­хи­ва­то­ром до­ку­мен­та равен 50% от ис­ход­но­го;
• время, тре­бу­е­мое на сжа­тие до­ку­мен­та, — 6 се­кунд, на рас­па­ков­ку — 2 се­кун­ды.

Какой спо­соб быст­рее и на сколь­ко?

В от­ве­те на­пи­ши­те букву А, если быст­рее спо­соб А, или Б, если быст­рее спо­соб Б. Сразу после буквы на­пи­ши­те, на сколь­ко се­кунд один спо­соб быст­рее дру­го­го.

На­при­мер, если спо­соб Б быст­рее спо­со­ба А на 23 се­кун­ды, в от­ве­те нужно на­пи­сать Б23.

Еди­ни­цы из­ме­ре­ния «се­кунд», «сек.», «с» и т. п. к от­ве­ту до­бав­лять не нужно.

По­яс­не­ние.

Общее время скла­ды­ва­ет­ся из вре­ме­ни сжа­тия, рас­па­ков­ки и пе­ре­да­чи. Время пе­ре­да­чи t рас­счи­ты­ва­ет­ся по фор­му­ле t = Q / q, где Q — объём ин­фор­ма­ции, q — cко­рость пе­ре­да­чи дан­ных.

Спо­соб А. Найдём сжа­тый объём: 6 · 0,5 = 3 Мбайт. Пе­ре­ведём Q из Мбайт в биты: 3 Мбай­т =  3 · 2²⁰ байт = 3 · 2²³ бит. Найдём общее время: t = 6 с + 2 с + 3 · 2²³ бит / 2²² бит/с = 8 с + 6 с = 14 с.

Спо­соб Б. Общее время сов­па­да­ет с вре­ме­нем пе­ре­да­чи: t = 6 · 2²³ бит / 2²² бит/с = 12 с.

Таким об­ра­зом, спо­соб Б быст­рее на 14 − 12 = 2 с.

 

Ответ: Б2.

 

10. Сколь­ко су­ще­ству­ет раз­лич­ных сим­воль­ных по­сле­до­ва­тель­но­стей длины от трёх до четырёх в четырёхбук­вен­ном ал­фа­ви­те {A, C, G, T}?По­яс­не­ние.

Если в ал­фа­ви­те M сим­во­лов, то ко­ли­че­ство всех воз­мож­ных «слов» (со­об­ще­ний) дли­ной N равно Q = M^N. В нашем слу­чае M = 4, а N = 3 или 4. Сле­до­ва­тель­но Q = 4³ + 4⁴ = 64 + 256 = 320.

 

Ответ: 320.

 

11. Ниже на пяти язы­ках про­грам­ми­ро­ва­ния за­пи­са­на ре­кур­сив­ная функ­ция (про­це­ду­ра) F.

 

 

Бей­сик	Python
SUB F(n) PRINT n, IF n > 2 THEN F(n − 1) F(n − 2) F(n − 3) END IF END SUB	def F(n): print (n, end=») if n > 2: F(n − 1) F(n − 2) F(n − 3)
Пас­каль	Ал­го­рит­ми­че­ский язык
procedure F(n: integer); begin write(n); if n > 2 then begin F(n − 1); F(n − 2); F(n − 3) end end;	алг F(цел n) нач вывод n если n > 2 то F(n − 1) F(n − 2) F(n − 3) все кон
Си
void F(int n ){ printf(«%d», n); if (n > 2) { F(n − 1); F(n − 2); F(n − 3); } }

 

 

Что вы­ве­дет про­грам­ма при вы­зо­ве F(4)? В от­ве­те за­пи­ши­те по­сле­до­ва­тель­ность вы­ве­ден­ных цифр слит­но (без про­бе­лов).

По­яс­не­ние.

Рас­смот­рим струк­ту­ру вы­зо­ва функ­ций, оче­ред­ность.

 

F(4) {

F(3) {

F(2)

F(1)

F(0)

}

F(2)

F(1)

}

 

Так как число пе­ча­та­ет­ся сразу при за­хо­де в функ­цию, то по­ря­док чисел будет сов­па­дать с по­ряд­ком вы­зо­вов.

 

Ответ:4321021

 

12. Если маска под­се­ти 255.255.252.0 и IP-адрес ком­пью­те­ра в сети 226.185.90.162, то номер ком­пью­те­ра в сети равен_____По­яс­не­ние.
13. Так как пер­вые два ок­те­та (октет — число маски, со­дер­жит 8 бит) оба равны 255, то в дво­ич­ном виде они за­пи­сы­ва­ют­ся как 16 еди­ниц, а зна­чит, пер­вые два ок­те­та опре­де­ля­ют адрес сети.
14. За­пи­шем число 252 в дво­ич­ном виде:

Итого, по­след­ние два ок­те­та маски за­пи­сы­ва­ют­ся как 11111100 00000000

3. За­пи­шем по­след­ние два ок­те­та IP-ад­ре­са ком­пью­те­ра в сети:

 

Итого, по­след­ние два ок­те­та IP-ад­ре­са ком­пью­те­ра в сети за­пи­сы­ва­ют­ся так: 01011010 10100010

4. Со­по­ста­вим по­след­ние ок­те­ты маски и ад­ре­са ком­пью­те­ра в сети:

11111100 00000000

01011010 10100010

Жир­ным вы­де­ле­на нуж­ная нам часть. Пе­ре­ве­дем её в де­ся­тич­ную си­сте­му счис­ле­ния:

Ответ:674

 

 

 

 

13. B не­ко­то­рой стра­не ав­то­мо­биль­ный номер дли­ной 6 сим­во­лов со­став­ля­ют из за­глав­ных букв (ис­поль­зу­ют­ся толь­ко 33 раз­лич­ных буквы) и де­ся­тич­ных цифр в любом по­ряд­ке. Каж­дый такой номер в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством бай­тов (при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством битов). Опре­де­ли­те объём па­мя­ти, от­во­ди­мый этой про­грам­мой для за­пи­си 125 но­ме­ров. (Ответ дайте в бай­тах.)По­яс­не­ние.

Со­глас­но усло­вию, в но­ме­ре могут быть ис­поль­зо­ва­ны 10 цифр (0..9) и 33 буквы, всего 10 + 33 = 43 сим­во­лов. Из­вест­но, что с по­мо­щью N бит можно за­ко­ди­ро­вать 2^N раз­лич­ных ва­ри­ан­тов. По­сколь­ку 2⁵ < 43 < 2⁶, то для за­пи­си каж­до­го из 43 сим­во­лов не­об­хо­ди­мо 6 бит.

 

Для хра­не­ния всех 6 сим­во­лов но­ме­ра нужно 6 * 6 = 36 бит, а т. к. для за­пи­си ис­поль­зу­ет­ся целое число байт, то берём бли­жай­шее не мень­шее зна­че­ние, крат­ное вось­ми, это число 40 = 5 * 8 бит (5байт).

 

Тогда 125 но­ме­ров за­ни­ма­ют 5 * 125 = 625 байт.

 

 

Небольшое дополнение

По­че­му берется наи­мень­шее зна­че­ние, крат­ное 8, если можно за­пи­сать 4,5 байта?

Каж­дый номер ко­ди­ру­ет­ся целым чис­лом байт.

 

 

14. Си­сте­ма ко­манд ис­пол­ни­те­ля РОБОТ, «жи­ву­ще­го» в пря­мо­уголь­ном ла­би­рин­те на клет­ча­той плос­ко­сти, вклю­ча­ет в себя 4 ко­ман­ды-при­ка­за и 4 ко­ман­ды про­вер­ки усло­вия. Ко­ман­ды-при­ка­зы:

вверх

вниз

влево

впра­во

При вы­пол­не­нии любой из этих ко­манд РОБОТ пе­ре­ме­ща­ет­ся на одну клет­ку со­от­вет­ствен­но: вверх ↑, вниз ↓, влево ←, впра­во →.

Если РОБОТ начнёт дви­же­ние в сто­ро­ну на­хо­дя­щей­ся рядом с ним стены, то он раз­ру­шит­ся, и про­грам­ма прервётся.

Дру­гие 4 ко­ман­ды про­ве­ря­ют ис­тин­ность усло­вия от­сут­ствия стены у каж­дой сто­ро­ны той клет­ки, где на­хо­дит­ся РОБОТ:

свер­ху сво­бод­но

снизу сво­бод­но

слева сво­бод­но

спра­ва сво­бод­но

Цикл

 

ПОКА усло­вие

по­сле­до­ва­тель­ность ко­манд

КОНЕЦ ПОКА

 

вы­пол­ня­ет­ся, пока усло­вие ис­тин­но. В кон­струк­ции

 

ЕСЛИ усло­вие

ТО ко­ман­да1

ИНАЧЕ ко­ман­да2

КОНЕЦ ЕСЛИ

 

вы­пол­ня­ет­ся ко­ман­да1 (если усло­вие ис­тин­но) или ко­ман­да2 (если усло­вие ложно).

 

Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, начав дви­же­ние в ней и вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка A6)?

 

НА­ЧА­ЛО

ПОКА снизу сво­бод­но ИЛИ слева сво­бод­но

ЕСЛИ снизу сво­бод­но

ТО вниз

ИНАЧЕ влево

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

 

 

 

 

 

 

 

 

По­яс­не­ние.

При вы­пол­не­нии дан­ной про­грам­ме РОБОТ по­сту­па­ет сле­ду­ю­щим об­ра­зом: спер­ва РОБОТ про­ве­ря­ет, сво­бод­на ли клет­ка слева или снизу от него. Если это так, то РОБОТ пе­ре­хо­дит к пер­во­му дей­ствию внут­ри цикла. В этом цикле если у ниж­ней сто­ро­ны клет­ки, в ко­то­рой на­хо­дит­ся РОБОТ, нет стены, он дви­га­ет­ся вниз, в про­тив­ном слу­чае он пе­ре­ме­ща­ет­ся влево. После этого воз­вра­ща­ет­ся к на­ча­лу внеш­не­го цикла. Про­ана­ли­зи­ро­вав эту про­грам­му, при­хо­дим к вы­во­ду, что РОБОТ не может раз­бить­ся.

Про­ве­рив все клет­ки по вы­ве­ден­но­му нами пра­ви­лу дви­же­ния РО­БО­ТА, вы­яс­ня­ем, что число кле­ток, удо­вле­тво­ря­ю­щих усло­вию за­да­чи равно 21: F1-F6, А6-F6, A3-A5, B1-B5, C1, C2.

 

Ответ:21

 

15. На ри­сун­ке изоб­ра­же­на схема до­ро­г, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G, H, K, L, M. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город M?

По­яс­не­ние.

Нач­нем счи­тать ко­ли­че­ство путей с конца марш­ру­та – с го­ро­да М. N_X — ко­ли­че­ство раз­лич­ных путей из го­ро­да А в город X, N — общее число путей.

 

В «М» можно при­е­хать из G, H, F, K или L, по­это­му N = N_М = N_G + N_H + N_F + N _К + N _L (1)

 

Ана­ло­гич­но:

 

N_G = N_B + N_C;

N_H = N_C + N_F;

N_F = N_C + N_А + N_D;

N_К = N_F + N_D + N_E;

N_L = N_E.

 

До­ба­вим еще вер­ши­ны:

 

N_B = N_A + N_C;

N_C = N_A = 1;

N_D = N_A= 1;

N_E = N_А + N_D = 2.

 

Пре­об­ра­зу­ем вер­ши­ны:

 

N_B = N_A + N_C = 2;

N_C = N_A = 1;

N_D = N_A= 1;

N_E = N_А + N_D = 2.

 

N_G = N_B + N_C = 2 + 1 = 3;

N_H = N_C + N_F = 1 + 3 = 4;

N_F = N_C + N_А + N_D = 1 + 1 + 1 = 3;

N_К = N_F + N_D + N_E = 3 + 1 + 2 = 6;

N_L = N_E = 2.

 

Под­ста­вим в фор­му­лу (1):

 

N = N_М = 3 + 4 + 3 + 6 + 2 = 18.

 

Ответ:18

 

16. В си­сте­ме счис­ле­ния с не­ко­то­рым ос­но­ва­ни­ем де­ся­тич­ное число 57 за­пи­сы­ва­ет­ся как 111. Ука­жи­те это ос­но­ва­ние.По­яс­не­ние.

Со­ста­вим урав­не­ние: 111_n = 1 · n² + 1 · n¹ + 1 · n⁰ = 57₁₀, где n — ос­но­ва­ние этой си­сте­мы счис­ле­ния. Урав­не­ние n² + n − 56 = 0 имеет два корня: 7 и −8. Таким об­ра­зом, ос­но­ва­ние си­сте­мы счис­ле­ния — 7.

 

Ответ: 7.

 

 

17. В языке за­про­сов по­ис­ко­во­го сер­ве­ра для обо­зна­че­ния ло­ги­че­ской опе­ра­ции «ИЛИ» ис­поль­зу­ет­ся сим­вол «|», а для ло­ги­че­ской опе­ра­ции «И» — сим­вол «&». В таб­ли­це при­ве­де­ны за­про­сы и ко­ли­че­ство най­ден­ных по ним стра­ниц не­ко­то­ро­го сег­мен­та сети Ин­тер­нет.

 

За­прос	Най­де­но стра­ниц (в ты­ся­чах)
Шве­ция	3200
Фин­лян­дия	2300
Шве­ция & Фин­лян­дия	100

 

Какое ко­ли­че­ство стра­ниц (в ты­ся­чах) будет най­де­но по за­про­су Шве­ция | Фин­лян­дия?

Счи­та­ет­ся, что все за­про­сы вы­пол­ня­лись прак­ти­че­ски од­но­вре­мен­но, так что набор стра­ниц, со­дер­жа­щих все ис­ко­мые слова, не из­ме­нял­ся за время вы­пол­не­ния за­про­сов.

По­яс­не­ние.

По фор­му­ле вклю­че­ний и ис­клю­че­ний имеем:

 

m(Шве­ция | Фин­лян­дия) = m(Фин­лян­дия) + m(Шве­ция) — m(Шве­ция & Фин­лян­дия) = 3200 + 2300 — 100 = 5400.

 

18. На чис­ло­вой пря­мой даны два от­рез­ка: P = [3, 33] и Q = [22, 44]. Вы­бе­ри­те такой от­ре­зок A, что фор­му­ла

 

(x ∈ Q) → ((x ∈ P) → (x ∈ A))

 

тож­де­ствен­но ис­тин­на, то есть при­ни­ма­ет зна­че­ние 1 при любом зна­че­нии пе­ре­мен­ной х.

 

1) [2, 20]

2) [10, 25]

3) [20, 40]

4) [25, 30]

По­яс­не­ние.

Вве­дем обо­зна­че­ния:

 

(x ∈А) ≡ A; (x ∈ P) ≡ P; (x ∈ Q) ≡ Q.

 

При­ме­нив пре­об­ра­зо­ва­ние им­пли­ка­ции, по­лу­ча­ем:

 

Q → (P → A) ⇔ ¬Q ∨ (P → A) ⇔ ¬Q ∨ ¬P ∨ A.

 

Ло­ги­че­ское ИЛИ ис­тин­но, если ис­тин­но хотя бы одно утвер­жде­ние. Усло­вие ¬Q ∨ ¬P = 1 ис­тин­но на мно­же­стве (−∞, 22) ∪ (33, ∞). По­сколь­ку вы­ра­же­ние ¬Q ∨ ¬P ∨ A долж­но быть тож­де­ствен­но ис­тин­ным, вы­ра­же­ние A долж­но быть ис­тин­ным на от­рез­ке [22, 33]. Из пе­ре­чис­лен­ных от­рез­ков толь­ко от­ре­зок [20, 40] удо­вле­тво­ря­ет этому усло­вию.

 

Ответ:3

 

19. Зна­че­ния эле­мен­тов дву­мер­но­го мас­си­ва А были равны 0. Затем зна­че­ния не­ко­то­рых эле­мен­тов были из­ме­не­ны (см. пред­став­лен­ный фраг­мент про­грам­мы):

n := 0;

for i:=1 tо 5 do

for j:=1 tо 6-i do begin

n := n + 1;

A[i,j] := n;

end;

Какой эле­мент мас­си­ва будет иметь в ре­зуль­та­те мак­си­маль­ное зна­че­ние?

 

1) A[1,1]

2) A[1,5]

3) A[5,1]

4) A[5,5]

По­яс­не­ние.

В пе­ре­мен­ной n на­кап­ли­ва­ет­ся сумма про­хо­дов цикла. Это число всё время растёт, сле­до­ва­тель­но, наи­боль­шим эле­мен­том мас­си­ва будет тот, зна­че­ние ко­то­ро­му будет при­сво­е­но по­след­ним. Это эле­мент A[5,1].

 

Ответ: 3

 

20. Ниже за­пи­са­на про­грам­ма. По­лу­чив на вход число , эта про­грам­ма пе­ча­та­ет два числа, L и M. Ука­жи­те наи­мень­шее из таких чисел , при вводе ко­то­рых ал­го­ритм пе­ча­та­ет сна­ча­ла 3, а потом 8.

var x, L, M: integer;

begin

readln(x);

L:=0; M:=0;

while x > 0 do begin

L:= L + 1;

if x mod 2 = 1 then

M:= M + x mod 10;

x:= x div 10;

end;

writeln(L); write(M);

end.

По­яс­не­ние.

Строч­ка L:= L + 1; в дан­ной про­грам­ме счи­та­ет ко­ли­че­ство цифр в числе, зна­чит число трех­знач­ное.

При по­мо­щи ко­манд if x mod 2 = 1 then M:= M + x mod 10; под­счи­ты­ва­ет­ся сумма всех цифр числа x, если оно нечётно. Наи­мень­шее число, удо­вле­тво­ря­ю­щее усло­вию — 107.

 

Ответ:107

 

21. Опре­де­ли­те, какое число будет на­пе­ча­та­но в ре­зуль­та­те вы­пол­не­ния сле­ду­ю­ще­го ал­го­рит­ма (для ва­ше­го удоб­ства ал­го­ритм пред­став­лен на четырёх язы­ках):

 

 

Бей­сик	Пас­каль
DIM A, B, T, M, R AS INTEGER A = -20: B = 20 M = A: R = F(A) FOR T = A TO B IF F(T) < R THEN M = T R = F(T) ENDIF NEXT T PRINT R FUNCTION F(x) F = 16 * (9 — x)* (9 — x) + 127; END FUNCTION	var a,b,t,M,R :integer; Function F(x:integer):integer; begin F : = 16 * (9 — x)* (9 — x) + 127; end; begin a : = -20; b : = 20; M : = a; R : = F(a); for t : = a to b do begin if (F(t) < R ) then begin M : = t; R : = F(t) end end; write(R); end.
Си	Ал­го­рит­ми­че­ский язык
#include<stdio.h> int F(int x) { return 16 * (9 — x)* (9 — x) + 127; } void main() { int a, b, t, M, R; a = -20; b = 20; M = a; R = F(a); for (t = a; t <= b; t++){ if (F(t) < R) { M = t; R = F(t); } } printf(«%d», R); }	алг нач цел a, b, t, R, M a : = -20; b : = 20 M : = a; R : = F(a) нц для t от a до b если F(t) < R то M : = t; R : = F(t) все кц вывод R кон алг цел F(цел x) нач знач : = 16 * (9 — x)* (9 — x) + 127 кон

 

 

 

 

По­яс­не­ние.

1. Ал­го­ритм ищет наи­мень­шее зна­че­ние функ­ции F(t) на ин­тер­ва­ле от a до b.
2. Имеем:  , гра­фик этой функ­ции – па­ра­бо­ла, ветви ко­то­рой на­прав­ле­ны вверх, по­это­му функ­ция при­ни­ма­ет наи­мень­шее зна­че­ние в вер­ши­не.

 

3. Най­дем абс­цис­су вер­ши­ны:

 

 

как видно, она лежит в нуж­ном ин­тер­ва­ле.

 

4. Под­ста­вим

 

 

Ответ:127

 

22. У ис­пол­ни­те­ля Удво­и­тель две ко­ман­ды, ко­то­рым при­сво­е­ны но­ме­ра:

 

1. при­бавь 1,
2. умножь на 2.

 

Пер­вая из них уве­ли­чи­ва­ет на 1 число на экра­не, вто­рая удва­и­ва­ет его.

Про­грам­ма для Удво­и­те­ля — это по­сле­до­ва­тель­ность ко­манд. Сколь­ко су­ще­ству­ет про­грамм, ко­то­рые число 3 пре­об­ра­зу­ют в число 26?

По­яс­не­ние.

Обо­зна­чим R(n) — ко­ли­че­ство про­грамм, ко­то­рые пре­об­ра­зу­ют число 2 в число n. Обо­зна­чим t(n) наи­боль­шее крат­ное 2, не пре­вос­хо­дя­щее n. За­ме­тим, что мы можем по­лу­чить толь­ко числа, крат­ные 2.

Верны сле­ду­ю­щие со­от­но­ше­ния:

1. Если n не де­лит­ся на 2, то тогда R(n) = R(t(n)), так как су­ще­ству­ет един­ствен­ный спо­соб по­лу­че­ния n из t(n) — при­бав­ле­ни­ем еди­ниц.
2. Пусть n де­лит­ся на 2. Тогда R(n) = R(n / 2) + R(n − 1)= R(n / 2) + R(n − 2) (если n > 4). При n = 4: R(n) = 1 (один спо­соб: при­бав­ле­ни­ем еди­ни­цы), при n = 5: R(n) = 1. До­ста­точ­но вы­чис­лить зна­че­ния R(n) для всех чисел, крат­ных 2 и не пре­вос­хо­дя­щих 26.

Имеем:

R(4)= 1 = R(5),

R(6) = 2 = R(7),

R(8) = R(4) + R(6) = 1 + 2 = 3 = R(9),

R(10) = R(5) + R(8) = 1 + 3 = 4 = R(11),

R(12) = R(6) + R(10) = 2 + 4 = 6 = R(13),

R(14) = R(7) + R(12) = 2 + 6 = 8 = R(15),

R(16) = R(8) + R(14) = 3 + 8 = 11 = R(17),

R(18) = R(9) + R(16) = 3 + 11 = 14 = R(19),

R(20) = R(10) + R(18) = 4 + 14 = 18 = R(21),

R(22) = R(11) + R(20) = 4 + 18 = 22 = R(23),

R(24) = R(12) + R(22) = 6 + 22 = 28 = R(23),

R(26) = R(13) + R(24) = 6 + 28 = 34.

 

Ответ: 34.

 

23. A, B и С – целые числа, для ко­то­рых ис­тин­но вы­ска­зы­ва­ние

¬(А = B) ∧ ((B < A)→(2C > A)) ∧ ((A < B)→(A > 2C))

Чему равно A, если C = 8 и B = 18?.

По­яс­не­ние.

Ло­ги­че­ское «И» ис­тин­но тогда и толь­ко тогда, когда ис­тин­ны оба утвер­жде­ния.

1) ¬(А = B) = 1, то есть А ≠ 18 = 1.

2) ((B < A)→(2C > A)) При­ме­ним пре­об­ра­зо­ва­ние им­пли­ка­ции: (18 > A) ∨ (16 > A) = 1

3) (A < B)→(A > 2C) При­ме­ним пре­об­ра­зо­ва­ние им­пли­ка­ции: (A > 18) ∨ (A > 16) = 1

 

Из 2) и 3) сле­ду­ет, что (18 > A) и (A > 16), так как в про­тив­ном слу­чае воз­ни­ка­ет про­ти­во­ре­чие А = 17

 

Критерии оце­ни­ва­ния выполнения задания	Баллы
Выполнены все три дей­ствия	3
Правильно вы­пол­не­ны два дей­ствия из трёх. При этом при на­пи­са­нии опе­ра­ций срав­не­ния до­пус­ка­ет­ся одно не­пра­виль­ное ис­поль­зо­ва­ние строгих/нестрогих не­ра­венств (считается не­су­ще­ствен­ной ошибкой, по­греш­но­стью записи). Например, вме­сто «y>=x» один раз ис­поль­зу­ет­ся «y>x». В ра­бо­те (во фраг­мен­тах программ) до­пус­ка­ет­ся на­ли­чие от­дель­ных син­так­си­че­ских ошибок, не ис­ка­жа­ю­щих за­мыс­ла ав­то­ра ре­ше­ния	2
Правильно вы­пол­не­но толь­ко одно дей­ствие из трёх, то есть либо толь­ко при­ве­де­на таблица, ко­то­рая со­дер­жит ошиб­ки в не более чем одной строке, либо таб­ли­ца не при­ве­де­на (или при­ве­де­на и со­дер­жит ошиб­ки более чем в одной строке), но ис­прав­ле­на одна ошиб­ка программы. При оце­ни­ва­нии этого за­да­ния на 1 балл до­пус­ка­ет­ся не учи­ты­вать кор­рект­ность ра­бо­ты про­грамм на точ­ках гра­ниц об­ла­стей (вместо не­стро­гих не­ра­венств в ре­ше­нии были ис­поль­зо­ва­ны стро­гие не­ра­вен­ства или наоборот). В ра­бо­те (во фраг­мен­тах программ) до­пус­ка­ет­ся на­ли­чие от­дель­ных син­так­си­че­ских ошибок, не ис­ка­жа­ю­щих за­мыс­ла ав­то­ра решения	1
Ни один из пунк­тов за­да­ния не выполнен, то есть не вы­пол­не­ны критерии, поз­во­ля­ю­щие по­ста­вить уче­ни­ку 1 балл	0
Максимальный балл	3

 

Тре­бо­ва­лось на­пи­сать про­грам­му, ко­то­рая вво­дит с кла­ви­а­ту­ры ко­ор­ди­на­ты точки на плос­ко­сти (x, y — дей­стви­тель­ные числа) и опре­де­ля­ет при­над­леж­ность точки за­штри­хо­ван­ной об­ла­сти (вклю­чая гра­ни­цы). Про­грам­мист то­ро­пил­ся и на­пи­сал про­грам­му не­пра­виль­но. Ниже для Ва­ше­го удоб­ства про­грам­ма пред­став­ле­на на четырёх язы­ках про­грам­ми­ро­ва­ния.

 

Бей­сик	Пас­каль
INPUT x, y IF x>=-1 THEN IF y>=-1 THEN IF y<=1 THEN IF x*x+y*y<=1 THEN PRINT «при­над­ле­жит» ELSE PRINT «не при­над­ле­жит» END IF END IF END IF END IF END	var x,y: real; begin readln(x,y); if x>=-1 then if y>=-1 then if y<=1 then if x*x+y*y<=1 then write(‘при­над­ле­жит’) else write(‘не при­над­ле­жит’); end
Си	Ал­го­рит­ми­че­ский
#include<stdio.h> void main() { float x,y; scanf(«%f%f»,&x,&y); if (x>=-1) if (y>=-1) if (y<=1) if (x*x+y*y<=1) printf(«при­над­ле­жит»); else printf(«не при­над­ле­жит»); }	алг нач вещ x,y ввод x,y если x>=-1 то если y>=-1 то если y<=1 то если x*x+y*y<=1 то вывод ‘при­над­ле­жит’ иначе вывод ‘не при­над­ле­жит’ все все все все кон

 

По­сле­до­ва­тель­но вы­пол­ни­те сле­ду­ю­щее.

 

1. Пе­ре­ри­суй­те и за­пол­ни­те таб­ли­цу, ко­то­рая по­ка­зы­ва­ет, как ра­бо­та­ет про­грам­ма при ар­гу­мен­тах, при­над­ле­жа­щих раз­лич­ным об­ла­стям (A, B, C, D, E, F, G, H, I). Точки, ле­жа­щие на гра­ни­цах об­ла­стей, от­дель­но не рас­смат­ри­вать. Ко­ор­ди­нат­ные оси не яв­ля­ют­ся гра­ни­ца­ми об­ла­стей. В столб­цах усло­вий ука­жи­те «да», если усло­вие вы­пол­нит­ся, «нет», если усло­вие не вы­пол­нит­ся, «—» (про­черк), если усло­вие не будет про­ве­рять­ся, «не изв.», если про­грам­ма ведёт себя по-раз­но­му для раз­ных зна­че­ний, при­над­ле­жа­щих дан­ной об­ла­сти. В столб­це «Про­грам­ма вы­ве­дет» ука­жи­те, что про­грам­ма вы­ве­дет на экран. Если про­грам­ма ни­че­го не вы­во­дит, на­пи­ши­те «—» (про­черк). Если для раз­ных зна­че­ний, при­над­ле­жа­щих об­ла­сти, будут вы­ве­де­ны раз­ные тек­сты, на­пи­ши­те «не изв.». В по­след­нем столб­це ука­жи­те «да» или «нет».

 

Об­ласть	Усло­вие1 (x>=–1)	Усло­вие 2 (y>=–1)	Усло­вие 3 (y<=1)	Усло­вие 4 (x*x+y*y<=1)	Про­грам­ма вы­ве­дет	Об­ласть об­ра­ба­ты­ва­ет­ся верно
A
В
С
D
Е
F
G
Н
I

 

2. Ука­жи­те, как нужно до­ра­бо­тать про­грам­му, чтобы не было слу­ча­ев её не­пра­виль­ной ра­бо­ты. (Это можно сде­лать не­сколь­ки­ми спо­со­ба­ми, до­ста­точ­но ука­зать любой спо­соб до­ра­бот­ки ис­ход­ной про­грам­мы.)

 

Пояснение.

Эле­мен­ты от­ве­та:

 

Об­ласть	Усло­вие1 (x>=–1)	Усло­вие 2 (y>=–1)	Усло­вие 3 (y<=1)	Усло­вие 4 (x*x+y*y<=1)	Про­грам­ма вы­ве­дет	Об­ласть об­ра­ба­ты­ва­ет­ся верно
A	нет	—	—	—	—	нет
B	да	да	нет	—	—	нет
C	нет	—	—	—	—	нет
D	да	да	да	нет	не при­над­ле­жит	нет
E	да	да	да	да	при­над­ле­жит	да
F	да	да	да	нет	не при­над­ле­жит	да
G	да	да	да	нет	не при­над­ле­жит	нет
H	нет	—	—	—	—	нет
I	да	нет	—	—	—	нет

 

Воз­мож­ная до­ра­бот­ка (Пас­каль, от­дель­но рас­смат­ри­ва­ем об­ла­сти, ле­жа­щие по раз­ные сто­ро­ны от пря­мой x=0):

 

if (x*x+y*y<=1) and (x>=0) or (x<=0) and (x>=-1) and (y<=1) and (y>=-1) then

write(‘при­над­ле­жит’)

else write(‘не при­над­ле­жит’)

 

Воз­мож­ная до­ра­бот­ка (Си, объ­еди­не­ние двух пе­ре­се­ка­ю­щих­ся об­ла­стей):

 

if((x*x+y*y<=1) || (x>=-1) && (x<=0) && (fabs(y)<=1))

printf(«при­над­ле­жит»);

else

printf(«не при­над­ле­жит»);

 

Об­ра­ти­те вни­ма­ние! При раз­де­ле­нии об­ла­сти вдоль какой-либо линии точки, ко­то­рые лежат на этой линии внут­ри об­ла­сти, могут быть при­чис­ле­ны к одной части, к дру­гой или к обеим (то есть, на­при­мер, в при­ведённом ре­ше­нии на языке Пас­каль одно из усло­вий (x>=0 или x<=0) может быть стро­гим) Могут быть и дру­гие вер­ные спо­со­бы до­ра­бот­ки.

 

Критерии оце­ни­ва­ния вы­пол­не­ния задания	Баллы
Предложен пра­виль­ный алгоритм, вы­да­ю­щий вер­ное значение. До­пус­ка­ет­ся за­пись ал­го­рит­ма на дру­гом языке, ис­поль­зу­ю­щая ана­ло­гич­ные переменные. В случае, если язык про­грам­ми­ро­ва­ния ис­поль­зу­ет ти­пи­зи­ро­ван­ные переменные, опи­са­ния пе­ре­мен­ных долж­ны быть ана­ло­гич­ны опи­са­ни­ям пе­ре­мен­ных на есте­ствен­ном языке. Ис­поль­зо­ва­ние не­ти­пи­зи­ро­ван­ных или не­объ­яв­лен­ных пе­ре­мен­ных воз­мож­но толь­ко в случае, если это до­пус­ка­ет­ся язы­ком программирования, при этом ко­ли­че­ство пе­ре­мен­ных и их иден­ти­фи­ка­то­ры долж­ны со­от­вет­ство­вать усло­вию задачи. В алгоритме, за­пи­сан­ном на языке программирования, до­пус­ка­ет­ся на­ли­чие от­дель­ных син­так­си­че­ских ошибок, не ис­ка­жа­ю­щих за­мыс­ла ав­то­ра программы.	2
В любом ва­ри­ан­те ре­ше­ния может при­сут­ство­вать не более одной ошиб­ки из числа следующих: 1) не ини­ци­а­ли­зи­ру­ет­ся или не­вер­но ини­ци­а­ли­зи­ру­ет­ся пе­ре­мен­ная; 2) при вы­во­де от­ве­та не учитывается, что тре­бу­е­мо­го числа в мас­си­ве может не быть; 3) от­сут­ству­ет вывод от­ве­та; 4) в срав­не­нии перепутан знак; 5) не­вер­но осу­ществ­ля­ет­ся про­вер­ка де­ли­мо­сти; 6) на де­ли­мость про­ве­ря­ет­ся не зна­че­ние элемента, а его индекс; 7) в слож­ном усло­вии вме­сто ло­ги­че­ской опе­ра­ции «И» ис­поль­зу­ет­ся ло­ги­че­ская опе­ра­ция «ИЛИ»; 8) ис­поль­зу­ет­ся переменная, не объ­яв­лен­ная в раз­де­ле опи­са­ния переменных; 9) не ука­за­но или не­вер­но ука­за­но усло­вие за­вер­ше­ния цикла; 10) ин­декс­ная пе­ре­мен­ная в цикле не ме­ня­ет­ся (например, в цикле while) или ме­ня­ет­ся неверно; 11) не­вер­но рас­став­ле­ны опе­ра­тор­ные скобки	1
Ошибок, пе­ре­чис­лен­ных в п. 1–11, две или больше, или ал­го­ритм сфор­му­ли­ро­ван не­вер­но	0
Максимальный балл	2

 

На пу­стой шах­мат­ной доске в одной из кле­ток стоит шах­мат­ный конь. Опи­ши­те на рус­ском языке или на одном из язы­ков про­грам­ми­ро­ва­ния ал­го­ритм по­лу­че­ния спис­ка кле­ток, ко­то­рые конь может до­стичь за один ход из дан­ной клет­ки. На вход про­грам­мы по­сту­па­ют два целых числа: х, у (1 < х,у < 8) — ко­ор­ди­на­ты клет­ки, в ко­то­рой стоит конь. На вы­хо­де про­грам­мы дол­жен быть вы­ве­ден спи­сок пар целых чисел — ко­ор­ди­на­ты кле­ток, до­сти­жи­мых конём из ис­ход­ной клет­ки за один ход.

 

Пояснение.

За­ме­тим, что раз­ность со­от­вет­ству­ю­щих ко­ор­ди­нат кле­ток со­единённых ходом коня, равна 1 и 2 по мо­ду­лю. Можно ис­поль­зо­вать дан­ный кри­те­рий при пе­ре­бо­ре кле­ток доски. При­мер про­грам­мы на языке Пас­каль:

var i, j, x, y, d1, d2 : integer;

begin

readln(x, y);

for i := 1 to 8 do

for j := 1 to 8 do

begin

d1 := abs(i-x);

d2 := abs(j-y);

if ((d1=1) and (d2=2)) or ((d1=2) and (d2=1)) then writeln(i, ‘ ‘, j);

end;

end.

 

Критерии оце­ни­ва­ния вы­пол­не­ния задания	Баллы
Не вы­пол­не­но ни одно из условий, поз­во­ля­ю­щих по­ста­вить 3, 2 или 1 балл.	0
Не вы­пол­не­ны условия, поз­во­ля­ю­щие по­ста­вить 3 или 2 балла, и вы­пол­не­но одно из сле­ду­ю­щих условий. 1. Пер­вое за­да­ние вы­пол­не­но полностью. 2. Во вто­ром за­да­нии пра­виль­но ука­за­но одно из двух воз­мож­ных зна­че­ний S и для этого зна­че­ния ука­за­на и обос­но­ва­на вы­иг­рыш­ная стра­те­гия Пети. 3. Пер­вое за­да­ние вы­пол­не­но частично, и для од­но­го из осталь­ных за­да­ний пра­виль­но ука­за­но зна­че­ние S. 4. Для вто­ро­го и тре­тье­го за­да­ния пра­виль­но ука­за­ны зна­че­ния S.	1
Не вы­пол­не­ны условия, поз­во­ля­ю­щие по­ста­вить 3 балла, и вы­пол­не­но одно из сле­ду­ю­щих условий. 1. За­да­ние 3 вы­пол­не­но полностью. 2. Пер­вое и вто­рое за­да­ния вы­пол­не­ны полностью. 3. Пер­вое за­да­ние вы­пол­не­но пол­но­стью или частично; для за­да­ний 2 и 3 ука­за­ны пра­виль­ные зна­че­ния S.	2
Вы­пол­не­ны вто­рое и тре­тье задания. Пер­вое за­да­ние вы­пол­не­но пол­но­стью или частично. Здесь и далее в ре­ше­ни­ях до­пус­ка­ют­ся ариф­ме­ти­че­ские ошибки, ко­то­рые не ис­ка­жа­ют сути ре­ше­ния и не при­во­дят к не­пра­виль­но­му ответу.	3
Максимальный балл	3

 

Два иг­ро­ка, Петя и Ваня, иг­ра­ют в сле­ду­ю­щую игру. Перед иг­ро­ка­ми лежит куча кам­ней. Иг­ро­ки ходят по оче­ре­ди, пер­вый ход де­ла­ет Петя. За один ход игрок может:

до­ба­вить в кучу один ка­мень (дей­ствие А) или

утро­ить ко­ли­че­ство кам­ней в куче, а затем убрать из кучи 2 камня (дей­ствие Б).

На­при­мер, имея кучу из 10 кам­ней, за один ход можно по­лу­чить кучу из 11 или 28 кам­ней. У каж­до­го иг­ро­ка, чтобы де­лать ходы, есть не­огра­ни­чен­ное ко­ли­че­ство кам­ней.

Игра за­вер­ша­ет­ся в тот мо­мент, когда ко­ли­че­ство кам­ней в куче ста­но­вит­ся более 30. По­бе­ди­те­лем счи­та­ет­ся игрок, сде­лав­ший по­след­ний ход, то есть пер­вым по­лу­чив­ший кучу, в ко­то­рой будет 31 или боль­ше кам­ней.

В на­чаль­ный мо­мент в куче было S кам­ней, 2 ≤ S ≤ 30.

 

Го­во­рят, что игрок имеет вы­иг­рыш­ную стра­те­гию, если он может вы­иг­рать при любых ходах про­тив­ни­ка. Опи­сать стра­те­гию иг­ро­ка – зна­чит опи­сать, какой ход он дол­жен сде­лать в любой си­ту­а­ции, ко­то­рая ему может встре­тить­ся при раз­лич­ной игре про­тив­ни­ка.

 

Вы­пол­ни­те сле­ду­ю­щие за­да­ния. Во всех слу­ча­ях обос­но­вы­вай­те свой ответ.

1.

а) При каких зна­че­ни­ях числа S Петя может вы­иг­рать пер­вым ходом? Ука­жи­те все такие зна­че­ния и вы­иг­ры­ва­ю­щий ход Пети.

б) Ука­жи­те такое зна­че­ние S, при ко­то­ром Петя не может вы­иг­рать за один ход, но при любом ходе Пети Ваня может вы­иг­рать своим пер­вым ходом. Опи­ши­те вы­иг­рыш­ную стра­те­гию Вани.

2. Ука­жи­те два зна­че­ния S, при ко­то­рых у Пети есть вы­иг­рыш­ная стра­те­гия, причём (а) Петя не может вы­иг­рать пер­вым ходом, но (б) Петя может вы­иг­рать своим вто­рым ходом, не­за­ви­си­мо от того, как будет хо­дить Ваня.

Для ука­зан­ных зна­че­ний S опи­ши­те вы­иг­рыш­ную стра­те­гию Пети.

3. Ука­жи­те такое зна­че­ние S, при ко­то­ром

– у Вани есть вы­иг­рыш­ная стра­те­гия, поз­во­ля­ю­щая ему вы­иг­рать пер­вым или вто­рым ходом при любой игре Пети, и при этом

– у Вани нет стра­те­гии, ко­то­рая поз­во­лит ему га­ран­ти­ро­ван­но вы­иг­рать пер­вым ходом.

Для ука­зан­но­го зна­че­ния S опи­ши­те вы­иг­рыш­ную стра­те­гию Вани.

По­строй­те де­ре­во всех пар­тий, воз­мож­ных при этой вы­иг­рыш­ной стра­те­гии Вани (в виде ри­сун­ка или таб­ли­цы). На реб­рах де­ре­ва ука­зы­вай­те, кто де­ла­ет ход, в узлах – ко­ли­че­ство кам­ней в по­зи­ции.

 

Пояснение.

1. а) Петя может вы­иг­рать, если S=11, …, 30. При мень­ших зна­че­ни­ях Sза один ход нель­зя по­лу­чить кучу, в ко­то­рой не менее 31 камня. Пете до­ста­точ­но уве­ли­чить ко­ли­че­ство кам­ней в 3 раза и от­нять два камня (дей­ствие Б).

б) Ваня может вы­иг­рать пер­вым ходом (как бы ни играл Петя), если ис­ход­но в куче будет S = 10 кам­ней. Тогда после пер­во­го хода Пети в куче будет 11 кам­ней или 28 кам­ней. В обоих слу­ча­ях Ваня вы­пол­ня­ет дей­ствие Б и вы­иг­ры­ва­ет в один ход.

2. Воз­мож­ные зна­че­ния S: 4, 9. В этих слу­ча­ях Петя, оче­вид­но, не может вы­иг­рать пер­вым ходом. Од­на­ко он может по­лу­чить кучу из 10 кам­ней (при S= 4 он вы­пол­ня­ет дей­ствие Б; при S= 9 – до­бав­ля­ет 1 ка­мень т. к. вы­пол­ня­ет дей­ствие А). Эта по­зи­ция разо­бра­на в п. 1 б. В ней игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­рать не может, а его про­тив­ник (то есть Петя) сле­ду­ю­щим ходом вы­иг­ра­ет.
3. Воз­мож­ное зна­че­ние S: 8. После пер­во­го хода Пети в куче будет 9 кам­ней или 22 камня. Если в куче ста­нет 22 камня, Ваня вы­пол­нит дей­ствие Б и вы­иг­ра­ет своим пер­вым ходом. Си­ту­а­ция, когда в куче 9 кам­ней, разо­бра­на

в п. 2. В этой си­ту­а­ции игрок, ко­то­рый будет хо­дить (те­перь это Ваня), вы­иг­ры­ва­ет своим вто­рым ходом.

В таб­ли­це изоб­ра­же­но де­ре­во воз­мож­ных пар­тий при опи­сан­ной стра­те­гии Вани. За­клю­чи­тель­ные по­зи­ции (в них вы­иг­ры­ва­ет Ваня) подчёрк­ну­ты. На ри­сун­ке это же де­ре­во изоб­ра­же­но в гра­фи­че­ском виде (оба спо­со­ба изоб­ра­же­ния де­ре­ва до­пу­сти­мы).

 

	По­ло­же­ния после оче­ред­ных ходов
Исх. полож.	1‐й ход Пети (разо­бра­ны все ходы)	1‐й ход Вани (толь­ко ход по стра­те­гии)	2‐й ход Пети (разо­бра­ны все ходы)	2‐й ход Вани (толь­ко ход по стра­те­гии)
8	8+1 =9	9+1=10	10+1=11	3*11–2=31
			3*10–2=28	3*28–2=82
	3*8–2=22	3*22–2=64

 

 

Критерии оце­ни­ва­ния вы­пол­не­ния задания	Баллы
Программа ра­бо­та­ет для любых вход­ных дан­ных про­из­воль­но­го раз­ме­ра и на­хо­дит ответ, не со­хра­няя вход­ные дан­ные в массиве, раз­мер ко­то­ро­го со­от­вет­ству­ет числу N (количеству запросов). Про­грам­ма про­смат­ри­ва­ет вход­ные дан­ные один раз. До­пус­ка­ет­ся на­ли­чие в тек­сте про­грам­мы одной син­так­си­че­ской ошибки: про­пу­щен или не­вер­но ука­зан знак пунктуации, не­вер­но на­пи­са­но или про­пу­ще­но за­ре­зер­ви­ро­ван­ное слово языка программирования, не опи­са­на или не­вер­но опи­са­на переменная, при­ме­ня­ет­ся операция, не­до­пу­сти­мая для со­от­вет­ству­ю­ще­го типа дан­ных (если одна и та же ошиб­ка встре­ча­ет­ся не­сколь­ко раз, то это счи­та­ет­ся за одну ошибку).	4
Программа ра­бо­та­ет верно, но вход­ные дан­ные за­по­ми­на­ют­ся в массиве, раз­мер ко­то­ро­го со­от­вет­ству­ет числу N. Этот массив, возможно, потом сортируется. До­пус­ка­ет­ся на­ли­чие от одной до трех син­так­си­че­ских ошибок. Возможно, в прин­ци­пи­аль­но верно ор­га­ни­зо­ван­ном вводе дан­ных есть одна ошиб­ка (например, ис­поль­зо­ва­ние read вме­сто readln в Пас­ка­ле или не­вер­ное счи­ты­ва­ние стро­ки в C++). Три балла также выставляется, если в эф­фек­тив­ной программе, удо­вле­тво­ря­ю­щей кри­те­ри­ям вы­став­ле­ния 4 баллов, есть одна ошибка, в ре­зуль­та­те ко­то­рой про­грам­ма ра­бо­та­ет не­вер­но на не­ко­то­рых на­бо­рах не­ти­пич­ных вход­ных данных.	3
Программа ра­бо­та­ет в целом верно, эф­фек­тив­но или нет, но в ре­а­ли­за­ции ал­го­рит­ма со­дер­жит­ся до двух оши­бок (неверная ини­ци­а­ли­за­ция счётчиков, до­пу­ще­на ошиб­ка в прин­ци­пи­аль­но верно ор­га­ни­зо­ван­ной сор­ти­ров­ке или ал­го­рит­ме по­ис­ка ми­ни­маль­ных элементов, ис­поль­зу­ет­ся знак “<” вме­сто “<=”, “or” вме­сто “and” и тому подобное). Возможно, не­кор­рект­но ор­га­ни­зо­ва­но счи­ты­ва­ние вход­ных данных. До­пус­ка­ет­ся на­ли­чие от одной до пяти син­так­си­че­ских ошибок, опи­сан­ных выше	2
Программа, возможно, не­вер­но ра­бо­та­ет при не­ко­то­рых вход­ных данных, но по приведённому тек­сту ре­ше­ния ясно, что эк­за­ме­ну­е­мый понимает, из каких эта­пов долж­но со­сто­ять ре­ше­ние задачи. При ис­поль­зо­ва­нии сор­ти­ров­ки она может быть ре­а­ли­зо­ва­на прин­ци­пи­аль­но не­вер­но (например, вме­сто двух цик­лов ис­поль­зу­ет­ся один), или до­пу­ще­на прин­ци­пи­аль­ная ошиб­ка в по­ис­ке нуж­ных элементов. Всего до­пус­ка­ет­ся до 4 раз­лич­ных оши­бок в ре­а­ли­за­ции алгоритма, в том числе опи­сан­ных в кри­те­ри­ях при­сво­е­ния двух баллов. До­пус­ка­ет­ся на­ли­чие от одной до семи син­так­си­че­ских ошибок, опи­сан­ных выше.	1
Задание не вы­пол­не­но или вы­пол­не­но неверно.	0
Максимальный балл	4

 

На вход про­грам­ме по­да­ют­ся све­де­ния о но­ме­рах школ уча­щих­ся, участ­во­вав­ших в олим­пиа­де. В пер­вой стро­ке со­об­ща­ет­ся ко­ли­че­ство уча­щих­ся N, каж­дая из сле­ду­ю­щих N строк имеет сле­ду­ю­щий фор­мат: <Фа­ми­лия> <Ини­ци­а­лы> <номер школы>, где <Фа­ми­лия> — стро­ка, со­сто­я­щая не более чем из 20 сим­во­лов, <Ини­ци­а­лы> — стро­ка, со­сто­я­щая из 4-х сим­во­лов (буква, точка, буква, точка), <номер школы> — не более чем дву­знач­ный номер. <Фа­ми­лия> и <Ини­ци­а­лы>, а также <Ини­ци­а­лы> и <номер школы> раз­де­ле­ны одним про­бе­лом. При­мер вход­ной стро­ки:

Ива­нов П.С. 57

 

Тре­бу­ет­ся на­пи­сать как можно более эф­фек­тив­ную про­грам­му (ука­жи­те ис­поль­зу­е­мую вер­сию языка про­грам­ми­ро­ва­ния, на­при­мер, Borland Pascal 7.0), ко­то­рая будет вы­во­дить на экран ин­фор­ма­цию, из какой школы (школ) было боль­ше всего участ­ни­ков олим­пи­а­ды.

 

Пояснение.

var nс:аrrау[1..99] of integer;

р:1..99;

с: char;

i, N, max: integer;

begin

readln(N);

for i:=l to 99 do nc[i]:=0;

for i:=l to N do

begin

repeat

read(c)

until с=’  ‘;

repeat

read(c)

until с=’  ‘;

readln(p);

nc[p]:=nc[p]+1;

end;

max:=0;

for i:=1 to 99 do

if nc[i]>0 then

if nc[i]>max then max:=nc[i];

for i:=l to 99 do

if nc[i]=max then writeln(i);

readln

end.