then write('принадлежит')

2020-02-03

297

Обсуждений (0)

0.00 из 5.00 0 оценок

⇐ Предыдущая 12

Else write('не принадлежит')

end.

Могут быть и другие способы доработки.

Решение для варианта 2 полностью аналогично варианту 1.

С2. Приведем алгоритм решения задачи на русском языке.

Введем целочисленную переменную Diff с первоначальным значением, равным разности второго и первого элементов, в которую будем заносить разности значений элементов. Введем также переменную MinDiff для записи результата вычислений. Установим первоначальное значение MinDiff равным Diff. В цикле от третьего элемента до конца массива вычисляем разность текущего элемента и предыдущего и заносим его в переменную Diff. Далее сравниваем значения Diff и MinDiff. В случае, если текущая разность меньше, заносим значение текущей разности в переменную MinDiff. По окончании цикла выводим значение переменной MinDiff.

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

program ex_c2;

const N = 30;

var a:array[1..N] of integer;

Diff, MinDiff, i: integer;

begin

Diff := a[2] – a[1];

MinDiff := Diff;

for i := 3 to N do

begin

Diff := a[i] – a[i –1];

if MinDiff > Diff then MinDiff := Diff

end;

writeln(MinDiff);

end.

Решение для варианта 2 в целом аналогично варианту 1. Особенностью второго варианта является необходимость предусмотреть в алгоритме проверку присутствия в массиве положительного элемента, и в случае отсутствия таковых требуется выдать соответствующее сообщение.

С3. Вариант 1.

Выигрывает второй игрок.[5] Приведем два способа решения

1 способ. Построение неполного дерева игры.

При таком способе рассматриваются все возможные варианты позиций, которые могут получиться после выполнения очередного хода. Позиции при этом играют роль вершин графа, а возможность перехода от одной позиции к другой обозначается ребром, соединяющим эти позиции. Можно изображать получающееся дерево стандартным образом, а можно оформить его в виде таблицы, где в каждой ячейке записаны координаты фишки на каждом этапе игры. При этом некоторые ветви могут не рассматриваться, если они уже были рассмотрены ранее (тогда-то и получается неполное дерево игры), но надо точно обосновывать, что отсечение ветвей не приводит к потере нерассмотренных вариантов.

Приведем неполное дерево вариантов для данной игры.

	1 ход	2 ход	3 ход	4 ход
Стартовая позиция	I-й игрок (все варианты хода)	II-й игрок (выигрышный ход)	I-й игрок (все варианты хода)	II-й игрок (выигрышный ход, один из вариантов)
1, 0	1, 4	4, 4	4, 8	4, 12
			4, 7	4 ,11
			7, 4	10 ,4
	1, 3	4, 3	4, 7	4 ,11
			4, 6	4 ,10
			7 ,3	10 ,3
	4, 0	4, 4 или 4, 3	Уже рассмотрено

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

Этот вывод должен быть обязательно сформулирован. Без него решение считается неполным.

2 способ. Построение таблицы выигрышных и проигрышных позиций.

Скажем сначала несколько слов об этом способе, поскольку он практически отсутствует в учебной литературе

Совокупность всех незаключительных позиций игры разбивается на два множества: множество выигрышных позиций и множество проигрышных позиций. Обозначим множество выигрышных позиций буквой V, а множество проигрышных позиций буквой Р. Чем характеризуются эти множества? Это можно описать совершенно формально. Позиция х является выигрышной (т.е. х ÎV), если существует ход (т.е. ребро графа), ведущий из х в заключительную позицию или позицию из множества Р. В свою очередь, позиция х является проигрышной (т.е. х ÎР), если любой ход из этой позиции ведет в позицию из множества V. Это позволяет расставить знаки + и – по следующему правилу: знаком – отмечаются все заключительные и проигрышные позиции, а знаком + отмечаются все выигрышные. Фактически это некий алгоритм: сначала знак – выставляется для всех заключительных позиций, затем выставляется знак + для каждой позиции, в которой есть ход, ведущий в позицию, помеченную знаком –, затем выставляется знак – для каждой позиции, у которой все ходы ведут в позиции, помеченные знаком +, и т.д.

Вот как выглядит заполненная таблица:

‑

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

Вариант 2. Выигрывает первый игрок. Для этого своим первым ходом он должен поставить фишку в точке с координатами (4,–4). Для доказательства того, что после этого хода он выигрывает, приведем неполное дерево вариантов игры, оформленное в виде таблицы, где в каждой ячейке координаты фишки на каждом этапе игры.

1 ход	2 ход	3 ход	4 ход	5 ход
Позиция после первого хода	II-й игрок (все варианты хода)	I-й игрок (выигрышный ход)	II-й игрок (все варианты хода)	I-й игрок (выигрышный ход, один из вариантов)
4, –4	8, –4	12, –4	Выигрыш первого игрока
	8, 0	12, 4	Выигрыш первого игрока
	4, 0	4, 4	8, 4	12, 8
			4, 8	8, 12
			8, 8	12, 12

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

А вот решение той же задачи с помощью таблицы выигрышных и проигрышных позиций:

‑

–

‑

–

‑

–

‑

–

‑

–

‑

‑1

‑

‑2

‑

‑3

‑

‑4

‑

–

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

С4. Вариант 1.

Программа читает входные данные, не запоминая их все, а сразу подсчитывая в массиве, хранящем 99 целых чисел согласно номерам школ, количество участников олимпиады из каждой школы или метку, что ученики этой школы присутствовали. Затем распечатываются индексы ненулевых элементов этого массива.

Пример правильной и эффективной программы:

program ex_c4_1;

var nc:array[1..99] of integer;

p:1..99;

c:char;

i, k, N, max: integer;

begin

readln(N);

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

for i:=1 to N do

begin

repeat read(c) until c =’ ’; {считана фамилия}

repeat read(c) until c =’ ’; {считаны инициалы}

readln(p);

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

end;

for i:=1 to 99 do

if nc[i]>0 then writeln(i);

readln

end.

Вариант 2.

Программа читает все входные символы до точки один раз, помечая в массиве, состоящем из 10 элементов, какие цифры встретились во входных данных. Сами цифры при этом не запоминаются. За дополнительный проход этого массива печатаются те цифры, которые оказались помеченными, в противном случае выводится –1.

Пример правильной и эффективной программы на языке Паскаль:

program ex_c4_2;

var a: array[0..9] of boolean;

c: char;

i, k: integer;

begin

for i:= 0 to 9 do a[i]:=false;

read(c);

while c<>'.' do

begin

if c in ['0'..'9'] then

begin

k:=ord(c)-ord('0');

a[k]:=true

end;

read(c);

end;

k:=0;

for i:= 9 to 0 do

if a[i] then begin k := k+1; write(i) end;

if k=0 then write(–1);

writeln

end.

IV. Литература

1. Гейн А.Г. Информатика и информационные технологии: учеб. для 8 кл. общеобразоват. учреждений / А.Г. Гейн, А.И. Сенокосов, Н.А. Юнерман. – М.: Просвещение, 2008. – 175 с.

2. Гейн А.Г. Информатика и информационные технологии: учеб. для 9 кл. общеобразоват. учреждений / А.Г. Гейн, А.И. Сенокосов.– М.: Просвещение, 2006. – 301 с.

3. Гейн А.Г. Информатика и ИКТ: учеб. для 10 кл. общеобразоват. учреждений / А.Г. Гейн, А.Б. Ливчак, А.И. Сенокосов, Н.А. Юнерман – М.: Просвещение, 2008. – 301 с.

4. Гейн А.Г. Информатика и ИКТ: учеб. для 11 кл. общеобразоват. учреждений / А.Г. Гейн, А.И. Сенокосов. – М.: Просвещение, 2009. – 337 с.

5. Гусева И.Ю. ЕГЭ. Информатика. Раздаточный материал тренировочных тестов. / И.Ю. Гусева. – СПб.: Тригон, 2008. – 120 с.

6. ЕГЭ 2008. Информатика. Федеральный банк экзаменационных материалов / Авт.-сост. П.Я.Якушкин, С.С. Крылов. – М.: Эксмо, 2008. – 128 с.

7. Единый государственный экзамен 2008. Информатика. Учебно-тренировочные материалы для подготовки учащихся / Авт.-сост. С.С. Крылов, В.Р. Лещинер, П.Я.Якушкин. – ФИПИ – М.: Интеллект-Центр, 2007. – 120 с.

8. Молодцов В.А. Информатика: тесты, задания, лучшие методики / В.А. Молодцов, Н.Б. Рыжикова. – Ростов на Дону: Феникс, 2008. – 217 с.

9. Русаков С.В. Тестовые задания по базовому курсу информатики / С.В. Русаков, Л.В. Шеставкова. – М.: Чистые пруды, 2006. – 32 с.

[1] Ознакомиться с демоверсией ЕГЭ-2009 можно на сайте ФИПИ: www.fipi.ru

[2] Такую работу можно выполнить, используя и демонстрационный вариант ЕГЭ-2009. Тогда оба предложенных нами варианта можно прорешать во втором режиме.

[3] Мы дословно воспроизвели инструкцию к выполнению заданий этой части. На самом деле задания можно выполнять и записывать их решение в любом порядке, но для каждого из заданий нельзя разрывать запись его решения.

[4] Задания можно выполнять и записывать их решение в любом порядке, но нельзя разрывать запись решения.

[5] При определении расстояния от начала координат до текущей точки с координатами (х, у) надо пользоваться формулой .

2020-02-03

297

Обсуждений (0)

0.00 из 5.00 0 оценок

⇐ Предыдущая 12

Обсуждение в статье: then write('принадлежит')

Обсуждений еще не было, будьте первым... ↓↓↓