算法合集之問題中的變與不變(已修改)
2024-10-28 20:36 本頁面
【正文】 問題中的變與不變 長(zhǎng)沙市雅禮中學(xué) 陳雪 引言 ? 對(duì)變量進(jìn)行操作是信息學(xué)中的常見問題。 ? 如果能找到變量之間的關(guān)系，把變量轉(zhuǎn)化成不變量，那么算法的效率就將得到質(zhì)的提升。 [例一 ]螞蟻 ? 一條樹枝上有 N只螞蟻。給出他們的位置，如何安排螞蟻初始的方向使得全部螞蟻掉落的時(shí)間最早或最晚。 ? 最多 1,000,000只螞蟻。 感性認(rèn)識(shí) ? 左邊的螞蟻向左端走，右邊的螞蟻向右端走。 ? 如何使全部掉落的時(shí)間最晚？ ? 猜想：讓左邊的螞蟻向右端走，同時(shí)右邊的螞蟻向左端走。 理性分析 ? 直接證明猜想難度比較大。 ? 看一般的情況 : ? 紀(jì)錄 2只螞蟻的有用信息 :速度 和位置 。 ? 設(shè) 。 iV iW)},(),{( bbaa WVWVU ?? 在螞蟻相遇前一刻 , )},1(),1{( WWU ??在螞蟻相遇后一顆 )},1(),1({39。 ww?? 一個(gè)集合內(nèi)螞蟻相遇 集合不變 繼續(xù)分析 ? 另 ? 任何兩只屬于集合 U內(nèi)的螞蟻相遇之后，集合 U不變。 ? 集合 U只隨著時(shí)間的變化而變化。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1