![>](style_images/2/nav_m.gif)
![]() |
NetLab · Rules · Torrent Tracker · Have a problem? · Eng/Rus |
![]() ![]() ![]() ![]() ![]() |
Welcome Guest ( Log In | Register | Validation ) | Resend Validation Email |
![]() |
|
|
||
Superman Group: Members Posts: 1014 Warn:0% ![]() |
Привет. Мне нужно решить вот такую задачку: Есть "треугольник" который строится из двух параметров. 1) Начальное число N 2) Стартовое вычитаемое число s Строится "треугольник" так: из N вычитаются все натуральные числа от s до 3-х включительно. Из каждого получившегося числа (назовём их N1, N2, ... Nx) снова вычитаются s, но для N=N1 -> s=s, для N=N2 -> s=s-1, для N=N3 -> s=s-2, для N=N4 -> s=s-3, для N=Nx -> s=3. С каждым полученым числом всё повторяется снова пока результат вычитания положителен. Сложно? Смотрите картинку, так понятнее.
Нужно посчитать: 1) СУММУ всех чисел N 2) Колличество нечётных N Господа-товарищи программисты, убедительная просьба не беспокоится. Я знаю, что эта задачка решается элэментарной рекурсией в три строчки. И уже это сделал, НО! При N=50000 и s=300 эта рекурсия длится несколько дней. Мне нужно МАТЕМАТИЧЕСКОЕ решение с минимальным вычислением и максимальной скоростью. Очень приветствуется всякий флуд и флэйм, поскольку он может натолкнуть на идею. Если кто знает как вообже в математике называется что-то подобное, тоже буду признателен. This post has been edited by anatolyArts on 04-08-2009, 07:37 |
||
|
Posted: 01-08-2009, 19:28
(post 2, #907464)
|
||
proRock ![]() Group: Netlab Soldier Posts: 25100 Warn:0% ![]() |
![]() ![]() |
||
|
Posted: 01-08-2009, 19:33
(post 3, #907469)
|
||
Superman Group: Members Posts: 1014 Warn:0% ![]() |
Не знаю как с нобелевкой, но если кто решит - за мной не заржавеет ![]() |
||
|
Posted: 02-08-2009, 00:56
(post 4, #907513)
|
||
Жмурик Group: Members Posts: 442 Warn:0% ![]() |
Есть у мну ректальное впечатление, что решение факториально зависит от параметра Н. Нобелевкой здесь, конечно, не очень пахнет, но какая нить премия в теории чисел - стопудово ![]() |
||
|
Posted: 02-08-2009, 21:10
(post 5, #907642)
|
||
Visionary Group: Members Posts: 5181 Warn:0% ![]() |
Рекурсией "в лоб" - там совсем нездоровые числа идут. ![]() |
||
|
Posted: 03-08-2009, 07:57
(post 6, #907741)
|
||
Superman Group: Members Posts: 1014 Warn:0% ![]() |
Set, я примерно так и делаю. Всё равно очень долго. Параметры всё время разнообразные и таблица в короткий срок сильно разростается. Что не приемлемо в этом случае ибо программа должна влазить в 2-3 килобайта. Поэтому, она(таблица) всё время урезается и содержит только базовые пары. Не сильное ускорение. |
||
|
Posted: 03-08-2009, 19:00
(post 7, #907779)
|
||
Сварливый Мозг Клуба ![]() Group: Roots Posts: 22883 |
![]() P.S. А что если S = -1 ? ![]() |
||
|
Posted: 03-08-2009, 20:13
(post 8, #907792)
|
||||||||
Superman Group: Members Posts: 1014 Warn:0% ![]() |
НО КАК БЫТЬ ДАЛЬШЕ?!!!! ![]()
|
||||||||
|
Posted: 03-08-2009, 21:53
(post 9, #907811)
|
||
ОТК АудиоРелизов Group: News makers Posts: 2641 Warn:0% ![]() |
Чёрт возьми, зачем называть натуральные числа реальными? ![]() А задачка интересная. Ща подумаем. |
||
|
Posted: 04-08-2009, 06:04
(post 10, #907845)
|
||
Сварливый Мозг Клуба ![]() Group: Roots Posts: 22883 |
чиста от нечего делать попробовал сохранять результаты от итерационных (рекурсивных) вычислений в массиве. По-простому, без всяких там хеш-функций. Не сильно оптимально по использованию памяти, конечно. Да и с точностью некоторые проблемы, ибо там суммы довольно быстро вылазят за 64 бита. Но (50000, 300) считается за 1 минуту и 6 секунд. Да, я понимаю, что это далеко не 2-3 килобайта. Это даже не 2-3 мегабайта. Но может стоит табличку статично посчитать и держать в файле? И просто дергать из нее значения... Кстати, если оно несколько дней считать рекурсивно может, то значит с памятью особых проблем нет. Как минимум стека хватает на туеву хучу рекурсивных вызовов ![]() |
||
|
Posted: 04-08-2009, 07:38
(post 11, #907851)
|
||
Superman Group: Members Posts: 1014 Warn:0% ![]() |
![]() FiL, это на девелопментовой машине и памяти и скорости хватает. А там где оно бежать будет могут быть проблемы. This post has been edited by anatolyArts on 04-08-2009, 07:41 |
||
|
Posted: 04-08-2009, 12:11
(post 12, #907864)
|
||
Штатный бредогенератор. Group: Members Posts: 1764 Warn:0% ![]() |
При третьем подходе в голове возникла мысль: "напишите программу деления для компьютера без заранее реализованной инструкции процессора". Хорошая чесалка для мозгов, подвисают. |
||
|
Posted: 04-08-2009, 18:00
(post 13, #907901)
|
||
Сварливый Мозг Клуба ![]() Group: Roots Posts: 22883 |
Енот, ну писал я такое. И что? делить-то как раз не сложно. |
||
|
Posted: 04-08-2009, 19:22
(post 14, #907928)
|
||
Part time flamer Group: Read Only Posts: 7784 Warn:0% ![]() |
FiL LISP ? |
||
|
Posted: 04-08-2009, 21:03
(post 15, #907948)
|
||
Сварливый Мозг Клуба ![]() Group: Roots Posts: 22883 |
|
||
![]() |