大数相乘与x的y次方大数实现.doc

这是一个大数相乘以及xy的实现的算法 实现方式：用字符数组实现#include#includeusing namespace std;/大数相乘void hugemulti(const char * a,const char * b)char *c = new charstrlen(a)+strlen(b)+1;cstrlen(a)+strlen(b) = 0;/char字符串的最后要有0字符结束，不然会出问题/数组的初始化（全部为0）for(int index = 0;index strlen(c);index+)cindex = 0;/用来标记最高位在C数组中的位置int mark = 0;/把两个数倒过来乘/* 比如说12345*789 = 5 4 3 2 1X 9 8 7 _ 5 0 1 1 1 1 0 6 7 8 9 5 1 4 6 8 _ 5 0 2 0 4 7 9所得到的结果也是反的*/for(int index = 0;index strlen(b);index+)for(int secdex = 0;secdex=0;index-)coutcindex;coutendl;/s释放内存delete c;c = NULL;/x的n次方,因为我们要改变数组a的值，所以要传入数组a的地址void xny(char * a, char * b)/数组c用来存储结果char *c = new charstrlen(*a)+strlen(b)+1;/在c字符串的最后加上0标志cstrlen(*a)+strlen(b) = 0;/数组的初始化for(int index = 0;index strlen(c);index+)cindex = 0;/用来标记最高位在C数组中的位置int mark = 0;for(int firdex = 0;firdex strlen(b);firdex+)for(int secdex = 0;secdexstrlen(*a);secdex+)/处理进位int temp = (bfirdex-0)*(*a)secdex-0);int m = cfirdex+secdex-0;int k =(m+temp%10);cfirdex+secdex = k%10+0;cfirdex+secdex+1 = (cfirdex+secdex+1-0)+temp/10+k/10)+0;/这里的mark跟hugemulti函数里面的mark同，因为每次c数组都是新的，而且里面都是0,所以只能通过temp的值来考虑进位if(temp/10) mark = firdex+secdex+1;elsemark = firdex+secdex;delete (*a);(*a) = NULL;/这里mark表示位置,所以length至少为mark+2*a = new char mark+2;(*a)mark+1 = 0;for(int i = 0;i =mark;i+)(*a)i = ci;delete c;c = NULL;int n = 100;/把字符串反转void reversal(char *str)if(strlen(str) = 0)return;for(int index = 0;index strlen(str)/2;index+)char temp = strindex;strindex = strstrlen(str)-index-1;strstrlen(str)-index-1=temp;int main(void)string number1,number2;int n;/获得两个大数char *a = NULL,*b = NULL;cout请输入两个大数:number1number2;a = new charnumber1.length()+1;b = new charnumber2.length()+1;anumber1.length() = 0;bnumber2.length() = 0;strcpy(a,number1.c_str();strcpy(b,number2.c_str();reversal(a);reversal(b);cout大数相乘的结果:endl;hugemulti(a,b);/为两个大数分配内存空间coutnumber1;coutn;delete a;a = NULL;delete b;b = NULL;a = new charnumber1.length()+1;b = new charnumber1.length()+1;anumber1.length() = 0;bnumber1.length() = 0;strcpy(a,number1.c_str();strcpy(b,number1.c_str();reversal(a);reversal(b);for(int i = 0;i n-1;i+)/循环n-1次就可以了xny(&a,b);reversal(a);coutnumber1的n