淺談標(biāo)記在計算機程序設(shè)計中的應(yīng)用

鮑康勝

(合肥市第六中學(xué) 安徽合肥 230000)

一、引言

素數(shù)是一個很經(jīng)典的問題，但是對于很多學(xué)生來說，并不能很好地理解素數(shù)的概念，即使掌握了素數(shù)的概念也不會判斷一個數(shù)是否為素數(shù)，本文使用“標(biāo)記”的方法來判斷素數(shù)，并且詳細闡明使用的步驟。

求解素數(shù)時，最常見的就是用因子可能的范圍去依次掃描判斷，效率不高，數(shù)據(jù)量大時，容易超時，而線性篩素數(shù)算法大大提高了效率，確保了每個素數(shù)只被篩1次達到線性的復(fù)雜度，也有使用隨機產(chǎn)生數(shù)值的方法和一道循環(huán)掃描的方法來實現(xiàn)素數(shù)的求解。

作者從事高中信息學(xué)奧林匹克競賽的輔導(dǎo)工作有18個年頭了，因為根據(jù)全國信息學(xué)奧賽大綱，對選手的程序設(shè)計能力和數(shù)學(xué)建模能力要求很高，經(jīng)過長期的實踐摸索，作者發(fā)現(xiàn)初學(xué)者對“標(biāo)記”，理解不清，掌握不透，學(xué)生普通反映編寫困難，而“標(biāo)記”又是基礎(chǔ)算法，在后面的樹論、圖論等都會用到標(biāo)記，所以學(xué)好“標(biāo)記”顯得至關(guān)重要。

二、“標(biāo)記”使用的新思考

標(biāo)記的作用：把對問題的求解轉(zhuǎn)換成對標(biāo)記的判斷。

使用步驟三步走：

1.初始化標(biāo)記：你能夠直接判定結(jié)果的對立面,有幾種狀態(tài)，就取幾個值。

2.對標(biāo)記賦值：對每個對象的標(biāo)記值進行分析處理，對它賦值。

3.對標(biāo)記判斷：最后，只需要對標(biāo)記進行判斷，統(tǒng)計標(biāo)記的情況即可圓滿解決問題。

案例1：素數(shù)大酬賓，鍵盤讀入一個正整數(shù)n,判斷n是不是質(zhì)數(shù)，輸出“YES” or “No”

【輸入格式】zs.in

輸入文件一行有兩個數(shù)(n是小于32768的整數(shù))

【輸出格式】zs.out

輸出文件：是質(zhì)數(shù)時，輸出“Yes”，否則輸出“No”。

樣例輸入樣例輸出9No17Yes

問題分析：一個數(shù)是不是素數(shù)有兩種狀態(tài)，一種“是”，另一種“不是”，我們使用整型 flag變量，分別取1(對應(yīng)是)和0(對應(yīng)不是)。下面用新總結(jié)的標(biāo)記三步走來，實現(xiàn)質(zhì)數(shù)判定的C++程序

#include

using namespace std;

int main()

{

int i,n;

intflag=1;//第1步：初始化標(biāo)記，假定是質(zhì)數(shù)，因為很容易判斷不是質(zhì)數(shù)。

cin>>n;

for(i=2;i<=n/2;i++)

if(n%i==0) //當(dāng)前n能整除i

{

flag=0; //第2步：肯定不是質(zhì)數(shù)，對標(biāo)記賦值

break;//提前結(jié)束

}

else continue;//如果當(dāng)前i不能則繼續(xù)判斷下一個i+1

if(flag==1)//第3步：對標(biāo)記進行判斷，問題得解

cout<<"Yes"<

else cout<<"No"<

return 0;

}

案例2:開燈問題，現(xiàn)有放成一排的n盞燈，它們從1到n依次按順序進行編號?，F(xiàn)有m個同學(xué)，也從1到m依次按照順序編號。第1個同學(xué)(1號)將所有的燈全部關(guān)閉；第2個同學(xué)(2號)將凡是2的倍數(shù)的燈都打開；第3個同學(xué)(3號)將凡是3的倍數(shù)的燈都做相反處理(即該燈如果是開著的，則將它關(guān)閉；如果是關(guān)閉的，則將它打開)；后面的同學(xué)都和3號一樣，將凡是自己編號倍數(shù)的燈做相反處理。請統(tǒng)計第m個同學(xué)操作后，哪些燈是亮著的，輸出它們的編號。

【輸入格式】Light.in

輸入文件第一行有兩個整數(shù)n和m。分別表示燈的數(shù)量和人的數(shù)量。(n,m均是小于32768的自然數(shù)，且n>=m)

【輸出格式】Light.out

輸出文件 在同一行輸出燈亮的編號。沒有燈亮輸出“No”。

【樣例輸入】【樣例輸出】 5 3 2 3 4

問題分析：因為每盞燈有兩種狀態(tài)，“開”與“關(guān)”，因此我們使用整型flag數(shù)組，flag[i]=1表示第i盞燈是開的，“flag[i]=0表示第i盞燈是u關(guān)的。

下面用新總結(jié)的標(biāo)記三步走來實現(xiàn)：C++開燈與關(guān)燈的程序

#include

using namespace std;

int main()

{

int n,m,i,k,num=0;

int flag[32769];//標(biāo)記數(shù)組，每一盞燈都有一個標(biāo)記

//flag[3]=0表示第3盞燈是滅的,=1表示開的

cin>>n>>m;

for(i=1;i<=n;i++) //第1步初始化標(biāo)記：所有的燈都是滅

flag[i]=0;

for(i=2;i<=m;i++) //i:從第2個人開始到第m個人結(jié)束

{ //對i的整數(shù)倍做相反處理

for(k=i;k<=n;k=k+i) //k:表示i的整數(shù)倍

if(flag[k]==0) //第2步：對標(biāo)記賦值,如果是關(guān)的，則打開，否則關(guān)閉

flag[k]=1;

else flag[k]=0;

}

for(i=1;i<=n;i++)//掃描所有的燈

{

if(flag[i]==1)//第3步：對標(biāo)記判斷，解決問題

{

num++;

cout<

}//end if flag

}//end for i

cout <

return 0;

}

案例3:出現(xiàn)次數(shù)最多的數(shù)(weight)

聰明的卡卡西幫助工人師傅們解決了難題， 師傅們?yōu)榱吮硎靖兄x， 帶領(lǐng)他們到了附近的西瓜地， 請他們吃西瓜， 正好看到農(nóng)民伯伯正在給每個西瓜稱重， 每個西瓜的重量都記錄在紙上， 農(nóng)民伯伯想知道這遍地的西瓜哪個重量的西瓜最多。 卡卡西眼前一亮， 大聲地說： “伯伯， 讓我來幫你完成吧！”

輸入： 輸入數(shù)據(jù)有兩行。

第一行只有一個正整數(shù) n， 表示西瓜的總個數(shù)。

第二行有n 個整數(shù)分別為：s1, s2, …, sn， 表示每個西瓜的重量， 相鄰的數(shù)用空格分隔。

輸出： 這 n 個西瓜重量中出現(xiàn)次數(shù)最多的數(shù)。 如果有多個這樣的數(shù)， 請輸出其中最小的一個。

【樣例輸入】(Weight.in)

【樣例輸出】(Weight.out)數(shù)據(jù)范圍: 3≤n≤1000，1≤si≤10000

【樣例輸入】【樣例輸出】610 1 10 20 30 2010

問題分析：考慮到n最大是1000，如果排序找最小的，效率低下。再仔細看一下，每個數(shù) si<=10000,故：我們使用整型標(biāo)記數(shù)組flag[10001]，初始化都是0， flag[i]=4表示第i這個數(shù)出現(xiàn)了4次，flag[i]=20表示第i這個數(shù)出現(xiàn)了20次。因為如果有多個數(shù)出現(xiàn)的次數(shù)都是最多的，要求輸出最小的，我們可以直接從標(biāo)記數(shù)組下標(biāo)掃描正好從小到大。

下面用新總結(jié)的標(biāo)記三步走來實現(xiàn)：

#include

using namespace std;

int main()

{

int i,maxn=0,n,x;

int flag[10001]={0};//第1步初始化標(biāo)記flag[34]=2;表示34出現(xiàn)2次

cin>>n;

for(i=1;i<=n;i++)//讀入n個數(shù)

{

cin>>x;

flag[x]++;//第2步：對標(biāo)記賦值,漂亮，讀入x把x的標(biāo)記+1

}

for(i=0;i<=10000;i++) //掃描0.1..10000標(biāo)記

{

if(flag[i]>= maxn)

maxn =flag[i];

}

for(i=0;i<=10000;i++)

{

if(flag[i]== maxn) //第3步：對標(biāo)記判斷，解決問題

{

cout<

break;//提前結(jié)束

} //end if

}//end for i

return 0;

}

三、結(jié)論和討論

剛剛拋磚引玉的3個經(jīng)典案例，我們可以看出用總結(jié)的標(biāo)記三步走算法，按照步驟來編寫程序，更容易理解和掌握，學(xué)生們反響很好。

值得注意的事，三步走中：第1步：初始化標(biāo)記重要，這個也很有講究，正確的初始化能讓后面的對比效果顯著。方法是應(yīng)該考慮，你很容易判斷標(biāo)記的結(jié)果是什么？那么你就初始化他的對立面，如：案例1中質(zhì)數(shù)，只要在2、3、…、sqrt(n)中找到一個數(shù)是n的因子，那么就能立刻判斷n不 是質(zhì)數(shù)，相反而要判斷n是質(zhì)數(shù)必須等上面的所有數(shù)判斷完都沒有找到，才能說是比較而言，很容易判斷n不是質(zhì)數(shù)，故我們先假定n是質(zhì)數(shù)，初始化為1。

總結(jié)：本論文把標(biāo)記的使用分為三步：分別是初始化，對標(biāo)記賦值，判斷標(biāo)記。由于篇幅有限，圖論中的最短路徑問題，求解最小生成樹，強通連分量TJ算法等等，都需要用標(biāo)記來實現(xiàn)，期待感興趣的老師一起來探索。