算法--大数开方

?????? 之前已找到比较好的大数乘法算法，现在我们来解决大数开方问题，如有大数n，求其开方x，则x与n必满足x*x=n;也就是说我们能遍历x找到n的开方，但是问题在于我们是不可能对大数遍历的。如果我们可以确定它的大致范围，仅仅测试几个不容易直接判断的数据就找到目标数据就好了。

???? 1-一个n位数的开方的位数m满足下列条件：

???????? m=n/2(n为偶数);

???????? m=n/2+1(n为奇数);

???????? 以此我们可以确定大数开方的位数，然后判断最高位：

???????? 设一个数为abcd，那么它的开方设ef，将e从0~9遍历，如果当e=x时，xf^2<abcd<(x+1)f^2，即可确定x为ef的最高位，然后将f从0~9遍历，当得到xy^2<abcd<x(y+1)^2时，即可确定y为其次高位，同理可算出其它位数更多的大数开方

???? 2-1中表达式xf^2<abcd<(x+1)f^2与xy^2<abcd<x(y+1)^2是大数比较，这是比较简单的问题，把他们每位都放入数组中，从最高位开始比较，一旦有一个位有大小关系即可相应判断大小，另外保存相等数位的数量以判断是否相等，一旦相等现有数据就是其开方不需再循环遍历求其它数位的数值。

???? 下面贴上代码：(此代码因用于解决某题目需要，功能为输入两个大数，并将它们的开方输出，但上诉方法都体现在函数模块中)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include <cstdlib>
using namespace std;

void assignment(int* s,int n){//数组初始化为0
	for(int i=0;i<n;i++){
		s[i]=0;
	}
} 
void Multiplication(char *arr1,char* arr2,int* Result){ //大数乘法
	int n,m;n=strlen(arr1);m=strlen(arr2);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			Result[i+j]=Result[i+j]+(arr1[i]-'0')*(arr2[j]-'0');
		}
	}
}
int reorganize(int *Result,int n){//将大数乘法的结果整理得到最终的十进制形式
	int k,z=0,t=0,p=0;
	for(int i=0;i<n;i++){
		if(Result[i]>9){
			t=Result[i]%10;
			Result[i+1]=Result[i+1]+Result[i]/10;
			Result[i]=t;  			
		}
	}
	k=n;
	while(k--){
		if(Result[k]!=0){
			z=1;
		}
		if(z==1){
			p++;
		}
	}
	return p;
}
int Comparison(int *Result,int *Root,int n){//大数比较
	int k=0,s=n;
	for(int i=n-1;i>=0;i--){
		if(Result[i]<Root[i])return 1;
		else if(Result[i]>Root[i])return 0;
		else if(Result[i]==Root[i])k++;
		if(k==s)return -1;
	}
	return 0;
}
int getsqrt(char *arr,int *Result,int z,int n){//大数开方	 
	int t;
	for(int i=z-1;i>=0;i--){
		for(int j=0;j<10;j++){
			arr[i]=j+'0';
			assignment(Root,n);
			Multiplication(arr,arr,Root);
			if(Root[n-1]<=9)reorganize(Root,n);t=Comparison(Result,Root,n);	
			if(t==1){

				arr[i]=j+'0'-1;
				break;
			}
			if(t==-1){
				arr[i]=j+'0';
				return 0;
			}

		}			
	}
	return 0;	
}
int main(){
	string s1,s2;
	int n,m,z1,z2;char h;
	cin>>s1>>s2;//以输入字串的方式输入数据，方便动态为数据分配空间
	n=s1.length();m=s2.length();
	int *ar1=new int[n+1];int *ar2=new int[m+1];          
	z1=n%2==0?n/2:n/2+1;z2=m%2==0?m/2:m/2+1; //确定方根的位数          
	char *arr1=new char[z1+1];char *arr2=new char[z2+1];
	arr1[z1]='';arr2[z2]='';                   
	int *Root1=new int[n+1];int *Root2=new int[m+1];int *Root=new int[z1+z2];
	int i=n-1,j=m-1;
	stringstream ss1(s1);while(ss1>>h)ar1[i--]=h-'0';ar1[n]=0;
//将输入字符数据转化为整型数据
	stringstream ss2(s2);while(ss2>>h)ar2[j--]=h-'0';ar2[m]=0;
	memset(arr1,'0',z1);memset(arr2,z2);
	assignment(Root,z1+z2);	
	getsqrt(arr1,ar1,Root1,n+1);
	getsqrt(arr2,ar2,Root2,z2,m+1);	
        return 0;		
}