Уведомления

Группа в Telegram: @pythonsu

#1 Янв. 22, 2013 07:05:30

Frog-king
Зарегистрирован: 2012-11-30
Сообщения: 31
Репутация: +  1  -
Профиль   Отправить e-mail  

Задачка для всех

Мне кажется, что место имеет скорее неточность Вашей интерпретации Сэр ))
Вы же сами подчеркнули КАЖДЫЙ, а потом говорите что для 123 выполняется только для 3.
Дело в том что в тех. институте (да и в школе бывает) обычно учат что такое пилообразная функция и как она выглядит.
Постройте график - по x - номер элемента по у - значение x-го элемента.
так вот построив 123 или 321 - получим прямую, в отличии от 121 или 213 например.

Офлайн

#2 Янв. 22, 2013 12:26:16

Lexander
От:
Зарегистрирован: 2008-09-19
Сообщения: 1139
Репутация: +  33  -
Профиль   Отправить e-mail  

Задачка для всех

Frog-king
Вы же сами подчеркнули КАЖДЫЙ, а потом говорите что для 123 выполняется только для 3.
Еще раз обращаю ваше внимание на неточность.
Я не писал только для 3. Это вы уже сами придумали. ;)
Было:
В последовательности 123 для элемента 3 это правило выполняется тоже

Ладно, спорить в этом направлении не вижу смысла.
Предлагаю вернуться к задаче.
А вы не пробовали ее решать с помощью:
1). рекурсии
2). преобразования в двоичную систему и операции с битами
?

ЗЫ
Кстати, о пилообразной функции, не спора ради, просто уточняю.
В том же институте учат, что краевые точки множества обладают всеми свойствами множества.
В прикладной сфере аналогом являются крайние зубья пилы или ножа с серрейторной заточкой.
В нашем случае тройка - крайний зуб пилы.



Офлайн

#3 Янв. 22, 2013 13:34:25

Frog-king
Зарегистрирован: 2012-11-30
Сообщения: 31
Репутация: +  1  -
Профиль   Отправить e-mail  

Задачка для всех

Рекурсией не пробовал ( думаю на валидных данных число рекурсии достигнут предела в питоне).
С двоичной системой также, не пробовал.
У меня тупое образование инженера-метролога, нас алгоритмам не обучали. ))
Если у Вас есть мысли конкретней опешите алгоритм. плиз

Другое моё решение которое было чуть побыстрее предыдущего кода было нативным и заключалось лишь в архитектуре кода - каждый элемент представлял собой экземпляр некого класса, который имел как-бы три состояния(на самом деле методы): first - элемент первый в последовательности, second - соответственно 2-й элемент(получал своё значение в зависимости от первого элемента), и change- вычислял значение i-го элемента в зависимости от предыдущих двух. Экземпляры хранили свои значения.
Ну а далее просто - получаем значение первого элемента, второго, третьего .. n-ого -> результат +1 -> получаем ещё возможное значение n -ого элемента -> результат +1 -> повтор последнего действие пока значение не привесит к переходим на n-1 элемент. Вообщем я думаю мысль понятна.
PROFIT

ЗЫ Это не пила уже получается а НОЖ ))

Офлайн

#4 Янв. 22, 2013 13:43:15

EchoXSpace
Зарегистрирован: 2013-01-19
Сообщения: 14
Репутация: +  0  -
Профиль   Отправить e-mail  

Задачка для всех

Warning! Быдлокод
Отработал за 200 сек и отожрал 1,5 гб %)


# "Saw"
# Import lib
import string, time
from itertools import product
# Calcularize
def calc(n, k):
    count = 0
    result = 0
    s = set()
    for saw in product(string.digits[1:k + 1], repeat = n):
        if saw not in s:
            for i in range(n):
                mn = i - 1
                mx = i + 1
                if mn < 0:
                    if saw[i] > saw[mx] or saw[i] < saw[mx]:
                        result += 1
                elif mx > n - 1:
                    if saw[i] > saw[mn] or saw[i] < saw[mn]:
                        result += 1
                elif saw[mn] > saw[i] < saw[mx] or saw[mn] < saw[i] > saw[mx]:
                        result += 1
            if result < n:
                result = 0
            elif result == n:
                result = 0
                count += 1
        s.add(saw)                   
    return count
    
# Input var's
n = int(input('N '))
k = int(input('K '))
# Output
t1 = time.time()
print(calc(n, k))
t2 = time.time()
print(t2 - t1)

Отредактировано EchoXSpace (Янв. 22, 2013 14:07:56)

Офлайн

#5 Янв. 22, 2013 14:07:28

Frog-king
Зарегистрирован: 2012-11-30
Сообщения: 31
Репутация: +  1  -
Профиль   Отправить e-mail  

Задачка для всех

У меня оплавился процессор
Что-то твой код не верные результаты дает: n =4 k = 4 -> 0 и т.д.
А вообще за repeat Спасибо (не знал).

Офлайн

#6 Янв. 22, 2013 14:08:21

EchoXSpace
Зарегистрирован: 2013-01-19
Сообщения: 14
Репутация: +  0  -
Профиль   Отправить e-mail  

Задачка для всех

Во, поправил

Питон только изучаю, сейчас прохожу функции

Отредактировано EchoXSpace (Янв. 22, 2013 14:13:32)

Офлайн

#7 Янв. 22, 2013 14:15:30

Frog-king
Зарегистрирован: 2012-11-30
Сообщения: 31
Репутация: +  1  -
Профиль   Отправить e-mail  

Задачка для всех

во теперь верно но ещё медленней
Есть вариант как ускорить??

Офлайн

#8 Янв. 22, 2013 14:20:45

EchoXSpace
Зарегистрирован: 2013-01-19
Сообщения: 14
Репутация: +  0  -
Профиль   Отправить e-mail  

Задачка для всех

2 потока, проверка на одинаковые числа (“1, 1, 2, 1, 2, 1, 2, 1” исключать сразу)

1 поток набивает числа, 2 - проверяет условия

Поправил код, теперь память не ест

# "Saw"
# Import lib
import string, time
from itertools import product
# Calcularize
def calc(n, k):
    list = []
    count = 0
    result = 0
    for saw in product(string.digits[1:k + 1], repeat = n):
        for i in range(n):
            mn = i - 1
            mx = i + 1
            if mn < 0:
                if saw[i] > saw[mx] or saw[i] < saw[mx]:
                    result += 1
            elif mx > n - 1:
                if saw[i] > saw[mn] or saw[i] < saw[mn]:
                    result += 1
            elif saw[mn] > saw[i] < saw[mx] or saw[mn] < saw[i] > saw[mx]:
                    result += 1
        if result < n:
            result = 0
        elif result == n:
            result = 0
            count += 1
    return count
    
# Input var's
n = int(input('N '))
k = int(input('K '))
# Output
t1 = time.time()
print(calc(n, k))
t2 = time.time()
print(t2 - t1)

Можно попробовать сравнивать не все числа, а через число.

Отредактировано EchoXSpace (Янв. 22, 2013 14:52:00)

Офлайн

#9 Янв. 22, 2013 15:57:27

Frog-king
Зарегистрирован: 2012-11-30
Сообщения: 31
Репутация: +  1  -
Профиль   Отправить e-mail  

Задачка для всех

По поводу такого рода потоков - попробую завтра.
Вообще для новичка неплохо мне кажется.
Единственное я думаю такое извращение типа string.digits не стоит использовать можно просто range(1, k+1)
ещё если заменить на for i in xrange(n): будет выполняться чуть побыстрее.




Офлайн

#10 Янв. 23, 2013 14:52:51

sergeek
Зарегистрирован: 2012-06-26
Сообщения: 470
Репутация: +  43  -
Профиль   Отправить e-mail  

Задачка для всех

def f(k,n):
    d_up = {i : tuple(range(i+1,k)) for i in range(0,k-1)}
    d_down = {i : tuple(range(i)) for i in range(1,k)}
    
    up = [0]*k 
    dn = [0]*k
    for i in range(k):
        for j in range(i):
            dn[j] += 1
        for j in range(i+1,k):
            up[j] += 1
                
    for i in range(n-2):
        n_up = [0]*k 
        n_dn = [0]*k
        
        for key in d_up:
            for e in d_up[key]:
                n_up[e] += dn[key]
                
        for key in d_down:
            for e in d_down[key]:
                n_dn[e] += up[key]
                
        up, dn = n_up, n_dn
    return sum(dn)*2

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version