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

鮑康勝

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

一、引言

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

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

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

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

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

使用步驟三步走：

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

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

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

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

【輸入格式】zs.in

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

【輸出格式】zs.out

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

樣例輸入樣例輸出9No17Yes

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

#include

using namespace std;

int main()

{

int i,n;

intflag=1;//第1步：初始化標(biāo)記，假定是質(zhì)數(shù)，因?yàn)楹苋菀着袛嗖皇琴|(zhì)數(shù)。

cin>>n;

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

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

{

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

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

}

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

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

cout<<"Yes"<

else cout<<"No"<

return 0;

}

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

【輸入格式】Light.in

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

【輸出格式】Light.out

輸出文件 在同一行輸出燈亮的編號(hào)。沒(méi)有燈亮輸出“No”。

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

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

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

#include

using namespace std;

int main()

{

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

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

//flag[3]=0表示第3盞燈是滅的,=1表示開(kāi)的

cin>>n>>m;

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

flag[i]=0;

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

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

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

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

flag[k]=1;

else flag[k]=0;

}

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

{

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

{

num++;

cout<

}//end if flag

}//end for i

cout <

return 0;

}

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

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

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

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

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

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

【樣例輸入】(Weight.in)

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

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

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

下面用新總結(jié)的標(biāo)記三步走來(lái)實(shí)現(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個(gè)數(shù)

{

cin>>x;

flag[x]++;//第2步：對(duì)標(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步：對(duì)標(biāo)記判斷，解決問(wèn)題

{

cout<

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

} //end if

}//end for i

return 0;

}

三、結(jié)論和討論

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

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

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