作法 : 大數直式方法

詳情請參考 : ACM 10023 10023 - Square root

/******************************************************/

#include<stdio.h>           
#include<stdlib.h>
#include<string.h>
main()
{
 int t,time=0;
 char x[1001];
    while(scanf("%s",x)==1)
       {
         int a,b,c,d,s[1301]={0},n=strlen(x);
         for(a=0,b=n-1;b>=0;b--,a++)  s[a+100]=x[b]-48;
         n=n+100;
         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[1301]={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("%c",b+48);
               if(a==100) printf(".");
               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");
       }
 return 0;
}