国产成人精品一区二区三在线观看 ,精品中文字幕一区二区三区四区,久久香蕉国产线看观看亚洲片

本文實(shí)例講述了java分治法與二分搜索算法。分享給大家供大家參考，具體如下：

1、分治法

分治法的基本思想是將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題相互獨(dú)立且與原問(wèn)題相同。遞歸的解這些子問(wèn)題，然后將各子問(wèn)題的解合并得到原問(wèn)題的解。

分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：

　 1) 該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決
　 2) 該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題，即該問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。
　 3) 利用該問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解；
　 4) 該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共的子子問(wèn)題。

分治法的基本步驟：

分治法在每一層遞歸上都有三個(gè)步驟：

　　分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；
　　解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題；
　　合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。

它的一般的算法設(shè)計(jì)模式如下：

									divide-and-conquer(p)

									if |p|≤n0

									then return(adhoc(p))

									//將p分解為較小的子問(wèn)題 p1 ,p2 ,...,pk

									for i←1 to k

									do yi ← divide-and-conquer(pi) △ 遞歸解決pi

									t ← merge(y1,y2,...,yk) △ 合并子問(wèn)題

									return(t)

其中|p|表示問(wèn)題p的規(guī)模；n0為一閾值，表示當(dāng)問(wèn)題p的規(guī)模不超過(guò)n0時(shí)，問(wèn)題已容易直接解出，不必再繼續(xù)分解。adhoc(p)是該分治法中的基本子算法，用于直接解小規(guī)模的問(wèn)題p。因此，當(dāng)p的規(guī)模不超過(guò)n0時(shí)直接用算法adhoc(p)求解。算法merge(y1,y2,...,yk)是該分治法中的合并子算法，用于將p的子問(wèn)題p1,p2 ,...,pk的相應(yīng)的解y1,y2,...,yk合并為p的解。

子問(wèn)題的劃分：人們從大量實(shí)踐中發(fā)現(xiàn)，在用分治法設(shè)計(jì)算法時(shí)，最好使子問(wèn)題的規(guī)模大致相同。換句話說(shuō)，將一個(gè)問(wèn)題分成大小相等的k個(gè)子問(wèn)題的處理方法是行之有效的。許多問(wèn)題可以取 k = 2。這種使子問(wèn)題規(guī)模大致相等的做法是出自一種平衡(balancing)子問(wèn)題的思想，它幾乎總是比子問(wèn)題規(guī)模不等的做法要好。

2、二分搜索

大部分程序員應(yīng)該都知道二分搜索的大致原理，這里不再贅述。需要說(shuō)明的是二分搜索是所有以比較為基礎(chǔ)的搜索算法時(shí)間復(fù)雜度最低的算法。用二叉樹(shù)描速二分查找算法，最壞情況下與二叉樹(shù)的最高階相同。比較二叉樹(shù)線性查找也可用二叉樹(shù)表示，最壞情況下比較次數(shù)為數(shù)組元素?cái)?shù)量。任何一種以比較為基礎(chǔ)的搜索算法，其最壞情況所用時(shí)間不可能低于o(logn)。

Java分治法與二分搜索算法實(shí)例分析

二分搜索程序清單如下：

									import java.util.scanner;

									public class binarysearch {

									  public static int binarysearch (int[] a,int x,int n) {

									    int left = 0;

									    int right = n - 1;

									    while(left <= right) {

									      int middle = (left + right) / 2;

									      if(x == a[middle]) return middle;

									      if(x >= a[middle]) left = middle + 1;

									      else right = middle - 1;

									    }

									    return -1;

									  }

									  public static void main(string args[]) {

									    system.out.println("服務(wù)器之家測(cè)試結(jié)果：");

									    int[] a = new int[10];

									    for(int i = 0; i < a.length; i++) {

									      a[i] = i+1;

									      system.out.print(a[i] + " ");

									    }

									    system.out.println();

									    system.out.println("請(qǐng)輸入你要查詢(xún)的數(shù)：");

									    scanner sc = new scanner(system.in);

									    int b = sc.nextint();

									    int num = binarysearch(a, b, a.length) + 1;

									    system.out.println("要查找的數(shù)在第" + num + "個(gè)位置");

									  }

									}