Python-сообщество

Orange___XD · Окт. 25, 2015 08:48:05

Всем доброго времени суток!
Сама задача:
Для числа m найти наименьшее положительное целое число с суммой цифр m, которое делится на m

Задачу решить почти получилось, для 10 работает, а вот для больших чисел работает слишком долго, и я не уверен, работает ли вообще.
Хотелось бы узнать, можно ли как-то ускорить процесс?

def num():
    file = open('input.txt', 'r')
    str_list = []
    nums_list = []
    for line in file:
        str_list.append(line)
    for nums in str_list:
        num = int(nums)
        if num >= 9:
            n = num // 9
            str_m_num = "9" * n
            m_num = int(str_m_num)
            m_num_sum = 0
            list = ['n']
            def sum(m_num, n):
                m_num_sum = 0
                for n in str(m_num):
                    m_num_sum += int(n)
                return m_num_sum
            m = sum(m_num, n)
            for i in list:
                if m_num % int(num) == 0:
                    m_num += num
                    m = sum(m_num, n)
                    if m == int(num):
                        break
                else:
                    m_num += 1
                sum(m_num, n)
                list.append(n)
                a1 = m_num % int(num)
                a2 = m
            nums_list.append(m_num)
    file_2 = open('output.txt', 'w')
    for element in nums_list:
        file_2.write(str(element) + "\n")
num()

py.user.next · Окт. 25, 2015 09:51:59

Orange___XD
Для числа m найти наименьшее положительное целое число с суммой цифр m, которое делится на m

Надо перебирать числа, делящиеся на m, и проверять сумму их цифр.
Нижняя граница может быть поднята (если там число 100, то трёхзначные числа можно не проверять, так как максимальная сумма цифр равна 27).

Отредактировано py.user.next (Окт. 25, 2015 09:59:37)

Orange___XD · Окт. 25, 2015 15:32:10

py.user.next
Надо перебирать числа, делящиеся на m, и проверять сумму их цифр.

def num(num):
    if num >= 9:
        n = num // 9
        str_m_num = "9" * n
        m_num = int(str_m_num)
        m_num_sum = 0
        list = ['n']
        result = []
        l = n + 2
        str_2_m_num = int("9" * l)
        def sum(m_num):
            m_num_sum = 0
            n = 0
            for n in str(m_num):
                m_num_sum += int(n)
            return m_num_sum
        res = [x for x in range(m_num, str_2_m_num, 1) if x % num == 0]
        for element in res:
            m = sum(element)
            if m == num:
                result.append(element)
                break
        print(result)
num()

Немного переписал, но все равно числа больше 50 уже вычисляются очень медленно (терпения не хватило замерить, сколько)
Возможно как-либо еще больше ускорить?

py.user.next · Окт. 25, 2015 16:49:31

Orange___XD
но все равно числа больше 50 уже вычисляются очень медленно

Я для 50 сделал, а 100 уже тормозит. Значит, не подходит такой способ. Нужен какой-то другой алгоритм.

old_monty · Окт. 25, 2015 16:55:03

Предлагаю свой вариант:

def dsum(m):
    remainder = 0
    quotient = m
    dsum = 0
    while quotient >= 10:
        remainder = quotient % 10
        quotient = quotient // 10
        dsum += remainder
    dsum +=quotient
    return dsum
 
while True:
    m = int(input("Введите число m (или 0 для выхода): "))
    if m == 0:
        break
    i = m
    while not (m == dsum(i) and i % m == 0):
        i += 1
    print("Найденное число: %d; его сумма цифр: %d" % (i, dsum(i))

Примечание: тоже при m > 52 заметно тормозит, потому что никакой оптимизации по скорости (исключение заведомо непригодных диапазонов, увеличение шага приращений и т.д.) я не делал.

Отредактировано old_monty (Окт. 25, 2015 17:08:04)

py.user.next · Окт. 25, 2015 17:47:59

old_monty

def dsum(m):
    remainder = 0
    quotient = m
    dsum = 0
    while quotient >= 10:
        remainder = quotient % 10
        quotient = quotient // 10
        dsum += remainder
    dsum +=quotient
    return dsum

Так

def s(n):
    return sum(map(int, str(n)))

Или так

def s(n):
    r = 0
    while n > 0:
        r += n % 10
        n //= 10
    return r

old_monty
исключение заведомо непригодных диапазонов, увеличение шага приращений

Там, походу, нужно какое-то свойство чисел использовать.

old_monty · Окт. 25, 2015 19:13:31

py.user.next

def s(n):
    return sum(map(int, str(n)))

Я тоже пробовал играться со строковым представлением чисел. Это работает без ошибок (хотя конечно, у меня - новичка в Python - реализация была сделана не так красиво):

>>> m = 12345
>>> s = sum([int(i) for i in list(str(m))])
>>> s
15

Но я отказался от этой идеи. Выигрыша в скорости не заметно. И вообще, фокусы со строками вместо чисел похожи на какое-то жульничество.

py.user.next
Там, походу, нужно какое-то свойство чисел использовать.

Полностью согласен. Но это уже задача для математика, а не программиста.

py.user.next · Окт. 26, 2015 00:17:28

old_monty

s = sum([int(i) for i in list(str(m))])

Удаляем квадратные скобки

s = sum(int(i) for i in list(str(m)))

без квадратных скобок получится генератор (генераторное выражение). Разница есть: для списка занимается память под все элементы, тогда как для генератора - только под текущий.

Удаляем создание списка

s = sum(int(i) for i in str(m))

строка сама по себе является итерабельной (перебираемой).

old_monty
И вообще, фокусы со строками вместо чисел похожи на какое-то жульничество.

Она хуже только в том плане, что строки медленнее чисел (из-за способа хранения в памяти).

>>> import sys
>>> 
>>> sys.getsizeof(123456789)
16
>>> sys.getsizeof('123456789')
34
>>>

old_monty
Но это уже задача для математика, а не программиста.

Решить можно, конечно, но смысла особого нет. Это олимпиадная задача; они тем и отличаются, что заставляют мозг синтезировать новые варианты, а в практическом плане нигде не используются.

Отредактировано py.user.next (Окт. 26, 2015 00:27:38)

old_monty · Окт. 26, 2015 08:31:14

py.user.next
Большое спасибо! Это важные сведения, я об этом не знал. Ошибочно думал, что это просто более компактная форма записи, “синтаксический сахар”.

Python-сообщество

Уведомления

#1 Окт. 25, 2015 08:48:05

Нужна помощь в решении задачи

#2 Окт. 25, 2015 09:51:59

Нужна помощь в решении задачи

#3 Окт. 25, 2015 15:32:10

Нужна помощь в решении задачи

#4 Окт. 25, 2015 16:49:31

Нужна помощь в решении задачи

#5 Окт. 25, 2015 16:55:03

Нужна помощь в решении задачи

#6 Окт. 25, 2015 17:47:59

Нужна помощь в решении задачи

#7 Окт. 25, 2015 19:13:31

Нужна помощь в решении задачи

#8 Окт. 26, 2015 00:17:28

Нужна помощь в решении задачи

#9 Окт. 26, 2015 08:31:14

Нужна помощь в решении задачи

Board footer