学步园

#include <iostream>
using namespace std;

/**
* 大数相乘，使用字符串解决
*/

/**
* 将字符转换成数字
*/
int ctoi(char ch){
	if(ch < '0' || ch > '9'){
		cout<<"transfer error"<<endl;
		return -1;
	}
	return ch-48;
}

/**
* 将数字转换成字符
*/
char itoc(int x){
	if(x < 0 || x > 9){
		cout<<"transfer error"<<endl;
		return -1;
	}
	return x+48;
}

/**
* 逆置一个字符串
*/
void reverseString(char *s){
	int n = 0;
	char *p = s;
	while(*p++ != '\0') n++;
	for(int i=0;i<n/2;i++){
		char tmp = *(s+i);
		*(s+i) = *(s+n-1-i);
		*(s+n-1-i) = tmp;
	}
}

/**
* 大数相乘： 字符串的形式传入两个大数，以字符串的形式返回相乘结果。
* a * b = c
* 从b的最低位开始，对其每一个字符，都与a的每个字符相乘，将结果存入空间w，进位存入more。
* 需要注意的是：b当前字符与a的某个字符相乘，结果没有产生进位(<10),但是加上上次的进位之
* 后才产生进位，这种情况需要注意。
*/
char *big_multiply(char *a, char *b){
	char *p = a;
	char *q = b;
	int more = 0;
	int max_end = 0;

	//分别求出b和a的长度(为了从右向左循环)
	int m = 0;
	while(*p++ != '\0') m++;	//a length = m
	int n = 0;
	while(*q++ != '\0') n++;	//b length = n

	//申请空间存放相乘结果(逆置，初始化为字符0)
	char *c = (char *)malloc(sizeof(char)*(m+n+1));
	char *w = c;
	for(int k=0;k<m+n+1;k++) *w++ = '0';
	
	int begin = 0;					//每一轮结果存放的起始位置递增
	for(int j=n-1;j>=0;j--){				//每个b的字符都和a的所有字符乘一次
		w = c+begin;				//每一轮，起点都往前移动一步
		for(int i=m-1;i>=0;i--){			//a的每个字符
			int v = ctoi(a[i])*ctoi(b[j]);	//相乘
			int tmp = ctoi(*w)+v%10+more;	//三个部分相加
			
			if(tmp > 9){		//特殊情况: 相加之后产生新的进位
				*w++ = itoc(tmp%10);	//再次对10取模再存入
				more = v/10 + tmp/10;	//加上相加产生的进位
			}
			else{			//正常情况(三个部分相加没有产生进位)
				*w++ = itoc(tmp);		//存入
				more = v/10;		//进位
			}
		}
		if(more != 0)				//检查是否有进位
			*w++ = itoc(more);
		more = 0;					//重置进位
		begin++;					//起点移动
	}
	*w = '\0';
	cout<<"result:"<<c<<endl;
	reverseString(c);					//逆置
	return c;
}

double big_pow(double x, int n){
	if(n == 0) return 1;
	else if(n == 1) return x;
	else{
		if(n % 2 == 0){
			return big_pow(x, n/2) * big_pow(x, n/2);
		}
		else{
			return big_pow(x, n/2) * big_pow(x, n/2+1);
		}
	}
}

int main(){
	char *a = "123456";
	char *b = "669";
	cout<<big_multiply(a,b)<<endl;
	return 0;
}