非递归版求幂函数

#include<stdio.h>
int MinSubsequenceSum(const int A[],int n)
{
    int i,sum,MinSum;
    sum=MinSum=0;
    for(i=0;i<n;i++)
    {
        sum+=A[i];
        if(sum<MinSum)
            MinSum=sum;
        if(sum>0)
            sum=0;
    }
    return MinSum;
}
void main()
{
    int arr[10]={3,4,-2,5,-4,6,-2,8,-9,-23};
    int min=MinSubsequenceSum(arr,10);
    printf("%d\n",min);
}

参考如下：

快速求正整数次幂，当然不能直接死乘。举个例子：

3 ^ 999 = 3 * 3 * 3 * … * 3

直接乘要做998次乘法。但事实上可以这样做，先求出2^k次幂：

3 ^ 2 = 3 * 3
3 ^ 4 = (3 ^ 2) * (3 ^ 2)
3 ^ 8 = (3 ^ 4) * (3 ^ 4)
3 ^ 16 = (3 ^ 8) * (3 ^ 8)
3 ^ 32 = (3 ^ 16) * (3 ^ 16)
3 ^ 64 = (3 ^ 32) * (3 ^ 32)
3 ^ 128 = (3 ^ 64) * (3 ^ 64)
3 ^ 256 = (3 ^ 128) * (3 ^ 128)
3 ^ 512 = (3 ^ 256) * (3 ^ 256)

再相乘：

3 ^ 999
= 3 ^ (512 + 256 + 128 + 64 + 32 + 4 + 2 + 1)
= (3 ^ 512) * (3 ^ 256) * (3 ^ 128) * (3 ^ 64) * (3 ^ 32) * (3 ^ 4) * (3 ^ 2) * 3

这样只要做16次乘法。即使加上一些辅助的存储和运算，也比直接乘高效得多（尤其如果这里底数是成百上千位的大数字的话）。

我们发现，把999转为2进制数：1111100111，其各位就是要乘的数。这提示我们利用求二进制位的算法（其中mod是模运算）：

REVERSE_BINARY(n)
1 while (n > 0)
2     do output (n mod 2)
3       n ← n / 2

这个算法给出正整数n的反向二制进位，如6就给出011（6的二进制表示为110）。事实上这个算法对任意的p进制数是通用的，只要把其中的2换成p就可以了。

如何把它改编为求幂运算？我们发现这个算法是从 低位向高位做的，而恰好我们求幂也想从低次幂向高次幂计算（参看前面的例子）。而且我们知道前面求出的每个2^k次幂只参与一次乘法运算，这就提示我们并 不把所有的中间结果保存下来，而是在计算出它们后就立即运算。于是，我们要做的就是把输出语句改为要做的乘法运算，并在n减少的同时不断地累积求2^k次 幂。

还是看算法吧：

POWER_INTEGER(x, n)
1 pow ← 1
2 while (n > 0)
3     do if (n mod 2 = 1)
4            then pow ← pow * x
5       x ← x * x
6       n ← n / 2
7 return pow

不难看出这个算法与前面算法的关系。在第1步给出结果的初值1，在while循环内进行运算。3、4中的if语句就来自REVERSE_BINARY的输出语句，不过改成了如果是1则向pow中乘。5句则是不断地计算x的2^k次幂，如对前面的例子就是计算2^2、2^4、2^8、…、2^512。

应该指出，POWER_INTEGER比 前面分析的要再多做两次乘法，一次是向pow中第一次乘x，如2^1也要进行这个乘法；另一次则是在算法的最后，n除以2后该跳出循环，而前面一次x的自 乘就浪费掉了（也可以考虑改变循环模式优化掉它）。另外，每趟while循环都要进行一次除法和一次模运算，这多数情况下除法和模运算都比乘法慢许多，不 过好在我们往往可以用位运算来代替它。

相应的C++代码如下

NumberType pow_n(NumberType x, unsigned int n)
{
    NumberType pw = 1;

    while (n > 0) {
        if ((n % 2) == 1)
            pw *= x;
        x *= x;
        n /= 2;

    }

    return pw;
}

进行简单的优化后则有：

NumberType optimized_pow_n(NumberType x, unsigned int n)
{
    NumberType pw = 1;

    while (n > 0) {
        if (n & 1)        // n & 1 等价于 (n % 2) == 1
            pw *= x;
        x *= x;
        n >>= 1;        // n >>= 1 等价于 n /= 2
    }

    return pw;
}

注1：快速求幂算法POWER_INTEGER常被写成递归的形式，算法实质完全相同，但却是无必要的。

注2：这个算法并不是做乘法数最少的，但多数情况下是足够快并且足够简单的。如果单纯追求做乘法数最少，则未必应该用2^k次幂进行计算。如果还允许做除法，则问题会进一步复杂化。

如：

x ^ 2 = x * x
x ^ 4 = (x ^ 2) * (x ^ 2)
x ^ 8 = (x ^ 4) * (x ^ 4)
x ^ 16 = (x ^ 8) * (x ^ 8)
x ^ 31 = (x ^ 16) * (x ^ 8) * (x ^ 4) * (x ^ 2) * x
要8次乘法。

x ^ 2 = x * x
x ^ 4 = (x ^ 2) * (x ^ 2)
x ^ 8 = (x ^ 4) * (x ^ 4)
x ^ 10 = (x ^ 8) * (x ^ 2)
x ^ 20 = (x ^ 10) * (x ^ 10)
x ^ 30 = (x ^ 20) * (x ^ 10)
x ^ 31 = (x ^ 30) * x
只要7次乘法。

x ^ 2 = x * x
x ^ 4 = (x ^ 2) * (x ^ 2)
x ^ 8 = (x ^ 4) * (x ^ 4)
x ^ 16 = (x ^ 8) * (x ^ 8)
x ^ 32 = (x ^ 16) * (x ^ 16)
x ^ 31 = (x ^ 32) / x
只要6次乘或除法。

不过具体得出上述乘（除）法数更少的算法会变得相当复杂，在许多情况下时间收益还会得不偿失。因此往往并不实用。ACM Japan 2006中有一道题即要求计算最少乘法数，可参看：

http://acm.pku.edu.cn/JudgeOnline/problem?id=3134

 

zz from:http://www.cnblogs.com/wallace/archive/2009/12/27/1633683.html

时间： 2024-10-29 13:17:23

非递归版求幂函数的相关文章

非递归版归并排序

非递归版的归并排序,省略了中间的栈空间,直接申请一段O(n)的地址空间即可,因此空间复杂度为O(n),时间复杂度为O(nlogn); 算法思想: 开始以间隔为1的进行归并,也就是说,第一个元素跟第二个进行归并.第三个与第四个进行归并: 然后,再以间隔为2的进行归并,1-4进行归并,5-8进行归并: 再以2*2的间隔,同理,知道2*k超过数组长度为止. while(i<length){ Merge(arr,temp,i,length); i *= 2; } 当不够两组进行归并是,如果超过k个元素,

c语言-C语言版非递归马踏棋盘·死循环了·求大神解答·小弟新手求助

问题描述 C语言版非递归马踏棋盘·死循环了·求大神解答·小弟新手求助 这是出现死循环的代码bool solution(Move move, Pos &beginPos){ if(!move) { printf("solution Failed!"); return false; } int chessBoard[8][8] = {0}; push(move, beginPos); chessBoard[beginPos.mX][beginPos.mY] = 1; int ste

求二分查找的递归和非递归的时间空间效率比较

问题描述 求二分查找的递归和非递归的时间空间效率比较 求二分查找的递归和非递归的时间空间效率比较,为什么在刘汝佳的书上说,一般用非递归方法 解决方案 递归算法写起来简单,但是有两个不足,一个是调用接口的开销,函数调用本身是有开销的.另一个是堆栈内存比较小,递归调用层次深,容易引起堆栈溢出错误(著名的stack overflow).非递归没有这个问题.还有就是一些编程语言(很久很久以前,在你出生的年代之前),是没有函数调用的,那么就不能递归了. 解决方案二: 递归牵涉到环境保存和环境恢复操作,因此

c++ c 树-不用栈的非递归二叉树遍历 求改正 (C++新手)

问题描述 不用栈的非递归二叉树遍历 求改正 (C++新手) 原程序如下,添加了双亲域parent和标志域mark:不知道哪里不对: #include""iostream""using namespace std;class BinTree; class BinNode{private: int data; BinNode *lchild;BinNode *rchild;BinNode *parent;int mark;friend class BinTree; };

求大神看看，C语言二叉树非递归遍历问题 ，最后输出正确，然后在程序崩溃

问题描述 求大神看看,C语言二叉树非递归遍历问题 ,最后输出正确,然后在程序崩溃 #include #include #include typedef struct TNode { char date; struct TNode *lchild,*rchild; }TNode,*BiTree; typedef struct { BiTree top; BiTree *base; int stacksize; }Stack; int createBiTree(BiTree &S){ char ch

求大神告诉我我的二叉树后序遍历非递归哪里错了

问题描述 求大神告诉我我的二叉树后序遍历非递归哪里错了 #include using namespace std; struct binode { int data; binode *lchild,*rchild; }; binode *Q[100],*S[100]; struct element { binode *ptr; int flag; }; class bitree { public: void create_bitree(){root=creat(root);} void dele

java数学归纳法非递归求斐波那契数列的方法_java

本文实例讲述了java数学归纳法非递归求斐波那契数列的方法.分享给大家供大家参考.具体如下: Integer能表示的最大值为 2147483647 大概是21.4亿,这里没有考虑溢出情况(当size为983时就会溢出)! import java.util.List; import java.util.ArrayList; /** * @author jxqlovejava * 斐波那契数列 */ public class Fibonacci { public static List<Intege

二分查找的递归和非递归

查找算法 常见的查找算法大概有顺序查找.二分查找.二叉排序树查找.哈希表法(散列表).分块查找等, 下面简单了解一下其他几种查找算法. 1.顺序查找 也就是暴力方法,按顺序比较每个元素,直到找到关键字为止. 条件:无序或有序数据,时间复杂度:O(n) 2.二叉排序树查找 二叉排序树的性质: 1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值: 2. 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值: 3. 它的左.右子树也分别为二叉排序树. 在二叉查找树b中查找x的过

二叉树的建立、销毁、各种遍历（递归、非递归）

二叉树的基本操作,都使用递归: //二叉树 class Node { public: char data; Node *left; Node *right; Node():data(' '),left(NULL),right(NULL){} Node(char ch):data(ch),left(NULL),right(NULL){} }; //广义表建立二叉树,输入:A(B(D,E(G,)),C(,F))* void CreateBinTree(Node* & Root,char *str)