1. 循环约分法
-- 建立计算最大公约数的函数
DROPFUNCTION IF EXISTS fn_gcd;
delimiter $$
CREATEFUNCTION fn_gcd (n BIGINT, r BIGINT)
RETURNSBIGINT DETERMINISTIC
BEGIN
DECLARE small BIGINT;
DECLARE big BIGINT;
DECLARE left1 BIGINT;
SET small := LEAST(n,r);
SET big := n + r - small;
SET left1 := MOD(big,small);
WHILE left1 > 0 DO
SET big := small;
SET small := left1;
SET left1 := MOD(big,small);
END WHILE;
RETURN small;
END $$
delimiter ;
-- 建立计算组合的函数
DROPFUNCTION IF EXISTS fn_combinationcalc;
delimiter $$
CREATEFUNCTION fn_combinationcalc (n BIGINT, r BIGINT)
RETURNSBIGINT DETERMINISTIC
BEGIN
DECLARE l_r BIGINT;
DECLARE v BIGINT;
DECLARE i BIGINTDEFAULT 1;
DECLARE cd BIGINT;
DECLARE x BIGINT;
IF r > n/2 THEN
SET l_r := n-r;
ELSE
SET l_r := r;
END IF;
IF (l_r=0 or l_r=n) THEN
RETURN 1;
END IF;
SET v := 1;
WHILE i <= l_r DO
SET cd := fn_gcd(v,i);
IF cd > 1 THEN
SET x := i/cd;
SET v := (v/cd) * ((n+1-i)/x);
ELSE
SET v := v * ((n+1-i)/i);
END IF;
SET i := i+1;
END WHILE;
RETURN v;
END $$
delimiter ;
-- 测试
select fn_combinationcalc(10,7);
2. 递归法
-- 建立递归存储过程
DROPPROCEDURE IF EXISTS p_combinationcalc;
SET @@session.MAX_SP_recursion_depth=99;
delimiter $$
CREATEPROCEDURE p_combinationcalc (IN n BIGINT, IN r BIGINT, OUT ret BIGINT)
BEGIN
DECLARE l_r BIGINT;
DECLARE l_ret BIGINT;
IF r > n/2 THEN
SET l_r := n-r;
ELSE
SET l_r := r;
END IF;
IF (l_r=0 or l_r=n) THEN
SET ret := 1;
ELSE IF l_r = 1 THEN
SET ret := n;
ELSE
CALL p_combinationcalc(n-1,r,l_ret);
SET ret := l_ret;
CALL p_combinationcalc(n-1,r-1,l_ret);
SET ret := ret + l_ret;
END IF;
END IF;
END $$
delimiter ;
-- 测试
call p_combinationcalc(10,7,@r);
select @r;
递归法由于不断地进栈出栈,在计算C(70,7)时速度非常慢,已经力不从心,循环法依然很快。
--转自