ReSQL.ru
     
powered by simpleCommunicator - 2.0.51     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Улучшить качество кода: Питон
6 сообщений из 6, страница 1 из 1
Улучшить качество кода: Питон
    #39380522
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Задача лежит здесь

Код решения
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
def triplet_dict(nmax):
    triplets = {}
    for a in range(1, nmax//3+1):
        for b in range( a+1, (nmax-a)//2+1 ):
            c = int( sqrt(a*a+b*b) )
            if a*a + b*b == c*c:
                if a+b+c in triplets:
                    triplets[a+b+c] = max(triplets[a+b+c], a*b*c)
                else:
                    triplets[a+b+c] = a*b*c
    return triplets



хотелось бы
1) увеличить скорость выполнения кода
2) и услышать критику по качеству кода и алгоритму.
...
Рейтинг: 0 / 0
08.01.2017, 15:52
| Ответить | Цитировать | Написать  
Улучшить качество кода: Питон
    #39380748
Фотография NekZ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NekZ
Участник
mini.weblab,

На первый взгляд задача не решается в лоб, а явно намекает на поиск сторон в прямоугольном треугольнике у которого известен лишь периметр. Поиск максимального abc намекает на использование "жадного" алгоритма.
...
Рейтинг: 0 / 0
09.01.2017, 11:30
| Ответить | Цитировать | Написать  
Улучшить качество кода: Питон
    #39381141
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
NekZ,

1) ну вообще-то, я ее как раз-таки в лоб и решила: сгенирировала все возможные триплеты с макс. произведением и сохранила в data dictionary (использовав периметр как ключ), а дальше в тест кейсах просто доставала данные из словаря по ключу.
2) я думаю, жадный алгоритм тут не сработает
...
Рейтинг: 0 / 0
09.01.2017, 23:04
| Ответить | Цитировать | Написать  
Улучшить качество кода: Питон
    #39381175
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
попробовала реализовать идею жадного алгоритма
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
def triplet_dict(nmax):
    triplets = {}
    for a in range(1, nmax//3+1):
        for b in range( a+1, (nmax-a)//2+1 ):
            c = int( sqrt(a*a+b*b) )
            if a*a + b*b == c*c:
                triplets[a+b+c] = a*b*c
    return triplets


я вас правильно поняла, NekZ?
в любом случае код теперь выглядит лучше (спасибо)
...
Рейтинг: 0 / 0
10.01.2017, 03:06
| Ответить | Цитировать | Написать  
Улучшить качество кода: Питон
    #39384630
Програмёр
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Програмёр
Участник
mini.weblab,

мой вариант (прошёл все тесты)
Код: python
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
#!/bin/python3

import sys


t = int(input().strip())
for a0 in range(t):
    n = int(input().strip())
    prod = 0
    for a in range(n//3):
        b = (n - n*a/(n-a))/2
        if(b != b//1): continue
        if(a*b*(n-a-b)>prod): prod=a*b*(n-a-b)
    print(int(prod if prod>0 else -1))



строка выделенная красным была посчитана из системы выражений
N = a+b+c
a^2+b^2 = c^2

Просто выразил b через N и a, тем самым избавив себя от необходимости считать квадраты и корни. Да и как видно у функции есть всего один параметр "a" (N не является параметром, так как в условиях этого алгоритма это константа).

В этом коде всё просто:
1. Перебираю все целые "a"
2. Для каждого значения a проверяю будет ли целым b (если да, то я уже уверен что и c будет целым)
3. Умножаю a*b*c (точнее a*b*(N-a-b), что тоже выведено из первого уравнения системы) и смотрю является ли это значение больше предыдущего. Если да - запоминаю
...
Рейтинг: 0 / 0
14.01.2017, 03:00
| Ответить | Цитировать | Написать  
Улучшить качество кода: Питон
    #39384745
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Програмёр,
спасибо! хорошее замечание!
...
Рейтинг: 0 / 0
14.01.2017, 17:02
| Ответить | Цитировать | Написать  
6 сообщений из 6, страница 1 из 1
Форумы / PHP, Perl, Python [игнор отключен] [закрыт для гостей] / Улучшить качество кода: Питон
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=23&msg=39384745&tid=1460801]:
 0ms
get settings:
 10ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 47ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 46ms
get tp. blocked users:
 1ms
others: 282ms
total:  420ms
созд. / загр.: 420ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]