摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : 直式開方法，大數乘法，大數減法，大數比大小，大數進位

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;
}