NetLab · Rules · Torrent Tracker · Have a problem? · Eng/Rus  Help      Search      Members      Gallery      Calendar
Welcome Guest ( Log In | Register | Validation ) Resend Validation Email
>  NetLab -> Forums -> Сайт -> Флейм -> Topic: Нужна помощь зала

 

> Нужна помощь зала, Математики, где вы?
Print topic |
 anatolyArts Member is Offline
   Posted: 01-08-2009, 15:35 (post 1, #907427)

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. С каждым полученым числом всё повторяется снова пока результат вычитания положителен. Сложно? Смотрите картинку, так понятнее.
SPOILER!

Нужно посчитать:
1) СУММУ всех чисел N
2) Колличество нечётных N

Господа-товарищи программисты, убедительная просьба не беспокоится. Я знаю, что эта задачка решается элэментарной рекурсией в три строчки. И уже это сделал, НО! При N=50000 и s=300 эта рекурсия длится несколько дней. Мне нужно МАТЕМАТИЧЕСКОЕ решение с минимальным вычислением и максимальной скоростью.

Очень приветствуется всякий флуд и флэйм, поскольку он может натолкнуть на идею. Если кто знает как вообже в математике называется что-то подобное, тоже буду признателен.

This post has been edited by anatolyArts on 04-08-2009, 07:37
PM Email Poster Shared files
Top Bottom
 Гордый Member is Offline
 Posted: 01-08-2009, 19:28 (post 2, #907464)

proRock
Group: Netlab Soldier
Group: Netlab Soldier
Posts: 25100
Warn:0%-----
QUOTE (anatolyArts @ 01-08-2009, 14:35)
Очень приветствуется всякий флуд и флэйм, поскольку он может натолкнуть на идею. Если кто знает как вообже в математике называется что-то подобное, тоже буду признателен.
Я насчёт по-флудить... а ты уверен, что эта проблема в математике уже решена? Может нобелевку за это дело положено? :actu: :diablo:
PM
Top Bottom
 anatolyArts Member is Offline
 Posted: 01-08-2009, 19:33 (post 3, #907469)

Superman

Group: Members
Posts: 1014
Warn:0%-----
Не знаю как с нобелевкой, но если кто решит - за мной не заржавеет :beer:
PM Email Poster Shared files
Top Bottom
 Ben Member is Offline
 Posted: 02-08-2009, 00:56 (post 4, #907513)

Жмурик

Group: Members
Posts: 442
Warn:0%-----
Есть у мну ректальное впечатление, что решение факториально зависит от параметра Н. Нобелевкой здесь, конечно, не очень пахнет, но какая нить премия в теории чисел - стопудово :)
PM Email Poster Shared files MSN
Top Bottom
 Set Member is Offline
 Posted: 02-08-2009, 21:10 (post 5, #907642)

Visionary

Group: Members
Posts: 5181
Warn:0%-----
Рекурсией "в лоб" - там совсем нездоровые числа идут. :) Пихай сумму N и число нечётных N для каждой ветки в хэш-таблицу по её паре (N, s) - тогда не надо будет просчитывать одно и тоже для одинаковых веток.
PM
Top Bottom
 anatolyArts Member is Offline
 Posted: 03-08-2009, 07:57 (post 6, #907741)

Superman

Group: Members
Posts: 1014
Warn:0%-----
Set, я примерно так и делаю. Всё равно очень долго. Параметры всё время разнообразные и таблица в короткий срок сильно разростается. Что не приемлемо в этом случае ибо программа должна влазить в 2-3 килобайта. Поэтому, она(таблица) всё время урезается и содержит только базовые пары. Не сильное ускорение.
PM Email Poster Shared files
Top Bottom
 FiL Member is Offline
 Posted: 03-08-2009, 19:00 (post 7, #907779)

Сварливый Мозг Клуба
Group: Roots
Group: Roots
Posts: 22885
QUOTE (anatolyArts @ 01-08-2009, 08:35)

Строится "треугольник" так: из N вычитаются все реальные числа от s до 3-х включительно.
Не, ребята. С такими условиями оно работать не будет. Вычитать все реальные числа из некоего промежутка - это задача не для слабонервных :)

P.S. А что если S = -1 ? :)
PM Email Poster ICQ AOL MSN
Top Bottom
 anatolyArts Member is Offline
 Posted: 03-08-2009, 20:13 (post 8, #907792)

Superman

Group: Members
Posts: 1014
Warn:0%-----
QUOTE (FiL @ 03-08-2009, 16:00)
Не, ребята. С такими условиями оно работать не будет.
Ну почему же? Вот первый шаг я, можно сказать, сделал: ту часть "треугольника" где числа ещё не отпадают я посчитал. Тут на картинке видно.
SPOILER!
Вертикальная сумма каждого этапа (до начала отпада) равна среднему арифметическому всех чисел этапа умноженному на колличество чисел. По природе "треугольника" чтобы посчитать среднее арифметическое, достаточно вычесть из N среднее число s. 25-((5+3)/2) и так по всем этапам. Колличесто же чисел соответствует диагонали номер s-2 треугольника паскаля.
SPOILER!
Всего "не отпадающих" этапов = N/s. Считается просто и быстро.

НО КАК БЫТЬ ДАЛЬШЕ?!!!! :fear2:


QUOTE
P.S. А что если S = -1 ? :)
По определению s >= 3. Я просто забыл сказать.
PM Email Poster Shared files
Top Bottom
 dmvn Member is Offline
 Posted: 03-08-2009, 21:53 (post 9, #907811)

ОТК АудиоРелизов

Group: News makers
Posts: 2641
Warn:0%-----
Чёрт возьми, зачем называть натуральные числа реальными? :) Исправьте, плз, а то не по-русски получается.

А задачка интересная. Ща подумаем.
PM Email Poster Shared files Users Website
Top Bottom
 FiL Member is Offline
 Posted: 04-08-2009, 06:04 (post 10, #907845)

Сварливый Мозг Клуба
Group: Roots
Group: Roots
Posts: 22885
чиста от нечего делать попробовал сохранять результаты от итерационных (рекурсивных) вычислений в массиве. По-простому, без всяких там хеш-функций. Не сильно оптимально по использованию памяти, конечно. Да и с точностью некоторые проблемы, ибо там суммы довольно быстро вылазят за 64 бита. Но (50000, 300) считается за 1 минуту и 6 секунд.

Да, я понимаю, что это далеко не 2-3 килобайта. Это даже не 2-3 мегабайта. Но может стоит табличку статично посчитать и держать в файле? И просто дергать из нее значения...

Кстати, если оно несколько дней считать рекурсивно может, то значит с памятью особых проблем нет. Как минимум стека хватает на туеву хучу рекурсивных вызовов :)
PM Email Poster ICQ AOL MSN
Top Bottom
 anatolyArts Member is Offline
 Posted: 04-08-2009, 07:38 (post 11, #907851)

Superman

Group: Members
Posts: 1014
Warn:0%-----
QUOTE (dmvn @ 03-08-2009, 18:53)
Чёрт возьми, зачем называть натуральные числа реальными? :) Исправьте, плз, а то не по-русски получается.
Спасибо, исправил. Я просто плохо перевёл. Никогда не учил математику по русски. :)

FiL, это на девелопментовой машине и памяти и скорости хватает. А там где оно бежать будет могут быть проблемы.

This post has been edited by anatolyArts on 04-08-2009, 07:41
PM Email Poster Shared files
Top Bottom
 Enot Pk Member is Offline
 Posted: 04-08-2009, 12:11 (post 12, #907864)

Штатный бредогенератор.

Group: Members
Posts: 1764
Warn:0%-----
При третьем подходе в голове возникла мысль: "напишите программу деления для компьютера без заранее реализованной инструкции процессора".

Хорошая чесалка для мозгов, подвисают.
PM Email Poster Users Website ICQ MSN
Top Bottom
 FiL Member is Offline
 Posted: 04-08-2009, 18:00 (post 13, #907901)

Сварливый Мозг Клуба
Group: Roots
Group: Roots
Posts: 22885
Енот,
ну писал я такое. И что? делить-то как раз не сложно.
PM Email Poster ICQ AOL MSN
Top Bottom
 Lord KiRon Member is Offline
 Posted: 04-08-2009, 19:22 (post 14, #907928)

Part time flamer

Group: Read Only
Posts: 7784
Warn:0%-----
FiL
LISP ?
PM
Top Bottom
 FiL Member is Offline
 Posted: 04-08-2009, 21:03 (post 15, #907948)

Сварливый Мозг Клуба
Group: Roots
Group: Roots
Posts: 22885
QUOTE (Lord KiRon @ 04-08-2009, 12:22)
FiL
LISP ?
не, при чем тут лисп? просто нужна была как-то библиотека для работы с целыми числами произвольной длины. Ну и писал что-то подобное. Умножение, деление... сначала реализовав сложение и вычитание.
PM Email Poster ICQ AOL MSN
Top Bottom
Флейм
Topic Options
>  NetLab -> Forums -> Сайт -> Флейм -> Topic: Нужна помощь зала
Powered by Invision Power Board v1.3.1 Final.