Generic placeholder image
闲敲代码、落灯花
What's past is prologue

联系邮箱:email@hezehua.net


联系QQ:1907330840

座右铭

保持热情,持续学习,每日精进

算法--大数开方

算法--大数开方

本文与作者在csdn上的博文【算法--大数开方】保持同步


     1-一个n位数的开方的位数m满足下列条件:

         m=n/2(n为偶数);

         m=n/2+1(n为奇数);

         以此我们可以确定大数开方的位数,然后判断最高位:

         设一个数为abcd,那么它的开方设ef,将e从0~9遍历,如果当e=x时,xf^2<abcd<(x+1)f^2,即可确定x为ef的最高位,然后将f从0~9遍历,当得到xy^2<abcd<x(y+1)^2时,即可确定y为其次高位,同理可算出其它位数更多的大数开方

     2-1中表达式xf^2<abcd<(x+1)f^2xy^2<abcd<x(y+1)^2是大数比较,这是比较简单的问题,把他们每位都放入数组中,从最高位开始比较,一旦有一个位有大小关系即可相应判断大小,另外保存相等数位的数量以判断是否相等,一旦相等现有数据就是其开方不需再循环遍历求其它数位的数值。

     下面贴上代码:(此代码因用于解决某题目需要,功能为输入两个大数,并将它们的开方输出,但上诉方法都体现在函数模块中)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<sstream>
#include <cstdlib>
using namespace std;

void assignment(int* s,int n){//数组初始化为0
    for(int i=0;i<n;i++){
        s[i]=0;
    }
} 
void Multiplication(char *arr1,char* arr2,int* Result){ //大数乘法
    int n,m;n=strlen(arr1);m=strlen(arr2);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            Result[i+j]=Result[i+j]+(arr1[i]-'0')*(arr2[j]-'0');
        }
    }
}
int reorganize(int *Result,int n){//将大数乘法的结果整理得到最终的十进制形式
    int k,z=0,t=0,p=0;
    for(int i=0;i<n;i++){
        if(Result[i]>9){
            t=Result[i]%10;
            Result[i+1]=Result[i+1]+Result[i]/10;
            Result[i]=t;            
        }
    }
    k=n;
    while(k--){
        if(Result[k]!=0){
            z=1;
        }
        if(z==1){
            p++;
        }
    }
    return p;
}
int Comparison(int *Result,int *Root,int n){//大数比较
    int k=0,s=n;
    for(int i=n-1;i>=0;i--){
        if(Result[i]<Root[i])return 1;
        else if(Result[i]>Root[i])return 0;
        else if(Result[i]==Root[i])k++;
        if(k==s)return -1;
    }
    return 0;
}
int getsqrt(char *arr,int *Result,int *Root,int z,int n){//大数开方  
    int t;
    for(int i=z-1;i>=0;i--){
        for(int j=0;j<10;j++){
            arr[i]=j+'0';
            assignment(Root,n);
            Multiplication(arr,arr,Root);
            if(Root[n-1]<=9)reorganize(Root,n);t=Comparison(Result,Root,n);  
            if(t==1){

                arr[i]=j+'0'-1;
                break;
            }
            if(t==-1){
                arr[i]=j+'0';
                return 0;
            }

        }           
    }
    return 0;   
}
int main(){
    string s1,s2;
    int n,m,z1,z2;char h;
    cin>>s1>>s2;//以输入字串的方式输入数据,方便动态为数据分配空间
    n=s1.length();m=s2.length();
    int *ar1=new int[n+1];int *ar2=new int[m+1];          
    z1=n%2==0?n/2:n/2+1;z2=m%2==0?m/2:m/2+1; //确定方根的位数          
    char *arr1=new char[z1+1];char *arr2=new char[z2+1];
    arr1[z1]='\0';arr2[z2]='\0';                   
    int *Root1=new int[n+1];int *Root2=new int[m+1];int *Root=new int[z1+z2];
    int i=n-1,j=m-1;
    stringstream ss1(s1);while(ss1>>h)ar1[i--]=h-'0';ar1[n]=0;
//将输入字符数据转化为整型数据
    stringstream ss2(s2);while(ss2>>h)ar2[j--]=h-'0';ar2[m]=0;
    memset(arr1,'0',z1);memset(arr2,'0',z2);
    assignment(Root,z1+z2); 
    getsqrt(arr1,ar1,Root1,z1,n+1);
    getsqrt(arr2,ar2,Root2,z2,m+1); 
        return 0;       
} 



      

猜你喜欢
生成子集——位向量法
阅读 380

生成0~n序列的子集对于0~n的每一个值在集合中都有存在和不存在两种状态,所以递归每个值的存在状态即可生成子集#include #include #include #include

在生成1~n的排列一文中,我们获取排列时用了控制不相等来实现让每个数都不重复地出现,所以如果要生成含有重复元素的全排列,对对生成1~n的排列的程序适当修改即可。 首先,把各个元素改成用户输入,输入数组为p,然后把if(a[k]==j)改为if(a[k]==p[j]),a[cur]=j改成a[cur...

子集生成算法——增量构造法
阅读 1071

思路是一次选出一个元素放入集合中生成0~n的子集,每次选出最小的值放入集合中,通过从0递增得到下一个位置的值。#include #include #include #include

在棋盘上放置8个皇后,使得他们不能相互攻击,此时,每个皇后的攻击范围为同行同列和同对角线,要求找出所有解, 回忆之前分析生成排列所用的解答树,我们再把问题简化为四皇后问题,规则不变,写出它的完整解答树 与生成1~n的排列这篇博文中的解答树最大的不同点就是----只有一条或者几条路径可以...

算法--库函数实现全排列
阅读 396

c++的STL中提供了一个库函数next_permutation,代码如下: #include #include #include #include #include #include using namespace std; int main(){ int n,p[10]; ...

生成子集——二进制法
阅读 546

用二进制位的0和1表示集合中是否存在该元素要生成0~n的子集,先生成0~n的二进制序列,这些序列的0、1位正好可以对应一个子集中全集在该位置上的元素是否存在,将其作为子集中存在的元素的标记,输出对应元素。#include #include

乘法运算过程模拟法首先获取输入的乘数(a)与被乘数(b)字符串,按一般乘法运算过程,先是a的最后一位数字与b的最后一位数字相乘,接着a中用于相乘的数下标递减,直到a中所有数字与b最后一位都相乘过,保存结果后再递减b中的用于相乘的数字的下标,循环下去,直到b中每一位数都与a所有数相乘完。 在这个过程...

大数乘法(一)
阅读 488

常用的大数相乘算法有模拟加减法和分治法,第一种符合我们的运算习惯,第二种用数学方法提高了效率,(具体描述与实现可参考http://www.cnblogs.com/heyonggang/p/3599857.html)而两种各有优势的方法的程序实现都比较复杂,并且不易于初学者理解,于是我琢磨出了一个将...