谁能解释下“手算开平方”的方法 - 编程论坛

#2

brian19942011-05-20 13:32

为何空无一人？？

#3

brian19942011-05-22 16:22

求顶起！

#4

buffer2011-05-22 18:50

求平方根的算法，可以利用牛顿法来解方程x^2 - n = 0
有递归式：
x_k+1 = (x_k + n / x_k) / 2
初始x0可以选择n

PS：教你cheat

对于uva的这题，用long double类型就能AC

#5

brian19942011-05-24 14:34

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=1000+10;

struct bign
{
      int len,s[maxn];
      bign() { len=1; memset(s,0,sizeof(s)); }
};
bign n;
int test,all;

bign init()
{
     bign c;
     char s[maxn]; scanf("%s",s);
     c.len=strlen(s);
     for (int i=1;i<=c.len;i++)
         c.s[i]=s[c.len-i]-'0';
     return c;
}

bign past(bign a,int b)
{
     a.s[1]+=b;
     for (int i=1;a.s[i]>=10;i++)
     {
         a.s[i+1]+=a.s[i]/10;
         a.s[i]%=10;
     }
     while (a.s[a.len+1]>0)
           a.len++;
     return a;
}

bign time(bign a,int b)
{
     for (int i=1;i<=a.len;i++)
     {
         a.s[i]*=b;
         if (i>1)
         {
            a.s[i]+=a.s[i-1]/10;
            a.s[i-1]%=10;
         }
     }
     while (a.s[a.len]>=10)
     {
           a.s[a.len+1]+=a.s[a.len]/10;
           a.s[a.len]%=10;
           a.len++;
     }
     return a;
}

bool more(bign a,bign b)
{
     if (a.len>b.len) return true;
     if (a.len<b.len) return false;
     for (int i=a.len;i>=1;i--)
     {
         if (a.s[i]>b.s[i]) return true;
         if (a.s[i]<b.s[i]) return false;
     }
     return true;
}

bign cut(bign a,bign b)
{
     for (int i=1;i<=a.len;i++)
     {
         a.s[i]-=b.s[i];
         if (a.s[i]<0)
         {
            a.s[i]+=10;
            a.s[i+1]--;
         }
     }
     while (a.s[a.len]==0 && a.len>1)
           a.len--;

     return a;
}

void ouit(bign a)
{
     for (int i=a.len;i>=1;i--)
         printf("%d",a.s[i]);
     printf("\n");
}

int main()
{
    scanf("%d",&test); all=test;
    while (test--)
    {
          if (test<all-1) printf("\n");
          n=init();
          bign ans,remain;

          for (int i=(n.len+1)/2*2;i>=2;i=i-2)
          {
              int group = n.s[i]*10 + n.s[i-1];

              bign odd;
              odd=time(ans,20);
              odd=past(odd,1);

              remain=time(remain,100);
              remain=past(remain,group);

              int count=0;
              while (more(remain,odd))
              {
                    count++;
                    remain=cut(remain,odd);
                    odd=past(odd,2);
              }

              ans=time(ans,10);
              ans=past(ans,count);
          }

          ouit(ans);
    }
    return 0;
}

#6

brian19942011-05-24 14:34

回复 4楼 buffer

...

#7

ymqq2011-06-12 02:38

用泰勒公式展开求根式！忽略高阶数。

#8

beyondyf2011-06-15 19:39

long double能表示到10的500次方么？我真不知道。
要我还是得做大数运算，不过用牛顿迭代法需要做大数除法，所以我会选择试商，这样只需要做大数乘法就可以了。
算法复杂度应该是log(log(n))

#9

brian19942011-06-16 13:17

废话，本来就是试商。。。。