第5章 算法考点精解

前面两章讨论了C语言的基本概念、基本语句、程序结构、各种数据类型、函数、指针、链表、文件等与语法相关的内容，本章主要针对江苏省二级C等级考试中经常出现的算法进行归纳总结，包括基本操作、非数值计算常用经典算法、数值计算常用经典算法、解决各类问题的一般算法。

算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。形成解题思路是推理实现的算法，编写程序是操作实现的算法。

在计算机的等级考试题目中，程序填空及上机编程题一般都与算法有关，所以要了解等级考试大纲中规定的算法并掌握常考算法。

5.1 基本操作

一、知识点综述

1．交换 (*****)

变量交换算法是一种很简单的算法，也是最为基础的一个算法，各种其他的算法往往都要运用到这一基本算法，如各种排序算法就会使用到交换变量的算法。

实现变量的值的交换最常用的方法是借助一个临时变量来实现将两个数的值进行交换。下面的函数实现了两个数的交换。

void swap(int x, int y) { int temp; temp=x; x=y; y=temp; }

因为函数参数的传递是值传递，是单向的，如果主函数调用了此函数，尽管形式参数x和y的值交换了，而主函数中的实际参数是不会改变的。要想实现地址传递，应该用指针实现。

void swap(int *x, int *y) { int temp; temp=*x;

*x=*y; *y=temp; }

函数调用时将实参的地址传递给指针x和y，例如：swap(&a, &b);实现x和y指向的地址单元的值的交换，即a和b的值的交换。

2．累加 (*****)

累加就是对若干个数求和，其最基本的思想就是“反复做加法”。一般来说，计算机每次只处理两个数的相加运算，所以多个数相加必须通过多次的两两相加来实现，用循环就很容

易实现数的累加。

使用循环时，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示最后结果的初值。

用c语言实现1+2+3+4+5+……+n的累加。 【方法1】for循环实现 int add(int n) { int i,sum=0;

for(i=1;i<=n;i++) sum=sum+i; return sum; }

【方法2】while循环实现 int add(int n) { int i,sum;

sum=0; i=1; while(i<=n)

{ sum=sum+i; i=i+1; }

return sum; }

do-while循环也可以实现累加。请读者自己完成。

3．累乘 (*****)

累乘就是对若干个数求积，其最基本的思想就是“反复做乘法”，实际上就是求一个数的阶乘,实现方法与累加类似。

在累乘之前，一定要将用于存放乘积的变量的值初始化为1。 用c语言求n的阶乘：n! = 1?2?3?4?…?n (n>=0) int product (int n) { int i,p=1;

for(i=2;i<=n;i++) p=p*i;

return p; }

如果n的值比较大，考虑累乘的结果可能会超过32767，函数返回值应定义为长整型，确保程序运行的正确。 long func(int n)

{ int i; long p=1;

for(i=2;i<=n;i++) p*=i; return p; }

5.2 非数值计算常用经典算法

一、知识点综述

1．穷举 (***)

穷举法的基本思想是：一一列举各种可能的情况，并判断哪一种可能是符合要求的解。这是一种在“没有其它办法的情况的方法”，是一种最“笨”的方法，然而对一些无法用解析法求解的问题往往能奏效，通常采用循环来处理穷举问题。

【例题】有1、2、3、4四个数字，能组成多少个互不相同且无重复数字的三位数？都是多少？

程序分析：可填在百位、十位、个位的数字都是1、2、3、4。组成所有的排列后再去掉不满足条件的排列。

main() { int i,j,k;

for(i=1;i<5;i++) ／*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++)

if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/ printf(\ }

2．排序 (*****)

排序就是将数组中的元素按从大到小的顺序或者从小到大的顺序重新排列。排序方法有很多，C语言中最常用的排序方法有冒泡排序、选择排序、插入排序。 1)冒泡排序 (*****)

算法思想：依次比较相邻的两个数，将小数放在前面，大数放在后面。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。排序步骤如下：

① 将数组中相临的两个数两两比较，如果第一个数大于（小于）第二个数，两者交换

位置，即将小的排前面，大的排后面。 ② 第一趟比较，小的调到前头，经n-1次两两相邻比较，最大的数已沉底，放在最后

一个位置，小的数浮起。 ③ 第二趟对余下的n-1个数比较，比较n-2次，得次大的数在最后第二个位置。 ④ 重复上述过程，n个数比较n-1趟，在第i趟中进行n-1-i次两两比较。 下面的函数是按升序从前往后排。 void BubbleSort(int a[],int n)

{ int i,j, tmp;

for(i=0;ia[j+1]) /*从小到大*/

{ tmp=a[j]; a[j]=a[j+1]; a[j+1]=tmp; } /*交换a[j]与a[j+1],大数后移*/

} }

2)选择排序 (*****)

算法思想：从待排序的序列中，选择最小的一个记录，与第一个数据交换；然后从不包