首页 > 其他分享 >【codevs3119】高精度开根号（二分答案）

【codevs3119】高精度开根号（二分答案）

时间：2023-03-25 12:32:56浏览次数：37  
标签：二分 return Bigint int len num ans codevs3119 根号


problem

高精度开根号

  • 输入一个数
  • 求平方根

solution

  • 二分答案，如果mid*mid>原数就去找更小的，反之找更大的。
  • 精度小于二忽略不计？
  • 用到高精加,高精乘,加低精,除低精,比较大小这几个。

放弃调试，明天重写。
mmp

codes1（更快的AC版本

//二分答案
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int maxn = 1010;
int a[maxn], l[maxn], r[maxn], m[maxn], t[maxn];
//m=l+r>>1
void mid(){
    //m = l;
    memcpy(m,l,sizeof(l));
    //m += r;
    m[0] = r[0]+1;
    for(int i = 1; i <= r[0]; i++){
        m[i] += r[i];
        if(m[i]>=10){
            m[i] %= 10;
            m[i+1]++;
        }
    }
    while(m[0]>1 && m[m[0]]==0)m[0]--;
    //m /= 2;
    for(int i = m[0]; i >= 1; i--){
        if(i > 1)m[i-1]+=m[i]%2*10;
        m[i] /= 2;
    }
    while(m[0]>1 && m[m[0]]==0)m[0]--;
}
//return m*m>a;
bool C(){
    //t = 0;
    memset(t,0,sizeof(t));
    //t = m*m;
    for(int i = 1; i <= m[0]; i++)
        for(int j = 1; j <= m[0]; j++)
            t[i+j-1] += m[i]*m[j];
    t[0] = m[0]*2;
    for(int i = 1; i <= t[0]; i++){//处理进位
        t[i+1] += t[i]/10;
        t[i] %= 10;
    }
    while(t[0]>1 && t[t[0]]==0)t[0]--;
    //return t>a;
    if(t[0] != a[0])return t[0]>a[0];
    for(int i = t[0]; i >= 1; i--)
        if(t[i]!=a[i])return t[i]>a[i];
    return 0;
}

int main(){
    //输入
    string s;  cin>>s;
    a[0] = s.size();
    for(int i = 1; i <= a[0]; i++)a[i] = s[a[0]-i]-'0';
    //二分
    l[0] = 1;
    r[0] = a[0]/2+2;
    r[r[0]] = 1;
    for(int i = 1; i <= 2000; i++){
        mid();  //m=l+r>>1;
        if(C())memcpy(r,m,sizeof(m));//r=m;
        else memcpy(l,m,sizeof(m));//l=m;
    }
    //输出
    for(int i = l[0]; i >= 1; i--)cout<<l[i];
    return 0;
}

//二分答案
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const int maxn = 1010;
int a[maxn], l[maxn], r[maxn], m[maxn], t[maxn];
//m=l+r>>1
void mid(){
    //m = l;
    memcpy(m,l,sizeof(l));
    //m += r;
    m[0] = r[0]+1;
    for(int i = 1; i <= r[0]; i++){
        m[i] += r[i];
        if(m[i]>=10){
            m[i] %= 10;
            m[i+1]++;
        }
    }
    while(m[0]>1 && m[m[0]]==0)m[0]--;
    //m /= 2;
    for(int i = m[0]; i >= 1; i--){
        if(i > 1)m[i-1]+=m[i]%2*10;
        m[i] /= 2;
    }
    while(m[0]>1 && m[m[0]]==0)m[0]--;
}
//return m*m>a;
bool C(){
    //t = 0;
    memset(t,0,sizeof(t));
    //t = m*m;
    for(int i = 1; i <= m[0]; i++)
        for(int j = 1; j <= m[0]; j++)
            t[i+j-1] += m[i]*m[j];
    t[0] = m[0]*2;
    for(int i = 1; i <= t[0]; i++){//处理进位
        t[i+1] += t[i]/10;
        t[i] %= 10;
    }
    while(t[0]>1 && t[t[0]]==0)t[0]--;
    //return t>a;
    if(t[0] != a[0])return t[0]>a[0];
    for(int i = t[0]; i >= 1; i--)
        if(t[i]!=a[i])return t[i]>a[i];
    return 0;
}

int main(){
    //输入
    string s;  cin>>s;
    a[0] = s.size();
    for(int i = 1; i <= a[0]; i++)a[i] = s[a[0]-i]-'0';
    //二分
    l[0] = 1;
    r[0] = a[0]/2+2;
    r[r[0]] = 1;
    for(int i = 1; i <= 2000; i++){
        mid();  //m=l+r>>1;
        if(C())memcpy(r,m,sizeof(m));//r=m;
        else memcpy(l,m,sizeof(m));//l=m;
    }
    //输出
    for(int i = l[0]; i >= 1; i--)cout<<l[i];
    return 0;
}

code2（更容易读懂被TLE一个点的版本

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 2010;
struct Bigint{ int len, num[maxn]; };

//return a+b;
Bigint add(Bigint a, Bigint b){
    Bigint ans;  memset(ans.num,0,sizeof(ans.num));
    ans.len = max(a.len,b.len)+1;
    for(int i = 1; i <= ans.len; i++){
        ans.num[i] += a.num[i]+b.num[i];
        ans.num[i+1] += ans.num[i]/10;
        ans.num[i] %= 10;
    }
    while(ans.len>1 && ans.num[ans.len]==0)ans.len--;
    return ans;
}
//return (a+b)/2;
Bigint avg(Bigint a, Bigint b){
    Bigint ans;  memset(ans.num,0,sizeof(ans.num));
    ans = add(a,b);
    //copy from
    for(int i=ans.len;i>=2;i--){
        ans.num[i-1]+=( ans.num[i]%2)*10; 

        ans.num[i]/=2;
    }
    ans.num[1] /= 2;
    if(ans.num[ans.len]==0)ans.len--;
    return ans;
}
//return a+2;
Bigint plustwo(Bigint x){
    x.num[1] += 2;
    for(int i = 1; i <= x.len; i++){
        x.num[i+1] += x.num[i]/10;
        x.num[i] %= 10;
    }
    if(x.num[x.len+1]>0)x.len++;
    return x;
}

//return a*b;
Bigint times(Bigint a, Bigint b){
    Bigint ans;  memset(ans.num,0,sizeof(ans.num));
    ans.len = a.len+b.len+1;
    for(int i = 1; i <= a.len; i++)
        for(int j = 1; j <= b.len; j++)
            ans.num[i+j-1] += a.num[i]*b.num[j];
    for(int i = 1; i <= ans.len; i++){
        ans.num[i+1] += ans.num[i]/10;
        ans.num[i] %= 10;
    }
    while(ans.len>1 && ans.num[ans.len]==0)ans.len--;
    return ans;
}

//return a<=b;
bool over(Bigint a, Bigint b){
    if(a.len != b.len)return a.len < b.len;
    for(int i = a.len; i >= 1; i--)
        if(a.num[i] != b.num[i])return a.num[i]<b.num[i];
    return true;
}


Bigint l, r, mid, tmp;
int main(){
    ios::sync_with_stdio(false);
    string s;  cin>>s;
    tmp.len = s.size();
    for(int i = 1; i <= tmp.len; i++)
        tmp.num[i] += s[tmp.len-i]-'0';
    
    l.len = 1, l.num[1] = 3; r = tmp;
    do{
        mid = avg(l,r);
        if(!over(times(mid,mid),tmp))r = mid;
        else l = mid;
    }while(over(plustwo(l),r)); //l+2<=r;
    /*
    for(int i = 1; i <= 1500; i++){
        mid = avg(l,r);
        if(!over(times(mid,mid),tmp))r = mid;
        else l = mid;
    }
    */
    for(int i = l.len; i >= 1; i--)
        cout<<l.num[i];
    /*
    mid = times(l,r);
    for(int i = mid.len; i >= 1; i--)
        cout<<mid.num[i];  cout<<'\n';
    */
    return 0;
}

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 2010;
struct Bigint{ int len, num[maxn]; };

//return a+b;
Bigint add(Bigint a, Bigint b){
    Bigint ans;  memset(ans.num,0,sizeof(ans.num));
    ans.len = max(a.len,b.len)+1;
    for(int i = 1; i <= ans.len; i++){
        ans.num[i] += a.num[i]+b.num[i];
        ans.num[i+1] += ans.num[i]/10;
        ans.num[i] %= 10;
    }
    while(ans.len>1 && ans.num[ans.len]==0)ans.len--;
    return ans;
}
//return (a+b)/2;
Bigint avg(Bigint a, Bigint b){
    Bigint ans;  memset(ans.num,0,sizeof(ans.num));
    ans = add(a,b);
    //copy from
    for(int i=ans.len;i>=2;i--){
        ans.num[i-1]+=( ans.num[i]%2)*10; 

        ans.num[i]/=2;
    }
    ans.num[1] /= 2;
    if(ans.num[ans.len]==0)ans.len--;
    return ans;
}
//return a+2;
Bigint plustwo(Bigint x){
    x.num[1] += 2;
    for(int i = 1; i <= x.len; i++){
        x.num[i+1] += x.num[i]/10;
        x.num[i] %= 10;
    }
    if(x.num[x.len+1]>0)x.len++;
    return x;
}

//return a*b;
Bigint times(Bigint a, Bigint b){
    Bigint ans;  memset(ans.num,0,sizeof(ans.num));
    ans.len = a.len+b.len+1;
    for(int i = 1; i <= a.len; i++)
        for(int j = 1; j <= b.len; j++)
            ans.num[i+j-1] += a.num[i]*b.num[j];
    for(int i = 1; i <= ans.len; i++){
        ans.num[i+1] += ans.num[i]/10;
        ans.num[i] %= 10;
    }
    while(ans.len>1 && ans.num[ans.len]==0)ans.len--;
    return ans;
}

//return a<=b;
bool over(Bigint a, Bigint b){
    if(a.len != b.len)return a.len < b.len;
    for(int i = a.len; i >= 1; i--)
        if(a.num[i] != b.num[i])return a.num[i]<b.num[i];
    return true;
}


Bigint l, r, mid, tmp;
int main(){
    ios::sync_with_stdio(false);
    string s;  cin>>s;
    tmp.len = s.size();
    for(int i = 1; i <= tmp.len; i++)
        tmp.num[i] += s[tmp.len-i]-'0';
    
    l.len = 1, l.num[1] = 3; r = tmp;
    do{
        mid = avg(l,r);
        if(!over(times(mid,mid),tmp))r = mid;
        else l = mid;
    }while(over(plustwo(l),r)); //l+2<=r;
    /*
    for(int i = 1; i <= 1500; i++){
        mid = avg(l,r);
        if(!over(times(mid,mid),tmp))r = mid;
        else l = mid;
    }
    */
    for(int i = l.len; i >= 1; i--)
        cout<<l.num[i];
    /*
    mid = times(l,r);
    for(int i = mid.len; i >= 1; i--)
        cout<<mid.num[i];  cout<<'\n';
    */
    return 0;
}


标签：二分,return,Bigint,int,len,num,ans,codevs3119,根号
From： https://blog.51cto.com/gwj1314/6149278

相关文章

  • 【hdu6547】Tree（树链剖分， 线段树区间根号）
    problemalgorihtm1、树链剖分什么是树链剖分（重链剖分）？树链，就是树上的路径。剖分，就是把路径分类为重链和轻链。对于树上的一个点，与其相连的边中，连向的节点子树大小最大（重儿子）......
  • 【230324-5】求：1/Sin10°-根号3/Cos10°
    ......
  • hdu 1853 Cyclic Tour(费用流OR二分图最佳匹配，5级)
    O- CyclicTourTimeLimit:1000MS     MemoryLimit:65535KB     64bitIOFormat:%I64d&%I64uSubmit StatusSystemCrawler (2013-05-30)......
  • 力扣-数组-二分查找704
        1classSolution(object):2defsearch(self,nums,target):3"""4:typenums:List[int]5:typetarget:int6......
  • P1570 KC 喝咖啡（小数二分）
    P1570KC喝咖啡题意：给定调料种数\(n\)和能加入的调料数\(m\)，以及每种调料的美味度\(v_i\)，消耗的时间\(c_i\)。请选择单位时间的美味度最大的咖啡。分析：\(t=\fra......
  • P1163 银行贷款（小数二分）
    P1163银行贷款分析变量命名如下：\(n\)表示贷款的原值，\(m\)表示每月支付的分期付款金额，\(k\)表示分期付款还清贷款所需的总月数。\(p\)表示贷款的月利率第......
  • 二分
    二分算法（一个简单且非常实用的算法）算法思想，通过中间值不断缩短检索区域-->大大降低T的可能性-->只要是检索的题目都可以用二分查找来解决算法思路：1.确定左右边界2.......
  • Tree Master (根号分治,离散化)
    题目大意:给出一个树,每次给出2个相同高度的点,然后依次向父亲走,问val[a]*val[b]这些值加起来是多少 思路:直接map映射关联容器,时间复杂度过大根号分治?于是......
  • 704.二分查找——学习笔记
    题目：给定一个n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。示例1输入:nums=[-1,0,3......
  • Leetcode 4. 寻找两个正序数组的中位数（二分）
    题目链接在这里：是一道很好的二分题，一开始没有想到越界怎么处理，忽略了(m+n)/2一定介于min(n,m)和max(n,m)之间，因此如果确定在短的数组上进行二分就不用考虑越界问题了，其次......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99