TransWikia.com

Наихудший делитель

Stack Overflow на русском Asked by fox_price on January 30, 2021

Будем считать, что число а лучше числа b, если сумма цифр числа а больше суммы цифр числа b, а в случае равенства сумм, если число а меньше числа b.

Дано число n. Найдите такой его делитель d, что любой другой делитель с числа n лучше, чем d.

Пример:

Ввод: 10
Вывод: 10
Ввод: 239
Вывод: 1

Я понял, что здесь нужно считать нули. Вот мой код:

a=input()
b=0
for i in range(len(a)):
    if int(a[i])==0:
        b+=1
if int(a)<10:
    print(a)
elif b==0:
    print(1)
else:
    print(a)

Не проходит дальше 4-го теста..

3 Answers

Вот так можно:

def main(n):
    for i in range(len(str(n))):
        k = 10**i
        if not n % k:
            worst = k
    return worst

n = int(input())
print(main(n))

Answered by n1tr0xs on January 30, 2021

Примерный алгоритм

# функция определения суммы цифр числа
def sum_digits(a):
    res = 0

    while a != 0:
        res += a % 10
        a /= 10

    return res


# функция определения является ли число a лучше числа b
def is_best(a, b):
    sum_a = sum_digits(a)
    sum_b = sum_digits(b)

    if sum_a > sum_b:
        return True

    if sum_a == sum_b:
        return a < b

    return False


# основной функционал
n = int(input())

worst = 1

for value in range(2, n + 1):
    # рассматривать только делители числа n
    if n % value == 0:
        # найти худшее число
        if not is_best(value, worst):
            worst = value

print(worst)

Answered by Zhihar on January 30, 2021

вообще код какой-то кривоватый

ваш код умеет выводить только или 1 или само число, а в задаче вопрос про делители числа, т.е. ваш ответ никаких иных делителей принципиально не выводит

поэтому и тест валится - ведь в тесте 4 скорее всего результат - один из делителей (для 10 например 2 или 5)

Почему бы вам не переписать алгоритм так (в лоб):

  1. найти все делители числа n и записать их в список

  2. создать функцию проверки на "лучшесть" из 2 чисел

  3. сделать проход по всем делителям (т.е. будет выполнено n^2 проходов) и сравнить с остальными делителями

P.S.

предложенный алгоритм имел сложность O(n^2), но это я погорячился :)

лучше подойдет такой алгоритм:

  1. идем по числу m от 2 до n и определяем, что число является делителем n
  2. сравниваем делитель m с предыдущем делителем m_prev через функцию "лучшести" и если число лучше предыдущего, то записываем его в m_prev

в итоге сложность такой задачи будет O(n), что гораздо лучше

и никаких лишних списков заполнять не надо

ну и цикл от 2, потому что m_prev = 1

и кстати тогда проверку надо на то, что пользователь ввел 1 и тогда выдать сразу ответ - 1

Answered by Zhihar on January 30, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP