cy分治解題報(bào)告ppt課件-文庫(kù)吧資料
2024-12-14 02:42本頁(yè)面
【正文】 ? 如果本題中 Vi的規(guī)模進(jìn)一步擴(kuò)大，你能想出解決的辦法嗎？ 三色二叉樹(shù) ? 一棵二叉樹(shù)可以按照如下規(guī)則表示成一個(gè)由 0、 2組成的字符序列，我們稱之為“二叉樹(shù)序列 S”： ? 對(duì)一棵二叉樹(shù)的節(jié)點(diǎn)進(jìn)行染色。因此超車次數(shù)就是冒泡法中元素一共要被交換的次數(shù)。 小結(jié) ? 整個(gè)超車的過(guò)程實(shí)際上就是一個(gè)不斷交換相鄰元素的排序過(guò)程。 } 運(yùn)算量 =O(nk) *107 編制測(cè)試數(shù)據(jù) ? 用手工可以檢驗(yàn)的小數(shù)據(jù)，驗(yàn)證程序的正確性 ? 編寫程序隨機(jī)生成大數(shù)據(jù)，檢驗(yàn)程序的執(zhí)行效率（使用隨機(jī)函數(shù)） ? 注意檢驗(yàn)邊界條件。k100。 num[v]++。in。 memset(num,0,sizeof(num))。 . ViVj, XiXj, … ? 能否考慮用速度的值來(lái)表示問(wèn)題？ ? num[v]：表示當(dāng)前車之前速度為 v的車有多少輛 ? 如何定義超車： ? 車輛 i能被超過(guò)的次數(shù)為 ???991][iVkknum算法 int num[100]。 ? 在現(xiàn)實(shí)問(wèn)題，也往往存在這樣現(xiàn)象，大家應(yīng)該對(duì)此充分重視。 ? 嘗試換一種數(shù)據(jù)結(jié)構(gòu)，改變問(wèn)題的表示方法往往能收到意想不到的效果。 ? 如果想不到這種方法怎么辦？ 另一種解法 ? 在一個(gè)問(wèn)題無(wú)法得到解決時(shí)，就需要換一個(gè)角度看問(wèn)題。 ? 典型例子：二分法 ? 難點(diǎn)：合并 算法優(yōu)化 ——分治策略 ? 思想：將 n個(gè)元素分成大小大致相同的兩個(gè)子序列，分別對(duì) 2個(gè)子序列求逆序?qū)?shù)，再將 2個(gè)子序列合并得到原序列的逆序?qū)?shù)。 ? 本題時(shí)限 1秒 ！ ? 算法低效的原因：每次只能計(jì)算 1個(gè)逆序?qū)Α?j++) if (v[i] v[j]) count++。 i++) for (j = i+1。 for (i = 0。 算法 int v[n]。 ? 由于超車的判斷只涉及 Xi的大小關(guān)系，與具體取值無(wú)關(guān)，因此 Xi可以不必存儲(chǔ)，而用數(shù)組的下標(biāo)代替 Xi。 ? 基本運(yùn)算：判斷超車。 數(shù)學(xué)模型 ? 題目給了哪些數(shù)據(jù)？ ? N個(gè)有序?qū)?(Xi,Vi) ? 如何定義超車？ ? i車將超過(guò) j車，當(dāng)且僅當(dāng) XiXj且 ViVj ? 模型：求序列的逆序?qū)?shù)。比賽沒(méi)有終點(diǎn)，即會(huì)永遠(yuǎn)進(jìn)行下去。第 i個(gè)飛船從起跑線右邊 Xi (Xi106)處開(kāi)始向右行駛。數(shù)據(jù)結(jié)構(gòu) ? 基本數(shù)據(jù)結(jié)構(gòu) ? 搜索、分治 ? 動(dòng)態(tài)規(guī)劃 ? 貪心 …… How to practice? Online Judge ? ? ? Online Contest ? 3月 20日 網(wǎng)上熱身賽 13:0021:00 首屆福州大學(xué)程序設(shè)計(jì)競(jìng)賽試題講解 解題的一般步驟 ? 理解題意，建立數(shù)學(xué)模型 ? 設(shè)計(jì)模型在計(jì)算機(jī)中表示的方法（數(shù)據(jù)結(jié)構(gòu)） ? 設(shè)計(jì)解決該問(wèn)題的算法 ? 分析算法的時(shí)空效率 ? 編程實(shí)現(xiàn) ? 測(cè)試程序的正確性和效率 ? 小結(jié) 飛船賽 ? N個(gè)飛船在直線跑道上比賽。 return 0。 ifstream fin(“”)。T, Microsoft, etc) ? Regional Contest 每年 10， 11， 12月
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1