| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1365 人关注过本帖
标题:谁能解释下“手算开平方”的方法
只看楼主 加入收藏
brian1994
Rank: 2
来 自:广东省中山市一中
等 级:论坛游民
帖 子:63
专家分:47
注 册:2011-5-15
结帖率:75%
收藏
已结贴  问题点数:5 回复次数:8 
谁能解释下“手算开平方”的方法
UVA数论中有道题是求10^1000以内的数的开方(数据中每个数保证是某个正整数的平方)
手算开平方,是我认为最有效的方法。但是我不是很懂... ...
请各位大牛来解释,最后来个伪代码
搜索更多相关主题的帖子: 正整数 开平 
2011-05-18 13:54
brian1994
Rank: 2
来 自:广东省中山市一中
等 级:论坛游民
帖 子:63
专家分:47
注 册:2011-5-15
收藏
得分:0 
为何空无一人??
2011-05-20 13:32
brian1994
Rank: 2
来 自:广东省中山市一中
等 级:论坛游民
帖 子:63
专家分:47
注 册:2011-5-15
收藏
得分:0 
求顶起!
2011-05-22 16:22
buffer
Rank: 5Rank: 5
等 级:职业侠客
帖 子:73
专家分:326
注 册:2010-12-31
收藏
得分:5 
求平方根的算法,可以利用牛顿法来解方程x^2 - n = 0
有递归式:
x_k+1 = (x_k + n / x_k) / 2
初始x0可以选择n

PS:教你cheat对于uva的这题,用long double类型就能AC
2011-05-22 18:50
brian1994
Rank: 2
来 自:广东省中山市一中
等 级:论坛游民
帖 子:63
专家分:47
注 册:2011-5-15
收藏
得分:0 
#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;
}
2011-05-24 14:34
brian1994
Rank: 2
来 自:广东省中山市一中
等 级:论坛游民
帖 子:63
专家分:47
注 册:2011-5-15
收藏
得分:0 
回复 4楼 buffer
...
2011-05-24 14:34
ymqq
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:141
专家分:143
注 册:2010-7-14
收藏
得分:0 
用 泰勒公式 展开 求根 式!忽略 高阶 数。
2011-06-12 02:38
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
long double能表示到10的500次方么?我真不知道。
要我还是得做大数运算,不过用牛顿迭代法需要做大数除法,所以我会选择试商,这样只需要做大数乘法就可以了。
算法复杂度应该是log(log(n))

重剑无锋,大巧不工
2011-06-15 19:39
brian1994
Rank: 2
来 自:广东省中山市一中
等 级:论坛游民
帖 子:63
专家分:47
注 册:2011-5-15
收藏
得分:0 
废话,本来就是试商。。。。
2011-06-16 13:17
快速回复:谁能解释下“手算开平方”的方法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030981 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved