![程序设计与算法基础]()
程序设计与算法基础
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;
}
|
