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

Isem
Тогда со сложностью O(N), а именно N:

if 6*sum( i*i for i in lst ) == N*(N+1)*(2*N+1):
    print( "Да, это так" )

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

Отредактировано (Фев. 7, 2011 13:01:51)

Да, забыл поставить простое условие на длину списка. Ну то есть len(lst) == N. Странно, что ни кто не обратил внимания на это.

doza_and
9^2 + (9 - 1)^2 == 12^2 + 1 True
10^3 + (10 - 1)^3 == 12^3 + 1 True

поэтому предлагаемый вами алгоритм некорректен.

Isem
а, забыл поставить простое условие на длину списка. Ну то есть len(lst) == N. Странно, что ни кто не обратил внимания на это.

doza_and
10^3 + (10 - 1)^3 == 12^3 + 1 True

Isem
Да, забыл поставить простое условие на длину списка. Ну то есть len(lst) == N. Странно, что ни кто не обратил внимания на это.

lst = (2, 1, 2, 3, 3, 3, 7)
len(lst) = 7
>>sum(i**3 for i in range(1,7))==sum(i**3 for i in (2, 1, 2, 3, 3, 3, 7))
True

Isem

>>> list(range(1,7))
[1, 2, 3, 4, 5, 6]

Может быть я не умею считать до семи?

def s(x):
	return sum(c**3 for c in x)

>>> s((5, 5, 1, 4, 5, 1))
441
>>> s((1,2,3,4,5,6))
441
>>>

По поводу N я подумал что перед этим у вас будет N=len(lst) зачем дополнительно N передавать.
Извините наверное недостаточно подробно написал.
Пусть длина списка больше или равна 9
и одна последовательность есть
она удовлетворяет условиям задачи и ваш алгоритм дает True
получим из нее другую последовательность заменой пары рядом стоящих цифр.
она не удовлетворяет условиям задачи но ваш алгоритм дает True
поскольку 9^2 + (8)^2 == 12^2 + 1
Таким образом, существуют корректные входные данные для которых алгоритм дает некорректный результат.

Ну в алгоритме не квадрат, а куб, и я указал, что куб - это не последнее число (там многоточие поставлено).

coni-lole
Но тогда вы не ответили не предыдущий ответ
Код:

def s(x):
return sum(c**3 for c in x)

>>> s((5, 5, 1, 4, 5, 1))
441
>>> s((1,2,3,4,5,6))
441
>>>