C语言常考算法

二级C语言程序设计题中经常用到的基本模块

求最大值、最小值 
    int find_max(int a[ ], int n)
    int find_min(int a[ ], int n)
判断某数为素数
    int is_prime(int n) 
求最大公约数和最小公倍数
  int gcd(int a, int b)
  int lcm(int a, int b)
数组元素逆置
    void exchange(int a[ ], int n)
冒泡排序
    void bubble_sort(int v[ ], int n)
选择排序
    void selection_sort(int v[], int n)

求最大值、最小值

int find_max(int a[ ], int n)
{
    int i, max=a[0];
    for(i=1; i<n; i++) 
        if(a[i]>max) max = a[i];
    return max;
}

除了返回最大值外，还可以返回最大值所在的位置，修改后的代码如下：

int find_max(int a[ ], int n)
{
    int i, max=0;
    for(i=1; i<n; i++) 
        if(a[i]>a[max]) max = i;
    return max;
}

判断某数为素数

如果 n 是素数，函数 is_prime 返回1；n不是素数，则返回 0

int is_prime(int n) 
{
	int i;
	if (n<2) return 0;
	for (i=2; i*i<=n; i++) 
		if (n%i == 0) return 0;	
	return 1;
}

#include <stdio.h>

int main( )
{
    int i, j;
    for (i=2; i<100; i++)
    {
        for (j=2; j<i; j++)
            if (i%j==0) break;
        if (j==i) printf("%d\n", i);
    }
    return 0;
}

两个数的最大公约数通常写成gcd(a, b)，最小公倍数写成 lcm(a, b)。
最大公约数*最小公倍数 = 两数的乘积 gcd(a,b) * lcm(a,b) = a*b

求最大公约数和最小公倍数

int gcd(int a, int b)
{
    return (b==0) ? a : gcd(b, a % b);
}

求出了最大公约数，也就能快速算出最小公倍数了。

int lcm(int a, int b)
{
    return a/gcd(a,b)*b;
}

数组元素逆置
第一个与最后一个交换，第二个与倒数第二个交换，第 i 个数和第 n-i-1 个数交换

void exchange(int a[ ], int n)
{
    int i, t;

    for(i=0; i<n/2; i++) {
        t=a[i];   a[i]=a[n-i-1];  a[n-i-1]=t;
    }
}

冒泡排序

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

首先分析下列代码：

        for(j=0; j<i; j++)
            if(v[j]>v[j+1]) 
            {  t=v[j]; v[j]=v[j+1];  v[j+1]=t;  }

两个结论：
1） 这段代码对 i+1 个数 （v[0] v[1] … v[i]）进行了 i 次 ( j = 0: i-1) 比较
2） 比较结束后， v[ i ] 是最大的。

数组的长度为 n
第 1 轮，i = n-1, 使得 v[n-1] 最大
第 2 轮，i = n-2 , 使得 v[n-2] 除了 v[n-1] 外最大
第 3 轮，i = n-3, 使得 v[n-2] 除了 v[n-1], v[n-2] 外最大
最后， i = 0, 比较 v[0] 和 v[1]， 结束后， v[1] 在 v[0] v[1] 中最大

如果要确保整个数组是有序的，i = n-1 to 0，得到以下程序

void bubble_sort(int v[ ], int n)
{
    int i, j, t;
    for(i=0; i<n-1; i++) 
    	for (j=0; j<n-1-i; j++) 
            if (v[j]<v[j+1]) 
            {  t = v[j]; v[j] = v[j+1]; v[j+1]=t;  }
}

冒泡排序法的记忆口诀

n 个数字来排队，
两两相比小靠前，
外层循环 n-1，
内层循环再减 i

完整的测试程序如下：

#include <stdio.h>

void bubble_sort(int v[ ], int n)
{
    int i, j, t;
    for(i=0; i<n-1; i++) 
    	for (j=0; j<n-1-i; j++) 
            if (v[j]>v[j+1]) 
            {  t = v[j]; v[j] = v[j+1]; v[j+1]=t;  }
}

int main(int argc, char *argv[])
{
	int v[6] = { 2, 3, 9, 1, 0, 7};
	int i;
	
	bubble_sort(v, 6);	
	for (i=0; i<6; i++)
		printf("%d ", v[i]);
	printf("\n");
	return 0;
}

输出中间结果的程序

#include <stdio.h>

void print_array(int v[], int n)
{
    int i;
    for (i=0; i<n; i++)
        printf("%4d", v[i]);
    printf("\n");
}

void bubble_sort(int v[], int n)
{
    int i, j, t;
    for(i=0; i<n-1; i++)  {
        for (j=0; j<n-1-i; j++)
            if (v[j]>v[j+1]) {
                t = v[j];
                v[j] = v[j+1];
                v[j+1]=t;
            }
        print_array(v,n);
    }
}

int main(int argc, char *argv[])
{
    int v[6] = { 2, 3, 9, 1, 0, 7};
    bubble_sort(v, 6);
    return 0;
}

选择排序

选择排序(selection sort)是一种简单直观的排序算法。它的工作原理如下：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

void selection_sort(int v[], int n)
{
    int i, j, t, min;
    for (i = 0; i < n; i++) {
        min = i;  // 先假设最小下标为i
        for (j = i + 1; j < n; j++)
            if (v[j] < v[min])
                min = j; // 对i之后的数进行扫描将最小的数赋予min
        if (min != i) {
            t = v[i]; v[i] = v[min]; v[min] = t;
        }  // 判断min与i是否相等，若＝则说明原假设正确反之交换数值
    }
}