Числа вида 2m•3n
Числа вида 2m•3n
Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне.
Рассмотрим следующую задачу для подготовки к ЕГЭ с сайта Полякова (задача 25 из варианта 19):
(№ 3977) Найдите все натуральные числа, N, принадлежащие отрезку [150 000 000; 300 000 000], которые можно представить в виде N = 2m•3n, где m – чётное число, n – нечётное число. В ответе запишите все найденные числа в порядке возрастания, а справа от каждого числа – сумму m+n.
Первая мысль - делить наше число сперва на два до тех пор, пока оно делится, а потом на три. При делении считать, сколько делений было выполнено (т.е. определить степени m и n). Если после таких делений получается 1, то число k не содержит других простых делителей, кроме 2 и 3. Если число m четное, а число n - нечетное, то напечатать число и сумму m+n.
Программа выглядит так:
for i in range(150000000, 300000000+1):
k=i
m=0
while k%2 == 0:
k //= 2
m += 1
n=0
while k%3 == 0:
k //= 3
n += 1
if k == 1 and m%2 == 0 and n%2 == 1: print(i,m+n)
Присвоение k=i требуется потому, что при поиске степеней m и n значение переменной k изменяется. Если бы мы использовали для вычислений непосредственно переменную цикла i, мы испортили бы её значение и тем самым нарушили работу цикла.
Результат работы программы следующий:
181398528 21
201326592 27
229582512 19
254803968 25
Программа работает, выдает правильный ответ, но работает медленно: выполнение занимает около двух минут.
Куда лучшая идея - перебирать числа вида 2**m * 3**n.
Предварительно выясняем, что 2**29=536870912, а 3**18=387420489. Поэтому для чисел вида 2**m*3**n, не превышающих 300000000, m<29, а n<18.
В этом случае программа выглядит так:
for m in range(0,29,2):
for n in range(1,18,2):
k = 2**m * 3**n
if k >= 150000000 and k <= 300000000: print(k,m+n)
Циклы с шагом 2 обеспечивают четность числа m и нечетность числа n, как требуется в условии.
Программа выполняется менее миллисекунды. Результат следующий:
229582512 19
181398528 21
254803968 25
201326592 27
Числа правильные, но следуют не в порядке возрастания, как требуется в условии. Но чисел всего 4, поэтому расположить их в порядке возрастания несложно и вручную. Но можно и запомнить их в массивах, а потом отсортировать массивы. (Если бы чисел было больше, то сделать это было бы очень желательно - сортировать несколько десятков чисел вручную тяжеловато.)
Приведем вариант программы с сортировкой массивов:
a=[]
mpn=[]
for m in range(0,29,2):
for n in range(1,18,2):
k = 2**m * 3**n
if k >= 150000000 and k <= 300000000:
a.append(k)
mpn.append(m+n)
for i in range(len(a)-1):
for j in range(i+1,len(a)):
if a[i]>a[j]:
a[i],a[j] = a[j],a[i]
mpn[i],mpn[j] = mpn[j],mpn[i]
for i in range(len(a)): print(a[i],mpn[i])
Программа выдает результат, упорядоченный по возрастанию чисел. Время работы по-прежнему составляет доли миллисекунды.
Программу можно сократить, если воспользоваться встроенной в язык операцией sort. Для этого нужно хранить число и сумму m+n вместе: как два элемента одного массива. Тогда элементы массива a будут тикими массивами, содержащими пары чисел.
Для сортировки такого массива придется написать очень простую функцию, которая возвращает первый элемент массива x (т.е. x[0]). Имя этой функции иы указываем как ключ сортировки. В результате наши подмассивы, содержащиеся в массиве a, будут упорядочены по возрастанию их первых элементов.
Вот код, использующий такой подход:
def f(x):
return x[0]
a=[]
for m in range(0,29,2):
for n in range(1,18,2):
k = 2**m * 3**n
if k >= 150000000 and k <= 300000000:
a.append([k,m+n])
a.sort(key=f)
for i in range(len(a)): print(a[i][0],a[i][1])
(c) Ю.Д.Красильников, 2021 г.
Комментарии
Отправить комментарий