Armenian Knowledge Base  

Go Back   Armenian Knowledge Base > Technical sections > Languages, Compilers, Interpreters > Algorithms
Register

Reply
 
LinkBack Thread Tools
Old 26.09.2002, 08:39   #1
Младенец
 
Join Date: 09 2002
Location: ?????????
Posts: 13
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Question Tрудная Задача / Длинная арифметика

Trvac ! N bnakan tiv@: Gtnum enq ajd tvi tvanshan-
nerov stacvox amenamec ev amenapoqr tver@: Ajnu-
hetev hashvum nranc tarberutjun@: Orinak, erb
N = 174, apa max = 741 ev min = 147
max - min = 594:

Ajspisov N tvic kstananq mi nor tiv: Nujn@ kanenq
ajd tvi het: Kstananq tveri hajordakanutjun: Ajd
hajordakanutjan mej inch vor texic Ksatcvi cikl
(qani vor stacvox tveri qanak@ verjavor hat !):
Anhrajesht ! gtnel ajd cikli erkarutjun@:
Harkavor ! gtnel algoritm@, cod@ anpajman che:

Orinak`
N = 8252
8252, 6264, 4176, 6174, 6174:
Cikli erkarutjun@ = 0;
N = 32528,
32528, 62964, 71973, 83952, 74943, 62964
Cikli erkarutjun@ = 3;

Hajoxutjun !!!
Reply With Quote
Old 26.09.2002, 21:19   #2
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

Решение в лоб:
Вход:
Нужен массив чисел + начальное число.
Алгоритм:
1. получаем digit - ы (тут но проблем, я думаю)
2. сортируем их в нисходящем порядке
2.1. с начала в конец - макс число
2.2. с конца в начало - мин число
3. формируем новое число (тут тоже проблем быть не должно).
4. Добавляем число в массив в конец (например std::vector, CArray).
5. ищем это число в массиве (std::find в первом случае, простой итерацией во втором)
6. (stl вариант) if (it == num.end()) 1 шаг
else break;
//длинна цикла.
7. return num.end() - it;

Можно использовать так же deque.
Использование CList, std::list не советую.
Reply With Quote
Old 27.09.2002, 11:19   #3
Младенец
 
Join Date: 09 2002
Location: ?????????
Posts: 13
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

To Agregat

Perebory mijocov lucum@, chenq karox hashvel lucum
qani vor xndrum N skzbnakan tvi hamar drvac er
@ndhamen@ hetevjal sahmanapakum@`
Code:
 N <= 10  ^  100
Ajsinqn anhrajesht! gtnel matematikakan algoritm:
Reply With Quote
Old 27.09.2002, 14:52   #4
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

Я могу предложить модификацию алгоритма на logN.
В массиве хранишь структуру следующего содержания
{
число;
шаг, на котором встретилось это число;
}
массив сортируешь по поервому параметру.
Поиск делаешь бинарный - время logN
Кроме того, я не думаю, что существует конечная формула для вычисления...
Reply With Quote
Old 28.09.2002, 11:32   #5
Младенец
 
Join Date: 09 2002
Location: ?????????
Posts: 13
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Angry

To Agregat

Iharke ajd qajli mijocov du kkar&acnes qo pe-
rebori
mijocov lucvox algoritmum find gorco-
xutjun@, bajc qo algoritm@ mievnujn ! kmna pe-
rebor
, hnaravor ! vor qo massivi erkarutjun@
darna 10 ^ 100(ajdqan angam el kkatarven qo al-
goritmum gorcoxutjunner@): Lucman exanak@ hnara-
vor ! patasxani tvjal xndrin, bajc qo karciqov
perebori mijocov lucum@ im mtqov chi an-
cel: Xndirn hamarum enq chlucvac ev noric shesh-
tum `
Pntreq matematikakan algoritm !!! (code - n anpajman che!!!)
Reply With Quote
Old 01.10.2002, 14:11   #6
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

Скажем так...

теоретически самая длинная последовательность может быть ~9 * 10 ^ 99.
Но на самом деле, исходя именно из того, что у нас получается разбиение числового поля на подмножества (притом разбиение с пересечеснием в одной точке).
Я не готов показать это, но я почти уверен, что количество множеств состоящих из коротоких циклов настолько велико, что во всех оставшиеся циклы не будут большие.
Исходя из этого, я считаю, что мой алгоритм (решение в лоб, а не перебор) - будет заканчиваться (сходиться) достаточнои быстро.
Нахождение же всех классов эквивалентности - очень дорогая операция и на самом деле придется сделать перебор по всему полю, чтобы построить эту таблицу... долговато будет.
Ну вот такие дела.

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

Удачи...
Reply With Quote
Old 02.10.2002, 09:26   #7
Младенец
 
Join Date: 09 2002
Location: ?????????
Posts: 13
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Post

To Agregat
Agregat jan, du der miak forumistn es vor arajarkum e xndir@ lucox inch vor algoritm, bajc
qez chi tvum, vor tvjal xndrin` &akatajin grohi mijocov lucvox algoritm karox er arajarkel angam
sksnak programist@ : Xndri djvarutjun@ kajanum e nranum vor gtnenq matematikakan algoritm
lucox xndir@ : Asem vor ajdpisi algoritm es el chgitem , der man em galis:

Husov em vor verj@ klucenq
Reply With Quote
Old 02.10.2002, 14:01   #8
Грустно...
 
Agregat's Avatar
 
Join Date: 08 2002
Location: Там, где всегда идут дожди
Age: 35
Posts: 21,717
Downloads: 2
Uploads: 0
Reputation: 250 | 7
Post

De, будем надеяться...
Reply With Quote
Old 04.10.2002, 14:53   #9
Младенец
 
Join Date: 09 2002
Location: ?????????
Posts: 13
Downloads: 0
Uploads: 0
Reputation: 0 | 0
Talking

Budem
Reply With Quote
Sponsored Links
Reply

Thread Tools


На правах рекламы:
реклама

All times are GMT. The time now is 16:58.


Powered by vBulletin® Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.