![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Регистрация: 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 секунда. Как можно убыстрить программу? |
![]() |
![]() |
![]() |
#2 |
Белик Виталий :)
Старожил
Регистрация: 23.07.2007
Сообщений: 57,097
|
![]()
Ну еще бы... Такое число то огромное.
I'm learning to live...
|
![]() |
![]() |
![]() |
#3 |
Форумчанин
Регистрация: 08.01.2010
Сообщений: 165
|
![]()
Число нормальное, просто используется алгоритм сложностью O(n), а можно обойтись алгоритмом сложностью O(lg n), если заменить множество умножений на K на быстрое возведение в степень.
|
![]() |
![]() |
![]() |
#4 |
Регистрация: 22.09.2010
Сообщений: 8
|
![]()
то есть, сначала нужно возвести в необходимую степень К, а потом только умножать его на А1 и сделать операцию mod?
|
![]() |
![]() |
![]() |
#5 | |
Форумчанин
Регистрация: 08.01.2010
Сообщений: 165
|
![]() Цитата:
алгоритма быстрого возведения в степень. Единственное замечание - чтобы избежать переполнения (если K придётся возводить в степень 1000000), код по ссылке нужно будет немного изменить - добавить mod B после каждого умножения в процедуре. |
|
![]() |
![]() |
![]() |
#6 | |
Регистрация: 22.09.2010
Сообщений: 8
|
![]() Цитата:
|
|
![]() |
![]() |
![]() |
#7 | |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,543
|
![]() Цитата:
for j:=1 to N // заменяем на for j:=1 to N mod B
программа — запись алгоритма на языке понятном транслятору
|
|
![]() |
![]() |
![]() |
#8 | |
Форумчанин
Регистрация: 08.01.2010
Сообщений: 165
|
![]() Цитата:
Конечно, есть вероятность, что я тебя понял неправильно - в этом случае я заранее прошу меня извинить. Но всё-таки мне кажется, ты просто написал то, что тебе пришло в голову, не пробуя даже скомпилировать и проверить свой вариант. Может быть ты нам всем скажешь, откуда взята эта чудесная "МАТЕМАТИКА", с помощью которой ты решил, что если от количества умножений взять остаток, это никак не изменит результат? |
|
![]() |
![]() |
![]() |
#9 |
Старожил
Регистрация: 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. |
![]() |
![]() |
![]() |
#10 |
Форумчанин
Регистрация: 08.01.2010
Сообщений: 165
|
![]()
Хм, приношу свои извинения, был неправ) про то, что отстатки будут периодичны я и забыл)
|
![]() |
![]() |
![]() |
|
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
На чем написана программа | Владимир-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 |