Ctrl →

lyapun · Фев. 4, 2011 08:04:08

Здраствуйте!

Помогите придумать как лучше сделать такую задачку:

Есть список из чисел от 1 до N. Числа расположены в случайном порядке. Необходимо, проверить что в списке есть все числа от 1 до N при этом каждое число встречается только один раз.

Спасибо

Isem · Фев. 4, 2011 08:55:15

if len(lst) == N == len( set(lst) ):
    print( "Да" )

Здесь lst - список, содержащий числа от 1 до N

.Serj. · Фев. 4, 2011 08:58:03

def f(num,lst): return reduce(lambda x,y:x+y,map(lambda x: num==x,lst))

def g(numlst,lst):                                                     
    for num in numlst:
        if f(num,lst) != 1:
            return False
    return True

In [44]: l
Out[44]: [1, 3, 9, 0, 5, 1, 8, 3, 4, 10, 100500, 100500]

In [45]: set(l)
Out[45]: set([0, 1, 3, 4, 5, 8, 9, 10, 100500])

In [46]: g([1,2,3],l)
Out[46]: False

In [47]: g([1,2,3],set(l))
Out[47]: False

In [48]: g([0,1,3],l)
Out[48]: False

In [49]: g([0,1,3],set(l))
Out[49]: True

Zubchick · Фев. 4, 2011 10:59:15

Довольно порочный метод, со сложностью аж N^3
Тут не надо умничать, надо пройтись старым добрым циклом, увеличивая значение переменной счетчика внутри цикла… вот и все. И будет квадратичная сложность :)

lyapun · Фев. 4, 2011 16:27:08

Спасибо всем!
Заюзал вариант Isem'a

doza_and · Фев. 4, 2011 20:42:07

Вообще задача вроде линейной сложности.

a=numpy.zeros(N)
a[arr]=1
if min(a)==0:
     print "не хватает"

arr это ваш массив с данными

Отредактировано (Фев. 4, 2011 20:42:55)

Zubchick · Фев. 4, 2011 22:00:33

да, я напутал не квадратичная а 2*N

Isem · Фев. 4, 2011 22:57:55

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

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

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

Отредактировано (Фев. 4, 2011 23:07:57)

doza_and · Фев. 5, 2011 10:14:35

Спасибо за интересное решение. Но ему не хватает конструктивного указания как выбирать степень при разном N.
“Поиск метода доказать что это не так” - очень лестное предложение, было-бы интересно заняться, но наверное требуется побольше времени. :) Интересующиеся могут посмотреть что такое десятая проблема Гильберта. http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D1%8B_%D0%93%D0%B8%D0%BB%D1%8C%D0%B1%D0%B5%D1%80%D1%82%D0%B0

Если у вас Isem есть предложения - не скромничайте - озвучте.

Отредактировано (Фев. 5, 2011 10:56:16)

doza_and · Фев. 5, 2011 10:54:19

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

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

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

Уведомления

#1 Фев. 4, 2011 08:04:08

Хитрый поиск в списке

#2 Фев. 4, 2011 08:55:15

Хитрый поиск в списке

#3 Фев. 4, 2011 08:58:03

Хитрый поиск в списке

#4 Фев. 4, 2011 10:59:15

Хитрый поиск в списке

#5 Фев. 4, 2011 16:27:08

Хитрый поиск в списке

#6 Фев. 4, 2011 20:42:07

Хитрый поиск в списке

#7 Фев. 4, 2011 22:00:33

Хитрый поиск в списке

#8 Фев. 4, 2011 22:57:55

Хитрый поиск в списке

#9 Фев. 5, 2011 10:14:35

Хитрый поиск в списке

#10 Фев. 5, 2011 10:54:19

Хитрый поиск в списке

Board footer