分治法求x的n次方的JAVA程序

以下是使用分治法求x的n次方的Java程序：

Copy code

public class Power {

public static void main(String[] args) {

double x = 2.0 // 底数

double n = 10 /世隐亏/ 指数

double result = power(x, n)

System.out.println(x + " 的 " + n + " 次方为：" + result)

}

// 分治法求幂运算

public static double power(double x, double n) {

if (n == 0) { // n为0时，直接返回1

return 1

}

double half = power(x, n / 2)

if (n % 2 == 0) { // n为偶数时，两半乘起来即可

return half * half

} else { // n为奇数时，需要多乘一次x

return half * half * x

}

}

}

首先，在 main() 方法中定义了底数 x 和指数 n。然后调用 power() 方法求 x 的 n 次方，并将结果输出到屏幕上。

power() 方法使用了分治法来实现幂运算。当 n 是0时，直接返回1；否则将 n 分成两半，分别递归求出两半的幂，然后根据 n 是奇数还是偶数来计算结果，最后返回计算结果。

由于每次递归将 n 除以2，因此该算法的时携粗间复杂搜神度为 Θ(lgn)。

生活中用分治法解决问题的案例如下：

找出伪币

给你一个装有16个硬币的袋子。16个硬币中有一个是伪造的，并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务，将提供一台可用来比较两组硬币重量的仪器，利用这台仪器，可以知道两组硬币的重量是否相同。

比较硬币1与硬币2的重量。假如硬币1比硬币2轻，则硬币1是伪造的；假如硬币2比硬币1轻，则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等，则比较硬币3和硬币4。同样，假如有一个硬币轻一些，则寻找伪币的任务完成。

假如两硬币重量相等，则继续比较硬币5和硬币6。按照这种方式，可以最多通过8次比较来判断伪币的存在并找出这一伪币。

另外一种方法就是利用分而治之方法。假如把16个硬币的例子看成一个大的问题。

第一步，把这一问题分成两个小问题。随机选择8个硬币作为第一组称为A组，剩下的8个硬币作为第二组称为B组。这样，就把16个硬币的问题分成两个8硬币的问题来解决。

第二步，判断A和B组中是否有伪币。可以利用仪器来比较A组硬币和B组硬币的重量。假如两组硬币重量相等，则可以判断伪币不存在。假如两组硬币重量不相等，则存在伪币，并且可以判断它位于较轻的那一组硬币中。

最后，在第三步中，用第二步的结果得出原先1 6个硬币问题的答案。若仅仅判断硬币是否存在，则第三步非常简单。无论A组还是B组中有伪币，都可以推断这1 6个硬币睁码中存在伪币。因此，仅仅通过一次重量的比较，就可以判断伪币是否存在。

假设需要识别出这一伪币。把两个或三个硬币的情况作为不可再分的小问题。注意如果只有一个硬币，那么不能判断出它是否就是伪币。在一个小问题中，通过将一个硬币分别与其他两个硬币比较，最多比较两次就可以找到伪币。

这样16硬币的问题就被分为两个8硬币（A组和B组）的问题。通过比较这两组硬币的重量，可以判断伪币是否存在。如果没有伪币，则算法终止。否则继续划分这两组硬币来寻找伪币。假设B是轻的那一组，因此含早尘再把它分成两组，每组有4个硬币。

称其中一组为B1，另一组为B2。比较这两组，肯定有一组轻一些。如果B1轻，则伪币在B1中，再将B1又分成两组，每组有两个硬币，称其中一组为B1a，另一组为B1b。比较这两组，可以得到一个较轻的组。

由于这个组只有两个硬币，因此不必再细分。比较组中两个硬币的重量谈禅，可以立即知道哪一个硬币轻一些。较轻的硬币就是所要找的伪币。

扩展资料：

解题步骤

分治法解题的一般步骤：

（1）分解，将要解决的问题划分成若干规模较小的同类问题；

（2）求解，当子问题划分得足够小时，用较简单的方法解决；

（3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

参考资料来源：百度百科-分治算法

#include <stdio.h>族轿

#define N 21

int max(int a,int b){

if(a>银穗桥b)

return a

return b

}

int getM(int * a,int l,int u){

if(u==l)

return a[u]

else{

return max(getM(a,l,(u+l)/锋猛2),getM(a,(u+l)/2+1,u) )

}

}

int main()

{

int a[N]={1,2,3,4,5,6,7,8,9,21,11,12,13,14,15,16,17,18,19,20,17}

printf("max=%d",getM(a,0,N-1))

return 0

}

---