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 [email protected]: Gtnum enq ajd tvi tvanshan-
nerov stacvox amenamec ev amenapoqr [email protected]: Ajnu-
hetev hashvum nranc [email protected]: Orinak, erb
N = 174, apa max = 741 ev min = 147
max - min = 594:

Ajspisov N tvic kstananq mi nor tiv: [email protected] kanenq
ajd tvi het: Kstananq tveri hajordakanutjun: Ajd
hajordakanutjan mej inch vor texic Ksatcvi cikl
(qani vor stacvox tveri [email protected] verjavor hat !):
Anhrajesht ! gtnel ajd cikli [email protected]:
Harkavor ! gtnel [email protected], [email protected] anpajman che:

Orinak`
N = 8252
8252, 6264, 4176, 6174, 6174:
Cikli [email protected] = 0;
N = 32528,
32528, 62964, 71973, 83952, 74943, 62964
Cikli [email protected] = 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 | 8
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 [email protected], chenq karox hashvel lucum
qani vor xndrum N skzbnakan tvi hamar drvac er
@[email protected] hetevjal [email protected]`
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 | 8
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-
[email protected], bajc qo [email protected] mievnujn ! kmna pe-
rebor
, hnaravor ! vor qo massivi [email protected]
darna 10 ^ 100(ajdqan angam el kkatarven qo al-
goritmum [email protected]): Lucman [email protected] hnara-
vor ! patasxani tvjal xndrin, bajc qo karciqov
perebori mijocov [email protected] 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 | 8
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 [email protected] lucox inch vor algoritm, bajc
qez chi tvum, vor tvjal xndrin` &akatajin grohi mijocov lucvox algoritm karox er arajarkel angam
sksnak [email protected] : Xndri [email protected] kajanum e nranum vor gtnenq matematikakan algoritm
lucox [email protected] : Asem vor ajdpisi algoritm es el chgitem , der man em galis:

Husov em vor [email protected] 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 | 8
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 22:02.


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