SGU 111 大数开根号

要知道手算开方的方法，模拟一下即可。百度手算开方连接

我写得应该算最简单的了，SGU上数据有点水，有些代码侥幸过了。

练代码能力的水题，纯手敲， 为了开方需要，串表示大数时高位从0开始保存。?

给串赋值的时候好多地方出错，不应该直接赋值int型的数字。

每个操作结束后要清除前导零。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
bool cmp(char *s1,char *s2) { // 大数比较大小,s1 >= s2,return 1;

	int l1 = strlen(s1),l2 = strlen(s2);
	if(l1 != l2) return l1 > l2;
	int i;
	for(i = 0; i < l1; i++)
		if(s1[i] != s2[i]) return s1[i] > s2[i];
	return 1;
}
void clean(char *s) { // 去掉前导0
	int i = 0,len = strlen(s);
	while(s[i] == '0') i++;
	if(i == len) i--;
	strcpy(s,s+i);
}
void mult(char *s,int t,char *c) { // 大数s 乘以整数t 结果放在大数c中
	int len = strlen(s);
	int i,j = 0;
	int tp,add = 0;
	for(i = len-1; i >= 0; i--) {
		tp = (s[i] -'0') * t + add;
		c[j++] = tp%10 + '0';
		add = tp/10;
	}
	while(add) {
		c[j++] = add%10 + '0';
		add /= 10;
	}
	c[j] = '';
	for(i = 0; i < j/2; i++)
		swap(c[i],c[j-1-i]);
    clean(c);
}
void sub(char *s1,char *s2) {   // 大数 s1 -= s2
	int l1 = strlen(s1)-1,l2 = strlen(s2)-1;
	int add = 0;
	int i,j;
	while(l2 >= 0) {
		s1[l1] -= s2[l2]+add-'0';
		if(s1[l1] < '0')  {
			s1[l1] += 10;
			add = 1;
		}
		else add = 0;
		l1--; l2--;
	}
	while(l1 >= 0 && add) {
		s1[l1] -= add;
		if(s1[l1] < '0') {
			s1[l1] += 10;
			add = 1;
		}
		else add = 0;
	}
	clean(s1);
}

char ans[505];
void sqr(char *s) { // 大数开根号
	char str[1003] = {}; // str保存余数
	int len = strlen(s);
	int sta;
	//长度奇偶讨论
	if(len&1) {
		int f = s[0]-'0';
		int t = (int)sqrt(f);
		ans[0] = t +'0';
		str[0] = f - t*t+'0';
		sta = 1;
	}
	else {
		int f = s[0]*10+s[1]-11*'0';
		int t = (int)sqrt(f);
		ans[0] = t +'0';
		int w = f - t*t;
		if(w >= 10) {
		    str[0] = w/10+'0';
		    str[1] = w%10+'0';
		}
		else str[0] = w+'0';
		sta = 2;
	}
	char tp[1003],tmp[1003];
	int i,j,cnt = 1;

	for(i = sta; i < len; i+=2) {
	    int p = strlen(str);
		str[p++] = s[i]; str[p++] = s[i+1]; str[p] = '';
		clean(str);
		mult(ans,20,tp);
		int l = strlen(tp);
		for(j = 9; j >= 0; j--) {
			tp[l-1] = j+'0'; tp[l] = '';
			mult(tp,tmp);
			if(cmp(str,tmp)) break;
		}
		ans[cnt++] = j+'0';
		sub(str,tmp);
	}
	clean(ans);
}
char s[1003];
int main() {
	int i,j;
	scanf("%s",s);
    sqr(s);
    puts(ans);
	return 0;
}