cy分治解題報(bào)告ppt課件-在線瀏覽
2025-01-25 02:42本頁面
【正文】 賽 數(shù)學(xué)基礎(chǔ)筆試 日常訓(xùn)練 暑期集訓(xùn) 福州大學(xué) ACM/ICPC隊(duì)選拔賽 (每年 8月 ) ACM隊(duì)隊(duì)員的基本原則 ? 基本要求 ? 人品好 ? 愿意花時間在這項(xiàng)賽事上 ? 有團(tuán)隊(duì)合作精神 ? 能力要求 ? 程序設(shè)計(jì) ? 英語科技文獻(xiàn)閱讀 ? 數(shù)學(xué) 相關(guān)的知識 數(shù)學(xué)知識 ? 離散、組合 ? 數(shù)論、圖論 ? 計(jì)算幾何 算法 amp。每個飛船的起跑位臵均不相同。比賽開始后，它能在零時間內(nèi)加速到最大速度 Vi (Vi100)并永遠(yuǎn)保持此速度。求比賽過程中發(fā)生幾次超車。 ? 注意題目的數(shù)據(jù)范圍！ why? 數(shù)據(jù)結(jié)構(gòu) ? 原則：選擇的數(shù)據(jù)結(jié)構(gòu)應(yīng)能夠高效的處理題目中涉及的基本運(yùn)算。 ? 數(shù)據(jù)結(jié)構(gòu)：將 (Xi,Vi)存入數(shù)組中，即可根據(jù)超車的定義，直接求出答案。 ? int v[n]。 int count=0。 i n。 j n。 ? 運(yùn)算量 (n1)+(n2)+…+2+1=n(n1)/2 算法效率分析 ? 1=N=*105 ? 運(yùn)算量 = n(n1)/2=*1010 次 ? 1GHz = 109 次 /秒 ? 解決該問題，本算法約需要 半分鐘 。 算法優(yōu)化 ——分治策略 ? 思想：將規(guī)模為 n的問題分解為 k個規(guī)模較小的子問題，這些子問題與原問題相互獨(dú)立且與原問題相同，遞歸的解這些子問題，然后將子問題的解合并，得到原問題的解。 ? 難點(diǎn)：如何合并？ ? 原序列逆序?qū)?shù) =2個子序列逆序?qū)χ?滿足 V[i]V[j](0in/2+1,n/2jn+1)的數(shù)對數(shù) 算法優(yōu)化 ——分治策略 ? 滿足 V[i]V[j](0in/2+1,n/2jn+1)的數(shù)對數(shù)？如何計(jì)算？ ? 方法 1：對每個 i: while (v[i]v[j++]) … ? 還是 O(n2)的復(fù)雜度 ? 方法 2：如果兩個子序列是有序的 …… ? 6 4 2 5 3 1 ? 如何保證有序？邊合并邊排序即可 例子 6 4 2 5 3 1 6 4 2 5 3 1 6 4 2 5 3 1 6 4 2 5 3 1 逆序?qū)?=3 逆序?qū)?=3 排序： 6 逆序?qū)?=3+2 排序： 6,5 逆序?qū)?=5+1 排序： 6,5,4,3,2,1 6 5 4 3 2 1 算法效率分析 ? T(n)=2T(n/2)+O(n) ? 用迭代法解該遞推方程得 T(n)=O(nlogn) ? 計(jì)算量 =nlogn=*106log(*106) = *106 ? 效率提高的原因：充分利用有序性，每次可計(jì)算多個逆序?qū)Α? 切入點(diǎn)： ? 嘗試將逆序?qū)栴}轉(zhuǎn)化為已有現(xiàn)成的算法的經(jīng)典模型，即排序模型。 充分注意數(shù)據(jù)范圍 ? 它能在零時間內(nèi)加速到最大速度 Vi (Vi100) ? 其他的數(shù)據(jù)范圍都很大，唯獨(dú)這個數(shù)據(jù)范圍很小，這個矛盾往往是解題的突破口。 ? Tradeoff 新的數(shù)據(jù)結(jié)構(gòu) ? 原來是用車的編號來表達(dá)問題。 int count=0。 for (i=0。i++) { cinxv。 for (k=v+1。k++) { count+=num[k]。例如，本題中只有 1輛車時算法能否得到正確結(jié)果。這個
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1