Возникла такая задача. Имеется дробь, в числителе которой произведение из n факториалов, в знаменателе - произведение из m факториалов. Типа:

Если считать в лоб, то сразу упираешься в машиннуе переполнение. Пытаюсь сортировать факториалы и сначала получать частное двух наибольших, умнажать его на частное двух следующих и т.д. Но что-то все равно кисло получается. Может есть какой-то алгоритм борьбы с такими зверями? Может логарифмы считать? Кто с этим сталкивался?

Кстати очень рульная идея. А почему те не хочешь ее реализовать?
Правда с точностью возникнут траблы... но все же лучше чем ничего.

Это сообщение отредактировал(а) ivashkanet - 9.1.2008, 18:17

Я бы писал длинную арифметику.

Хочу. Просто она пришла мне в голову в процессе написания поста и, когда я пост отправлял, она там еще дозревала.

PPS05, медленно работает - и без того время рассчета не малое. 

Почему? 100! простым последовательным умножением за доли секунды. Зато точность не потеряешь.

 
_Y_, формулой Стирлинга можешь воспользоваться 

почему кисло? они же вроде отлично сокращаться должны исходя из свойств факториала.

Добавлено через 4 минуты и 23 секунды
.. по идее дробь вида 1/K или K/1 остатья должна после сокращаения.

+1, надо для начала всё посокращать, а потом и длинная математика вряд ли понадобится...

_Y_, ты бы хоть пару примеров привёл, какие реальные данные у тебя будут...

Добавлено через 3 минуты и 50 секунд
Кстати что-то мне подсказывает, что здесь пригодится треугольник Паскаля  

Если не ошибаюсь, можно аналитически выразить степени простых множителей в числителе и знаменателе, тогда легко сократить.

Т.е. обрабатываем по множителю и считаем разложение. N! суть произведение последовательных, а в них мы знаем, что, пр., множитель 2 встречается с двойки шагом 2 и т.д., мы можем посчитать его количество в произведении 1 * 2 * ... * N. 

...Хотя, не думаю, что это проще, чем обычное разложение подфакториального числа.

Это сообщение отредактировал(а) PPS05 - 9.1.2008, 20:42

_Y_, в общем, задача интересная, хочется написать код. узнать бы полную формулировку задачи. какие ограничения на m, n, F, G?

неа, 4!*5!/2!*7! = 2/7

source777, угу. я собсвенно про ограничения и спросил потом именно по этой причине.

Предлагаю следующий способ решения:

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] для максимального уменьшения числа сомножителей. 

Как приду домой гляну еще раз.