python: эффективность в задаче со степенными рядами - PullRequest
Новая
       13

python: эффективность в задаче со степенными рядами

0 голосов
/ 18 октября 2018

Определение проблемы:

Это проблема из кодовых войн .

Определение самообращенной последовательности мощности ,S, as: 

S(0) = 0
S(1) = 1
S(2) = 1^2 + 2 = 3
S(3) = 1^3 + 2^2 + 3 = 8
...
S(n) = 1^n + 2^(n-1) + ... + (n-1)^2 + n

Реализация функции, которая принимает 2 аргумента (num_dig и ord_max) и находит наименьшее число последовательности, меньшее чем num dig, которое также имеет ord_max количество цифр.

Если есть число с правильным количеством цифр, результатом должен быть массив в виде: 

[True, smallest found term] 

[False, -1]

Вот несколько примеров: 

n-th Term    Term Value
1              0
2              1
3              3
4              8
5              22
6              65
7              209
8              732
9              2780
10             11377
11             49863
12             232768
13             1151914
14             6018785

Таким образом, тестовые примеры включают: 

min_length_num(5, 10) == [True, 10]   # 10th term has 5 digits
min_length_num(7, 11) == [False, -1]  # no terms before 13th has 7 digits
min_length_num(7, 14) == [True, 13]   # 13th term already has 7 digits

Мой подход :

Я создаю генератор, который выдает все значения степенного ряда S вплоть до значения n: 

def seq(n):
    for i in range(n):
        s = range(i+1)
        j = i+1
        tot = 0
        while j > 0:
            for k in s:
                tot += k**j
                j -=1
            break
        yield tot

Затем я проверяю значения генераторов и: либо возвращаю True, как только я сталкиваюсь с первым значением с требуемым количеством цифр, либо возвращаю False в противном случае: 

def min_length_num(num_dig, ord_max): 
    i = 1
    for n in seq(ord_max):
        if len(str(n)) == num_dig:
            return [True, i]
        elif len(str(n)) > num_dig:
            break
        i +=1
    return [False, -1]

Это проходит всетестирует, но не завершает тестовый процесс, поскольку время ожидания истекло.Диапазон ввода принимает значение ord_max <= 1000. </p>

Я не очень разбираюсь в генераторах, поэтому, возможно, я делаю что-то не так или делаю это неправильно.Буду признателен за помощь.Спасибо.

РЕДАКТИРОВАТЬ: другое решение.

Поскольку я знаю ord_max <= 1000, я мог бы просто предварительно вычислить все значения и изменить код следующим образом:</p> 

p = [n for n in seq(1000)]

def min_length_num(num_dig, ord_max): 
    i = 1
    for k in p[:ord_max]:
        if len(str(k)) == num_dig:
            return [True, i]
        elif len(str(k)) > num_dig:
            break
        i +=1
    return [False, -1]

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

Ответы [ 2 ]

0 голосов
/ 18 октября 2018

Аналогично предложению @ Mbo, но вместо обновления последовательностей с различиями между старой и новой степенью, вы можете просто умножить существующую последовательность на соответствующие приращения и добавить новый номер термина (минус один, поскольку значение первого члена равно0) в последовательности: 

def min_length_num(dig, max_term):
    seq = []
    target = pow(10, dig - 1)
    term = 1
    while term <= max_term:
        for i in range(term - 1):
            seq[i] *= i
        seq.append(term - 1)
        if sum(seq) >= target:
            return [True, term]
        term += 1
    return [False, -1]

, так что: 

print(min_length_num(5, 10))
print(min_length_num(7, 11))
print(min_length_num(7, 14))

будет выводить: 

[True, 10]
[False, -1]
[True, 13]
0 голосов
/ 18 октября 2018

Не полное решение, но некоторые советы по оптимизации:

Вам не нужно снова и снова вычислять все степени натуральных чисел - я подозреваю, что возведение в степень - это довольно длительная операция.Вместо этого сохраняйте список текущих мощностей и умножайте power[k] на k на каждом шаге 

 1  4  3       //3rd stage
 1  8  9  4    //4th stage

и обновляйте значение суммы с разницей между старой и новой силой 

 S(4) = S(3) + (8-4) + (9-3) + 4 = 22

Также предварительно рассчитайте цельзначение с необходимым количеством цифр 

  powten = 10**(num_dig-1)  //1 000 000 for num_dig=7

и сравнение сумм с powten без преобразования в строку

...