MySQL存储程序计算组合数C(n,r)的两种方法 _MySQL, Oracle及数据库讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  MySQL, Oracle及数据库讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 1973 | 回复: 0   主题: MySQL存储程序计算组合数C(n,r)的两种方法         下一篇 
shunli
注册用户
等级:新兵
经验:36
发帖:59
精华:0
注册:2011-9-23
状态:离线
发送短消息息给shunli 加好友    发送短消息息给shunli 发消息
发表于: IP:您无权察看 2015-8-14 10:22:11 | [全部帖] [楼主帖] 楼主


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)时速度非常慢,已经力不从心,循环法依然很快。

--转自北京联动北方科技有限公司




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论