算法系列：求幂算法 - 文章 - 伯乐在线
& 算法系列：求幂算法
1.快速求幂算法
在这篇文章我会展示怎样通过求一个数的幂的基本思路，来引导我们发现一些抽象的东西比如半群和含幺半群。
有一个很有名的对一个数求幂的算法,也就是说,求一个数x的n次方或者这样简单表示：x^n。在的4.63节 求幂值中提出这个算法。
这个算法很简单的实现就是x乘以自己n次，但是在这里当然会提供一种比这种方式更快的算法。正在谈论的算法通常被称作二进制法(binary method)、梯度求幂(the powering ladder)或者反复平方法(repeated-squaring algorithm)
假设我们想计算2^23，在这里x = 2，n = 23，这个算法首先把23表示成二进制的形式10111。扫描这个二进制数(10111)每当遇到0或1，则相应的求x的平方或者乘以x。
这个方法有一个问题就是它扫描二进制表示的数是从左到右进行的，但是对于计算机通常以相反的方向能够更容易实现，因此Knuth提出一个替代的算法。
一个出自的4.63节的算法A的简单实现如下：
; html-script: false ]
function power1($x, $n) {
while (true) {
$t = $n % 2;
$n = floor($n/2);
if ($t == 1) {
$y = $y * $x;
if ($n == 0) {
$x = $x * $x;
return $y;
1234567891011121314151617181920
; html-script: false ]&&&&function power1($x, $n) {&&&&&&&&$y = 1;&&&&&&&&&while (true) {&&&&&&&&&&&&$t = $n % 2;&&&&&&&&&&&&$n = floor($n/2);&&&&&&&&&&&&&if ($t == 1) {&&&&&&&&&&&&&&&&$y = $y * $x;&&&&&&&&&&&&}&&&&&&&&&&&&&if ($n == 0) {&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&}&&&&&&&&&&&&&$x = $x * $x;&&&&&&&&}&&&&&&&&&return $y;&&&&}
这个函数需要两个整数，$x和$n然后返回$x的$n次幂作为结果。
首先创建一个辅助变量$y并且初始化为1，把它作为乘法的主体。
然后函数在每次循环迭代的时候扫描$n的二进制表示的数。如果遇到1则$y乘上$x，然后赋值回$y。每次循环都会计算$x的平方，并且把它赋值回$x。
遇到1意味着当前$n的值不能被2整除，换句话说就是，$n % 2 == 1。
同样的每次循环$n都会折半，然后向下取整得到结果。当$n等于0的时候，我们结束循环并且返回$y的值。
函数power能够这样被调用:
; html-script: false ]
1024 == power1(2, 10);
; html-script: false ]&&&&1024 == power1(2, 10);&&&&=& true
我能想象你现在就像这个gif中的男孩。
尽管这个算法看起来像一个 “呵呵，真有意思” (无语了，你别说了，我根本不关心)的故事，实际上当它用来计算非常的大数时时十分高效的。例如有很多的素数测试算法都是依赖这个算法的不同变式。
2.增加一些抽象
到目前为止还没有什么意想不到的事情发生，但是如果我们注意到求一个数的幂实际上和一个数自乘多次是等价的，我们也可以看到乘法实际上等价于自加多次。举个例子2 * 5能够像这样被计算2 + 2 + 2 + 2 + 2。
我们能把这个算法转换成一种更普遍的形式使它能同样应用在乘法还有加法上吗?当然可以，我们仅仅需要改变几样东西。
在当前实现中，我们创建$y作为乘法的主体，并设置为1。如果我们想把算法用在加法上，我们需要把$y设置为0。因此我们仅需要改变函数的单位元素的值。
第二步要提供一个函数给我们的算法，它能够作乘法或者加法。为了实现这个目的我们会传递一个担当二元运算的函数。例如：一个需要两个参数的函数。这个函数需要遵循以下的规则。必须满足：a·（ b · c ） = (a · b ) · c。还要求返回结果的类型必须和两个输入参数的类型一致。
幸运的是加法和乘法都满足，因此我们能够仅在一个函数中包含他们然后把它传递给我们的power算法。
这里是这个算法新的实现：
; html-script: false ]
function power2($x, $n, $id, $f) {
while (true) {
$t = $n % 2;
$n = floor($n/2);
if ($t == 1) {
$y = $f($y, $x);
if ($n == 0) {
$x = $f($x, $x);
return $y;
1234567891011121314151617181920
; html-script: false ]&&function power2($x, $n, $id, $f) {&&&&&&&&$y = $id;&&&&&&&&&while (true) {&&&&&&&&&&&&$t = $n % 2;&&&&&&&&&&&&$n = floor($n/2);&&&&&&&&&&&&&if ($t == 1) {&&&&&&&&&&&&&&&&$y = $f($y, $x);&&&&&&&&&&&&}&&&&&&&&&&&&&if ($n == 0) {&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&}&&&&&&&&&&&&&$x = $f($x, $x);&&&&&&&&}&&&&&&&&&return $y;&&&&}
我们能够像这样调用它:
; html-script: false ]
1024 == power2(2, 10, 1, function ($a, $b) { return $a * $b; });
; html-script: false ]&& 1024 == power2(2, 10, 1, function ($a, $b) { return $a * $b; });&&&&=& true
记住传递进我们算法的运算必须是可结合的,举个例子,减法不能被用在这里由于10 - ( 5 - 3) = 8但是(10 - 5 ) - 3 = 2。
3.附加更抽象的概念
从数学的角度说这个算法能够在任何满足结合律的代数结构中有效(在这个案例中就是整数的乘法和加法)，换言之，它能够用在半群中，引用一本关于的书。
一个半群的集合S含有一个可结合的运算 · ；
也就是说,x·(y · z) = (x · y) · z 对于所有的x, y, z ∈ S都成立。
一个半群的集合S含有一个可结合的运算 · ；也就是说,x·(y · z) = (x · y) · z 对于所有的x, y, z ∈ S都成立。
同样，这个集合必须有一个单位元素使得它有一个独异点:
一个独异点是一个集合M含有一个可结合运算·；伴有一个单位元素e∈ M满足e·x = x· e =
x对于所有x∈ M都成立。
一个独异点是一个集合M含有一个可结合运算·；伴有一个单位元素e∈ M满足e·x = x· e =&&x对于所有x∈ M都成立。
在这个预设条件下，有什么我们经常用在编程上的结构能使用这个算法的呢？如果你是一个web开发者，你不需要费大力气去获取strings。对于字符串（strings），使用string append作为二元操作而且空字符串(empty string)作为单位元素同样会带来类似的结果。如果一个字符串想重复n次,我们创建下面的函数:
; html-script: false ]
function repeat($s, $n) {
return power2($s, $n, "", function ($a, $b) {
return $a . $b;
; html-script: false ]&&&&function repeat($s, $n) {&&&&&&&&return power2($s, $n, "", function ($a, $b) {&&&&&&&&&&&&&&&&&& return $a . $b;&&&&&&&&&&&&&& });&&&&}
; html-script: false ]
"aaaaaaaaaa" == repeat("a", 10);
; html-script: false ]&&&&"aaaaaaaaaa" == repeat("a", 10);&&&&=& true
现在考虑一下数组(arrays)(或者其它语言称为列表(lists))。我们想把一个数组复制n次。在这里空数组是单位元素，对PHP来说array_merge会用来作为二元操作。
; html-script: false ]
function repeat_el($el, $n) {
return power2(array($el), $n, array(), function ($a, $b) {
return array_merge($a, $b);
; html-script: false ]&&&&function repeat_el($el, $n) {&&&&&&&&return power2(array($el), $n, array(), function ($a, $b) {&&&&&&&&&&&&&&&&return array_merge($a, $b);&&&&&&&&&&&&&& });&&&&}
; html-script: false ]
$arr = repeat_el("a", 10);
10 == count($arr);
; html-script: false ]&&&&$arr = repeat_el("a", 10);&&&&10 == count($arr);&&&&=& true
从上不难看出,像求一个数幂运算的这样简单事情给我们带来一个优雅的算法,它能被运用一些事情上,像重复的东西还有数组里的元素。
4.延伸阅读
这里的快速求幂算法是基于中，卷二的4.63节。
所有的关于工作原理的解答都可以在TAOCP或者在这本书上找到,这本书的PDF版本在作者的主页上可以免费下载。浏览章节：“Computing with large integers - The repeated squaring algorithm”
如果你想学习这个算法的一些用法或者想知道更多这个算法背后的理论,请查阅这本叫做的书。这本书非常了不起，它定义了不同类型的函数和使用类型系统确定函数是否是可结合的，二元的等等。作者是C++STL的设计者,所以这本书的内容可能会比较理论化,然后它能够直接应用在面向对象编程(OOP)。
半群 和 含幺半群的引用来自于。一本非常有趣的书，如果你对计算群论有兴趣的话。
如果你想学习更多有关幺半群还有它们的实现。里的有个章节非常有趣的介绍它:
这是一个十分有趣的练习,通过实现这些概念使用PHP和OOP,对于不喜欢使用PHP无爱的人,也可以选择其它你喜欢的语言。
5.你是想说Haskell?
既然我已经提及一本Haskell的书，这里有一个Haskell实现的求幂算法，使用的递归算法来自于这本书
; html-script: false ]
power :: (Eq a, Integral b) =& (a -& a -& a) -& a -& b -& a
power f a n
| n == 1 = a
| even n = square a (n `div` 2)
| otherwise = f a (square a ((n-1) `div` 2))
square a' n' = f (power f a' n') (power f a' n')
; html-script: false ]&&&&power :: (Eq a, Integral b) => (a -> a -> a) -> a -> b -> a&&&&power f a n&&&&&&| n == 1 = a&&&&&&| even n = square a (n `div` 2)&&&&&&| otherwise = f a (square a ((n-1) `div` 2))&&&&&&where&&&&&&&&square a' n' = f (power f a' n') (power f a' n')
几个函数调用的结果：
; html-script: false ]
*Main& :load pow.hs
[1 of 1] Compiling Main
( pow.hs, interpreted )
Ok, modules loaded: Main.
*Main& power (*) 2 10
*Main& power (+) 2 10
*Main& power (++) &a& 10
&aaaaaaaaaa&
; html-script: false ]&&*Main> :load pow.hs&&&&[1 of 1] Compiling Main&&&&&&&&&&&& ( pow.hs, interpreted )&&&&Ok, modules loaded: Main.&&&&*Main> power (*) 2 10&&&&1024&&&&*Main> power (+) 2 10&&&&20&&&&*Main> power (++) "a" 10&&&&"aaaaaaaaaa"
正如你所看到的,这个函数调用一个function(a-&a-&a)，例子中，对于integers使用*或者+,对于lists使用++。
我希望你会觉得这边文章有趣或者激起你学习与编程有关的数学的欲望。因为我认为我们掌握得越多数学方面的知识，我们就能更好的使用抽象的东西。
关于作者：
可能感兴趣的话题
抽象就是STL中power算法的实现，泛型编程确实挺有意思的
关于伯乐在线博客
在这个信息爆炸的时代，人们已然被大量、快速并且简短的信息所包围。然而，我们相信：过多“快餐”式的阅读只会令人“虚胖”，缺乏实质的内涵。伯乐在线内容团队正试图以我们微薄的力量，把优秀的原创文章和译文分享给读者，为“快餐”添加一些“营养”元素。
新浪微博：
推荐微信号
（加好友请注明来意）
– 好的话题、有启发的回复、值得信赖的圈子
– 分享和发现有价值的内容与观点
– 为IT单身男女服务的征婚传播平台
– 优秀的工具资源导航
– 翻译传播优秀的外文文章
– 国内外的精选文章
– UI,网页，交互和用户体验
– 专注iOS技术分享
– 专注Android技术分享
– JavaScript, HTML5, CSS
– 专注Java技术分享
– 专注Python技术分享
& 2018 伯乐在线博客分类：
对于给定的两个集合，使用哈希表可以在线性时间复杂度内得到他们的交集和并集，具体说明如下：
假设有集合A={1, 7, 5, 13, 9, 10, 11}, B={5, 7, 10, 1, 18, 12},
1)求交集，需要得到结果：A∩B={1, 5, 7,10}
&& 思路如下：
&& ①建立一个哈希表(HashTable)，其键(KEY)表示集合中数字的值，其值(VALUE)表示集合中数字出现的次数
&& ②遍历集合A，将集合中的每个数字(KEY)插入哈希表，每个数字的出现次数(VALUE)设置为1
&& ③遍历集合B，对于集合中的每个数字：
&&&&&&&&&&&&&&&&&& 如果哈希表中已经存在该数字，将对应的VALUE改为2
&&&&&&&&&&&&&&&&&& 如果哈希表中不存在该数字，忽略
&&& ④遍历哈希表，输出VALUE为2的数字，即得到A和B的交集
2) 求并集，需要得到结果：AUB={1,5,7,9,10,11,12,13,18}
&&&& 思路如下：
&&&& ①建立一个哈希表(HashTable)，其键(KEY)表示集合中数字的值，其值(VALUE)可以无视
&&&& ②遍历集合A，将集合中的每个数字(KEY)插入哈希表
&&&& ③遍历集合B，对于集合中的每个数字：
&&&&&&&&&&&&&&&&&&& 如果哈希表中已经存在该数字，忽略
&&&&&&&&&&&&&&&&&&& 如果哈希表中不存在该数字，将这个数字插入哈希表
&&&& ④遍历哈希表，输出哈希表中的每个KEY，即为A和B的并集
&&&&&&&& 上面以两个集合为例说明了交集和并集的求法，事实上，上述算法可以很方便的扩展到3个或3个以上的集合
的求交集和求并集。另外求并集时，由于哈希表的值（VALUE）部分不需要用到，所以这个数据结构也可以更换为
哈希集（HashSet)。
浏览: 640949 次
来自: 北京
感觉就是知识采集一样，博主能不能整理一下
whxtbest 写道2里面：如果T本身就是重复的话
2里面：如果T本身就是重复的话
比如S是aaab，T是aa ...
收集的资料挺多的 哈哈
(window.slotbydup=window.slotbydup || []).push({
id: '4773203',
container: s,
size: '200,200',
display: 'inlay-fix'您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
求N！的算法例：伪代码.PPT 47页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
求N！的算法例：伪代码
你可能关注的文档：
··········
··········
贪心法 （Greedy Algorithm） 贪心算法的基本思想是从小的方案推广到大的解决方法。它分阶段工作，在每一个阶段选择最好的方案，而不考虑其后的结果如何。 贪心法主要用于求解最优问题，但它已经发展成为一种通用的算法设计技术：核心是： 可行性——每一步选择必须满足问题的约束； 局部最优——它是当前可选择的方案中最优的； 不可取消性——选择一旦做出，在算法的其后步骤中不能被取消。 贪心法不能确定得到的最后解是最优的，也不能用于求解最大或最小问题。在算法的效率上，贪心法快速，程序实现需要的内存开销也较小。但遗憾的是，它们往往是不正确的。然而一旦被证明是正确的，其执行效率和速度有很大的优势。 30 ?
背包问题（分数背包问题）
假设有一个体积为M的背包以及n种物品，价值是
种物品的体积是 wi 。假设每种物品都可以取其一部分装入背包， xi 是取第i 种物品装进背包的百分比,
那么装入背包的总价值是
所谓一个最优装包方法，就是要找到一组 xi
使得在约束条件
下，背包中物品总价值
达到最大。
每步该做些什么? A:
把某种物品的一部分放进包里. Q:
以什么标准来确定“贪心”? ?
最大价值 ?
最小体积 ?
最大的价值密度pi / wi
M = 20, (p1, p2, p3) = (25, 24, 15) (w1, w2, w3)= (18, 15, 10) 答案是...?
( 0, 1, 1/2 ) P = 31.5 * 分治法 （Divide and Conquer ） 基本思想就是，将一个较大规模的问题分解为若干个较小规模的子问题，找出子问题的解，然后把各个子问题的解合并成整个问题的解。 分治法的分（Divide）是指划分较大问题为若干个较小问题，递归求解子问题；分治法的治（Conquer）是指从小问题的解构建大问题的解。 L型三方块覆盖方阵问题 金块问题 求一个整数序列的第k个大数问题 分治法的实现很可能可以采用递归的形式
32 金块问题: （挑出最重和最轻的两个金块） n=8时，普通方法需要的比较次数：(n-1)+(n-2) = 13。 分治法的比较次数：
比较次数 4 4 2 10 n=16时，普通方法需要的比较次数： (n-1)+(n-2) = 29。 分治法的比较次数：10+10+2 = 22
C(n) = 2 C(n/2) + 2
(当n&2) = 3n/2 -2 (当n为2的幂)
33 S N个元素 S1 N1个元素 S2 N2个元素 元素 & e 元素 & e ? 基于问题分解 ?求解集合S的第K大整数问题的一种递归思路
e N0个 基准元素e 元素 = e 当k&N0+N1时，转化成：求S2的第k - (N0+N1)个大问题 当k&=N1时，转化成：求S1的第k 个大问题 当N1&k&=N0+N1时，S的第k个大整数就是e * 动态规划法 （Dynamic Programming） 动态规划被描述为：如果一个较大问题可以被分解为若干个子问题，且子问题具有重叠，可以将每个子问题的解存放到一个表中，这样就可以通过查表解决问题。 核心思想是以空间换时间！ 第n个Fibonacci数的计算 0-1背包问题 钢条切割问题 35 第n个Fibonacci数的计算
F(N) = F(N – 1) + F(N – 2)
Fib( int N )
if ( N &= 1 )
Fib( N - 1 ) + Fib( N - 2 );
} F6 F2 F1 F0 F3 F1 F2 F1 F0 F2 F1 F0 F3 F1 F2 F1 F0 F3 F1 F2 F1 F0 F4 F4 F5 麻烦之处:
大量重复子问题的计算，计算量呈爆发式增长！ 解决方法:
从小算到大，记录最近两个数据，就可以计算后一个数据。 36 钢条切割问题 长度:
1 | 2 | 3 | 4 | 5
正在加载中，请稍后...}