DjangoBB LoFi version

Полная версия: Нужна помощь в решении задачи

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

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).

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 заметно тормозит, потому что никакой оптимизации по скорости (исключение заведомо непригодных диапазонов, увеличение шага приращений и т.д.) я не делал.

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
Но это уже задача для математика, а не программиста.

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

old_monty

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

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