浅谈标记在计算机程序设计中的应用

鲍康胜

(合肥市第六中学 安徽合肥 230000)

一、引言

素数是一个很经典的问题，但是对于很多学生来说，并不能很好地理解素数的概念，即使掌握了素数的概念也不会判断一个数是否为素数，本文使用“标记”的方法来判断素数，并且详细阐明使用的步骤。

求解素数时，最常见的就是用因子可能的范围去依次扫描判断，效率不高，数据量大时，容易超时，而线性筛素数算法大大提高了效率，确保了每个素数只被筛1次达到线性的复杂度，也有使用随机产生数值的方法和一道循环扫描的方法来实现素数的求解。

作者从事高中信息学奥林匹克竞赛的辅导工作有18个年头了，因为根据全国信息学奥赛大纲，对选手的程序设计能力和数学建模能力要求很高，经过长期的实践摸索，作者发现初学者对“标记”，理解不清，掌握不透，学生普通反映编写困难，而“标记”又是基础算法，在后面的树论、图论等都会用到标记，所以学好“标记”显得至关重要。

二、“标记”使用的新思考

标记的作用：把对问题的求解转换成对标记的判断。

使用步骤三步走：

1.初始化标记：你能够直接判定结果的对立面,有几种状态，就取几个值。

2.对标记赋值：对每个对象的标记值进行分析处理，对它赋值。

3.对标记判断：最后，只需要对标记进行判断，统计标记的情况即可圆满解决问题。

案例1：素数大酬宾，键盘读入一个正整数n,判断n是不是质数，输出“YES” or “No”

【输入格式】zs.in

输入文件一行有两个数(n是小于32768的整数)

【输出格式】zs.out

输出文件：是质数时，输出“Yes”，否则输出“No”。

样例输入样例输出9No17Yes

问题分析：一个数是不是素数有两种状态，一种“是”，另一种“不是”，我们使用整型 flag变量，分别取1(对应是)和0(对应不是)。下面用新总结的标记三步走来，实现质数判定的C++程序

#include

using namespace std;

int main()

{

int i,n;

intflag=1;//第1步：初始化标记，假定是质数，因为很容易判断不是质数。

cin>>n;

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

if(n%i==0) //当前n能整除i

{

flag=0; //第2步：肯定不是质数，对标记赋值

break;//提前结束

}

else continue;//如果当前i不能则继续判断下一个i+1

if(flag==1)//第3步：对标记进行判断，问题得解

cout<<"Yes"<

else cout<<"No"<

return 0;

}

案例2:开灯问题，现有放成一排的n盏灯，它们从1到n依次按顺序进行编号。现有m个同学，也从1到m依次按照顺序编号。第1个同学(1号)将所有的灯全部关闭；第2个同学(2号)将凡是2的倍数的灯都打开；第3个同学(3号)将凡是3的倍数的灯都做相反处理(即该灯如果是开着的，则将它关闭；如果是关闭的，则将它打开)；后面的同学都和3号一样，将凡是自己编号倍数的灯做相反处理。请统计第m个同学操作后，哪些灯是亮着的，输出它们的编号。

【输入格式】Light.in

输入文件第一行有两个整数n和m。分别表示灯的数量和人的数量。(n,m均是小于32768的自然数，且n>=m)

【输出格式】Light.out

输出文件 在同一行输出灯亮的编号。没有灯亮输出“No”。

【样例输入】【样例输出】 5 3 2 3 4

问题分析：因为每盏灯有两种状态，“开”与“关”，因此我们使用整型flag数组，flag[i]=1表示第i盏灯是开的，“flag[i]=0表示第i盏灯是u关的。

下面用新总结的标记三步走来实现：C++开灯与关灯的程序

#include

using namespace std;

int main()

{

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

int flag[32769];//标记数组，每一盏灯都有一个标记

//flag[3]=0表示第3盏灯是灭的,=1表示开的

cin>>n>>m;

for(i=1;i<=n;i++) //第1步初始化标记：所有的灯都是灭

flag[i]=0;

for(i=2;i<=m;i++) //i:从第2个人开始到第m个人结束

{ //对i的整数倍做相反处理

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

if(flag[k]==0) //第2步：对标记赋值,如果是关的，则打开，否则关闭

flag[k]=1;

else flag[k]=0;

}

for(i=1;i<=n;i++)//扫描所有的灯

{

if(flag[i]==1)//第3步：对标记判断，解决问题

{

num++;

cout<

}//end if flag

}//end for i

cout <

return 0;

}

案例3:出现次数最多的数(weight)

聪明的卡卡西帮助工人师傅们解决了难题， 师傅们为了表示感谢， 带领他们到了附近的西瓜地， 请他们吃西瓜， 正好看到农民伯伯正在给每个西瓜称重， 每个西瓜的重量都记录在纸上， 农民伯伯想知道这遍地的西瓜哪个重量的西瓜最多。 卡卡西眼前一亮， 大声地说： “伯伯， 让我来帮你完成吧！”

输入： 输入数据有两行。

第一行只有一个正整数 n， 表示西瓜的总个数。

第二行有n 个整数分别为：s1, s2, …, sn， 表示每个西瓜的重量， 相邻的数用空格分隔。

输出： 这 n 个西瓜重量中出现次数最多的数。 如果有多个这样的数， 请输出其中最小的一个。

【样例输入】(Weight.in)

【样例输出】(Weight.out)数据范围: 3≤n≤1000，1≤si≤10000

【样例输入】【样例输出】610 1 10 20 30 2010

问题分析：考虑到n最大是1000，如果排序找最小的，效率低下。再仔细看一下，每个数 si<=10000,故：我们使用整型标记数组flag[10001]，初始化都是0， flag[i]=4表示第i这个数出现了4次，flag[i]=20表示第i这个数出现了20次。因为如果有多个数出现的次数都是最多的，要求输出最小的，我们可以直接从标记数组下标扫描正好从小到大。

下面用新总结的标记三步走来实现：

#include

using namespace std;

int main()

{

int i,maxn=0,n,x;

int flag[10001]={0};//第1步初始化标记flag[34]=2;表示34出现2次

cin>>n;

for(i=1;i<=n;i++)//读入n个数

{

cin>>x;

flag[x]++;//第2步：对标记赋值,漂亮，读入x把x的标记+1

}

for(i=0;i<=10000;i++) //扫描0.1..10000标记

{

if(flag[i]>= maxn)

maxn =flag[i];

}

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

{

if(flag[i]== maxn) //第3步：对标记判断，解决问题

{

cout<

break;//提前结束

} //end if

}//end for i

return 0;

}

三、结论和讨论

刚刚抛砖引玉的3个经典案例，我们可以看出用总结的标记三步走算法，按照步骤来编写程序，更容易理解和掌握，学生们反响很好。

值得注意的事，三步走中：第1步：初始化标记重要，这个也很有讲究，正确的初始化能让后面的对比效果显著。方法是应该考虑，你很容易判断标记的结果是什么？那么你就初始化他的对立面，如：案例1中质数，只要在2、3、…、sqrt(n)中找到一个数是n的因子，那么就能立刻判断n不 是质数，相反而要判断n是质数必须等上面的所有数判断完都没有找到，才能说是比较而言，很容易判断n不是质数，故我们先假定n是质数，初始化为1。

总结：本论文把标记的使用分为三步：分别是初始化，对标记赋值，判断标记。由于篇幅有限，图论中的最短路径问题，求解最小生成树，强通连分量TJ算法等等，都需要用标记来实现，期待感兴趣的老师一起来探索。