Lane
程序设计与算法基础

程序设计与算法基础

hello 世界

序列一简单算法

首先这是一段引言,因为刚刚结束了大一上的学习,基本掌握了C语言的语法。虽然自己谈不上精通
但是基本上的语法结构和细节问题已比较清楚。但是,发现自己与大陆的其他一梯队的同学在ACM上存在一定差距,在此进行常见算法总结并附上一些解决原码。

快速幂

计算幂这一个话题,在c语言的math.h标准库中存在pow函数,但是在实际运用中,常常处理的数据
比较大。我们发现,计算幂便由两个元素构成——即底数与指数。我们在这里联想到了折半寻找的思路,
我们发现任意的数都可以由二进制的形式进行表达,如字面量(十进制)7表达为111,则$7=2^2+2^1+1$,不妨设底数为3。则幂的表达式变成了$result=3^1 * 3^2 * 3^4$,观察此表达式我们不难发现。当某个数的二进制表达式在该位为零时,则此时结果不参与运算仅仅“底数”进行一个倍乘处理。

for example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
int kuaipow(int di,int zhi, int a);
int main()
{
int di=3,zhi=4;
printf("%d",kuaipow(3,4,1));
}
int kuaipow(int di,int zhi,int a)
{
if(zhi==0)
return a;
else
{
if(zhi%2)
{
return kuaipow(di*di,zhi/2,a*di);
}
else
{
return kuaipow(di*di,zhi/2,a);
}
}
}

一些常见的排序算法

排序与查找c语言中解决问题的基础,现在就让我们简单地聊一聊排序。排序以算法的时间复杂度分类,譬如冒泡、选择、插入之流的时间复杂度为$o(n^2)$,在实际问题的解决中当然是时间复杂度越低,效率越高。那么接下来我来谈一谈常见的快速排序与归并排序。

for example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void quickSort(int arr[], int left, int right) {
if(left < right) {
int p = partition(arr, left, right);

quickSort(arr, left, p-1);
quickSort(arr, p+1, right);
}
}

int partition(int arr[], int left, int right) {
int pivot = arr[right];
int i = left - 1;

for(int j = left; j <= right - 1; j++) {
if(arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i+1], &arr[right]);
return i+1;
}
本文总阅读量
本文作者:Lane
本文链接:https://lakerswillwin.github.io/2024/05/03/c/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可