Методические рекомендации к решению задания №20 вариантов ЕГЭ по информатике и ИКТ

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

Библиотека материалов Дум Думыча

Муниципальное бюджетное общеобразовательное учреждение лицей № 4 имени профессора Евгения Александровича Котенко города Ейска муниципального образования Ейский район

Анализ программы содержащей подпрограммы, циклы и ветвления

Ейск

2018

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

Напомню широко известные признаки делимости в случае использования десятичной системы счисления.

а	Число Х делится на а, тогда и только тогда
2	Последняя цифра числа Х делится на 2 Пример:10842 делится на 2,так как последняя цифра чётная
3	Сумма цифр числа Х делится на 3 Пример:10824 делится на 3,так как его сумма цифр 1+0+8+2+4=15 делится на 3
4	Число, составленное из двух последних цифр числа Х, делится на 4 Пример: 48404 делится на 4, так как 2 последние цифры делятся на 4 Двузначное число делится на 4 тогда и только тогда, когда удвоенное число десятков, сложенное с числом единиц делится на 4 Пример:96 делится на 4, так как 9∙2+6=24и2∙2+4=8 делится на 4
5	Число Х заканчивается цифрой 5 Пример:1045 делится на 5, так как последняя цифра делится на 5
6	Число Х делится на 6 тогда и только тогда, когда оно делится и на 2, и на 3 (то есть если оно четное и сумма его цифр делится на 3). Пример: 78 делится на 6, так как оно чётно и 7+8=15 делится на 3 Число делится на 6 тогда и только тогда, когда учетверённое число десятков, сложенное с числом единиц делится на 6. Пример:3342 делится на 6,так как 334∙4+2=1338 и 133∙4+8=540 и5 4∙4=216 и 21∙4+6=90 и 9∙4=36 и 3∙4+6=18 и 1∙4+8=12 и 1∙4+2=6 делится на 6
7	Знакочередующаяся сумма трёхзначных граней числа, полученные при разбиении числа Х на трёхзначные числа, взятые справа налево, делится на 7 Пример: 138689257 делится на 7, так как 138-689+257=294, а 294 на 7 делится число делится на 7 тогда и только тогда, когда утроенное число десятков, сложенное с числом единиц делится на 7 Пример: 154 делится на 7, так как 15∙3+4=49 на 7 делится число делится на 7 тогда и только тогда, когда разность числа десятков и удвоенного числа единиц, взятая по модулю, делится на 7 Пример : 364 делится на 7, так как 36-4∙2=28 на 7 делится
8	Число делится на 8 тогда и только тогда, когда число, образованное тремя его последними цифрами, делится на 8 Пример:53328 делится на 8, так как 3 последние цифры делятся на 8 Трёхзначное число делится на 8 тогда и только тогда, когда число единиц, сложенное с удвоенным числом десятков и учетверённым числом сотен, делится на 8. Пример: 952 делится на 8 так как 9∙4+5∙2+2=48, а 48 на 8 делится.
9	Число Х делится на 9 тогда и только тогда, когда сумма его цифр делится на 9. Пример:7362 делится на 9, так как 7+3+6+2=18 делится на 9
10	Число Х делится на 10 тогда и только тогда, когда оно оканчивается на 0. Пример:100 делится на 10, так как последняя цифра 0
11	Число делится на 11 тогда и только тогда, когда знакочередующаяся сумма цифр делится на 11. Пример: 9163627 делится на 11, так 9-1+6-3+6-2+7=22, а 22 делится на 11. Число делится на 11 тогда и только тогда, когда на 11 делится сумма двузначных граней этого числа. Пример: 103785 делится на 11, так как 10+37+85=132 делится на 11
12	Число делится на 12 тогда и только тогда, когда оно делится на 4 и 3 одновременно, то есть сумма цифр делится на 3, а число, составленное из 2 последних цифр делится на 4. Пример:1356 делится на 12,так как 1+3+5+6=15 делится на 3и 2 последние цифры делятся на 4 Число делится на 12 тогда и только тогда, когда модуль разности числа единиц и удвоенного числа десятков делится на 12. Пример: 1236 делится на 12, так как 2∙123-6=240 делится на 12.
13	Число делится на 12 тогда и только тогда, когда оно делится на 4 и 3 одновременно, то есть сумма цифр делится на 3, а число, составленное из 2 последних цифр делится на 4. Пример:1356 делится на 12,так как 1+3+5+6=15 делится на 3и 2 последние цифры делятся на 4 Число делится на 12 тогда и только тогда, когда модуль разности числа единиц и удвоенного числа десятков делится на 12. Пример: 1236 делится на 12, так как 2∙123-6=240 делится на 12.
14	Число делится на 14 тогда и только тогда, когда оно делится на 4 и 7 одновременно, то есть число, составленное из 2 последних цифр делится на 4, а знакочередующаяся сумма трехзначных граней числа делится на 7. Пример: 284214 делится на 14,так как оно чётно и 284+-214=70 делится на 14
15	Число делится на 15, если оно делится на 3 и на 5(его сумма цифр делится на 3 и его последняя цифра либо 5,либо 0) Пример:675 делится на 15,так как 6+7+5=18 делится на 3 и его последняя цифра 5
16	Число делится на 16 если число, составляемое из его последних 4 чисел делится на 16 Пример:146432 делится на 16, так как последние 4 цифры делятся на 16
17	Число делится на 16 если число, составляемое из его последних 4 чисел делится на 16 Пример:146432 делится на 16, так как последние 4 цифры делятся на 16
18	Число делится на 18 тогда и только тогда, когда оно делится на 2 и 9 одновременно, то есть число четное и сумма его цифр делится на 9. Пример: 828 делится на 18, так как оно чётно и 8+2+8=18 делится на 9
19	Число делится на 19 тогда и только тогда, когда число десятков, сложенное с удвоенным числом единиц, делится на 19. Пример: 646 делится на 19, так как 64+2∙6=76,а 76на 19 делится. 1) отбрасываем последнюю цифру у числа 2) прибавляем к полученному числу произведение отброшенной цифры на 2; 3) с полученным числом проделываем операции 1) и 2) до тех пор, пока не останется число, меньшее или равное 19. 4) если остается 19, то исходное число делится на 19. Пример: 953819 делится на19,так как 95381+9∙2=95399 и 9539+9∙2=9557 и 955+7∙2=969 и 96+9∙2=114 и 11+4∙2=19=19
20	Число делится на 20 тогда и только тогда, когда число, образованное двумя последними цифрами, делится на 20. Пример:1380 делится на 20, так как 2 последние цифры делятся на 20
23	Число делится на 23 тогда и только тогда, когда число сотен, сложенное с утроенным числом, образованным двумя последними цифрами, делится на 23. Пример: 28842 делится на 23, так как 288+3∙42=414; 4+3∙14=46, а 46 на 23 делится Число делится на 23 тогда и только тогда, когда число десятков, сложенное с семикратным числом единиц, делится на 23. Пример: 391 делится на 23, так как 39+7∙1=46, а 46 делится на 23.
25	Число делится на 25 тогда и только тогда, когда число, образованное двумя последними цифрами, делится на 25. Пример:3874875 делится на 25,так как 2 последние цифры делятся на 25
27	Число делится на 27 тогда и только тогда, когда на 27 делится сумма трехзначных граней. Пример: 275481 делится на 27,так как 275+481=756 делится на 27
29	Число делится на 29 тогда и только тогда, когда число десятков, сложенное с утроенным числом единиц, делится на 29. Пример: 261 делится на 29, так как 26+3∙1=29 делится на 29
31	Число делится на 31 тогда и только тогда, когда модуль разности числа десятков и утроенного числа единиц делится на 31. Пример: 217 делится на 31, так как 21-3∙7=0 делится на 31
37	Число делится на 37 тогда и только тогда, когда на 37 делится сумма трехзначных граней. Пример:111111 делится на 17,так как 111+-111=0 делится на 37 Число делится на 37 тогда и только тогда, когда на 37 делится модуль утроенного числа сотен, сложенного с учетверённым числом десятков, за вычетом числа единиц, умноженного на семь. Пример: число 481 делится на 37, так как 3∙4+4∙8-7=37, а 37 на 37 делится.
41	Число делится на 41 тогда и только тогда, когда модуль разности числа десятков и четырёхкратного числа единиц делится на 41. Пример: 369 делится на 41, так как 36-4∙9=0 делится на 41
59	Число делится на 59 тогда и только тогда, когда число десятков, сложенное с числом единиц, умноженное на 6, делится на 59. Пример: 767 делится на 59, так как 76+6∙7=118; 11+6∙8=59 на 59 делится
99	Число делится на 99 тогда и только тогда, когда на 99 делится сумма двузначных граней . Пример: 12573 делится на 99, так как на 99 делится 12+57+30=99
101	Число делится на 101 тогда и только тогда, когда знакочередующаяся сумма двузначных граней делится на 101. Пример: 590547 делится на 101, так как на 101 делится 59-05+47=101

Число делится на 2ⁿ, если число составленное из его последних n цифр делится на 2ⁿ

Для делимости на число 9...9, состоящее из n девяток: надо разбить испытуемое число на n-разрядные блоки, начиная с младших разрядов, и всех их сложить (блок, образованный старшими разрядами, может быть короче); у полученного числа будет тот же остаток от деления, что и у исходного. Так как 99 делится на 11, то таким способом можно найти и остаток от деления на 11. Учитывая, что 999 делится на 111 и, следовательно, на 37, получаем признаки делимости на эти числа. Но есть более эффективный признак делимости на 11: надо складывать цифры числа, начиная с младших, чередуя знаки (первая цифра берётся со знаком плюс) — полученное число имеет тот же остаток от деления на 11, что и исходное.

Аналогичный признак делимости имеется и для числа 10...01, запись которого, кроме двух единиц, содержит n нулей. Испытуемое число разбивается на (n+1)-разрядные блоки, начиная с младших разрядов (блок, образованный старшими разрядами, может быть короче), и все они складываются с чередующимися знаками (первое число берётся со знаком плюс). Полученный результат имеет тот же остаток от деления, что и испытуемое число. Поскольку 1001=11·7·13, мы попутно получаем таким путём признаки делимости на 7, 13, 91, 77, 143.

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

Есть, однако, случаи, когда только применение признаков делимости позволяет найти остаток, так как непосредственное деление практически невозможно ввиду колоссальной вычислительной сложности.

Итак, вопрос о четности, то есть о делимости на 2, числа легко решается в десятичной системе - если последняя цифра четная, то четное и все число. Для всех систем счисления с чётным основанием, действует тот же признак чётности: число делится на 2, если его последняя цифра делится на 2. Для систем счисления с нечётным основанием существует другой признак чётности: число чётно тогда и только тогда, когда чётна сумма его цифр.

Рассмотрим на конкретном примере:

Укажите наибольшее трёхзначное натуральное число, при вводе которого эта программа напечатает сначала 2, потом – 6.

var x, a, b: longint;

begin

readln(x);

a := 0; b := 1;

while x > 0 do begin

if x mod 2 > 0 then

a := a + 1

else

b := b + (x mod 5);

x := x div 5;

end;

writeln(a); write(b);

end.

Решение:

1) в конце программы на экран выводятся переменные «a» и «b», следовательно, в переменной «а» в конце программы будет лежать значение 2, а в переменной «b» в конце программы будет лежать значение 6.

2) переменная «a» в начале равна нулю, затем при выполнении условия x mod 2 > 0 увеличивается на 1, то есть «a» – счётчик нечетных десятичных чисел.

3) переменная «b» в начале равна 1, затем при нарушении условия x mod 2 > 0, т.е. при четных десятичных числах к ней добавляется x mod 5 – последняя цифра записи числа x в системе счисления с основанием 5.

4) в цикле

while x > 0 do begin

...

x := x div 5;

end;

значение переменной x делится на 5, пока число не станет равно 0; это значит, что от его пятеричной записи по очереди отсекаются цифры, начиная с последней.

5) изменение переменных «a» и «b» выполняется в условном операторе

if x mod 2 > 0 then

a := a + 1

else

b := b + (x mod 5);

то есть после очередного отсечения получилось нечётное десятичное число, увеличивается счётчик «a», а если получилось чётное десятичное число – к значению переменной «b» суммируется последняя цифра пятеричной записи числа.

6) поскольку фактически идёт работа с пятеричной системой счисления, будем искать цифры нужного числа x в пятеричной системе, а потом переведём его в десятичную систему

7) значение «a» – это количество нечётных десятичных чисел, полученных в процессе отсечения, а «b» = 1 + сумма последних цифр пятеричной записи, полученных в процессе отсечения

8) поскольку основание системы нечётное, чётность числа зависит от суммы цифр: если сумма цифр в пятеричной записи чётная, то десятичное число чётное, а если в пятеричной записи числа сумма цифр нечётна, то десятичное число нечётно.

9) цифры пятеричной системы: 0,1,2,3,4

10) нам нужно расставить цифры в пятеричной записи числа так, чтобы из получаемых в процессе отсечении чисел два раза сумма цифр была нечётной, и, когда сумма цифр четна – последняя цифра суммируется со значением переменной «b», при этом сумма цифр должна дать (6-1)=5

11) наибольшая цифра в пятеричной системе «4», однако необходимо проверить, может ли число начинаться с «4» и сколько разрядов может иметь число в записи пятеричной системы, чтобы получить наибольшее трехзначное десятичное число.

12) наибольшее трехзначное десятичное число 999 в пятеричной записи имеет вид пятиразрядного числа 12444

13) таким образом, число может иметь пять разрядов и начинаться с цифры «1», при этом цифра нечетна, в переменной «а» получаем а=0+1

14) в следующем разряде может стоять «2», в сумме получим нечетное число «1+2», значит значение переменной «а» изменится и станет равным а=1+1=2

15) третья цифра должна быть нечётной, максимальной, чтобы в сумме получить четное число, возможное значение – 3, значение переменной «b» изменится и станет равным b=1+3=4

16) четвёртая цифра должна быть чётной, максимальной, чтобы в сумме получить число 6, прибавив к 4, возможное значение – 2

17) пятая цифра может быть только чётной, чтобы не изменить значение переменной «а», и сумма в переменной b не должна измениться, возможное значение – 0.

18) таким образом, запись пятеричного числа получилась 12320, что в десятичном представлении равно 960.

19) ответ: 960

Материалы подготовил(а): Воронова Ирина Николаевна

Скачать

Мне нравится | 2

Чтобы добавить отзыв, войдите, пожалуйста, или зарегистрируйтесь на сайте – легко и быстро.