(大整数开方) 输入一个正整数n(1≤n≤10100),试用二分法计算它的平方根的整数部分。
#include
#include
using namespace std;
const int SIZE=200;
struct hugeint{
\tint len,num[SIZE];
};
// 其中len表示大整数的位数;num[1]表示个位,num[2]表示十位,以此类推
hugeint times(hugeinta,hugeintb)
// 计算大整数a和b的乘积
{
\tinti,j;
\thugeint ans;
\tmemset(ans.num,0,sizeof(ans.num));
\tfor(i=1;i<=a.len;i )
\t\tfor(j=1;j<=b.len;j )
① =a.num[i]*b.num[j];
\tfor(i=1;i<=a.len b.len;i ){
\t\tans.num[i 1] =ans.num[i]/10;
② ;
\t}
\tif(ans.num[a.len b.len]>0)
\t\tans.len=a.len b.len;
\telse
\t\tans.len=a.len b.len-1;
\treturn ans;
}
hugeint add(hugeinta,hugeintb)
// 计算大整数a和b的和
{
\tinti;
\thugeint ans;
\tmemset(ans.num,0,sizeof(ans.num));
\tif(a.len>b.len)
\t\tans.len=a.len;
\telse
\t\tans.len=b.len;
\tfor(i=1;i<=ans.len;i ){
\t\tans.num[i] = ③ ;
\t\tans.num[i 1] = ans.num[i]/10;
\t\tans.num[i]%=10;
\t}
\tif(ans.num[ans.len 1]>0)
\t\tans.len ;
\treturn ans;
}
hugeint average(hugeinta,hugeintb)
// 计算大整数a和b的平均数的整数部分
{
\tinti;
\thugeint ans;
\tans=add(a,b);
\tfor(i=ans.len;i>=2;i--){
\t\tans.num[i-1] =( ④ )*10;
\t\tans.num[i]/=2;
\t}
\tans.num[1]/=2;
\tif(ans.num[ans.len]==0)
\t\tans.len--;
\treturn ans;
}
hugeint plustwo(hugeinta)
// 计算大整数加2之后的结果
{
\tinti;
\thugeint ans;
\tans=a;
\tans.num[1] =2;
\ti=1;
\twhile( (i<=ans.len)&&(ans.num[i]>=10) ){
\t\tans.num[i 1] =ans.num[i]/10;
\t\tans.num[i]%=10;
\t\ti ;
\t}
\tif(ans.num[ans.len 1]>0)
⑤ ;
\treturn ans;
}
boolover(hugeinta,hugeintb)
// 若大整数a>b则返回true,否则返回false
{
\tinti;
\tif( ⑥ )
\t\treturn false;
\tif( a.len>b.len )
\t\treturn true;
\tfor(i=a.len;i>=1;i--){
\t\tif(a.num[i]
\t\t\treturn false;
\t\tif(a.num[i]>b.num[i])
\t\t\treturn true;
\t}
\treturn false;
}
int main()
{
\tstring s;
\tinti;
\thugeint target,left,middle,right;
\tcin>>s;
\tmemset(target.num,0,sizeof(target.num));
\ttarget.len=s.length();
\tfor(i=1;i<=target.len;i )
\t\ttarget.num[i]=s[target.len-i]- ⑦
\tmemset(left.num,0,sizeof(left.num));
\tleft.len=1;
\tleft.num[1]=1;
\tright=target;
\tdo{
\t\tmiddle=average(left,right);
\t\tif(over( ⑧ ))
\t\t\tright=middle;
\t\telse
\t\t\tleft=middle;
\t}while(!over(plustwo(left),right) );
\tfor(i=left.len;i>=1;i--)
\t\tcout<
\treturn 0;
}
发表评论 取消回复