大数开方

大数开方：代入法

1、把被开方数的整数部分从个位起向左每隔n位为一节，用撇号分开；

2、根据左边第一节里的数，求得开n次算术根的最高位上的数，假设这个数为a；

3、从第一节的数减去求得的最高位上数的n次方，在它们的差的右边写上第二节数作为第一个余数；

4、用第一个余数除以n(10a)^(n-1),所求的整数部分试商(如果这个最大整数大于或等于10，就用9做试商)；

5、设试商为b。如果(10a+b)^n-(10a)^n小于或等于余数，这个试商就是n次算术根的第二位；如果(10a+b)^n-(10a)^n大于余数，就把试商逐次减1再试，直到(10a+b)^n-(10a)^n小于或等于余数为止。

6、用同样的方法，继续求n次算术根的其他各位上的数(如果已经算了k位数数字，则a要取为全部k位数字)。

?

大数开方算法思路：

步骤：

1、将被开方数从右向左每两位分成一组；

2、从左边第一组开始运算，把第一组数作为余数，执行3；

3、设置一个基数r=0；

4、用r乘以20加上试商的和再乘以试商，所得的结果与余数比较，如果所得结果比余数小，并且试商再增大1，所得结果大于余数，则该试商为所求平方根的第一个数字。

5、把r的值乘以10再加上试商的值，作为新的一轮的r的基值；

6、用余数减去上述所得结果，再与后面一组数组合，作为新的一组余数；

7、继续执行4；

代码：

#include <iostream>
#include <cstring> 
#include <cstdlib> 
using namespace std;
void sqrt(char *str)
{
	double i,r,n;
	int j,l,num,x[1005];
	if (strlen(str)==1&&str[0]=='0')
	{
		cout<<0<<endl;
		return;
	}
	if (strlen(str)%2==1)
	{
		n=str[0]-48;
		l=-1;
	}
	else
	{
		n=(str[0]-48)*10+str[1]-48;
		l=0;
	}
	r=0,num=0;
	while (true)
	{
		i=0;
		while (i*(i+20*r)<=n)
			i++;
		i--;
		n-=i*(i+20*r);
		r=r*10+i;
		x[num]=(int)i;
		num++;
		l+=2;
		if (l>=strlen(str))
			break;
		n=n*100+(double)(str[l]-48)*10+(double)(str[l+1]-48);
	}
	for (j=0; j<num; j++)
		cout<<x[j];
	cout<<endl;	
}
int main()
{
	char ch[1005];
	while (cin>>ch)
		sqrt(ch);
	return 0;
}