您好,登錄后才能下訂單哦!
這篇文章主要介紹“web分治算法怎么使用”,在日常操作中,相信很多人在web分治算法怎么使用問題上存在疑惑,小編查閱了各式資料,整理出簡單好用的操作方法,希望對大家解答”web分治算法怎么使用”的疑惑有所幫助!接下來,請跟著小編一起來學(xué)習(xí)吧!
在計算機(jī)科學(xué)中,分治法是一種很重要的算法。字面上的解釋是分而治之,就是把一個復(fù)雜的問題分成兩個或更多的相同或相似的子問題,再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解,原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎(chǔ),如排序算法(快速排序,歸并排序),傅立葉變換(快速傅立葉變換)……
任何一個可以用計算機(jī)求解的問題所需的計算時間都與其規(guī)模有關(guān)。問題的規(guī)模越小,越容易直接求解,解題所需的計算時間也越少。例如,對于n個元素的排序問題,當(dāng)n=1時,不需任何計算。n=2時,只要作一次比較即可排好序。n=3時只要作3次比較即可,…。而當(dāng)n較大時,問題就不那么容易處理了。要想直接解決一個規(guī)模較大的問題,有時是相當(dāng)困難的。
分治法的設(shè)計思想是:將一個難以直接解決的大問題,分割成一些規(guī)模較小的相同問題,以便各個擊破,分而治之。
分治策略是:對于一個規(guī)模為n的問題,若該問題可以容易地解決(比如說規(guī)模n較?。﹦t直接解決,否則將其分解為k個規(guī)模較小的子問題,這些子問題互相獨立且與原問題形式相同,遞歸地解這些子問題,然后將各子問題的解合并得到原問題的解。這種算法設(shè)計策略叫做分治法。
如果原問題可分割成k個子問題,1<k≤n,且這些子問題都可解并可利用這些子問題的解求出原問題的解,那么這種分治法就是可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式,這就為使用遞歸技術(shù)提供了方便。在這種情況下,反復(fù)應(yīng)用分治手段,可以使子問題與原問題類型一致而其規(guī)模卻不斷縮小,最終使子問題縮小到很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一對孿生兄弟,經(jīng)常同時應(yīng)用在算法設(shè)計之中,并由此產(chǎn)生許多高效算法。
(1)二分搜索 (2)大整數(shù)乘法 (3)Strassen矩陣乘法 (4)棋盤覆蓋 (5)合并排序 (6)快速排序 (7)線性時間選擇 (8)最接近點對問題 (9)循環(huán)賽日程表 (10)漢諾塔
一、回文字符串
這里的回文是指資格字符串,它從頭到尾讀與從尾到頭讀的內(nèi)容是一致的,比如說doggod,無論從左到右耗時從右到左都是一樣的。
def isPal(s): if len(s) <= 1: return True else: return s[0]==s[-1] and isPal(s[1:-1]) s = 'doggod' result = isPal(s) print result
二、二分查找
public static int binarySerach(int[] arr,int key){ int low = 0; int high = arr.length - 1; int middle = 0; if(key < arr[low] || key > arr[high] || low > high){ return -1; } while(low <=high){ middle = (low + high)/2; if(arr[middle] > key){ high = middle -1; } else if(arr[middle]< key){ low = middle + 1; } else { return middle; } } return -1; }
三、歸并排序
歸并排序(MERGE-SORT)是利用歸并的思想實現(xiàn)的排序方法,該算法采用經(jīng)典的分治(divide-and-conquer)策略(分治法將問題分(divide)成一些小的問題然后遞歸求解,而治(conquer)的階段則將分的階段得到的各答案"修補"在一起,即分而治之)。
第一, 分解: 把待排序的 n 個元素的序列分解成兩個子序列, 每個子序列包括 n/2 個元素.
第二, 治理: 對每個子序列分別調(diào)用歸并排序MergeSort, 進(jìn)行遞歸操作
第三, 合并: 合并兩個排好序的子序列,生成排序結(jié)果.
public static int[] sort(int[] a,int low,int high){ int mid = (low+high)/2; if(low<high){ sort(a,low,mid); sort(a,mid+1,high); //左右歸并 merge(a,low,mid,high); } return a; } public static void merge(int[] a, int low, int mid, int high) { int[] temp = new int[high-low+1]; int i= low; int j = mid+1; int k=0; // 把較小的數(shù)先移到新數(shù)組中 while(i<=mid && j<=high){ if(a[i]<a[j]){ temp[k++] = a[i++]; }else{ temp[k++] = a[j++]; } } // 把左邊剩余的數(shù)移入數(shù)組 while(i<=mid){ temp[k++] = a[i++]; } // 把右邊邊剩余的數(shù)移入數(shù)組 while(j<=high){ temp[k++] = a[j++]; } // 把新數(shù)組中的數(shù)覆蓋nums數(shù)組 for(int x=0;x<temp.length;x++){ a[x+low] = temp[x]; } }
到此,關(guān)于“web分治算法怎么使用”的學(xué)習(xí)就結(jié)束了,希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學(xué)習(xí),快去試試吧!若想繼續(xù)學(xué)習(xí)更多相關(guān)知識,請繼續(xù)關(guān)注億速云網(wǎng)站,小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。