Суббота, 18.05.2024, 20:02
Приветствую Вас Guest Member

Windows XP / 7 .

Главная | Программа работает дольше, чем нужно - Форум <<Помощь по компьютерам>> | Регистрация | Вход | RSS
[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Архив - только для чтения
Форум <<Помощь по компьютерам>> » Delphi программирование » Паскаль » Программа работает дольше, чем нужно (Программа работает дольше, чем нужно)
Программа работает дольше, чем нужно
AdminДата: Четверг, 23.09.2010, 16:01 | Сообщение # 1
Forum member
Группа: Admin
Зарегистрирован: 24.02.2010
Откуда: Цюрупинск
Пол: Мужчина
Сообщений: 691
Статус: Вне сайта
Программа работает дольше, чем нужно

Вопрос:

На вход программе даются 4 числа: А1, К, В, n. Требуется найти Аn по следующей формуле: Ai+1=Ai * K mod B.
(1<=A1<=100000, 1<=K<=10000, 1<=B<=100000, 1<=n<=1000000000).

Вот ее решение:
for i:=2 to n do
An:=An*K mod B

Но есть одна проблема: например, когда n=1000000000, то программа вычисляет где-то секунд 20. Но в условии сказано, что ограничение по времени: 1 секунда. Как можно убыстрить программу?


 
AdminДата: Четверг, 23.09.2010, 16:01 | Сообщение # 2
Forum member
Группа: Admin
Зарегистрирован: 24.02.2010
Откуда: Цюрупинск
Пол: Мужчина
Сообщений: 691
Статус: Вне сайта
Ответ:

Число нормальное, просто используется алгоритм сложностью O(n), а можно обойтись алгоритмом сложностью O(lg n), если заменить множество умножений на K на быстрое возведение в степень.


 
Форум <<Помощь по компьютерам>> » Delphi программирование » Паскаль » Программа работает дольше, чем нужно (Программа работает дольше, чем нужно)
  • Страница 1 из 1
  • 1
Поиск: