分治算法講解-全文預(yù)覽
【正文】 for (ints=1。 (2)然后定義一個(gè)m值，m初始化為1，m用來控制每一次填充表格時(shí)i（i表示行）和j（j表示列）的起始填充位置。實(shí)現(xiàn)過程：(3)循環(huán)賽在n1天內(nèi)結(jié)束請(qǐng)按此要求將比賽日程表設(shè)計(jì)成有n行和n1列的一個(gè)表。 im+n。 } } else//當(dāng)數(shù)組b已經(jīng)被完全賦值到數(shù)組c中 { while(im)//當(dāng)數(shù)組a還沒有完全賦值 { c[k]=a[i]。k++。//就把數(shù)組a的元素賦給數(shù)組c i++。j=0。 for(j=0。 cinmn。歸并排序原理：歸并排序具體工作原理如下（假設(shè)序列共有n個(gè)元素）：將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作（merge)，形成floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素將上述序列再次歸并，形成floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素重復(fù)步驟2，直到所有元素排序完畢歸并操作：歸并操作(merge)，也叫歸并算法，指的是將兩個(gè)順序序列合并成一個(gè)順序序列的方法。 right=n1。 for(i=0。 } else { left=middle+1。 if (a[middle]==key) { return middle。}二分遞歸：include iostreamusing namespace std。i++) cina[i]。 int n,key,i。 } else if(a[mid]key) high=mid1。void erfen(int a[],int n,int key){ int low=0,high=n1,mid。 break。 cinx。 for(i=0。（4）重復(fù)上述過程，直到在數(shù)組中找到相同的數(shù)字。其缺點(diǎn)是要求待查表為有序表，且插入刪除困難。 三：分治使用情況 1) 該問題的規(guī)?？s小到一定的程度就可以容易地解決2) 該問題可以分解為相同類型的小問題（前提）3) 利用該問題分解出的子問題的解可以合并為該問題的解；（關(guān)鍵） 4) 該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題。而當(dāng)n較大時(shí)，問題就不那么容易處理了。問題的規(guī)模越小，越容易直接求解，解題所需的計(jì)算時(shí)間也越少。比如：二分查找，歸并排序，快速排序，樹的遍歷等等任何一個(gè)可以用計(jì)算機(jī)求解的問題所需的計(jì)算時(shí)間都與其規(guī)模有關(guān)。n=3時(shí)只要作3次比較即可，…。（可能會(huì)用到遞歸，大問題里包含小問題，找到規(guī)律然后解決） 分治基本策略：對(duì)于一個(gè)規(guī)模為n的問題，若該問題可以容易地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個(gè)規(guī)模較小的子問題，這些子問題互相獨(dú)立且與原問題形式相同，遞歸地解這些子問題，然
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1