算法8.分治算法计算a^n

系统管理员 2022-07-13 11:22 153阅读 0赞

设a为一给定实数，设计一个分治算法，用于计算an (n为自然数)，并分析其计算时间复杂度，要求该算法的计算效率高于蛮力算法。  
1. 算法设计思路

1.当n为偶数的时候，an可以分治为(a^2/n)*(a^2/n)
        2.当n为奇数的时候，an可以分治为(a^2/n)*(a^2/n)*a
        3.当n=1，a^n=a;
        4.当n=0，a^n=1;

1.  算法实现的伪代码  
    功能描述：利用递归和分治求a^n  
    输入：a^n,a,n都为非负整数  
    输入：a^n的结果  
    int fun(int a,int n)\{利用递归和分治求a^n,输入a和n  
    当n=1，return a；  
    当n=0，return 1；  
    如果n%2=0，return fun(a,n/2)\*fun(a,n/2);  
    如果n%2!=0,return fun(a,n/2)\*fun(a,n/2)\*a  
    \}
2.  实现代码

import java.util.*;
    public class main {
        static int fun(int a, int n) {
       // 分治和递归的方法来求解a^n,输入a和n，其中分别表示a^n
            if (n == 0)// 如果n=0，则输出结果为1，
                return 1;
            else if (n == 1) {
       // 如果n=1，则输出a
                return a;
            } else if (n % 2 == 0)// 如果n为偶数，a^n可以分治为(a^2/n)*(a^2/n)，并且递归的调用自己
                return fun(a, n / 2) * fun(a, n / 2);
            else if (n % 2 != 0)// n为奇数的时候，a^n可以分治为(a^2/n)*(a^2/n)*a,并且递归的调用自己
                return fun(a, n / 2) * fun(a, n / 2) * a;
            return a;
        }
    
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            while (true) {
                System.out.println("依次输入非负整数a和n，系统会显示a^n");
                int a = in.nextInt();
                int n = in.nextInt();
                int result = fun(a, n);
                System.out.println("a^n=" + result);
            }
        }
    }

1.  算法运行结果及计算时间复杂度分析  
    ![这里写图片描述][SouthEast]  
    当n为偶数时，若递归运行到基值条件时，有2^k=n，可得，k=log n，  
    当n为奇数时，同理得k=log(n-1)，故最大的时间复杂度为log n。
2.  体会  
    分治法中，很多问题一般可以取n=2，例如a^2,。从分治法的一般设计模式可以知道，用分治法设计出来的程序一般的都是递归算法，所以，分治法的计算效率通常可以用递归方程来进行分析。

[SouthEast]: /images/20220713/63a8a5dc66e24441b649993b17907b11.png