【正文】 存在三個(gè)不同實(shí)根 (根的范圍在 100至 100之間 )，且根與根之差的絕對(duì)值 =1。 【 文件輸入 】 輸入僅一行，有四個(gè)數(shù)，依次為 a、 b、 c、 d 【 文件輸出 】 輸出也只有一行，即三個(gè)根 (從小到大輸出 ) 【 樣例輸入 】 1 5 4 20 【 樣例輸入 】 分析 ? 如果精確到小數(shù)點(diǎn)后兩位，可用簡(jiǎn)單枚舉法：將 x從 到 （步長(zhǎng) ）逐一枚舉，得到 20220個(gè) f(x)，取其值與 0最接近的三個(gè) f(x)，對(duì)應(yīng)的 x即為答案。 ? 直接使用求根公式，極為復(fù)雜。重復(fù)執(zhí)行如下的過程： ? (1).若 a+b或 f((a+b)/2)=0，則可確定根為(a+b)/2并退出過程； ? (2).若 f(a)*f((a+b)/2)0,則由題目給出的定理可知根在區(qū)間 (a,(a+b)/2)中 ,故對(duì)區(qū)間重復(fù)該過程； ? (3).若 f(a)*f((a+b)/2)0,則必然有 f((a+b)/2)*f(b)0,根在 ((a+b)/2,b)中 ,對(duì)此區(qū)間重復(fù)該過程。 分析 ? B、求方程的所有三個(gè)實(shí)根 ? 所有的根的范圍都在 100至 100之間，且根與根之差的絕對(duì)值 =1。即：除區(qū)間 [100， 100]外，其余區(qū)間[a,a+1]，只有當(dāng) f(a)=0或 f(a)若 f(a)=0 ，解即為 a；若 f(a)如此可求出方程的所有的解。 x0:=(x1+x2)div 2。y2:=cal(x2)。 if(x2x1 and y1*y20)then begin write((x2+x1)div 2:0:4)。end if(y1*y00 or x0x11)then divide(x1,x0)。 End。按照分治三步法來說， ? 歸并過程 為： （ 1）劃分： 把序列分成元素個(gè)數(shù)相等的兩半； （ 2）遞歸求解： 把兩半分別排序； （ 3）合并： 把兩個(gè)有序表合成一個(gè)有序表； 分析 ? 顯然，前兩部分是很容易完成的， 關(guān)鍵在于如何把兩個(gè)有序表合成一個(gè) 。 核心參考代碼 procedure MergeSort(left,right:integer)//歸并排序 begin if left=right then exit。 //找中間位 MergeSort(left,mid)。 //對(duì)右邊歸并 i:=left。 //合并左右 while(i=mid and j=right)do if(a[i]a[j])then begin temp[p]:=a[j]。inc(j)。inc(p)。end while(i=mid)do begin temp[p]:=a[i]。inc(i)。inc(p)。end for i:=left to right do a[i]:=temp[i]。 【 變形 1】 逆序?qū)?shù)目 ? 例題 3：求 “ 逆序?qū)?” 。例如數(shù)組（ 3， 1， 4，5， 2）的逆序?qū)τ?3,1,3,2,4,2,5,2。 ? 數(shù)據(jù)范圍： 1=n=30000。 C:=0。 ? 時(shí)間效率不盡如人意 … .. ? 問題出現(xiàn)在哪里呢？？ 分治算法： 采用二分法求解 : 記數(shù)列 a[st,ed]的逆序?qū)?shù)目為 d(st,ed)。 ? 和歸并排序一樣，劃分和遞歸求解都好辦，關(guān)鍵在于合并：如何求出 i在左邊，而 j在右邊的逆序?qū)?shù)目呢？統(tǒng)計(jì)的常見技巧是 “ 分類 ” 。 ? 幸運(yùn)的是，歸并排序可以幫助我們 “ 順便 ” 完成 f(j)的計(jì)算：由于合并操作是從小到大進(jìn)行排序的，當(dāng)右邊的 a[j]復(fù)制到 T中時(shí)，左邊還沒有來得及復(fù)制到 T的那些數(shù)就是左邊所有比 a[j]大的數(shù)。 ? 即把 “ if(a[i]a[j])then begin temp[p]:=a[j]。inc(j)。temp[p]:=a[j]。inc(j)。 ? 方法 1：順序查找。這個(gè)方法并沒有用到 “ n個(gè)數(shù)從小到大排列 ” 這一個(gè)關(guān)鍵條件，因而時(shí)間效率低下。假設(shè)需要在 a[L]~a[r]中查找元素 x。 ? 遞歸求解： 如果 a[m]x，那么元素只可能在 a[L]~a[m1]中； 如果 a[m]x，那么元素只可能在 a[m+1]~a[r]中。 方法 1：二分查找的遞歸實(shí)現(xiàn) function bsh(L,r,x:integer):integer。 if Lr exit(1)。 if a[m]=x bsh:=m。 else bsh:= bsh(m+1,r,x)。 方法 2：二分查找的非遞歸實(shí)現(xiàn)： function bsh(L,r,x:integer):integer。 while(L=r) do begin m:=(L+r) div 2。exit。 end bsh:=1。 【 擴(kuò)展 1】 二分查找求下界，即第一次出現(xiàn)的位置 function Erfen(L,r,x:integer):integer。 while(Lr)do begin mid:=(L+r)div 2。 end。 end。 【 文件輸出 】 輸出使得 xx達(dá)到 n位數(shù)字的最小正整數(shù) x。 快速冪 ? 【 問題描述 】 計(jì)算 an %k ， n=109。每次乘以 a， 時(shí)間復(fù)雜度 O(n)。 begin var x:integer。 for i:=1 to n do x:=x*a。 end。 合并：如果 n是偶數(shù)，則 an=(ax)2，否則 an=(ax)2*a 方法 2：分治算法 根據(jù)這個(gè)方法很容易寫出程序： function power(a,n:integer):integer。exit。 power:=((x*x)mod k*a)mod k。 power:=x*x mod k。 End。//輸入三個(gè)數(shù) t:=b。c[len]:=t mod 2。end。 for i:=len downto 1 do //用二分法實(shí)現(xiàn) ab mod k begin s:=s*s mod k。//如果是奇數(shù)，就多乘 a end。//輸出 ab mod k 求解線性遞推關(guān)系 【 例題 】 Fibonacci數(shù) 【 題目描述 】 Fibonacci數(shù)列定義為： f[i]=f[i2]+f[i1] (i2)，其中f[1]=1,f[2]=1。 【 文件輸入 】 輸入文件只有一行為一個(gè)整數(shù) n(1=n=2^311)。 【 樣例輸入 】 4 【 樣例輸出 】 3 【 數(shù)據(jù)范圍 】 對(duì)于 20%的數(shù)據(jù)， 1=n=1000 對(duì)于 40%的數(shù)據(jù)， 1=n=10000000 對(duì)于 100%的數(shù)據(jù)， 1=n=2^311 ? 樸素算法，肯定超時(shí) procedure Fib(n:integer) Begin var i:integer。f[1]:=1。 End。設(shè)計(jì)一個(gè)比賽的安排，使在 2n 1天內(nèi)每個(gè)隊(duì)都與不同的對(duì)手比賽。 【 文件輸出 】 輸出比賽安排表。 ? 仔細(xì)分析，可以發(fā)現(xiàn)，將問題進(jìn)行分解，能找出規(guī)律。 ? 當(dāng) n=2時(shí)，共有 4個(gè)球隊(duì)，需比賽 3天。 read(n)。a[1,1]:=1。 for i:=1 to n do m=2*m。 //構(gòu)造右上角方陣 a[i+h,j]:=a[i,j+h]。 //構(gòu)造右下角方陣 end。 end。（ n=60000） 分析 ? 【 問題簡(jiǎn)述 】 給定平面上 n個(gè)點(diǎn)的坐標(biāo)，找出其中歐幾里德距離最近的兩個(gè)點(diǎn)。 需要枚舉 O(n2)個(gè)點(diǎn)對(duì)，每個(gè)距離的計(jì)算時(shí)間為 O(1)，故總的時(shí)間復(fù)雜度為 O(n2)。 ? 合并：令 d=min{dL,dr}，則跨越兩邊的點(diǎn)對(duì)中，只有下面的豎條中的才有可