ACM 10023 10023 - Square root
作法 : 直式開方法,大數乘法,大數減法,大數比大小,大數進位
EX1: 951*951=904401
9, 5, 1 /*這裡填的數字 要等於左邊口裡面的數字/
----------
口->9 |90,44,01 /*從後面兩兩分組*/
+ 口->9 81
----- --------
18口->5 9,44,01
+ 口->5 9,25
------ -------
190口->1 19,01
+ 口->1 19,01
--------- ------
1902 0
EX2: 105*105=11025
1, 0, 5
口->1 ----------
+ 口->1 |1,10,25
------- 1
2口->0 ---------
+ 口->0 10,25
-------- 10,25
20口->5 -------
+ 口->5 0
--------
210
還是用講的比較方便...
有問題再問吧
上傳UVA時 請注意換行...
/*********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
main()
{
int t,time=0;
scanf("%d",&t);
while(t--)
{
time++;
char x[1001];
scanf("%s",x);
int a,b,c,d,s[2001]={0},n=strlen(x);
for(a=0,b=n-1;b>=0;b--,a++) s[a]=x[b]-48;
int tt[1501]={0},top=n,top2=1;
for(a=(n-1)/2*2;a>=0;a=a-2,top2++)/*直是開方法 兩兩分組*/
{
if(top>a+top2-2) /*明知道不用填就直接忽略*/
for(b=9;b>=0;b--) /*猜口裡面的數字*/
{
int ss[1501]={0};
tt[0]=b;
for(d=0;d<=top2;d++)/*大數乘法*/
{
ss[a+d]+=(b*tt[d]);
ss[a+d+1]+=(ss[a+d]/10);
ss[a+d]%=10;
}
int find=0;
for(c=top2+a+1;c>=0;c--)/*大數比大小*/
if(s[c]>ss[c]) {find=1;break;}
else if(ss[c]>s[c]) break;
if(find==1||c==-1)/*如果一比較小 或者是相同大小*/
{
for(c=0;c<=top;c++) /*大數減法*/
{
s[c]-=ss[c];
if(s[c]<0)
{
int temp=((-s[c])/10+((-s[c])%10!=0));
s[c]+=10*temp;
s[c+1]-=temp;
}
}
break;
}
}
else b=0;
printf("%d",b);
if(top!=-1)
{
tt[0]+=b; /*再加上一個B值*/
for(b=0;b<=top2+1;b++) /*可能會進位*/
if(tt[b]>=10)
{
tt[b+1]+=(tt[b]/10);
tt[b]%=10;
}
else break;
for(b=top2+1;b>=0;b--) tt[b+1]=tt[b];/*往前移*/
tt[0]=0;
for(b=top;b>=0;b--)
if(s[b]!=0) {top=b;break;}
if(b==-1) top=-1;
}
}
printf("\n");
if(t!=0) printf("\n");
}
return 0;
}