C语言相关算法

生成随机数

1
2
3
4
5
6


#include <stdlib.h>
#include <time.h>

srand((unsigned int) time(NULL)); //传入时间戳 注意，该行语句只需要调用一次！
int rand_sum = rand(); //生成随机数
rand_sum  = rand_sum % 100 + 1; //生成1-100范围的随机数

二分查找

 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
31
32
33
34
35
36


int main()
{
    int arr[10] = { 1,8,10,21,57,89,98,107,428,890 };
    int sum = 0;
    printf("请输入要查找的数字 >>");
    scanf("%d", &sum);

    int size = sizeof(arr) / sizeof(arr[0]);

    int left = 0;
    int right = size - 1;
    while (left <= right)
    {
        int middle = (left + right) / 2;

        if (arr[middle] < sum)
        {
            left = middle + 1;
        }
        else if (arr[middle] > sum)
        {
            right = middle - 1;
        }
        else
        {
            printf("%d数字在数组中的下标是%d\n", sum, middle);
            break;
        }
    }
    if (left > right)
    {
        printf("%d在数据中不存在\n", sum);
    }

    return 0;
}

算法逻辑:

首先找到要被查找数组中最中间的元素与被查找元素进行比较由于例子中数组内容为由小到大顺序排列。因此与最中间的数进行比较。如果大就往右侧查找，这样直接筛选掉左侧的所有元素
然后循环查找，在右侧中找中间值，继续查找。循环查找
直到查找到 / 右侧下标大于左侧下标(未找到) 查找结束

冒泡排序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void Bubble_Sort(int arr[], int sz)
{
    for(int i = 0; i < sz - 1; i++)
    {
        for(int j = 0; j < sz - 1 -i; j++)
        {
            if(arr[j] > arr[j + 1])
            {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}

假设总共有10个数，因此共需要比较 10 - 1 次即 i < sz - 1
然后在这一趟中，两两相比，如果不符合条件就交换

辗转相除法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


int gcd(int a, int b)
{
    while(b)
    {
        int temp = a % b;
        a = b;
        b = temp;
    }

    retrun a;
}

打印闰年

闰年的要求为:

可以被4整除但不能被10整除
可以被400整除

因此表达式可以写为:

(year % 4 == 0) && (year % 100 != 0)
(year % 400 == 0)

写成判断表达式为:

1

if((!(year % 4) && !(year % 100)) || !(year % 400))

因为在C中，0为false 非0为true

! 为取反

输出 1000 - 2000 之间的闰年

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


int main()
{
    for(int year = 1000; year <= 2000; year++)
    {
        if((!(year % 4) && !(year % 100)) || !(year % 400))
        {
            cout << year << " " << endl;
        }
    }

    return 0;
}

输出素数

素数，又称质数。是指在大于 1 的自然数中，除了 1 和它本身以外不能被其他自然数整除的数

最简单的想法可以这样:

遍历 2 - sum 本身之间的所有数，进行遍历。同时设定一个变量 flag 且假定这个数是素数。一旦能被其他数整除就更改flag变量的值

1
2
3
4
5
6
7
8
9


int flag = 1;
for(int i = 2; i < sum; i++)
{
    if(!(sum % i))
    {
        flag = 0;
        break;
    }
}

计算如下级数

$$ \sum_{n=1}^{100} (-1)^{n-1} \frac{1}{n} = \frac{1}{1} - \frac{1}{2} + \frac{1}{3} - \frac{1}{4} + ... + \frac{1}{99} - \frac{1}{100} $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


int main()
{
    double sum;
    for(int n = 1; n <= 100; n++)
    {
        if(n % 2 == 1)
        {
            sum += 1.0 / n;
        }
        else
        {
            sum -= 1.0 / n;
        }
    }
    cout << sum << endl;

    return 0;
}

求最大/小值

首先需要一个数来和需要求最大值的数组进行比较。这个数必须是一个合理的值。不能比要比较的所有数都大/小。否则无法比较

也不能是数组内的元素，可能会出现问题

1
2
3
4
5
6
7
8
9


//假设使用0作为比较的数字
int max = 0;
for(int i = 0; i < /* 数组的最大元素下标 */; i++)
{
    if(max < arr[i])
    {
        max = arr[i]; //如果发现目前的最大值没有数组内当前下标的值大，就替换
    }
}

输出 99 乘法表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


int main()
{
    for(int i = 1; i <= 9; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            printf("%d * %d = %-2d ", i, j, i * j);
        }
        printf("\n");
    }

    return 0;
}

%-2d为缩进向右两个字符

大小写字母转换

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int main()
{
    char ch;
    scanf("%c", &ch);

    if(ch >= 'A' && ch <= 'Z')
    {
        ch += 32;
    }
    else if(ch >= 'a' && ch <= 'z')
    {
        ch -= 32;
    }
    cout << ch << endl;

    return 0;
}

必须使用 else if ! 否则一旦一个字符从大写转换为小写，它将立即被第二个 if 语句转换为大写

输入 3 个整数，以从大到小的顺序输出

 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


int main()
{
    int a, b, c, t;
    printf(("请输入三个整数:n"):
    scanf("%d %d %d", &a, &b, &c);
    if (a > b)
    {
        t = a;
        a = b;
        b = t;
    }
    if (a > c)
    {
        t = a;
        a = c;
        c=t;
    }
    if(b > c)
    {
        t = b;
        b = c;
        c = t;
    }
    printf("%d %d %d\n",a,b,c);

    return 0;
}           

计算累加阶乘的和

$$ \sum_{n = 1}^{10} 1! + 2! + 3! + ... + 10! $$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


int main()
{
    int sum = 0;
    int ret = 1;

    for(int i = 1; i <= 10; i++)
    {
        ret *= i;
        sum += ret;
    }
    cout << sum << endl;

    return 0;
}

使用递归求阶乘

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


int fun(int x)
{
    if(!x)
    {
        retrun 1;
    }
    else
    {
        retrun x * fun(x - 1);
    }
}

该方法仅适用于不考虑栈溢出的情况！

使用递归将字符串逆序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


void Reverse(char* str)
{
    char tmp = *str; //取出第一个字符
    int len = strlen(str);
    *str = *(str + len - 1); //和最后一个字符交换
    *(str + len - 1) = '\0'; //刚刚替换的最后一个字符变为\0
    
    if(strlen(str + 1) >= 2) //判断未交换字符串长度
    {
        Reverse(str + 1); //传入下一个需要交换的字符
    }
    *(str + len - 1) = tmp; //将最后一个字符换成取出的第一个字符 
}

使用递归实现n的k次方

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


double Pow(int n, int k)
{
    if(!k)
    {
        return 1;
    }
    else if(k > 0)
    {
        return n * Pow(n, k - 1);
    }
    else
    {
        return 1.0 / (Pow(n, -k));
    }
}

将一个数分解质因数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


int main()
{
    int n = 90;
    printf("%d = ", n);
    for(int i = 2; i <= n; i++)
    {
        while(n != i)
        {
            if(!(n % i))
            {
                printf("%d * ", i);
                n /= i;
            }
            else
            {
                break;
            }
        }
    }
    cout << n << endl;

    return 0;
}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


int main()
{
    int a = 12;
    int b = 16;
    int ret = a * b;

    while(a != b)
    {
        if(a > b)
        {
            a -= b;
        }
        else
        {
            b -= a;
        }
    }
    cout << a << endl;
    cout << ret / a << endl;

    return 0;
}

求最小公倍数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int main()
{
    int a = 0;
    int b = 0;
    scanf("%d %d", &a, &b);
    
	for(int i = 1; ; i++)
    {
        if(!(a * i & b))
        {
            printf("%d\n", a * i);
            break;
        }
    }
    
    return 0;
}

不创建第三变量进行数值交换

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


//方案一 容易溢出
int main()
{
    int a = 3;
    int b = 5;
    
    a = a + b; //a = 8 b = 5
    b = a - b; //b = 8 - 5 = 3 
    a = a - b; //a = 8 - 3 = 5
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


//方案二 使用异或操作符
int main()
{
    int a = 3; //011
    int b = 5; //101
    
    a = a ^ b; //a = 110 b = 101
    b = a ^ b; //a = 110 b = 011
    a = a ^ b; //a = 101 b = 011
}

求一个整数在内存中1的个数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


int NumberOf1(size_t n)
{
    int count = 0;
    while(n)
    {
        if(n % 2)
        {
            count;
        }
        n /= 2;
    }
    return count;
}
//仅适用于正数的写法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


int NumberOf1(int n)
{
    int count = 0;
    for(int i = 0; i < 32; i++)
    {
        if((n >> i) & 1)
        {
            count++;
        }
    }
    return count;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


//方法2
int NumberOf1(int n)
{
    int count = 0;
    while(n)
    {
        n = n & (n - 1);
        count++;
    }
    return count;
}

求水仙花数(自幂数)

一个n位数，其每一位的数字的n次方之和正好等于其本身

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


int Is_Math(int sum)
{
    int count = 1;
    int tmp = sum;
    while(tmp / 10)
    {
        tmp /= 10;
        n++;
    }
    tmp = sum;
    int math = 0;
    while(tmp)
    {
        math += pow(tmp % 10, count);
        tmp /= 10;
    }
    
    if(math == sum)
    {
        return 1;
    }
    
    return 0;
}

一个数 /10%10 即可拿到这个数的末位。只要每次拿到末位后/=10再进行循环即可拿到这个数的每一位

但是这样会更改原本数的内容！所以如果还需要使用该数请做好备份！

左旋k个字符

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


void Left_Move(char* str, int k)
{
    int len = strlen(str);
    
    for(int i = 0; i < k; i++)
    {
        char tmp = *str;
        for(int j = 0; j < len - 1; j++)
        {
            *(str + j) = *(str + j + 1);
        }
        *(str + n - 1) = tmp;
    }
}

打分的平均值

有n位考官，输入若干个成绩，去掉一个最高分和最低分求平均分

 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


int main()
{
    int n = 10;
    double sum = 0.0;
    double score = 0.0;
    
    double max = 0.0;
    double min = 100.0;
    
    for(int i = 0; i < n; i++)
    {
        scnaf("%d", &score);
        sum += score;
        
        if(score > max)
        {
            max = score;
        }
        if(score < min)
        {
            min = score;
        }
    }
    
    pinrtf("%.2f\n", (sum - max - min) / 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


#define n 10 //有序数组的长度 需留出插入的空间

void Insert(int* arr, int sum)
{
    int i = n - 1;
    for(i; i >= 0; i--)
    {
        if(arr + i > sum)
        {
            arr + i + 1 = arr + i;
        }
        else
        {
            arr + i + 1 = sum;
            break;
        }
    }
    if(i < 0)
    {
        arr + 0 = sum;
    }
}