程序设计与算法基础
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; }
|
本文总阅读量次