Задача Euler Project № 12 Код Python дает странные результаты

Я пытался решить проблему номер 12 проекта Euler. Это проблема:

Последовательность чисел треугольника генерируется путем сложения натуральных чисел. Таким образом, 7-е число треугольника будет 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Первые десять членов будут такими:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Перечислим множители первых семи треугольных чисел:

  • 1: 1
  • 3: 1,3
  • 6: 1,2,3,6
  • 10: 1,2,5,10
  • 15: 1,3,5,15
  • 21: 1,3,7,21
  • 28: 1,2,4,7,14,28

Мы видим, что 28 — первое треугольное число, имеющее более пяти делителей.

Каково значение первого треугольного числа, имеющего более пятисот делителей?

Я определил две функции для выполнения этой работы:

1) allfactor(x): Это дает нам все факторы данного числа в форме списка. Пример: allfactor(10) дает нам [1, 2, 5, 10]

2)TriangularNo(x): это дает нам n-е треугольное число. Пример TriangularNo(5) дает нам 5

Вот полный код, который я написал:

facs=[]

def allfacof(x):
    for i in range(1,int(x/2)+1):
        if x%i==0:
            facs.append(i)
        else:
            pass
    facs.append(x)
    return(facs)



def TriangularNo(x):
    no=0
    for i in range(1,x+1):
        no=no+i
    return(no)

a=0 # a will tell us the number of iterations

while True:
    a+=1
    N=TriangularNo(a)
    length=(len(allfacof(N)))
    if int(length)>=500:
        print(N)
        break
    else:
        pass

Когда я запускаю этот код, я получаю 1378 в качестве вывода, что явно неверно, потому что len(allfacof(1378)) оказывается 8, а не 500, как требовалось в вопросе.

Обратите внимание, что в цикле while я использую if int(length)>=500:. Это означает, что когда мой код запускается, length каким-то образом получает значение = 500, но когда я запускаю функцию отдельно, она говорит, что ее длина равна 8.

Я просто не могу найти ошибку. Помогите пожалуйста мне


python number-theory
person Aaryan Dewan    schedule 09.03.2019    source источник
comment
Обратите внимание, что TriangularNo(n) — это просто n*(n+1)/2, что позволяет избежать ненужного зацикливания.   -  person Voo    schedule 09.03.2019
comment
@Ву Смарт! Спасибо   -  person Aaryan Dewan    schedule 09.03.2019

Ответы (2)


arrow_upward
2
arrow_downward

Проблема в том, что вы используете facs в качестве глобальной переменной и только добавляете к элементу. Вы должны сделать его членом allfacof(), чтобы он очищался после каждого значения. Если вы посмотрите на facs, вы обнаружите, что оно равно

1, 1, 3, 1, 2, 3, 6, 1, 2, 5, 10 ...

person Adam    schedule 09.03.2019

arrow_upward
1
arrow_downward

Хотя перемещение facs в all_factors_of() решает вашу непосредственную проблему, следующей проблемой этого кода является производительность. Давайте сначала рассмотрим генерацию треугольных чисел. Оптимизация, которую предлагает @Voo:

def TriangularNo(n):
    return n * (n + 1) / 2

подходит, если мы ищем произвольные треугольные числа, но это не так. Мы ищем последовательные треугольные числа, поэтому в данном случае формула замедляет наш код! При последовательном выполнении вам нужно сделать всего пару сложений, чтобы получить следующий номер треугольника, но, используя формулу, вам нужно выполнить сложение, умножение и деление! Дороже, если едешь последовательно. Поскольку мы идем последовательно, это кажется идеальным использованием генератора Python:

def triangular_number_generator():
    triangle = number = 1

    while True:
        yield triangle
        number += 1
        triangle += number

Отсюда становится ясно, что для получения следующего числа треугольника необходимы два сложения. Теперь давайте рассмотрим вашу функцию факторизации:

Ваша функция факторизации теряет производительность из-за того, что производит факторы по порядку. Но нас интересует только количество факторов, порядок не имеет значения. Поэтому, когда мы делим 28, мы можем добавить 1 и 28 в список факторов одновременно. То же самое с 2 и 14 — делаем 14 нашим новым верхним пределом. Аналогично 4 и 7, где 7 становится новым верхним пределом. Так мы быстрее собираем факторы и быстрее снижаем верхний предел, который нам нужно проверить. Вот остальная часть кода:

def factors_of(number):
    divisor = 1
    limit = number
    factors = []

    while divisor <= limit:

        if number % divisor == 0:
            factors.append(divisor)

            remainder = number // divisor

            if remainder != divisor:
                factors.append(remainder)

            limit = remainder - 1

        divisor += 1

    return factors

triangular = triangular_number_generator()
number = next(triangular)
factors = factors_of(number)

while len(factors) <= 200:
    number = next(triangular)
    factors = factors_of(number)

print(number)

Как это сравнить? Если мы запустим ваш фиксированный код с нижним пределом > 200 факторов, потребуется около минуты, чтобы получить ответ (2031120). Приведенный выше код занимает около 1/3 секунды. Теперь подумайте, сколько времени потребуется обоим, чтобы достичь > 500 факторов. Наконец, для достижения заявленной цели:

Каково значение первого треугольного числа, имеющего более пятисот делителей?

это сравнение в исходном коде:

if int(length)>=500:

вместо этого должно быть:

if length > 500:

Хотя то, как прыгает количество факторов, для 500 не имеет значения. Но для меньших лимитов, для тестирования, может иметь значение.

person cdlane    schedule 21.04.2020