c/c++实现任意大小的n的n次方的计算

• 1. 需求确定
• 2. 技术难点
• 3. 实现思路
• 4. c/c++实现
• 5. 注意事项
• 6. 当前存在的问题和优化方向

1. 需求确定

利用c/c++实现计算n的n次方（其中n为int型数据），并且最终输出结果不受编译器int或是long int等类型的存储位数限制的影响。n通过用户自行输入。

2. 技术难点

• 如何当结果的位数过大时依然完成对于数据的准确计算。（当所需存储的数值过大时将造成数值的越界）
• 降低算法的时间复杂度。

3. 实现思路

采用分治的思想利用n的2次方乘n的2次方得到n的4次方，再利用n的4次方计算n的8次方以此类推。这种方法的一般情况是当n等于2、4、8、16…也就是恰为2的几次方时为最理想情况，其他如n等于6时此方法只可计算到6的4次方，对于剩下的6的2次方需利用递归再次计算出6的2次方值为多少，最后再将这两个结果相乘得到最终结果。
相乘的实现则是通过将数据按位分离依次存入栈中，然后利用常规的竖式计算来计算任意位数的整数相乘。竖式计算所具有的特点如下图：

其中a表示存储a数据的栈的数据域，类似一维数组，z表示结果。由图中可看出结果的第0位为乘数第0位和被乘数第0位相乘所得结果与10取余，并将乘积除以10得到10位数字作为下一位的进位值，类推并归纳可得出:
z[n] = (a[x1]*b[y1]+a[x2]*b[y2]+···+上一位进位值)%10
其中x1+y1 = n,x2+y2 = n···
接下来的问题便是算法的c/c++实现。

4. c/c++实现

main.cpp:

#include
#include"stack.h"
#include using namespace std;
linkStack getMulResult(Stack p1, Stack p2, linkStack lsq);
Stack getFinalResult(int number, Stack sq);
Stack getCoupledResult(int number, Stack sq, bool IsOne);int main() {int number;cin >> number;double run_time;Stack sq;if (!creatStack(&sq)) {cout << "栈空间创建失败" << endl;exit(0);}int Num = number;//将数据压入栈while (number!=0) {int _number = number % 10;if (!pushStack(&sq, _number)) {cout << "压栈失败!" << endl;exit(0);}number = number / 10;}Stack ResultS = getFinalResult(Num, sq);for (int i = ResultS.top; i >= 0; i--) {//cout << result->s[i];printf("%d", ResultS.s[i]);}destroyStack(&ResultS);getchar();getchar();}Stack getFinalResult(int number, Stack sq) {if (number < 2) {return sq;}int ComNum = 2;while (ComNum <= number) {ComNum *= 2;}ComNum /= 2;Stack CouSq = getCoupledResult(ComNum, sq,true);int AloneNumber = number - ComNum;Stack AloneSq;if (AloneNumber > 0) {//处理剩余元素AloneSq = getFinalResult(AloneNumber, sq);//destroyStack(&sq);Stack s;linkStack result = &s;creatStack(result);getMulResult(CouSq, AloneSq, result);destroyStack(&CouSq);destroyStack(&AloneSq);return *result;}else{//内部无剩余//destroyStack(&sq);return CouSq;}
}Stack getCoupledResult(int number, Stack sq,bool IsOne) {if (number <= 1) {return sq;}Stack s;linkStack result = &s;creatStack(result);Stack ResultSq = *getMulResult(sq, sq, result);if (!IsOne) {destroyStack(&sq);}return getCoupledResult(number / 2, ResultSq,false);
}linkStack getMulResult(Stack p1, Stack p2, linkStack lsq) {if (p2.top > p1.top) {Stack t = p1;p1 = p2;p2 = t;}creatStack(lsq);int ComIndex = 0;if (p1.top <= -1 || p2.top <= -1) {cout << "两数相乘传入数据不正确,已返回空栈！" << endl;return lsq;}int MaxIndex = p1.top > p2.top? p1.top: p2.top;			//两数中最长位数int MinIndex = p2.top < p1.top?p2.top:p1.top;int SumIndex = p1.top + p2.top;							//结果位数总和int NextAdd = 0;for (int i = 0; i <= SumIndex; i++) {//t和z为移动标志，用于记录那位相乘int t = i;if (i > MaxIndex) {t = MaxIndex;}int z = 0;int AddResult = NextAdd;				//保留最后当前位的相加结果while(t>=0&&z<= MinIndex) {if (t + z == i) {int ProductResult = p1.s[t] * p2.s[z];AddResult += ProductResult;//cout << "计算：" << i << " " << t << "," << z << " " << ProductResult << endl;z++;t--;}else  {z++;}}NextAdd = AddResult / 10;if (!pushStack(lsq, AddResult % 10)) {cout << "两数计算过程入栈失败！" << endl;exit(0);}}if (NextAdd != 0) {if (!pushStack(lsq, NextAdd)) {cout << "两数计算过程入栈失败！" << endl;exit(0);}}return lsq;
}

Stack.h:

#include
#include
#define OK 1				//操作成功
#define ERRO 0				//操作失败
#define MAX_LENGTH 100		//初次创建栈的最长长度
#define ADD_LENGTH 40		//每次扩展栈的长度
typedef int State;			//利用BOOL表示操作是否成功
typedef int EmType;typedef struct {EmType* s;			//数据int top;			//当前栈顶位置int maxSize;		//最大长度
}Stack, *linkStack;//函数声明
State isFullStack(Stack s);						//判断栈满
State creatStack(linkStack s_link);				//创建空栈
State increaseStack(linkStack s_link);			//为栈重新分配空间
State pushStack(linkStack s_link, EmType ch);		//压栈
State isEmptyStack(linkStack s_link);			//判断栈空
EmType popStack(linkStack s_link);				//弹栈
void destroyStack(linkStack s);				//销毁栈

Stack.cpp:

#include"stack.h"
//栈函数实现
/*************************************************
Function: popStack
Description: 弹栈
Input:s_link 栈指针
Return: 返回是否为空
*************************************************/
EmType popStack(linkStack s_link) {return s_link->s[s_link->top--];
}/*************************************************
Function: isEmptyStack
Description: 判断栈空
Input:s_link 栈指针
Return: 返回是否为空
*************************************************/
State isEmptyStack(linkStack s_link) {if (s_link->top == -1)return OK;elsereturn ERRO;
}/*************************************************
Function: creatStack
Description: 为栈分配空间
Input:s_link 栈指针
Return: 返回是否执行成功
*************************************************/
State creatStack(linkStack s_link) {//为栈数据域分配连续空间s_link->s = (EmType*)malloc(MAX_LENGTH * sizeof(EmType));//判断是否分配成功if (s_link->s == NULL) return ERRO;//部分内容初始化s_link->maxSize = MAX_LENGTH;s_link->top = -1;return OK;
}/*************************************************
Function: pushStack
Description: 压栈
Input:s_link 栈指针
Return: 返回是否执行成功
*************************************************/
State pushStack(linkStack s_link, EmType ch) {if (isFullStack(*s_link)) {			//判断是否栈满，栈满则重新分配空间，否则直接压栈//栈满if (!increaseStack(s_link))		//重新分配栈空间,并判断是否分配成功return ERRO;}s_link->s[++s_link->top] = ch;return OK;
}/*************************************************
Function: increaseStack
Description: 为栈重新分配空间
Input:s_link 栈指针
Return: 返回是否执行成功
*************************************************/
State increaseStack(linkStack s_link) {//重新分配栈空间s_link->s = (EmType*)realloc(s_link->s, sizeof(EmType)*(s_link->maxSize + ADD_LENGTH));if (s_link->s == NULL)		//判断是否分配空间成功return ERRO;s_link->maxSize += ADD_LENGTH;return OK;
}/*************************************************
Function: isFullStack
Description: 判断栈满
Input:s_link 栈指针
Return: 返回是否执行成功
*************************************************/
State isFullStack(Stack s) {//如果当前top+1与栈最大空间相等则判断为栈满if (s.maxSize == s.top + 1)return OK;elsereturn ERRO;
}/*************************************************
Function: destroyStack
Description: 销毁栈
Input:s_link 栈指针
Return: 返回是否执行成功
*************************************************/
void destroyStack(linkStack s) {free(s->s);s->top = -1;
}

实现环境：
windows + vs2015
如果不习惯多文件共同编译，可以将所有代码都复制到main.cpp里面，应该没什么问题，需要请自行解决。

5. 注意事项

代码中使用了内存分配函数malloc，注意一定要在申请内存之后使用free函数释放掉，否则将造成严重的内存泄露。

6. 当前存在的问题和优化方向

问题：通过vs的debug功能，发现当前代码可能仍存在内存泄露问题，但是不是特别严重。
优化方向：

• 解决内存泄露问题
• 优化算法，降低时间复杂度，优化方向为从对于遗留数据也就是2次方之外的数据比如6的6次方中一次成对计算后的剩余的2次方的计算过程进行优化。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！