Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Форум программистов и сисадминов Киберфорум > Форум программистов > Python > Python для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
0 / 0 / 0
Регистрация: 14.10.2020
Сообщений: 10
1

Оптимизация кода

03.11.2020, 18:16. Показов 1793. Ответов 10
Метки alghoritms, codewars, pyhton (Все метки)
Author24 — интернет-сервис помощи студентам
Добрый день! Я только учусь и столкнулся с такой проблемой: Задание на кодварсе следующее: есть целые числа от m до n включительно. Нужно найти такие, чтобы сумма квадратов их делителей сама являлась квадратом. К примеру делители числа 42 это:1, 2, 3, 6, 7, 14, 21, 42. Квадраты их равны 1, 4, 9, 36, 49, 196, 441, 1764. Сумма квадратов делителей равна 2500, что является квадратом 50. Я написал код, на дефолтных проверках он проходит, но когда кодварс пытается сам подставить свои значения, то получается ошибка:Execution Timed Out. Помогите оптимизировать код и объяснить что с ним не так. Спасибо
Python
1
2
3
4
5
6
7
8
9
10

def list_squared(m, n):
    answer=[]
    for i in range(m,n+1):
        k=0
        for j in range(1,i+1):
            if i%(j)==0:
                k+=j**2
        if int(k**0.5)==float(k**0.5):
            answer.append([i,k])
    return answer
0
Лучшие ответы (1)
Сообщение: #14970036
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
 03.11.2020, 18:16
Ответы с готовыми решениями:

Оптимизация кода
Добрый день, прорешивая разные задачки, зачастую мне удавалось добиться результата, чтобы код...

Оптимизация кода
Оптимизируйте пожалуйста эти коды: s = input() res = set() for i in range(len(s)): for j in...

Оптимизация кода
Коллеги, здравствуйте! Как можно оптимизировать код, долго что-то выполняется import math...

Оптимизация кода
это код, который ищет в тексте пользователя самое большое расстояние между двумя одинаковыми...

Оптимизация кода
Мы будем работать с набором слов. Ваша задача — выписать все слова, которые являются анаграммами...

10
Эксперт Python
4639 / 2056 / 362
Регистрация: 17.03.2012
Сообщений: 10,139
Записей в блоге: 6
03.11.2020, 18:31 2
Вместо **0.5 использовать math.sqrt. Вместо **2, соответственно, j*j.
Вместо range(..., i+1) использовать sqrt(i) (в качестве правой границы цикла).
Провека на целость - не надо извлекать корень дважды.
0
0 / 0 / 0
Регистрация: 14.10.2020
Сообщений: 10
03.11.2020, 18:52  [ТС] 3
Это по сути ничего не изменит. А насчет правой границы: почему то когда я пишу вместо i+1 "math.ceil(math.sqrt(i)+1) у меня не меняется j во всех итерациях
0
Эксперт Python
4639 / 2056 / 362
Регистрация: 17.03.2012
Сообщений: 10,139
Записей в блоге: 6
03.11.2020, 19:17 4
zm127, проход до sqrt() изменит, для каждого числа переход от O(n) до O(sqrt(n)).
Почему не меняется j - не знаю, должен меняться.

Учитывая, что надо пройти несколько чисел, можно попробовать что-нибудь закешировать, но пока не вижу, что.
0
Эксперт Python
8581 / 4410 / 1852
Регистрация: 27.03.2020
Сообщений: 7,226
03.11.2020, 19:51 5
zm127, ограничения по n, m какие?
0
0 / 0 / 0
Регистрация: 14.10.2020
Сообщений: 10
03.11.2020, 20:03  [ТС] 6
list_squared(1, 250), Ответ должен быть такой:[[1, 1], [42, 2500], [246, 84100]])
Такой ответ у меня и получается,но видимо на проверке рандомными числами от кодварса выдает что время ожидания превышено
0
Эксперт Python
8581 / 4410 / 1852
Регистрация: 27.03.2020
Сообщений: 7,226
03.11.2020, 20:38 7
Лучший ответ Сообщение было отмечено zm127 как решение

Решение

zm127, максимальная разница между входными числами дается?

Добавлено через 1 минуту
zm127, попробуй. Может прокатит
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def intSqrt(n):
    if n < 2:
        return n
    else:
        sm = intSqrt(n >> 2) << 1
        lg = sm + 1
        if lg * lg > n :
            return sm 
        else:
            return lg 
 
def list_squared(m, n):
    answer=[]
    for i in range(m,n+1):
        k=0
        j = 1
        while j * j < i + 1 :
            if i%(j)==0:
                ij = i // j
                k += (j * j + ij * ij if j - ij else j * j)
            j += 1
        sq = intSqrt(k)
        if sq * sq == k :
            answer.append([i,k])
    return answer
    
print(list_squared(1,250))
Добавлено через 32 минуты
Или
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

from math import sqrt
def list_squared(m, n):
    answer=[]
    for i in range(m,n+1):
        k=0
        j = 1
        while j * j < i + 1 :
            if i%(j)==0:
                ij = i // j
                k += (j * j + ij * ij if j - ij else j * j)
            j += 1
        #sq = intSqrt(k)
        if int(sqrt(k)) * sqrt(k) == k :
            answer.append([i,k])
    return answer
    
print(list_squared(1,25000))
1
0 / 0 / 0
Регистрация: 14.10.2020
Сообщений: 10
03.11.2020, 21:04  [ТС] 8
Работает, спасибо большое, сейчас буду разбираться в коде
0
Status 418
Эксперт Python
4581 / 2348 / 602
Регистрация: 26.11.2017
Сообщений: 5,264
Записей в блоге: 3
03.11.2020, 21:07 9
list_squared(1, 10**8):
Кликните здесь для просмотра всего текста
[[1, 1],
[42, 2500],
[246, 84100],
[287, 84100],
[728, 722500],
[1434, 2856100],
[1673, 2856100],
[1880, 4884100],
[4264, 24304900],
[6237, 45024100],
[9799, 96079204],
[9855, 113635600],
[18330, 488410000],
[21352, 607622500],
[21385, 488410000],
[24856, 825412900],
[36531, 1514610724],
[39990, 2313610000],
[46655, 2313610000],
[57270, 4747210000],
[66815, 4747210000],
[92664, 13011964900],
[125255, 16430112400],
[156570, 35532250000],
[182665, 35532250000],
[208182, 60762250000],
[212949, 51437332804],
[242879, 60762250000],
[273265, 77829840400],
[380511, 163426147600],
[391345, 159696144400],
[411558, 240198010000],
[539560, 410752810000],
[627215, 410752810000],
[693160, 668633290000],
[730145, 557979120400],
[741096, 821017210000],
[773224, 796252828900],
[814463, 668633290000],
[931722, 1219036810000],
[992680, 1371943690000],
[1069895, 1195304890000],
[1087009, 1219036810000],
[1143477, 1475034540100],
[1166399, 1371943690000],
[1422577, 2044042090000],
[1592935, 2643160608400],
[1815073, 3327340810000],
[2281255, 5423402592400],
[2544697, 6498930490000],
[2713880, 10268820250000],
[2722005, 8796088272400],
[2828385, 9556753960000],
[3054232, 12389344022500],
[3132935, 10268820250000],
[3145240, 13949478010000],
[3188809, 10268820250000],
[3508456, 16715832250000],
[4026280, 22492823875600],
[4647985, 22492823875600],
[4730879, 22492823875600],
[5024488, 34298592250000],
[5054015, 26676192010000],
[5143945, 27619018944400],
[5260710, 41075281000000],
[5938515, 41667283200400],
[6128024, 51101052250000],
[6236705, 40593463690000],
[6366767, 41008398288400],
[6956927, 48643650250000],
[6996904, 65032773204100],
[7133672, 69417224890000],
[7174440, 82101721000000],
[7538934, 79625282890000],
[7736646, 83183520250000],
[7818776, 83183520250000],
[8292583, 69417224890000],
[8429967, 82101721000000],
[8504595, 85495543104400],
[8795423, 79625282890000],
[9026087, 83183520250000],
[9963071, 99810090250000],
[11477130, 194574601000000],
[11538505, 139610766490000],
[11725560, 219902206810000],
[12158135, 155004990010000],
[12939480, 260131092816400],
[12948776, 222689064472900],
[13495720, 256720506250000],
[13592118, 256720506250000],
[13736408, 256720506250000],
[15203889, 260131092816400],
[15857471, 256720506250000],
[16149848, 352301638090000],
[16436490, 399240361000000],
[16487415, 324554637160000],
[16909849, 289604836128400],
[18391401, 388917841000000],
[18422120, 469260440256400],
[20549528, 562320596890000],
[20813976, 647219040250000],
[20871649, 436988086147600],
[21251412, 683572005944100],
[22713455, 538266912336400],
[23250645, 639923030890000],
[23630711, 562320596890000],
[24738935, 640317720250000],
[26338473, 798006001000000],
[26343030, 1026882025000000],
[26594568, 1094306248090000],
[28113048, 1180753916410000],
[29429144, 1153804643290000],
[29778762, 1238934402250000],
[29973414, 1253591917210000],
[30666090, 1394947801000000],
[30915027, 1094306248090000],
[34207446, 1671583225000000],
[34741889, 1238934402250000],
[34968983, 1253591917210000],
[35721896, 1735430622250000],
[37113593, 1392676413216400],
[37343065, 1451977307232400],
[38598255, 1747952344590400],
[39256230, 2249282387560000],
[42021720, 2761901894440000],
[44935590, 2988262225000000],
[45795688, 2798293621210000],
[45798935, 2249282387560000],
[48988758, 3429859225000000],
[49375521, 2761901894440000],
[51516049, 2678594516419600],
[51912289, 2733777693091600],
[52867081, 2798293621210000],
[56215914, 4389206926188100],
[59748234, 5110105225000000],
[61116363, 4325879688816400],
[62158134, 5369738562250000],
[63286535, 4190089414810000],
[65585233, 4389206926188100],
[66903270, 6607901521000000],
[68219814, 6503277320410000],
[68678280, 7397510237088400],
[72006543, 5972971225000000],
[72517823, 5369738562250000],
[74955321, 6464320801000000],
[76233066, 8318352025000000],
[79046360, 8636077830250000],
[79589783, 6503277320410000],
[80456104, 8636077830250000],
[83597345, 7311087924010000],
[86369945, 7799719388640400],
[89718065, 8375196559210000],
[92879473, 8636077830250000],
[95812710, 13558506481000000],
[96569145, 10918017994062400]]


Добавлено через 2 минуты
Цитата Сообщение от zm127 Посмотреть сообщение
Работает
введи 108
0
0 / 0 / 0
Регистрация: 14.10.2020
Сообщений: 10
04.11.2020, 13:08  [ТС] 10
Цитата Сообщение от Gdez Посмотреть сообщение
if j - ij else j * j
Извините, а как понять эту строку? Что это за условие j-ij?
0
Эксперт Python
8581 / 4410 / 1852
Регистрация: 27.03.2020
Сообщений: 7,226
04.11.2020, 13:26 11
zm127, тернарный оператор
А условие - если делители числа равны, то в расчетах считается только один. Замена этому фрагменту:
Python
1
2
3
4

if j - ij != 0 :
    k += j*j + ij*ij
else:
    k += j*j
У 16, например, раскладывается => 16 и 1 ; 8 и 2 ; 4 и 4. Но делители - 16, 1, 8, 2, 4 => четверка одна(!)
В некоторых задачах используется - все полные квадраты имеют нечетное количество делителей
1
04.11.2020, 13:26
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
 04.11.2020, 13:26
Помогаю со студенческими работами здесь

Оптимизация скорости кода
a=2 b=3 c=5 d=50 your=int(input(&quot;Введите ваш баланс:&quot;)) def proga(x): for i in range(0,x+1):...

Оптимизация кода | requests
Доброго дня! Пытаюсь оптимизировать код и ускорить получния запрсов на сайт. Как смог...

Python. Оптимизация кода
Здравствуйте всем! Я недавно начал заниматься питоном и во время решения одной из моих задач,...

Оптимизация кода по времени
Есть задача. Всем известно, что со временем клавиатура изнашивается, и клавиши на ней начинают...

Оптимизация небольшого кода
Имеется код для решения задачи: дается строка, нужно узнать, можно ли, убрав только один в ней...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Поддержать - Реклама - Обратная связь
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru