Writeln(kMax);

End.

 

Возможные проблемы: · как видим, основная сложность в этой задаче – не написать программу, а придумать хороший (часто еще нужно – быстрый) алгоритм · проверьте, что будет записано в переменные до начала цикла (определены ли их начальные значения) · проверяйте, не выйдет ли индекс за границу массива в начале или в конце цикла · будьте внимательны с «крайними» случаями, например, нужно обязательно убедиться, что программа работает, когда интересующая нас цепочка стоит в самом начале или в самом конце массива

Еще пример задания:

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

Решение:

1) суть задачи: среди элементов каждой строки нужно выбрать максимальный, и все эти выбранные значения сложить

2) несложно сразу написать алгоритм на русском языке:
«Чтобы накапливать сумму, нужно ввести целую переменную Sum, в которую в самом начале записываем 0; далее в цикле просматриваем все строки, для каждой строки находим максимальный элемент и прибавляем его значение к Sum. Для определения максимального элемента в строке вводим переменную max и сначала записываем в нее значение первого элемента этой строки. Затем в цикле просматриваем все остальные элементы, начиная со второго до конца массива. Если очередной элемент больше значения max, записываем в max значение этого элемента».

3) сначала напишем программу на псевдокоде:

const N=10;

{ ввод матрицы N на N }

Sum:= 0;

for i:=1 to N do begin

{ max:= максимальный элемент в i-ой строке }

Sum:= Sum + max;

End;

4) остается записать на Паскале те части, которые взяты в фигурные скобки, и до конца оформить программу; по правилам ЕГЭ можно не писать в программе команды для ввода массива, поэтому мы оставим на этом месте комментарий:

const N=10;

var A: array[1..N,1..N] of integer;

i, k, max, Sum: integer;

Begin

{ ввод матрицы N на N }

Sum:= 0;

for i:=1 to N do begin

max:= A[i,1];

for k:=2 to N do

if A[i,k] > max then max:= A[i,k];

Sum:= Sum + max;

End;

Writeln(Sum);

End.

Возможные проблемы: · проверьте, правильно ли заданы (и заданы ли вообще) начальные значения для всех переменных · проверьте, правильно ли расставлены операторные скобки begin-end, ограничивающие тело цикла · проверяйте, не выйдет ли индекс за границу массива в начале или в конце цикла · не перепутайте номер строки (1-й индекс) и номер столбца (2-й индекс) · для надежности не рекомендуется использовать в одной программе переменные i и j, потому что они слишком похоже выглядят

 

Немного тактики: · в этом задании можно написать алгоритм на русском языке, а можно (вместо этого) написать компьютерную программу на одном из языков программирования · если вы хорошо умеете выражать свои мысли по-русски, собаководы эксперты рекомендуют писать только алгоритм на русском языке; дело в том, что если вы сделаете много ошибок в программе, оценка будет снижена даже при абсолютно правильном алгоритме · если вам сложно изъясняться на родном языке, а легче записать свои мысли на Паскале или Си – пишите программу, но тщательно проверяйте ее на предмет возможных случайных ошибок-опечаток, которые можно сделать просто по невнимательности: o задавайте все начальные значения для переменных o проверяйте правильность написания ключевых слов o если в теле цикла несколько операторов, заключайте их в блок begin-end o проверяйте начальное и конечное значение переменной цикла o если вы используете циклы while или repeat, проверьте, что переменная цикла изменяется в теле цикла o выводите на экран именно то, что требуется по условию o ставьте точку с запятой в конце операторов o НЕ ставьте точку с запятой перед else (Паскаль) o ставьте точку в конце последнего оператора end (Паскаль)

 

За что снимают баллы: · задано неверное начальное значение переменных (или вообще не задано) · неверно указано условие завершения цикла · «забыли» изменять переменную цикла в цикле while (repeat) · перепутаны знаки < и >, логические операции or и and · неверно расставлены операторные скобки begin-end · программа не выводит результат или выводит не то, что спрашивают · синтаксические ошибки (знаки пунктуации – запятые, точки, точки с запятой; неверное написание ключевых слов) допускаются в разумных пределах (если они не искажают замысел автора)

C3 (высокий уровень, время – 30 мин)

Тема: Динамическое программирование.

Что нужно знать:

· динамическое программирование – это способ решения сложных задач путем сведения их к более простым задачам того же типа

· с помощью динамического программирования решаются задачи, которые требуют полного перебор вариантов:

o «подсчитайте количество вариантов…»

o «как оптимально распределить…»

o «найдите оптимальный маршрут…»

· динамическое программирование позволяет ускорить выполнение программы за счет использования дополнительной памяти; полный перебор не требуется, поскольку запоминаются решения всех задач с меньшими значениями параметров

Пример задания:

Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет 4 камня в какую-то кучу. Игрок, после хода которого общее число камней в двух кучах становится больше 25, проигрывает.

Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход?

Каким должен быть первый ход выигрывающего игрока?

Ответ обоснуйте.

Решение [‡‡‡]:

1) Введем обозначения: х-первая куча, у-вторая куча. Старт: (х,у). Варианты хода игроков: (х*2,у), (х,у*2), (х+4,у), (х, у+4). Игрок проиграет, когда число камней в 2-х кучах станет 25 (х+у=25). Изобразим ход игры в виде дерева решений. Необходимо разветвить дерево до того момента, когда все варианты последнего хода станут проигрышными.

2)
После первого хода дерево будет выглядеть так:

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

3)
После первых 2 -х ходов дерево будет выглядеть так:

4) После первых 3 -х ходов дерево будет выглядеть так:

5) Когда 1 -й игрок совершает 3 -й ход, он проигрывает, когда (х,у) равны: 24,4, 3,32, 3,24, 28,4, 22,4 т.к. сумма х и у в этих случаях больше 25. На рисунке проигрышные позиции 1 -го игрока выделены сплошной рамкой:

6) Каждый игрок играет безошибочно, поэтому 1 -й игрок не пойдет в проигрышную позицию. Позиции: 24,4, 3,32, 3,24, 28,4, 22,4 разветвлять не будем.

7) Найдем в последней строке позиции, где сумма х и у близка к 25 -и. При прибавлении 4 -х количество камней увеличится минимум на 4. Поэтому позиции, где х+у принадлежит [22,25], на следующем ходу дадут только проигрыш при любом ходе игрока. Это правило касается тех позиций, где х и у больше 3 -х (если х или у равны 3 -м, то х+у принадлежит [23,25]). Найдем такие позиции: 6,16, 20,4, 7,16, 14,8, 18,4. На следующем рисунке они выделены розовым. Эти позиции на 4 -м ходу разветвлять не будем.

На рисунке проигрышные позиции 2 -го игрока выделены сплошной рамкой.

8) В последней строке видно, что минимальное значение х и у равно 4 -м, поэтому позиции, где х+у принадлежит [22,25] на следующем ходу дадут только проигрыш при любом ходе игрока. На рисунке они выделены розовым в последней строке (4 -й ход):

На 5 -м ходу получаются только проигрышные позиции (символом "П" обозначены проигрышные позиции).

Поэтому 1 -й игрок проигрывает. Выигрывает 2 -й игрок.

9) Найдем выигрышные позиции 2 -го игрока на 4 -м ходе. Это те позиции, что выделены розовым на 4 -м ходе. Рассмотрим позиции 2 -го игрока на 2 -м ходе.

10) Если 2-й игрок пойдет в позицию 3,16, то при ходе 1 -го игрока в позицию 6,16 или 7,16 на 3 -м ходе 2 -й игрок не может попасть в свои выигрышные позиции на 4 -м ходе.

11) Если 2-й игрок пойдет в позицию 10,4, то при ходе 1 -го игрока в позицию 20,4 на 3 -м ходе 2 -й игрок не может попасть в свои выигрышные позиции на 4-м ходе.

12) Если 2 -й игрок пойдет в позицию 6,8, то при ходе 1 -го игрока в позицию 6,16 на 3 -м ходе 2 -й игрок не может попасть в свои выигрышные позиции на 4 -м ходе.

13) Если 2 -й игрок пойдет в позицию 7,8, то при ходе 1 -го игрока в позицию 14,8 или 7,16 на 3 -м ходе 2 -й игрок не может попасть в свои выигрышные позиции на 4-м ходе.

14) Если 2-й игрок пойдет в позицию 14,4, то при ходе 1 -го игрока в позицию 14,8 или 18,4 на 3 -м ходе 2 -й игрок не может попасть в свои выигрышные позиции на 4-м ходе.

15)
Выигрышные позиции: 12,4, 3,12, 11,4. При любом ходе 1 -го игрока на 3 -м ходу 2 -й игрок может попасть в свои выигрышные позиции на 4 -м ходу. Выигрышные позиции 2 -го игрока на 2 -м ходе выделены зеленым:

16) Представим решение также в виде таблицы[§§§] (выигрышные ходы выделены и подчеркнуты пунктирной линией):

Позиция после первого хода	1-й ход	2-й ход	3-й ход	4-й ход
1-й игрок	2-й игрок	1-й игрок	2-й игрок
3,4	6,4	12,4	12,8	16,8
12,12
16,4	16,8
20,4
3,8	3,12	6,12	12,12
10,12
6,16
7,12	11,12
7,16
3,16	6,16
7,16
3,20
	7,4	11,4	11,8	15,8
11,12
15,4	15,8
19,4

 

17) Получается, выигрывает 2-й игрок

Еще пример задания:

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