國家集訓(xùn)隊(duì)2006論文集李天翼(已修改)
2025-05-18 00:18 本頁面
【正文】 從特殊情況考慮 復(fù)旦附中 李天翼 引子 ? 從特殊情況考慮是一種重要的數(shù)學(xué)思想。 ? 在算法設(shè)計(jì)中，巧妙地運(yùn)用這一思想，可以取得事半功倍的效果。 ? 特殊情況主要分為兩種：極端情況和簡(jiǎn)單情況 極端情況：例 1 Bra 簡(jiǎn)單情況：例 2 Sko 問題一 (POI 0304 Bra 改編 ) 問題描述 ? 如圖，給定 n個(gè)門 ,分別編號(hào)為 0至 n1。 每個(gè)門可能有多個(gè)輸入端，但只有一個(gè)輸出端。 ? 電路的信號(hào) 有三種可能性： 0、 1/2和 1。 ? 編號(hào)為 0和 1的門沒有輸入端， 0號(hào)門始終輸出0， 1號(hào)門始終輸出 1。對(duì)于其它的門，它的輸入信號(hào)中 ? 0的個(gè)數(shù)比 1的個(gè)數(shù)多時(shí)，它輸出 0； ? 1的個(gè)數(shù)比 0的個(gè)數(shù)多時(shí)，它輸出 1； ? 0的個(gè)數(shù)和 1的個(gè)數(shù)一樣多時(shí)，它輸出 1/2； ? 保證存在符合要求的輸出狀態(tài)。 ? 給定一個(gè)電路，要求盡可能多地確定每個(gè)門的輸出結(jié)果。 問題一 問題描述（續(xù)） 問題一 初步思考 ? 令 Cj,i表示 i號(hào)門的所有輸入端中，來自 j號(hào)門輸出端的數(shù)量。設(shè) P(i)為 i號(hào)門的輸出狀態(tài)。 ? C2,0=1,C2,1=1,C3,2=1,C3,4=1,C4,2=1,C4,4=1 其它均為 0 ? 令 ， 問題一 初步思考（續(xù)） 即相當(dāng)于 i(i1)號(hào)門所有輸入信號(hào)的平均值。 ? U(i)1/2，則 P(i)=0 ? U(i)=1/2，則 P(i)=1/2 ? U(i)1/2，則 P(i)=1 ? ?? ?1,01,0njijnjijC P jUiC???????? 令 Pmin(i) 和 Pmax(i)分別為 P(i)在所有可能的電路中能取到的最小值和最大值，它們是 P(i)的 極端 情況。 ? 顯然，若 Pmin(i)=Pmax(i) (0≤ i≤ n1)，則 i號(hào)門的輸出狀態(tài)是固定的，否則就不是固定的。 ? 因此，我們只需要求出 Pmin(i)和 Pmax(i)。 問題一 考慮極端情況 問題一 一個(gè)想法 ?如果 P(k)變大，那么所有的U(i)(
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1