算法1.复数乘积和整数划分问题

末蓝、 2022-07-14 13:39 177阅读 0赞

1.  设![这里写图片描述][SouthEast]

(1) 算法设计思路  
xy=(ac-bd)+(ad+bc)i可以转换成xy=(ac-bd)+((a+b)(c+d)-ac-bd)i，即为一个3次乘法计算。  
在对其中的ac，bd,(a+b)(c+d)进行大整数的乘法的分治设计。  
把a和c分为2段，每段长为n/2位，分别记为a1，a2和c1，c2，故a=a1\*2^(n/2)+a2，c=c1\*2(n/2)+c2.则ac=a1c1\*2^n+((a1-a2)(c2-c1)+a1c1+a2c2)\*2^(n/2)+a2c2。其他bd，和(a+b)(c+d)同理。采用递归的方法将xy划分，递归结束条件为位数剩下1.

(2) 算法实现的伪代码  
功能描述：计算a,b的乘积  
输入：a,b（均为非负整数）  
输出：a\*b的结果  
fun(stringa,string b)\{  
int n=a.length();  
ing m=b.length();  
if (n=1||m=1) return a\*b;  
long a1=(long)substring(0,n/2)//取左半边  
long a2=(long)substring(n/2,n)取右半边  
long b1=(long)substring(0,m/2)  
long b2=(long)substring(m/2,m)  
return long x=(long)(fun(a1,b1)\*pow(10,a2.length()+b2.length())+fun(a1,b2)\*pow(10,a2.length())+fun(a2,b1)\*pow(10,b2.length)+fun(a2,b2))  
\}

(3) 实现代码

import java.util.*;
            public class main {
                    static public long fun(String a,String b){
                            long sum=0;
                            long a0=Long.parseLong(a);//将a转换成整数
                            long b0=Long.parseLong(b);
                            int n=a.toString().length();//获取a的长度
                            int m=b.toString().length();
                            if (n==1||m==1)
                                    return a0*b0;//如果长度为1，则返回，结束递归
                            String a1=a.toString().substring(0, n/2);//获取a的左半边
                            String a2=a.toString().substring(n/2, n);//获取a的右半边
                            String b1=b.toString().substring(0, m/2);//获取b的左半边
                            String b2=b.toString().substring(m/2, m);//获取b的右半边
                            //运用公式直接运算，ac=a1c1*2^n+((a1-a2)(c2-c1)+a1c1+a2c2)*2^(n/2)+a2c2
                            sum=(long)(fun(a1,b1)*Math.pow(10,a2.length()+
                                    b2.length())+fun(a1,b2)*Math.pow(10,a2.length())
                                    +fun(a2,b1)*Math.pow(10,b2.length())+fun(a2,b2));
                            return sum;
                    }
                    public static void main(String []args){
                            Scanner in=new Scanner(System.in);
                            while(true){
                                    System.out.println("输入，a,b,c,d");
                                    System.out.println("分别表示x=a+bi 和 y=c+di");
                                    //录入数据
                                    String a=in.next();
                                    String b=in.next();
                                    String c=in.next();
                                    String d=in.next();
                                    long c0=Long.parseLong(c)+Long.parseLong(d);//将数据从字符串转化成long
                                    long b0=Long.parseLong(b)+Long.parseLong(a);
                                    //将long转换成字符串
                                    String ab=String.valueOf(b0);
                                    String cd=String.valueOf(c0);
                                    //调用函数
                                    long num1=fun(a, c);
                                    long num2=fun(ab, cd);
                                    long num3=fun(b, d);
                                    System.out.println("x*y="+(num1-num3)+"+"+(num2-num1-num3)+"i");
                                    System.out.println();
                            }
                    }
            }

(4) 算法运行结果及计算时间复杂度分析  
![这里写图片描述][SouthEast 1]  
时间复杂度：该方法主要是运用了大整数乘法的分治运算，  
T(n)=O(1), n=1  
3T(n/2)+O(n), n>1  
T(n)=O(n^log3)  
(5) 体会  
在考虑问题的时候，根据课本的知识进一步思考，如果两个整数的位数不一样，并且有可能为奇数，所以采用n/2划分的时候有可能会少了一位，所以使用字符串来录入数据。当2个整数的位数不一样的时候，构造的方法和构造位数一样的方法差不多。编写的过程中多次需要将字符串转换成long和将long转换成字符串。

1.  ![这里写图片描述][SouthEast 2]  
    \{6\}；  
    \{5+1\}；  
    \{4+2\}，\{4+1+1\}；  
    \{3+3\}，\{3+2+1\}，\{3+1+1+1\}；  
    \{2+2+2\}，\{2+2+1+1\}，\{2+1+1+1+1\}；  
    \{1+1+1+1+1+1\}。  
    (1) 算法设计思路
2.  设q（n，i），表示对n进行i划分
3.  当n=1或者i=1时，q（n，i）=1
4.  当n

import java.util.*;
    public class huafen {
        public static void main(String []args){
            Scanner in=new Scanner(System.in);
            while (true){
                System.out.println("输入要划分的正整数");
                int n=in.nextInt();
                int c=huafen(n, n);
                System.out.println("正整数 "+n+" 有 "+c+" 种不同的划分方案");
                System.out.println();
            }
        }
         static int huafen(int n,int i){
            if (n<1||i<1) //当n或者i小于1时，没有划分结果，直接返回0
                return 0;
            else if (n==1||i==1)//当n或者i=1时，只有一种划分结果
                return 1;
            else if (n<i)//当n<i最大的划分即为huafen（n,n）=1
                return huafen(n,n);
            else if (n==i)//当n=i，划分为n1=n和n1=n-1组成
                return huafen(n,n-1)+1;
            return huafen(n,i-1)+huafen(n-i,i);//划分为n1=i，和n1<=i-1组成
        }
    }

(3) 算法运行结果及计算时间复杂度分析

![这里写图片描述][SouthEast 3]  
时间复杂度O（NlogN）  
(4) 体会  
递归算法的结构比较清晰，但是运行效率比较低和花费的计算时间长，占用的存储空间多。对于该问题，先分析划分的大小，一般先考虑特殊值，例如i<1，i=1，i=n，i>n，最后再考虑i

[SouthEast]: /images/20220714/793148baa35b419ca827cccea2bd71c4.png
[SouthEast 1]: /images/20220714/bd40199574404439b392940380ad89a2.png
[SouthEast 2]: /images/20220714/edf860df8c614469b4f4283bb837b09b.png
[SouthEast 3]: /images/20220714/07a35df6178045b7bfd784c26976beeb.png