Решение задач С1, С2 и С3 Золотарева Е.В.. С1. Требовалось написать программу, которая вводит с клавиатуры натуральное число N, не превышающее 10 9, и. - презентация

1 Решение задач С1, С2 и С3 Золотарева Е.В.

2

3 С1. Требовалось написать программу, которая вводит с клавиатуры натуральное число N, не превышающее 10 9, и выводит сумму чётных цифр в десятичной записи этого числа или 0, если чётных цифр нет. Программист торопился и написал программу неправильно. Вот она: var N: longint; s: integer; begin readln(N);(1) s := 0;(2) while N > 1 do begin(3) if N mod 2 = 0 then begin(4) s := N mod 10;(5) end;(6) N := N div 10;(7) end;(8) write(s);(9) end. Последовательно выполните следующее. 1. Напишите, что выведет эта программа при вводе числа Приведите пример числа, при вводе которого программа выдаст верный ответ. 3. Найдите в программе все ошибки (их может быть одна или несколько). Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде.

4 C1. Требовалось написать программу, которая получает на вход натуральное число N, не превосходящее 10 9, и выводит число, которое получается из N после удаления всех единиц; порядок остальных цифр при этом не меняется. Например, число должно быть преобразовано в число Число, в котором все цифры – единицы и нули, должно быть преобразовано в 0. Незначащие нули в старших разрядах полученного числа печатать не нужно. Программист торопился и написал программу неправильно. var N, R, T: longint; d: integer; begin readln(N); R:=0; T:=1; while N>0 do begin d := N mod 10; if d1 then begin R := R + d*T; T := T+1 end; N := N div 10; end; writeln(T); end. Последовательно выполните следующее. Напишите, что выведет эта программа при вводе числа 314. Найдите все ошибки в этой программе (их может быть одна или несколько). Для каждой ошибки: 1) Выпишите строку, в которой сделана ошибка. 2) Укажите, как исправить ошибку – приведите правильный вариант строки. Обратите внимание, что требуется найти ошибки в имеющейся программе, а не написать свою, возможно, использующую другой алгоритм решения. при вводе числа 314 программа выводит 3 (неправильный ответ). Ошибка 1: выводить следует значение переменной R: строка: writeln(T); исправление: writeln(R); Ошибка 2: изменение переменной T в теле цикла строка: T := T+1 исправление: T := T*10

5 С1. Требовалось написать программу, при выполнении которой с клавиатуры вводится натуральное число, не превосходящее 10 8, и выводится его первая (старшая) цифра. Ученик написал такую программу: var n: longint; begin read(n); while n>10 do begin n := n mod 10 end; write(n); end. Последовательно выполните следующее. Напишите, что выведет эта программа при вводе числа Приведите пример числа, при вводе которого программа выдаст верный ответ. Найдите в программе все ошибки (их может быть одна или несколько). при вводе числа 1984 программа выводит 4 (неправильный ответ). программа работает верно для любого числа, у которого старшая цифра равна младшей, в том числе для любого однозначного числа Ошибка 1: в условии цикла должно быть строгое равенство: строка: while n>10 do begin исправление: while n>=10 do begin Ошибка 2: операция в теле цикла строка: n := n mod 10 исправление: n := n div 10

6 С1 var x: real; begin readln(x); if x>=-3 then if x1 then write('не принадлежит') else write('принадлежит') end. В столбцах условий укажите «да», если условие выполнится, «нет», если условие не выполнится, «» (прочерк), если условие не будет проверяться, «не изв.», если программа ведет себя по-разному для разных значений, принадлежащих данной области. В столбце «Программа выведет» Если программа ничего не выводит, напишите «» (прочерк). Если для разных значений, принадлежащих области, будут выведены разные тексты, напишите «не изв.». В последнем столбце укажите «Да» или «Нет». Х>=-3 Х1 ДА НЕ принадле жит принадле жит НЕТ

7 ОблУсл 1 (x>=-3) Усл 2 (x1) Программа выдает Область обрабатыва ется верно АНет---нет ВДа НетПринадлежДа С Не принадлДа D Не принадлНет EДаНет-- Х>=-3 Х1 ДА Не принадл принадл НЕТ

8 С1 var x: real; begin readln(x); if x>=-3 then if x1 then write('не принадлежит') else write('принадлежит') end. If (x=>-3) and (x =5) and (x

9 var x,y: real; begin readln(x,y); if y>=x then if y>=0 then if y=Х У>=0 У

10 Обл аст ь y>= x? y>=0 ? y=Х У>=0 У

11 var x,y: real; begin readln(x,y); if y>=x then if y>=0 then if y=0))

12 Требовалось написать программу, при выполнении которой с клавиатуры считываются координаты точки на плоскости (х, у - действительные числа) и определяется принадлежность этой точки заданной закрашенной области (включая границы). Ученик написал такую программу: var x, y: real; begin readln(x,у); if у >= x*x-6 then begin if x*x + у* у = 0 then write('принадлежит') else write('не принадлежит') end. При проверке работы программа выполнялась по шагам для некоторых контрольных значений х и у, при этом был заполнен протокол тестирования. В результате неаккуратного обращения протокол был испорчен, частично сохранились только четыре строки:

13 Область Условие 1 (y >= x*x-6) Условие 2 (x*x+y*y = 0) ВыводВерно да принадлежитнет не принадлежитда – Последовательно выполните следующее. Восстановите уцелевшие строки протокола, заполнив все клетки таблицы. Там, где содержание восстанавливается неоднозначно, запишите любое возможное значение. Например, если для нескольких областей получается одинаковая строка таблицы, укажите в графе « Область » любую из этих областей. Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)

14 Область Условие 1 (y >= x*x-6) Условие 2 (x*x+y*y = 0) ВыводВерно да принадлежитнет не принадлежитда – У>=x*x-6 x 2 +y 2 =0 НЕТДА НЕТ

15

16 …:=…; for i:=… to … do тело цикла Writeln(…); end. If …=… then Writeln(не найдено) else writeln (…); end. max:=99; for i:=1 to N do if (max 99) and (a[i] 0) then max:=a[i]; If max=99 then writeln (не найдено) else Writeln(max); end.

17 С2. Дан массив, содержащий 2014 положительных целых чисел. Симметричной парой называются два элемента, которые находятся на равном расстоянии от концов массива. Например, 1-й и 2014-й элементы, 2-й и 2013-й и т. д. Порядок элементов в симметричной паре не учитывается: элементы на 1 и 2014 местах – это та же самая пара, что и элементы на 2014 и 1 местах. Напишите на одном из языков программирования программу, которая подсчитывает в массиве количество симметричных пар, у которых сумма элементов больше 20. Программа должна вывести одно число – количество отобранных симметричных пар. Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из описанных переменных. const N=2014; var a: array [1..N] of integer; i, j, k: integer; begin for i:=1 to N do readln(a[i]); … end.

18 В цикле нужно находить сумму элемента массива (a[i]) с симметричным ему элементом, который имеет номер N-i+1 (так чтобы для i=1 мы получили N ). Если выполняется условие, что эта сумма больше 20, то увеличиваем счётчик – переменную k. ВАЖНО: поскольку мы просматриваем массив фактически сразу с двух концов, нужно остановиться на середине, то есть в цикле сделать N div 2 шагов, а не N : k:=0; for i:=1 to N div 2 do if a[i]+a[N+1-i] > 20 then k:= k + 1; writeln(k); end.

19 С3 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 22. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 22 или больше камней. В начальный момент в куче было S камней, 1 S 21. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах против ника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.

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

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

22 3. Укажите значение S, при котором: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах – количество камней в куче. При первом чтении условие этой задачи поражает и отпугивает своей длиной почти страница текста. Но на самом деле она довольно проста, и, что самое главное, в ней требуется понимание сути игровой стратегии и минимум рутинной работы. В результате вероятность случайной ошибки довольно низка. При первом чтении условие этой задачи поражает и отпугивает своей длиной почти страница текста. Но на самом деле она довольно проста, и, что самое главное, в ней требуется понимание сути игровой стратегии и минимум рутинной работы. В результате вероятность случайной ошибки довольно низка.

23 *2 1. а) Укажите все такие значения числа S, при которых Петя может выиграть в один ход б) Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом. П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 В1В1 1 а) Петя может выиграть за один ход при любом S > 10. Он должен увеличить вдвое число камней, при этом в куче всегда получится не менее 22 камней. При S = 10 Петя не может выиграть в один ход, потому что при его ходе +1 число камней в куче становится равно 11 (меньше 22), а при ходе *2 число камней в куче становится равно 20 (также меньше 22). Других возможных ходов у Пети нет. Из любой позиции после одного хода Пети (это мо- жет быть 11 или 20) Ваня может выиграть своим первым ходом, удвоив количество камней в куче.

24 *2 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 В1В1 2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём – Петя не может выиграть за один ход, и – Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. Для каждого указанного значения S опишите выигрышную стратегию Пети. П2П2 П2П2 *2 +1 Из позиций S = 9 и S = 5 Петя не может выиграть в один ход, но Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. При S = 9 ходом +1 Пете нужно перевести игру в позицию S = 10, которая является проигрышной (см. ответ на вопрос 1б). При S = 5 Петя пере- водит игру в ту же позицию ходом *2.

25 *2 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 П1П1 В1В1 П2П2 П2П2 Укажите значение S, при котором: – у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и – у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вани. В2В2 *2 +1 В позиции S = 8 у Вани есть выигрышная стратегия, которая позволяет ему выиграть первым или вторым ходом. Если Петя выбирает ход +1, в куче становится 9 камней, и Ваня выигрывает на втором ходу (см. ответ на вопрос 2). Если Петя выбирает ход *2, Ваня выигрывает первым ходом, удвоив число камней в куче.

26

27 1б) При S = 10 Петя не может выиграть в один ход, потому что при его ходе +1 число камней в куче становится равно 11 (меньше 22), а при ходе *2 число камней в куче становится равно 20 (также меньше 22). Других возможных ходов у Пети нет. Из любой позиции после одного хода Пети (это может быть 11 или 20) Ваня может выиграть своим первым ходом, удвоив количество камней в куче. 1 а) Петя может выиграть за один ход при любом S > 10. Он должен увеличить вдвое число камней, при этом в куче всегда получится не менее 22 камней. 2) Из позиций S = 9 и S = 5 Петя не может выиграть в один ход, но Петя может выиграть своим вторым ходом, независимо от того, как будет ходить Ваня. При S = 9 ходом +1 Пете нужно перевести игру в позицию S = 10, которая является проигрышной (см. ответ на вопрос 1б). При S = 5 Петя пере- водит игру в ту же позицию ходом *2.

28 В позиции S = 8 у Вани есть выигрышная стратегия, которая позволяет ему выиграть первым или вторым ходом. Если Петя выбирает ход +1, в куче становится 9 камней, и Ваня выигрывает на втором ходу (см. ответ на вопрос 2). Если Петя выбирает ход *2, Ваня выигрывает первым ходом, удвоив число камней в куче.

29 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или пять камней или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 20 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 41 или больше камней. В начальный момент в куче было S камней, 1 S При каких S: 1а) Петя выигрывает первым ходом; 1б) Ваня выигрывает первым ходом? 2. Назовите два значения S, при которых Петя может выиграть своим вторым ходом? 3. Назовите два значения S, при которых Ваня выигрывает своим первым или вторым ходом?