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;       
} 



      

猜你喜欢
算法--生成可重集排列
阅读 139

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

生成子集——位向量法
阅读 121

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

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

动态规划入门之国王的金矿
阅读 165

最近学习算法,对动态规划不太了解,使用的时候照搬转移方程式,知其然不知其所以然,今天看到一篇动态规划的教程,解释得非常通俗,原文在这里[动态规划入门教程] (http://blog.csdn.net/woshioosm/article/details/7438834),下面我用自己的记忆和理解...

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

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

用大数乘法计算阶乘
阅读 149

在比较小的范围内阶乘可以递归实现,而求更大的数的阶乘一般用到long long长整形数,不过,即使这样,在耗时和再大些的阶乘上力有不逮,所以,在输入比较大的情况下,用大数乘法计算阶乘是最好的选择。 计算过程分2步: 1、输入字符串s,将它的值保存到整型n中; 2、从1~i~n-1循环将i转化...

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

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

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