Python

Программа в Pyton

Рассматривается множество целых чисел, принадлежащих числовому отрезку [8800; 55535], которые удовлетворяют следующим условиям:

а) произведение разрядов больше 35;

б) хотя бы один из разрядов равен 7.

В ответе запишите два целых числа: наибольшее из таких чисел и их количество (через пробел).

Можете объяснить как это сделать? Я недопонимаю как записать произведение разрядов.Знаю, написано по-тупому, но это то как я понимаю задачу. Результат он выдает не тот, сравнивая с тем, что я нашла в интернете. Найденую программу я не понимаю, если вы можете объяснить, буду благодарна.

Анатолий Легков
Анатолий Легков
134
Без перебора всех атомов во Вселенной.
 from math import prod



def digiter(n):

    while n != 0: yield n % 10; n //= 10



n = 8817

last = 55527

step = [10] * 5 + [4] + [1] * 8 + [8] + [10] + [20]  # кольцо внутри сотни

cnt = 0

i = 0

while n  35)

            n += 100

            dl = list(digiter(n))

    else:

        dp = prod(dl)

        if dp > 35: cnt += 1

        n += step[i % len(step)]

        i += 1

print(last, cnt)
Внутри каждой сотни выбираем не все числа подряд, а только те, которые содержат 7 и не содержат 0 в младших разрядах (произведения с нулём уж точно не превышают 35). Для этого строим кольцо из шагов: 17 + 10 = 27, 27 + 10 = 37, 67 + 4 = 71, 79 + 8 = 87, и т.д. В каждую сотню мы попадаем, начиная с 17, и последнее число в сотне - 97, всего их - 17 шт.
Если в старшем разряде ноль (например, 11017), то нет смысла бежать по всей сотне или тысяче: пропускаем сразу 100 или 1100 элементов.
Рано или поздно обход попадёт внутрь диапазона чисел, содержащих семёрку в третьем или четвёртом разрядах, например, 11717. Эти случаи отлавливаем и запускаем полный перебор внутри сотни, т.е. от 11711 до 11799. То же делаем в последующих сотнях, пока остаётся семёрка в старшем разряде.
На выходе:
 55527 10958


Реализовано в виде конечного автомата с четырьмя ветвями обработки.

Количество итераций в этом алгоритме - не 55536 - 8800 = 46736, а около 11789 (включая однострочный for в ветке полного перебора), что лишь на 7.6% превосходит общее количество найденных чисел. Эти 7.6% - числа с малым произведением цифр (например, 11711) и нулевыми цифрами в полном переборе (например, 11720).
Можно сделать алгоритм и побыстрее, однократно вычисляя количество чисел в каждой сотне с нужным произведением цифр, но он при этом заметно усложнится.
As As
As As
87 571
Лучший ответ
As As P.S. Внутренний цикл while можно убрать, это даже сэкономит немного разбиений на цифры, которые являются здесь самой трудоёмкой операцией:
 #

    elif dl[2] == 7 or dl[3] == 7: 

        # для чисел, x7xxx, xx7xx - полный перебор внутри сотни от 11 до 99

        cnt += sum(1 for m in range(n - 6, n + 100 - 17) if prod(digiter(m)) > 35)

        n += 100 
 def product_of_digits(n): 

    product = 1 

    while n > 0: 

        product *= n % 10 

        n //= 10 

    return product 

 

count = 0 

max_num = 0 

for i in range(8800, 55536): 

    if product_of_digits(i) > 35 and '7' in str(i): 

        count += 1 

        max_num = i 

 

print(max_num, count)

Функция принимает целое число n в качестве аргумента и инициализирует переменную product равным 1. Эта переменная будет использоваться для отслеживания текущего произведения цифр числа n.

Затем функция переходит в цикл while, который продолжается до тех пор, пока n не станет больше 0. Внутри цикла последняя цифру получаем как остаток от деления (%) на 10. Эта цифра затем умножаются на текущее произведение. Оператор целочисленного деления (//) используется для удаления последней цифры из n путем деления ее на 10.
Таня Ищенко
Таня Ищенко
17 671

Похожие вопросы