Форум » Циклы и ветвления » егэ 21 № 87 » Ответить
егэ 21 № 87
GAF: Здравствуйте,у меня f(20,4) получается f(16,4)=(12,4)=(8,4)=(4,4)=4, тогда k=0 Значит мне нужно посчитать на промежутке от 1 до 100 количество чисел , в которых при вычитании 4 не дадут 2? 87) (Д. Муфаззалов, Белград). Напишите в ответе количество различных значений входной переменной a из интервала от 1 до 100 (включая границы), при которых программа выдаёт тот же ответ, что и при входном значении a = 20. Значение a = 20 также включается в подсчёт различных значений a. var i, k, a: integer; function f(x: integer; y: integer): integer; begin if x = y then f := x else if x > y then f := f(x - y, y) else f := f(x, y - x); end; begin k := 0; readln(a); for i := 1 to a do if f(i, 4) = 2 then k := k + 1; writeln(k); end.
Ответов - 1
polyakovss: Здравствуйте, GAF! function f(x: integer; y: integer): integer; begin if x = y then f := x else if x > y then f := f(x - y, y) else f := f(x, y - x); end; 1) Функция f(x,y) по алгоритму Евклида вычисляет наибольший общий делитель (НОД) чисел x и у, то есть f(x,y) = НОД(x,y). 2) f(i,4) = 2 --> НОД(i,4) = 2 3) Поскольку НОД(x,y) равен произведению одинаковых простых множителей x и y, то из НОД(i,4) = 2 следует, что в число простых множителей i может входить только одна 2, а произведение других простых множителей i даст числа 1, 3, 5, 7, 9, 11, 13, 15, ... Соответственно, i будет равно 2, 6, 10, 14, 18, 22, 26, 30, ... 4) В цикле for i := 1 to a do if f(i, 4) = 2 then k := k + 1; при a=20 условие выполнится для чисел 2, 6, 10, 14, 18 и k станет равно 5 (k = 5). 5) Такой же результат будет получен при a = 18, 19, 20, 21 (k = 5, i = 2, 6, 10, 14, 18). (При a > 21 будет k > 5). Ответ: 4 (четыре числа a = 18, 19, 20, 21).
полная версия страницы