全国计算机考试算法总结.docx

全国计算机考试算法总结.docx

《全国计算机考试算法总结.docx》由会员分享，可在线阅读，更多相关《全国计算机考试算法总结.docx（93页珍藏版）》请在冰点文库上搜索。

全国计算机考试算法总结

对象内容的清空

1.窗体与图片框内容清空对象名.Cls

2.标签对象名.Caption=””

3.文本框对象名.Text=””

4.列表框与组合框对象名.Clear

不同对象Value属性的功能与取值范围

1.选项按钮：

Value取值为True表示选中；取值为False表示没有选中

2.复选按钮：

Value取值为1表示选中；取值为0表示没有选中；取值为2表示灰化暂时不可用

3.滚动条：

Value取值范围在【Min,Max】属性区间范围内，取值表示滑块所在的位置

4.命令按钮：

Value取值为True或False，取值为True表示立即触发命令按钮的单击事件

列表框与组合框

1.当前选中的列表项序号对象名.ListIndex

2.最后一个列表项序号对象名.ListCount-1

3.当前选中的列表项内容对象名.List（对象名.ListIndex）或对象名.Text

4.增加列表项对象名.AddItem内容

5.修改某个列表项内容对象名.List（列表项序号）=内容

6.修改当前选中的列表项内容对象名.List（对象名.ListIndex）=内容

7.删除某个列表项对象名.RemoveItem列表项序号

8.删除当前选中的列表项对象名.RemoveItem对象名.ListIndex

9.依次访问所有列表项基本模式：

Fori=0To对象名.ListCount-1

访问每个列表项：

对象名.List（i）

Nexti

文件操作

顺序文件写操作

Open文件名ForOutput/Appendas[#]文件号

Print[#]文件号,写入内容列表

Write[#]文件号,写入内容列表

Close[#]文件号

顺序文件读操作

Open文件名ForInputas[#]文件号

Input#文件号,变量名（存放读出内容）列表

LineInput#文件号,变量名（存放读出内容）

变量名=Input（n,[#]文件号）Lof（文件号）

Close[#]文件号

Input#语句读取的是文件中的数据项

LineInput#语句读取的是文件中的一行

Input函数读取的是文件中的指定数目的字符。

已知文件中待读取的每个数据项类型结构时，建议使用Input#语句读取每项数据，否则使用LineInput一行行读取文件内容，或使用Input函数一个个字符读取文件内容。

当需要用程序从文件中读取单个或指定数量字符时，或者使用程序读取一个二进制的或非ASCII码文件时，使用Input函数较为适宜。

随机文件

对于随机文件的访问操作分为以下四个步骤：

（1）声明记录类型，定义相关变量

（2）Open文件名ForRandomAs文件号Len=记录长度

（3）Put#和Get#语句编辑文件

Put#文件号,[记录号],记录变量

Get#文件号,[记录号],记录变量

（4）Close[#]文件号

Put#通常用于记录的替换和添加

◆Put命令将记录写入由记录号指定的位置，同时覆盖原记录内容，所以常用于记录的改写替换，格式：

Put#文件号,替换记录号,新记录变量

◆追加记录就是指向随机文件尾追加新记录，所以先确定新记录的记录号，然后写入：

新记录的记录号=最后一条记录号+1

=Lof（文件号）/Len（记录变量）+1

写入记录：

Put#文件号,新记录号,新记录变量

◆任意位置插入记录，操作起来比较麻烦，需要采用类似在指定位置插入数组元素的算法实现：

先读取最后一条记录，然后将它追加写入文件，然后依次读取倒数第2条、倒数第3条记录……直至插入位置的记录，将它们顺序替换写入后一条记录位置，最后将新记录改写入指定位置。

删除记录

方法1：

可以将待删除记录的后续记录依次替换写入前一记录位置，实现记录被覆盖式的删除；但是会出现最后两个记录相同的、记录总数不变的状况。

方法2：

清空待删除的记录内容；但是该记录仍在文件中存在，而且通常文件中不能有空记录，因为它会浪费空间且会干扰顺序操作。

最好把上述两种方法操作后余下的记录拷贝到一个新文件，然后删除老文件，从而真正删除记录。

步骤如下：

（1）创建一个临时文件

（2）把有用的所有记录从原文件写入该临时文件

（3）关闭原文件，并用Kill语句删除

（4）使用Name语句把临时文件以原文件的名字重新命名

不管以何种方式访问文件，若已知文件读写操作内容的数据量，建议采用For循环进行文件读写，否则建议采用Do-Loop循环进行文件读写。

（1）已知读写文件的数据量，建议采用For循环进行文件读写操作

随机文件中的记录数=文件长度\记录长度

文件长度=LOF（文件号）

记录长度=Len（记录型变量）

（2）不知读写文件的数据量，建议采用DO循环

DoWhileNotEof（文件号）

……

Loop

进行文件读写操作

10.常用算法

5.6常用算法设计方法

经常采用的算法设计技术主要包括穷举搜索法、递推法、回溯法、分治法等。

5.6.1穷举搜索法

穷举搜索法的基本思想是根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。

因此，穷举搜索法常用于解决“是否存在”、“有多少种可能”等类型的问题。

穷举搜索法的特点是算法比较简单。

但当列举的可能情况较多时，执行穷举算法的工作量将会很大。

因此，在设计穷举法算法时，使方案优化，尽可能减少运算工作量应该是重点。

例5-15找出1~200中3的所有倍数。

分析：

3的倍数满足的条件是被3整除后余数为0。

本题可以采用穷举法在1~200间逐一判断，将符合条件的输出。

算法流程图描述如图5-9所示。

转换一下本题的思路，3的倍数可以不通过判断来得到，亦可以由程序产生在范围内的3的倍数。

算法描述如图5-10所示，可以看出，这种算法的效率要高于前一种算法。

图5-9例5-15算法流程图1图5-10例5-15算法流程图2

5.6.2递推法

递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。

设要求问题规模为N的解，当N=1时，解或为已知，或能非常方便地得到解。

能采用递推法构造算法的问题有重要的递推性质，即当得到问题规模为i-1的解后，由问题的递推性质，能从已求得的规模为1，2，…，i-1的一系列解，构造出问题规模为i的解。

这样，程序可从i=0或i=1出发，重复地，由已知至i-1规模的解，通过递推，获得规模为i的解，直至得到规模为N的解。

迭代法是一种特殊的递推法，是一种不断用变量的旧值递推新值的过程，常用于求方程或方程组近似根。

迭代法又分为精确迭代和近似迭代，“二分法”和“牛顿迭代法”等属于近似迭代法。

利用迭代算法解决问题，需要做好以下3个方面的工作。

（1）确定迭代变量。

在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

（2）建立迭代关系式。

迭代关系式指如何从变量的前一个值推出其下一个值的公式（或关系）。

迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

（3）对迭代过程进行控制。

在什么时候结束迭代过程？

这是编写迭代程序必须考虑的问题。

不能让迭代过程无休止地重复执行下去。

迭代过程的控制通常可分为两种情况：

一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。

例5-16验证谷角猜想。

日本数学家谷角静夫在研究自然数时发现了一个奇怪现象：

对于任意一个自然数n，若n为偶数，则将其除以2；若n为奇数，则将其乘以3，然后再加1。

如此经过有限次运算后，总可以得到自然数1。

人们把谷角静夫的这一发现叫做“谷角猜想”。

要求：

编写一个程序，由键盘输入一个自然数n，把n经过有限次运算后，最终变成自然数1的全过程打印出来。

分析：

定义迭代变量为n，按照谷角猜想的内容，可以得到两种情况下的迭代关系式：

当n为偶数时，n=n/2；当n为奇数时，n=n×3+1。

这个迭代过程需要重复执行多少次，才能使迭代变量n最终变成自然数1，这是我们无法计算出来的。

因此，还需进一步确定用来结束迭代过程的条件。

仔细分析题目要求，不难看出，对任意给定的一个自然数n，只要经过有限次运算后，能够得到自然数1，就已经完成了验证工作。

因此，用来结束迭代过程的条件可以定义为n=1。

5.6.3回溯法

回溯法也称试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。

当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解除了还不满足问题规模要求外，满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。

如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。

在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。

例5-17八皇后问题。

在8×8的格子中放入8个皇后棋子，放置的条件是任何两个皇后棋子都不占据棋盘上的同一列、同一行或同一对角线。

八皇后问题是比较经典的需要采用回溯法来解决的算法。

为了方便说明问题，在此我们将问题的规模适当减少，简化为四皇后问题，棋盘如图5-11（a）所示。

（a）四皇后问题棋盘（b）四皇后问题的一个解（c）四皇后问题的另一个解

图5-11皇后问题

解题过程是一个试探的过程，具体如下：

每行放置一个棋子，先将第1个棋子放在第1行第1列位置；第2个棋子要符合条件的话只能放在第2行的第3或第4列，先将第2个棋子放在第3列上；而这时第3行上的4个位置都不符合放置第3个棋子的条件了，因此，发现第2个棋子不应该放在第3列上，程序重新回去将第2个棋子的位置改为第4列，继续放置第3个棋子，第3行上仅有第2列可以放置，这时发现第4行上没有符合第4个棋子放置的位置了，我们逐步返回，第3个棋子已无其他可选择位置，第2个棋子也无其他可选择位置，只能重新回去修改第1个棋子的位置，将第1个棋子放在第2列上，这样，第2个棋子只有1个可放位置在第4列，第3个棋子也只有1个可放位置在第1列，最后第4个棋子被放置在第3列上，得到该问题的第一个符合条件的解，如图5-11（b）所示。

如果程序继续进行下去，我们还能找到另外符合条件的解，如图5-11（c）所示。

其中出现了较多次数的回溯，都是因为试探不成功需要重新回去寻找其他方案。

回溯法是解决未知问题的常用方法，使用回溯法时要注意问题的候选解要全面，以免遗漏正确解。

5.6.4分治法

分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。

如果原问题可分割成k个子问题（1

例5-18用二分法求方程f（x）=0在区间[a，b]上的实根，设f（a）与f（b）异号。

分析：

二分法求解方程的根是将设定区间逐步减半，最后将根锁定在一个极小的区间内，输出根的近似值。

具体过程如下：

首先取给定区间的中点c=（a+b）/2；然后判断f（c）是否为0。

若f（c）=0，则说明c即为所求的根，求解过程结束；如果f（c）≠0，则根据一项原则将原区间减半：

若f（a）f（c）<0，则取原区间的前一半部分；若f（b）f（c）<0，则取原区间的后一半部分，最后判断减半后的区间长度是否已经很小：

若|a-b|<，则求解过程结束，取（a+b）/2为根的近似值；否则在减半的区间重复以上的减半过程。

6.5常用算法及应用

6.5.1交换两个数据的值

设x和y是两个相同类型的变量，将两个变量中的值进行交换，如图6-10所示。

分析：

简单的使用x=y:

y=x并不能达到目的，这样的赋值会使x中的数值丢失而使y=x失去意义。

从日常生活中，我们也经常能遇到类似的情况。

有A、B两个杯子中分别装有红酒和咖啡，要求将两个杯子中的饮品互换。

由于两种饮品相互不能掺杂，因此必须使用另一个空杯C辅助完成，具体实施步骤如下：

步骤1：

先将A杯中的红酒倒入C杯中。

步骤2：

再将B杯中的咖啡倒入A杯中。

步骤3：

最后将C杯中的红酒倒入B杯中。

互换示意图如图6-11所示，这种方法中的三个步骤的顺序不能任意交换，但也可以先将B杯中的咖啡倒入C杯中，再将A杯中的红酒倒入B杯中，最后将C杯中的咖啡倒入A杯中。

图6-10交换两个数据程序执行效果图图6-11杯中饮品互换示意图

同理，两个变量数据的交换问题也可以使用辅助变量z来实现，还是分三步骤。

步骤1：

将x的值放入z中。

步骤2：

再将y的值放入x中。

步骤3：

最后将z中的值放入y中。

以上步骤的代码实现是z=x:

x=y:

y=z。

虽然步骤相同，但由于变量在内存中的值不会无故消失，一定需要用新值替换。

所以，交换过程的每个状态3个变量中的值和3个杯子中的物品还是有区别的，在使用时要特别注意执行中变量值的变化情况。

本算法中讨论两个整型变量的交换，交换的方法同样适用于其他基本类型和基本控件。

但对于基本控件的交换往往只是对控件的属性值进行交换，大部分情况下都可以使用对应类型的辅助变量实现，少数情况下需要借助辅助的第3个控件来完成。

对于数值型变量的交换，还可以采用数学的方法来实现x=x+y:

y=x-y:

x=x–y。

6.5.5数据的自运算

程序中经常出现一些变量，他们的值是通过前一次赋值经过运算得到的，这种相对于自己的一种运算我们称之为自运算，这种运算在本质上属于递推概念。

1．算术运算

算术运算主要用于数值型数据的自运算中，示例如下。

（1）将变量x的值增加1语句为x=x+1。

（2）将变量x的值减少1语句为x=x–1。

（3）将标签Label1的Left属性增加100，语句为Label1.Left=Label1.Left+100。

（4）将图像Image1的Width属性扩大两倍，语句为Image1.Width=Image1.Width*2。

2．字符运算

字符运算主要用于字符串型数据的自运算中，示例如下。

（1）在字符串s的后面添加字符“！

”，语句为s=s&“!

”。

（2）删除字符串s的最后一个字符，语句为s=Left（s,Len（s）-1）。

（3）在字符串s的后面添加字符“#”，语句为s=“#”&s。

（4）删除字符串s的第一个字符，语句为s=Right（s,Len（s）-1）。

（5）在字符串s的第k个字符后添加字符“*”，语句为s=Left（s,k）&"*"&Right（s,Len（s）-k）。

（6）删除字符串s的第k个字符，语句为s=Left（s,k-1）&Right（s,Len（s）-k）。

自运算的过程可以理解为在原来的基础上进行的某些运算。

为了达到一定的效果，我们必须充分掌握对象的常规属性变化所产生的后果以及各种运算的特征。

图6-12例6-7执行界面

例6-7统计点击次数。

如图6-12所示，单击窗体后在窗体上输出当前的点击次数。

分析：

在程序中，可以使用一种特殊的变量，初始值为0，每执行一次某个程序段，该变量的值就自增1，这样变量的值和程序段的执行次数一致，我们称这种变量为计数器。

程序代码如下：

PrivateSubForm_Click（）

StaticxAsInteger

x=x+1

Cls

Print"您已经连续点击了"&x&"次窗体。

"

EndSub

以上代码中使用了Static（静态）变量x，这种用Static定义的变量可以保留前一次执行本段程序时获得的值，因此x的值实际是从0开始进行了累加，即每次加1。

关于Static变量和过程级变量的描述可参见第10章。

7.3基本算法及应用

7.3.1求两个数的最大（小）值

最大值和最小值的求法基本一致，这里我们以求A和B最大值为例进行分析。

两个数的最大值要么是A，要么是B，主要任务就是要分清什么时候是A，什么时候是B。

两个数的关系无非有3种情形，即A>B，A=B，A

可以确定第1种情形中A是最大值，第3种情形中B是最大值，而第2种情形中可以是A也可以是B。

我们可以将这3种情形进行归纳，将前两种情形进行合并。

写出程序代码如下：

IfA>=BThenMax=AElseMax=B

其中Else中含有隐含条件A

若将后两种情形合并，可以写出如下程序代码：

IfA>BThenMax=AElseMax=B

对A=B情形的处理完全取决于编程人员代码的书写，在确定代码后，程序中对A=B时的处理就确定不变了，这样的程序是稳定的。

如果写出代码后对此情形的取值是任意随机的，那样的程序就是不稳定的。

一般我们要求程序尽量稳定。

例7-6求用户输入两个数的最大值和最小值，界面参考如图7-10所示。

程序代码如下：

PrivateSubCommand1_Click（）

DimAAsInteger,BAsInteger

DimMaxAsInteger,MinAsInteger

A=Val（Text1.Text）'接收数据

B=Val（Text2.Text）'接收数据

IfA>BThenMax=AElseMax=B

IfA

MsgBoxMax&"是最大值,"&Min&"是最小值"

EndSub

图7-10例7-6执行界面

注意，A和B的值需要接收用户输入的数据后才能进行比较，若不接收则A和B的值均是0，求值将无任何意义。

利用两个数最大（小）值算法，我们还可以求3个数最大（小）值。

7.3.2用户输入时按键的判断

用户输入时按键的判断往往有两种方法：

一是在输入时判断，使用文本框的Key事件；二是在全部输入完成后再对每个字符进行判断，使用循环结构依次获取字符串中的字符。

这里我们仅讨论第1种方法。

VisualBasic中对象的Key事件，包含KeyPress、KeyDown、KeyUp三个事件。

通常我们使用KeyPress事件判断用户的按键情况，KeyAscii是它的重要参数，表示用户按键的Ascii码值。

我们通过对KeyAscii的判断可以获知用户的按键，并对不同的按键进行区分处理；在KeyPress事件中更改KeyAscii的值还可以更改文本框中的显示，如语句KeyAscii=0将使用户的输入清除，即不显示在文本框中。

例7-7在文本框中输入一个字符串，要求只能出现字母。

我们在文本框的KeyPress事件中编写，直接过滤掉不合法的字符：

PrivateSubText1_KeyPress（KeyAsciiAsInteger）

If（KeyAsciiAsc（"z"））And（KeyAsciiAsc（"Z"））ThenKeyAscii=0'不合法的字符不显示

EndSub

代码中If语句的条件表达式较为复杂，它表示的含义是用户按键既不是小写字母，又不是大写字母。

通常，我们比较常用的是判断输入是字母的表达式：

KeyAscii>=Asc（"a"）AndKeyAscii<=Asc（"z"）OrKeyAscii>=Asc（"A"）And_KeyAscii>Asc（"Z"）

7.3.3信息的有效性验证

选择语句通常用于判断上，对结果的正确性及数据的有效性判断在实际应用中经常出现。

此类问题的解决过程中，将问题分析透彻，组织好语句的逻辑结构非常重要。

例7-8登录界面设计。

图7-11例7-8参考界面

分析：

如图7-11所示，在文本框中输入帐号和密码，并对输入的数据进行有效性和正确性检查。

这里的有效性指帐号和密码不能为空，正确性检查则是判断密码是否正确。

“确定”按钮的Click事件过程如下：

PrivateSubcmdok_Click（）

Iftxtuser.Text=""Ortxtpwd.Text=""Then

MsgBox"请输入完整信息！

"

Else

Iftxtpwd.Text<>"20082008"Then

MsgBox"密码错误，不能登录！

"

txtpwd.Text=""

txtpwd.SetFocus

Else

MsgBoxtxtuser.Text&"，欢迎您！

"

EndIf

EndIf

EndSub

这里我们将密码设置为唯一密码写入代码中，从代码中可以看出正确的密码为20082008。

这样的处理安全性较差，不适合用于安全级别较高的场合。

7.3.4单选钮和复选框的应用

由于单选钮和复选框的状态不唯一，需要通过判断才知道其选中状态，因此在这两个控件的应用中，选择语句出现的频率较高。

图7-12例7-9参考界面

单选钮体现出多选一的局面，在同一组单选钮中只有一个按钮的Value属性值为1，通常使用If…Then…ElseIf…的语句格式进行判断。

而复选框体现的是多项选择，同一组复选框中可以同时有多个被选中，也可以只选中一个，也可以一个都不选中，通常我们对各个复选框进行独立判断。

例7-9如图7-12所示，根据用户选择，求若干门课程的总分或平均分。

分析：

用户选择哪些课程我们无法确切的知晓，只能对所有可能的情况都进行对应的处理。

使用复选框对每门课程进行选择，若仅有选中和不选中两个状态，则三门课程共有8种被选情况。

显然，若使用If…Then…ElseIf结构会使代码较为复杂，因此还是对各门课程进行独立判断，若被选中则计入总分。

另外，计算平均分时必须计算总分和课程数，因此，在判断中还必须统计课程数。

最后的结果放在文本框中分行显示，须将文本框的MultiLine属性设置为True。

界面上各控件使用类别缩写和英文名称组成，参考代码如下：

PrivateSubcmdCal_Click（）

DimsumAsInteger,nAsInteger

IfchkChinese.Value=1Thensum=sum+Val（txtChinese.Text）:

n=n+1

IfchkMath.Value=1Thensum=sum+Val（txtMath.Text）:

n=n+1

IfchkEnglish.Value=1Thensum=sum+Val（txtEnglish.Text）:

n=n+1

IfoptTotal.ValueThen

txtResult.Text=n&"门课总分:

"&vbCrLf&sum

Else

Ifn<>0ThentxtResult.Text=n&"门课平均分:

"&vb