Light or Dark
offline
Опыт:
7,275Активность: |
Оптимизация задачи
Помогите пожалуйста!нужно решить задачу нахождение суммы простых делителей.ограничение по времени 2 секунды.число вводится до 10 в 9 степени.
я решил так(язык pascal): Код:
но вот проблема-не проходит по времени(>2 секунд)...пожалуйста помогите,что надо сделать! Light or Dark добавил: так что,никто не поможет????((((((((((( Light or Dark добавил: ну плиииз!помогите! |
01.05.2009, 17:15 | #1
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
MF
Что-то вокруг не так
offline
Опыт:
26,594Активность: |
Light or Dark я не думаю что ты вообще находишь простые делители, так как ты просто убеждаешься что число делится на i, но оно не обяз простое.
|
01.05.2009, 19:03 | #2
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J
expert
offline
Опыт:
48,447Активность: |
Код:
Отредактировано J, 02.05.2009 в 03:08. |
01.05.2009, 19:11 | #3
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
MF
Что-то вокруг не так
offline
Опыт:
26,594Активность: |
|
01.05.2009, 19:11 | #4
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J
expert
offline
Опыт:
48,447Активность: |
... это бы точно работало бы если мы на простые числа проверяли все числа, а не только делаители, а раз я проверяю только делители то я неуверен, ну нихачу просто думать |
01.05.2009, 19:16 | #5
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
MF
Что-то вокруг не так
offline
Опыт:
26,594Активность: |
J по идее вполне норм, ускорение процесса будет налицо. Если сначала проверять, что число простое, а потом делитель ли, то итераций будет больше. А так вроде норм.
|
01.05.2009, 19:22 | #6
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
Light or Dark
offline
Опыт:
7,275Активность: |
у меня все верно(ищет моя прога делители)....спросил у зав. кафедры-она говорит правильно,но надо идти до round(sqrt(ch)) (первый фор). но у меня это не работает((( |
01.05.2009, 19:34 | #7
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J
expert
offline
Опыт:
48,447Активность: |
Цитата:
|
|
01.05.2009, 19:35 | #8
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
MF
Что-то вокруг не так
offline
Опыт:
26,594Активность: |
Light or Dark
Не правильно, если введешь ch = 4 то при i = 4 условие сработает и 4 приплюсуется, а оно как бэ не простое число. MF добавил: Хотя... наверное я не прошарил, извинтиляюсь. |
01.05.2009, 20:16 | #9
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
adic3x
offline
Опыт:
108,439Активность: |
» asm Код:
ну грубо говоря я все загнал в регистры... но 0ffffffffh считает чувствительно долго (+ не факт что правильно) ADOLF добавил: на 15 - сумма 9 (1,3,5) вестимо на 16 - сумма 3 (1,2) ADOLF добавил: 10000000h (там чуть больше) - около четырех сек |
01.05.2009, 21:05 | #10
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J
expert
offline
Опыт:
48,447Активность: |
а, нужно ведь сумма а не список, чуть подправил код
J добавил: ADOLF мой тоже 0x10000000 делает около четырех сек =p |
01.05.2009, 21:20 | #11
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
adic3x
offline
Опыт:
108,439Активность: |
J, у тебя какой проц ?) и прогони какое то конкретное число - результаты сравним...
|
01.05.2009, 21:31 | #12
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J
expert
offline
Опыт:
48,447Активность: |
2,4 гГр.
J добавил: но это толкьо для 0x10000000 выполняется так быстро, чем больше список постых чисел тем будет дольше PS 1 это не простое число J добавил: PPS я вкрутил таймер, он оЧеНь точный, потому лучше отклчюить все что тормозит |
01.05.2009, 21:51 | #13
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
adic3x
offline
Опыт:
108,439Активность: |
1 не простое? лол) ну там всеравно, либо 0 либо 1 писать в регистр) только таймер я не прикручу) сейчас резулты сравню
// атлон 2к, 1.666 ADOLF добавил: как ни странно но у мну результат равен +1 к твоему (ну я понял да 1 надо выпилить в начале) |
01.05.2009, 21:56 | #14
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J
expert
offline
Опыт:
48,447Активность: |
ADOLF простое число нельзя представить в виде множителей простых чисел
1 = 1*1 получается 1 не простое число почтиай вики и посмотри списки простых чисел, там нигде нету еденицы |
01.05.2009, 21:56 | #15
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
adic3x
offline
Опыт:
108,439Активность: |
10000002h - 3.7 сек у тебя, сейчас себя проверю...
ADOLF добавил: так, к своей тулзу прикручивать таймер мне влом, твою из под оли запускать тоже...) |
01.05.2009, 22:03 | #16
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J
expert
offline
Опыт:
48,447Активность: |
=) вот чем плох асм) а мне всеволишь потребовалось перенести пару файликов из своей старой игры и добавить пару строчек, что заняло полторы минуты) Отредактировано J, 01.05.2009 в 22:12. |
01.05.2009, 22:07 | #17
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
adic3x
offline
Опыт:
108,439Активность: |
у меня бы это заняло минуты 3 - 4, но мне и то лень ;) ты прав... |
01.05.2009, 22:16 | #18
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
J
expert
offline
Опыт:
48,447Активность: |
максимум я ее смог сжать до 130кб, какую-то он туда левую инфу сует=/ у тебя наверно кб 1-10 занимает |
01.05.2009, 22:22 | #19
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|
adic3x
offline
Опыт:
108,439Активность: |
1.5 кб изза того, что надо выделять особую секцию писабельну под данные, что бы туда состояние есп пихать... мне нехватило одного регистра) инче бы меньше 600 кб .ехе весило бы
ADOLF добавил: можно сжимать дальше... сам алгоритм - 75 байт |
01.05.2009, 22:36 | #20
+0/−0
Профиль |
Приват |
Поиск |
Цитата |
IP: Записан
|