Ответы на задачи 24 (С1)

• Название: Ответы на задачи 24 (С1)
• Дата: 21.04.2018
• Размер: 1.99 Mb.
• Имя файла: answ24-C1.doc
• Тип: Программа; #41783
• страница: 18 из 18

sum := N mod 10;

while N > 0 do begin

digit := N mod 10;

if digit mod 3 > 0 then

sum := digit;

N := N div 10;

end;

Во-первых, подозрительно, что начальное значение суммы – не ноль, а последняя цифра введённого числа N mod 10 (обычно сумма накапливается, начиная с 1). При этом проверка на кратность 3 не делается, то есть в переменной sum может оказаться начальное значение, кратное 3.

Во-вторых, в теле цикла если найдена цифра, не кратная 3, она записывается в sum, стирая старое значение, то есть сумма не накапливается, а постоянно обновляется и в итоге будет равна старшей (последней с конца) цифре, не кратной трём. Теперь очевиден ответ на первый вопрос:

1) при вводе числа 654 будет выведено значение 5.

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

2. 
   программа выводит верное значение для трёхзначного числа 313.
   

Остались исправления:

3) в программе нужно исправить две ошибки

1. 
   Неверное начальное значение переменной sum:
   

Было: sum := N mod 10;

Исправление: sum := 0;

2. 
   Неверное изменение переменной sum:
   

Было: sum := digit;

Исправление: sum := sum + digit;

81. 
    Кажется, что эта задача очень похожа на предыдущую, а на самом деле она значительно сложнее. Сложность эта связана с тем, что число 0 кратно 3, поэтому требуемая сумма может быть равна 0, например, для числа 102. Поэтому сравнивать sum с нулем после цикла нельзя, нужно записывать начальное значение, которое отличается от любой возможной суммы, например, –1 .
    

Как только мы нашли цифру, кратную 3, нужно записать её в переменную sum (стирая -1!), а если сумма неотрицательна, добавляем к ней эту цифру:

if sum < 0 then

sum = digit

else

sum := sum + digit;

В остальном подход к решению аналогичен предыдущей задаче.

1) при вводе числа 653 будет выведено значение 6.

2) программа выводит верное значение для трёхзначного числа 113.

3) в программе нужно исправить ТРИ ошибки

1. 
   Неверное начальное значение переменной sum:
   

Было: sum := N mod 10;

Исправление: sum := -1;

2. 
   Неверное изменение переменной sum:
   

Было: sum := digit;

Исправление: if sum < 0 then

sum = digit

else

sum := sum + digit;

3. 
   Неверное сравнение при выводе:
   

Было: if sum > 0 then

Исправление: if sum > -1 then

82. 
    Выполняем ручную прокрутку программы, прослеживая последовательное изменение значений переменных f и fn после окончания работы цикла, а также выводимое значение fn-5, для нескольких первых значений n:
    

n	0	1	2	3	4	5	6	7	8
f	1	2	3	5	8	13	21	34	55
fn	1	1	2	3	5	8	13	21	34

Видим, что последовательные значения переменных f и fn повторяют ряд Фибоначчи. При n=4 программы выводит 0, это ответ на первый вопрос.

Теперь посмотрим, что выводится на экран (это значения fn-5) и какое значение ��(��) мы хотели бы видеть:

n	0	1	2	3	4	5	6	7	8
fn	1	1	2	3	5	8	13	21	34
fn-5	–4	–4	–3	–2	0	3	8	16	29
f(n)	0	1	1	2	3	5	8	13	21

Как следует из таблицы, при n=6 программа выводит правильное значение 8.

Сравнивая в таблице строки fn и ��(��), находим, что значения fn опережают нужную нам последовательность на 1 шаг из-за того, что фактически наша последовательность начинается с двух единиц, а не с 0 и 1, как требуется. Поэтому в самом начале в переменную fn нужно записать 0, а не 1.

Вот правильный ответ:

1) при вводе числа 4 будет выведено значение 0.

2) программа выводит верное значение для числа 6, это значение равно 8.

3) в программе нужно исправить две ошибки

1. 
   Неверное начальное значение переменной fn:
   

Было: fn := 1;

Исправление: fn := 0;

2. 
   Неверный вывод:
   

Было: writeln(fn – 5)

Исправление: writeln(fn)

Возможен другой вариант исправления:

3) в программе нужно исправить две ошибки

1. 
   Неверное начальное значение переменной f:
   

Было: f := 1;

Исправление: f := 0;

2. 
   Неверный вывод:
   

Было: writeln(fn – 5)

Исправление: writeln(f)

83. 
    Заметим, что в последней строке на экран выводится последнее значение переменной k. Выполняем ручную прокрутку программы, прослеживая (для некоторого большого a) последовательное изменение значений переменных k и s:
    

k	1	2	3	4	5
s	0	6	18	38	68

Цикл останавливается, когда нарушается условие s<=A, то есть значение s становится больше A. В данном случае при A < 6 мы получим результат 2, при A  [6; 17] – результат 3, при A  [18; 37] – результат 4, при A  [38; 67] – результат 5, и т.д. Отсюда следует ответ на первый вопрос:

1) при вводе числа 15 программа выведет ответ 3.

В правильной программе переменная k должна принимать только нечётные значения (в исходном варианте k «проходит» по всем натуральным числам). Вычислим соответствующие суммы:

k	1	3	5	6	9
s	2	14	44	100	190

Правильная программа при вводе числа 1 выводит 1, при A  [2; 13] – результат 3, при A  [14; 43] – результат 5 и т.д. Сравнивая две таблицы, находим, что при A  [6; 13] ошибочная программа выводит правильный результат 3, поэтому

2) минимальные значения A, при которых программа выведет правильный результат (равный 3) – это 6 и 7 .

Найдём ошибки в программе. Во-первых, переменная k должна изменяться с шагом 2 (через одно значение). То есть, вместо k:=k+1 нужно использовать оператор k:=k+2. Кроме того, после первого увеличения в цикле значение переменной k должно стать равно 1, поэтому начальное значение k должно быть равно –1.

3) в программе нужно исправить две ошибки

1. 
   Неверное начальное значение переменной k:
   

Было: k := 1;

Исправление: k := -1;

2. 
   Неверное изменение переменной k:
   

Было: k:=k+1;

Исправление: k:=k+2;

84. 
    Способ рассуждений при решении этой задачи точно такой же, как и для предыдущей. Поэтому приведём только правильный ответ:
    

1) при вводе числа 15 программа выведет ответ 4.

2) минимальные значения A, большие, чем 10, при которых программа выведет правильный результат (равный 5) – это 20 и 21.

3) в программе нужно исправить три ошибки

1. 
   Неверное начальное значение переменной k:
   

Было: k := 0;

Исправление: k := 1;

2. 
   Неверное изменение переменной k:
   

Было: k:=k+1;

Исправление: k:=k+2;

3. 
   Неверный вывод результата:
   

Было: writeln(k);

Исправление: writeln(k-2);

85. 
    Классический алгоритм решения этой задачи – проверка всех возможных делителей от 1 до n. Если число j является делителем числа n, то существует и второй делитель, равный n/j. Следовательно, все делители идут в парах, за исключением, возможно, точного квадратного корня из n. Поэтому можно искать только меньшие делители в каждой паре, которые находятся в интервале от 1 до (не включая правую границу). Проверка условия равносильна проверке условия , что позволит решить задачу в целых числах, не используя неточную вещественную арифметику:
    

j := 1;

k := 0;

while j * j < n do begin

if n mod j = 0 then

k := k + 2;

j := j + 1

end;

Каждый раз, когда мы находим делитель, счётчик делителей k увеличивается на 2, так как мы нашли сразу пару. Сравнивая этот фрагмент с программой, приведенной в условии, видим одну ошибку – начальное значение переменной j должно быть равно 1, а не 2, как в программе.

Кроме того в конце нужно проверить, не является ли n квадратом целого числа (после окончания цикла оно может быть равно только j!), и если является, нужно добавить ещё один делитель:

if j * j = n then

k := k + 1;

Видим вторую ошибку: в программе k увеличивается на 3, а нужно – на 1. В результате первой ошибки (неверное начальное значение j) получается уменьшение k на 2, а в результате второй – увеличение на 2. Эти две ошибки скомпенсируют друг друга, если случатся одновременно, а это возможно только для чисел, которые являются полными квадратами, большими 1. Минимальные из этих чисел – это 4 и 9. При вводе числа 10 условие j*j=n не выполняется, и значение k будет на 2 меньше, чем нужно, то есть, 4 – 2 = 2 (число 10 имеет 4 делителя).

1) при вводе числа 10 программа выведет неверный ответ 2.

2) минимальные значения n, при которых программа выведет правильный результат (равный 3) – это 4 и 9.

3) в программе нужно исправить две ошибки

1. 
   Неверное начальное значение переменной j:
   

Было: j := 2;

Исправление: j := 1;

2. 
   Неверное изменение переменной k:
   

Было: k:=k+3;

Исправление: k:=k+1;

86. 
    Чтобы понять, как работает алгоритм, применим ручную прокрутку для числа 157. Здесь только одна цифра 1 меньше 5, поэтому мы должны получить ответ 1.
    

	N	d	m
readln(N);	157
m := N mod 10;			7
d := N mod 10;		7
N := N div 10;	15
d := N mod 10;		5
N := N div 10;	1
d := N mod 10;		1
N := N div 10;		0

1) При вводе числа 157 программа выведет значение 7.

Поиск «максимума не из всех» осложняется тем, что мы не можем в качестве начального значения для переменной m взять первую с конца цифру, так как она может быть больше 5 (именно это произошло в примере с числом 157). А в приведённой программе видим:

readln(N);

m := N mod 10;

Поэтому первую ошибку нашли. В теле цикла все вроде бы логично: берём последнюю цифру числа и, если она меньше 5, сравниваем с максимумом из предыдущих. После этого делим число на 10, отбрасывая последнюю цифру. Цикл продолжается до тех пор, пока все цифры не обработаны (и не отброшены) и значение N не стало равно 0.

Смотрим на вывод ответа:

if m = 0 then

writeln('NO')

else writeln( m )

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

Таким образом, программа выдаёт правильный ответ, если в числе есть цифры, которые меньше 5, и последняя цифра (которая становится начальным значением m) тоже меньше 5. Наибольшее такое трёхзначное число – 994.

2) Наибольшее трёхзначное число, для которого программа выдаёт правильный ответ – 994.

Итак, мы нашли две проблемы – с начальным значением m и с выводом (проверкой на отсутствие нужных букв). Вариант с начальным значением 0 не работает, например, для числа 909 (тут 0 - правильный ответ). Поэтому можно взять в качестве начального значения –1. Если значение m останется равным –1, то ни одного подходящего числа не нашли – этот факт служит сигналом для вывода «NO».

3) в программе нужно исправить две ошибки

1. 
   Неверное начальное значение переменной m:
   

Было: m := N mod 10;

Исправление: m := -1;

2. 
   Неверное условие при выводе:
   

Было: if m = 0 then

Исправление: if m = -1 then

87. 
    Решение этой задачи полностью аналогично решению предыдущей. Поэтому приведём только правильный ответ:
    

1) При вводе числа 170 программа выведет неверный ответ NO.

2) Наименьшее трёхзначное число, для которого программа выдаёт правильный ответ – 103.

3) в программе нужно исправить две ошибки

1. 
   Неверное начальное значение переменной m:
   

Было: m := 0;

Исправление: m := -1;

2. 
   Неверное условие при выводе:
   

Было: if m = 0 then

Исправление: if m = -1 then

1 Аналогичная ситуация возникает при решении уравнения методом деления отрезка пополам (кто помнит :-).

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

http://kpolyakov.spb.ru