Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 22.09.2010, 21:07   #1
Ильнар70
 
Регистрация: 22.09.2010
Сообщений: 8
По умолчанию Программа работает дольше, чем нужно((

На вход программе даются 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 секунда. Как можно убыстрить программу?
Ильнар70 вне форума Ответить с цитированием
Старый 23.09.2010, 10:37   #2
Stilet
Белик Виталий :)
Старожил
 
Аватар для Stilet
 
Регистрация: 23.07.2007
Сообщений: 57,097
По умолчанию

Ну еще бы... Такое число то огромное.
I'm learning to live...
Stilet вне форума Ответить с цитированием
Старый 23.09.2010, 13:33   #3
kogemrka
Форумчанин
 
Аватар для kogemrka
 
Регистрация: 08.01.2010
Сообщений: 165
По умолчанию

Число нормальное, просто используется алгоритм сложностью O(n), а можно обойтись алгоритмом сложностью O(lg n), если заменить множество умножений на K на быстрое возведение в степень.
kogemrka вне форума Ответить с цитированием
Старый 23.09.2010, 18:38   #4
Ильнар70
 
Регистрация: 22.09.2010
Сообщений: 8
По умолчанию

Цитата:
Сообщение от kogemrka Посмотреть сообщение
Число нормальное, просто используется алгоритм сложностью O(n), а можно обойтись алгоритмом сложностью O(lg n), если заменить множество умножений на K на быстрое возведение в степень.
то есть, сначала нужно возвести в необходимую степень К, а потом только умножать его на А1 и сделать операцию mod?
Ильнар70 вне форума Ответить с цитированием
Старый 23.09.2010, 21:40   #5
kogemrka
Форумчанин
 
Аватар для kogemrka
 
Регистрация: 08.01.2010
Сообщений: 165
По умолчанию

Цитата:
Сообщение от Ильнар70 Посмотреть сообщение
то есть, сначала нужно возвести в необходимую степень К, а потом только умножать его на А1 и сделать операцию mod?
Именно, причём не просто возвести в степень, а при помощи специального
алгоритма быстрого возведения в степень.

Единственное замечание - чтобы избежать переполнения (если K придётся возводить в степень 1000000), код по ссылке нужно будет немного изменить - добавить mod B после каждого умножения в процедуре.
kogemrka вне форума Ответить с цитированием
Старый 24.09.2010, 06:15   #6
Ильнар70
 
Регистрация: 22.09.2010
Сообщений: 8
По умолчанию

Цитата:
Сообщение от kogemrka Посмотреть сообщение
Именно, причём не просто возвести в степень, а при помощи специального
алгоритма быстрого возведения в степень.

Единственное замечание - чтобы избежать переполнения (если K придётся возводить в степень 1000000), код по ссылке нужно будет немного изменить - добавить mod B после каждого умножения в процедуре.
А обязательно число переводить в двоичную запись?
Ильнар70 вне форума Ответить с цитированием
Старый 24.09.2010, 08:30   #7
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,543
По умолчанию

Цитата:
Ai+1=Ai * K mod B.
(1<=A1<=100000, 1<=K<=10000, 1<=B<=100000, 1<=n<=1000000000).
ответ лежит в МАТЕМАТИКЕ A (b+1)=A(1)
for j:=1 to N // заменяем на for j:=1 to N mod B
программа — запись алгоритма на языке понятном транслятору
evg_m вне форума Ответить с цитированием
Старый 25.09.2010, 17:50   #8
kogemrka
Форумчанин
 
Аватар для kogemrka
 
Регистрация: 08.01.2010
Сообщений: 165
По умолчанию

Цитата:
Сообщение от evg_m Посмотреть сообщение
ответ лежит в МАТЕМАТИКЕ A (b+1)=A(1)
for j:=1 to N // заменяем на for j:=1 to N mod B
Странно, лично у меня программа, написанная по алгоритму автора топика (пускай и работающая долго) и программа, написанная с использованием быстрого возведения в степень дают один результат, а программа с использованием твоей оптимизации - совершенно другой. Более того, на тестах, которые можно просчитать вручную программа по твоему алгоритму даёт результаты, не сходящиеся с просчитанными вручную.

Конечно, есть вероятность, что я тебя понял неправильно - в этом случае я заранее прошу меня извинить. Но всё-таки мне кажется, ты просто написал то, что тебе пришло в голову, не пробуя даже скомпилировать и проверить свой вариант.

Может быть ты нам всем скажешь, откуда взята эта чудесная "МАТЕМАТИКА", с помощью которой ты решил, что если от количества умножений взять остаток, это никак не изменит результат?
kogemrka вне форума Ответить с цитированием
Старый 25.09.2010, 19:13   #9
evg_m
Старожил
 
Регистрация: 20.04.2008
Сообщений: 5,543
По умолчанию

k=3 B=5

A1 =1 mod 5=1
A2=3**1=3 mod 5=3
a3=3**2=9 mod 5 =4
a4=3**3=27 mod 5 =2
A5=3**4=81 mod 5 =1 =A1
A6=3**5= A1 *3
программа — запись алгоритма на языке понятном транслятору

Последний раз редактировалось evg_m; 25.09.2010 в 19:17.
evg_m вне форума Ответить с цитированием
Старый 25.09.2010, 19:37   #10
kogemrka
Форумчанин
 
Аватар для kogemrka
 
Регистрация: 08.01.2010
Сообщений: 165
По умолчанию

Хм, приношу свои извинения, был неправ) про то, что отстатки будут периодичны я и забыл)
kogemrka вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
На чем написана программа Владимир-N Софт 5 06.06.2010 23:27
Работа со стеком. Не работает часть программы. Устала думать в чем дело. Angie Помощь студентам 0 18.05.2010 22:05
Не работает MySQL. Подскажите, в чем проблема???? just me PHP 4 07.04.2009 15:50
Нужна помощь. Винда дольше загружается, с каждым запуском. Michigan Свободное общение 14 24.04.2007 02:13