Цитата(_Y_ @ 9.1.2008, 17:13  ) |
| Может логарифмы считать |
Кстати очень рульная идея. А почему те не хочешь ее реализовать?
Правда с точностью возникнут траблы... но все же лучше чем ничего.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > посчитать дробь, состоящую из факториалов |
| Автор: _Y_ 9.1.2008, 18:13 | ||
Возникла такая задача. Имеется дробь, в числителе которой произведение из n факториалов, в знаменателе - произведение из m факториалов. Типа:
Если считать в лоб, то сразу упираешься в машиннуе переполнение. Пытаюсь сортировать факториалы и сначала получать частное двух наибольших, умнажать его на частное двух следующих и т.д. Но что-то все равно кисло получается. Может есть какой-то алгоритм борьбы с такими зверями? Может логарифмы считать? Кто с этим сталкивался? |
| Автор: ivashkanet 9.1.2008, 18:16 | ||
Кстати очень рульная идея. А почему те не хочешь ее реализовать? Правда с точностью возникнут траблы... но все же лучше чем ничего. |
| Автор: PPS05 9.1.2008, 18:23 |
| Я бы писал http://comp-science.narod.ru/DL-AR/okulov.htm. |
| Автор: _Y_ 9.1.2008, 18:32 | ||||
Хочу. Просто она пришла мне в голову в процессе написания поста и, когда я пост отправлял, она там еще дозревала. PPS05, медленно работает - и без того время рассчета не малое. |
| Автор: PPS05 9.1.2008, 18:37 | ||
Почему? 100! простым последовательным умножением за доли секунды. Зато точность не потеряешь. |
| Автор: Sartorius 9.1.2008, 18:49 |
| _Y_, формулой http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB |
| Автор: stab 9.1.2008, 20:10 | ||
почему кисло? они же вроде отлично сокращаться должны исходя из свойств факториала. Добавлено через 4 минуты и 23 секунды .. по идее дробь вида 1/K или K/1 остатья должна после сокращаения. |
| Автор: source777 9.1.2008, 20:14 | ||
_Y_, ты бы хоть пару примеров привёл, какие реальные данные у тебя будут... Добавлено через 3 минуты и 50 секунд Кстати что-то мне подсказывает, что здесь пригодится треугольник Паскаля  |
| Автор: PPS05 9.1.2008, 20:36 |
| Если не ошибаюсь, можно аналитически выразить степени простых множителей в числителе и знаменателе, тогда легко сократить. Т.е. обрабатываем по множителю и считаем разложение. N! суть произведение последовательных, а в них мы знаем, что, пр., множитель 2 встречается с двойки шагом 2 и т.д., мы можем посчитать его количество в произведении 1 * 2 * ... * N. ...Хотя, не думаю, что это проще, чем обычное разложение подфакториального числа. |
| Автор: stab 9.1.2008, 20:48 |
| _Y_, в общем, задача интересная, хочется написать код. узнать бы полную формулировку задачи. какие ограничения на m, n, F, G? |
| Автор: source777 9.1.2008, 21:26 | ||
|
| Автор: stab 10.1.2008, 08:29 |
| source777, угу. я собсвенно про ограничения и спросил потом именно по этой причине. |
| Автор: mmvds 10.1.2008, 12:50 |
| Предлагаю следующий способ решения: 1) Если чисел f[i] и g[i] немного и они не большие, то действительно достаточно создать еще два массива для числителя и знаменателя заполняя их множителями, а затем делать поиск элементов присутствующих и в том и другом массиве и заменять их например на 1, после чего перемножить все множители, не равные 1 для обоих массивов и поделить один на другой. 2) Если чисел f[i] и g[i] много и размерность массивов не позволяет записать все их множители, то будем сокращать кол-во множителей для m>n m!/n!=mnog(m-n,m) где функция mnog(m-n,n) добавляет в массив с сомножителями числа от m-n до n. Осталось только придумать алгоритм выбора этих самых m и n из f[i], g[i] для максимального уменьшения числа сомножителей. Как приду домой гляну еще раз. |