现在的位置: 首页 > 14 二级C语言 > 正文

C语言常考算法

2011年04月18日 14 二级C语言 ⁄ 共 477字 ⁄ 字号 暂无评论

非常简单的算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
求最大值、最小值 
    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)

求最大值、最小值

1
2
3
4
5
6
7
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;
}

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

1
2
3
4
5
6
7
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

1
2
3
4
5
6
7
8
int is_prime(int n) 
{
	int i;
	if (n<2) return 0;
	for (i=2; i<=sqrt(n); i++) 
		if (n%i == 0) return 0;	
	return 1;
}

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

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

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

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

1
2
3
4
int lcm(int a, int b)
{
    return a/gcd(a,b)*b;
}

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

1
2
3
4
5
6
7
8
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;
    }
}

冒泡排序

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

详细的排序过程请参考【分类目录】->【数组基础

首先分析下列代码:

1
2
3
        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,得到以下程序

1
2
3
4
5
6
7
8
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

完整的测试程序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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;
}

输出中间结果的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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)是一种简单直观的排序算法。它的工作原理如下:首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
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是否相等,若=则说明原假设正确反之交换数值
    }
}

抱歉!评论已关闭.