Ускорение выполнения задачи на паскале
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Ускорение выполнения задачи на паскале - 2009-01-02 12:32:26.736666
|
|
|
VaZoNeZ
Сообщений: -6758
Оценки: 0
Присоединился: 2008-10-31 14:38:43.796666
|
Задача:
Дано 1..20 чисел 1..100
Найти наименьший общий кратное.
Ввод:
2
2 3
Вывод:
6
Вот код:
program NSK;
uses SysUtils;
var
i,i2,n,c,checker:longint;
A:array[1..20] of byte;
f1,f2:text;
begin
Assign(f1, 'input.txt');
Assign(f2, 'output.txt');
reset(f1);
rewrite(f2);
Readln(f1, n);
for i:=1 to n do
Read(f1,A[i]);
c:=0;
while checker<>n do
begin
checker:=0;
inc(c);
for i2:=1 to n do
begin
if c mod A[i2]=0 then
inc(checker)
else
break;
end;
end;
writeln(f2, c);
close(f1);
close(f2);
end.
Два теста из десяти - перебор времени. Как можно оптимизировать?
|
|
|
|
|
RE: Ускорение выполнения задачи на паскале - 2009-01-02 12:53:20.093333
|
|
|
Unconnected
Сообщений: 158
Оценки: 0
Присоединился: 2008-09-11 22:02:01.983333
|
Конечно не знаю, но мож на асме будет быстрее?
А вообще с этой проблемой можешь пойти на forum.pascal.net.ru помогут.
|
|
|
|
|
RE: Ускорение выполнения задачи на паскале - 2009-01-02 12:56:01.983333
|
|
|
Sunzer
Сообщений: 253
Оценки: 31190
Присоединился: 2007-06-15 19:23:32.436666
|
program NSK;
uses SysUtils;
var
i,i2,n,c,checker:longint;
A:array[1..20] of byte;
f1,f2:text;
begin
Assign(f1, 'input.txt');
Assign(f2, 'output.txt');
reset(f1);
rewrite(f2);
Readln(f1, n);
for i:=1 to n do
Read(f1,A);
c:=0;
while checker<>n do
begin
checker:=0;
inc©;
for i2:=1 to n do
begin
if c mod A[i2]=0 then
inc(checker)
else
break;
end;
end;
writeln(f2, c);
close(f1);
close(f2);
end.
Можно убрать. Без них тоже работать будет. А так попробуй на асме писать. :)
|
|
|
|
|
RE: Ускорение выполнения задачи на паскале - 2009-01-02 13:01:25.706666
|
|
|
VaZoNeZ
Сообщений: -6758
Оценки: 0
Присоединился: 2008-10-31 14:38:43.796666
|
в том то и проблема - надо на паскале :(
типы перебираю, мож и выйдет….
|
|
|
|
|
RE: Ускорение выполнения задачи на паскале - 2009-01-02 13:16:23.140000
|
|
|
Unconnected
Сообщений: 158
Оценки: 0
Присоединился: 2008-09-11 22:02:01.983333
|
Попробуй как типизированный файл читать, должно меньше памяти кушать.
|
|
|
|
|
RE: Ускорение выполнения задачи на паскале - 2009-01-02 13:38:06.336666
|
|
|
JTG
Сообщений: 1189
Оценки: 0
Присоединился: 2007-03-05 11:56:01.993333
|
quote:
Найти наименьший общий делитель.
Я чего-то не понимаю, или наименьший общий делитель всегда будет 1? :D
ЗЫ: если имеется ввиду наименьшее общее кратное - то сюда http://www.opeople.ru/lofiversion/index.php?t480.html
|
|
|
|
|
RE: Ускорение выполнения задачи на паскале - 2009-01-02 16:40:24.026666
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
Во-первых, если уже пишешь код и просишь оптимизировать, то хоть комментарии к нему добавляй.
Во-вторых, определись, что ты ищешь: наименьшее общее кратное (НОК) или наибольший общий делитель (НОД). Конечно, наименьший общий делитель тоже можно искать, но он на самом деле всегда будет равен 1.
Ну в-третьих, что бы ты там не искал, твой алгоритм можно несколько раз серьёзно оптимизировать, но лучше всё-таки начать с гугла, или хотя бы банально с Википедии:
http://ru.wikipedia.org/wiki/%D0%9D%D0%B0%D0%B8%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B5%D0%B5_%D0%BE%D0%B1%D1%89%D0%B5%D0%B5_%D0%BA%D1%80%D0%B0%D1%82%D0%BD%D0%BE%D0%B5
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4%D0%B0
Там, в частности, написано, что НОК можно найти через НОД, а НОД, в свою очередь, относительно быстро находится по алгоритму Евклида. Относительно - потому что нахождение простых общих делителей само по себе является весьма трудоёмкой задачей и даже используется для построения мощных криптоалгоритмов.
|
|
|
|
|
RE: Ускорение выполнения задачи на паскале - 2009-01-02 20:40:55.980000
|
|
|
VaZoNeZ
Сообщений: -6758
Оценки: 0
Присоединился: 2008-10-31 14:38:43.796666
|
кратное, не так выразился….
я имел в виду несерьезно оптимизировать - перебор времени всего 0,016 сек
|
|
|
|
|
RE: Ускорение выполнения задачи на паскале - 2009-01-03 00:32:21.530000
|
|
|
kreol
Сообщений: 823
Оценки: 0
Присоединился: 2007-03-08 03:13:06.876666
|
quote:
ORIGINAL: VaZoNeZ
кратное, не так выразился….
я имел в виду несерьезно оптимизировать - перебор времени всего 0,016 сек
Ага, поправил в названии, теперь там "наименьший общий кратное")))
Так комментарии к коду я увижу?
|
|
|
|
|
RE: Ускорение выполнения задачи на паскале - 2009-01-06 17:42:59.290000
|
|
|
Denaturat
Сообщений: 1741
Оценки: 453
Присоединился: 2008-10-27 20:50:06.380000
|
обрати внимание - какой показательный топик
просто в рамочку и на стенку
оптимизация? переписать на ассемблере, точно быстрее будет. это ж ассемблер, ну! все чоткие пацаны пишут на ассемблере и у них всё быстро работает
какая там асимптотическая сложность, какие к собачьим монахам Кнут и Ландау…
|
|
|
|
|
|
