C语言算法总结

2.牛顿迭代求a的平方根

【思想汇总】迭代公式为xn+1=0.5(xn+a/xn),要求前后两次求出的x的差的绝对值小于10-5。

【算法语句】

float a,x0,x1;

scanf(“%f”,&a);

x0=a/2;

do

{

x0=x1; x1=(x0+a/x0)/2; /*循环N次当满足x0与x1的差小于10-5输出答案 /*先定义两个变量，利用公式求出第一组数*/ x1=(x0+a/x0)/2;

}while(fabs(x1-x0)>=1e-5); */

x1即为所求。

【思想推广】牛顿迭代法求平方根是一种逼近的数学思想，用途十分广泛，如上机指导实验六第三题，arcsh(x)函数。

3.求最大公约数，最小公倍数

【思想汇总】求此数有三种思想，一是定义法求解，二是相减求等法，三是辗转相除法。具体算法如下。

【算法语句】

gys(int m,int n)

{

}

gys(int m,int n)

{

}

gys(int m,int n)

{

}

int r; while((r=m%n)!=0) {m=n;n=r;}/*辗转相除法是最简单的方法，但要好好理解*/ return n; while(m!=n) if(m>n)m=m-n;/*此为相减求等法，大减小，这样逐步相减，当它相等时， else n=n-m; 即为答案*/ int i,x; x=m<n?m:n; for(i=x;i>=1;i--) if(m%i==0&&n%i==0)break;/*此为定义法，先找一个相对最小的数x， return i; 再定义一个变量从x到1递减，判断是否能同时被两个数整除*/ return m;

【思想推广】求公约数和公倍数在最近的考试中不常出现，只需理解其原理即可。其思想即是熟练掌握公式。

…… …… 余下全文

算法（Algorithm）：计算机解题的基本思想方法和步骤。算法的描述：是对要解决一个问题或要完成一项任务所采取的方法和步骤的描述，包括需要什么数据（输入什么数据、输出什么结果）、采用什么结构、使用什么语句以及如何安排这些语句等。通常使用自然语言、结构化流程图、伪代码等来描述算法。

一、计数、求和、求阶乘等简单算法

此类问题都要使用循环，要注意根据问题确定循环变量的初值、终值或结束条件，更要注意用来表示计数、和、阶乘的变量的初值。

一般情况下，计数初值为0、求和初值为0、阶乘初值为1

例1：用随机函数产生100个[0，99]范围内的随机整数，统计个位上的数字分别为1，2，3，4，5，6，7，8，9，0的数的个数并打印出来。

本题使用数组来处理，用数组a[100]存放产生的确100个随机整数，数组x[10]来存放个位上的数字分别为 1，2，3，4，5，6，7，8，9，0的数的个数。即个位是1的个数存放在x[1]中，个位是2的个数存放在x[2]中，??个位是0的个数存放在 x[10]。

void main()

{ int a[101],x[11],i,p;

for(i=0;i<=11;i++)

x[i]=0;

for(i=1;i<=100;i++)

{ a[i]=rand() % 100;

printf("%4d",a[i]);

if(i%10==0)printf("\n");

}

for(i=1;i<=100;i++)

{ p=a[i]%10;

if(p==0) p=10;

x[p]=x[p]+1;

}

for(i=1;i<=10;i++)

{ p=i;

if(i==10) p=0;

printf("%d,%d\n",p,x[i]);

}

printf("\n");

…… …… 余下全文

C语言常用算法模块的总结

一、最大值，最小值问题 教材page13/1.6、page36/2.4（2）、（3）、page98例5.1、5.2

二、连乘连加问题 page113、114、115 page129/6.3 page129/6.4、6.5

三、闰年算法 page17、 page107

四、连续小数相加减 page18、 page124

五、素数、整除问题 page18、 page124、 page126、 page127

六、大小写字母转换、密码问题 page51、 page87、 page89/4.9、 page104、 page67、 page128

七、格式化字符提醒 起于page 76

八、三角形面积问题 page86

九、一元二次方程 page87、 page89/4.8、 page108

十、分段一元函数 page100、 page110、 page111/5.5、5.6

十一、位运算 page112/5.7、 page129/6.2、6.3

十二、公约数公倍数 page129/6.1

十三、迭代法、二分法 page129-130/6.11-13

C语言常用算法模块的总结

一、最大值，最小值问题

教材page13/1.6、page36/2.4（2）、（3）、page98例5.1、5.2

主要思想：替换+中转 关联习语： if句

int a,b,c,max; 多余的一个max是承载中转的容器 scanf(“%d,%d,%d”,&a,&b,&c);

max=a; 定初值

if(max<b)

Max=b; 分别取a、 b、c相互比较，由于只需输 if(max<c) 出最大或者最小值，所以只需将最大值存 Max=c; 储在max中即可

…… …… 余下全文

算法（Algorithm）是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

    算法可以理解为有基本运算及规定的运算顺序所构成的完整的解题步骤。或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。

    一个算法应该具有以下五个重要的特征：

    1、有穷性： 一个算法必须保证执行有限步之后结束；

    2、确切性： 算法的每一步骤必须有确切的定义；

    3、输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；

    4、输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；

    5、可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

计算机科学家尼克劳斯-沃思曾著过一本著名的书《数据结构十算法= 程序》，可见算法在计算机科学界与计算机应用界的地位。

常见的五种算法：

一：分治算法

      在计算机科学中，分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……

…… …… 余下全文

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

#include <stdio.h>

void bubbleSort(int arr[], int count) {

int i = count, j; int temp; while(i > 0) {

for(j = 0; j < i - 1; j++) {

if(arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } i--; } }

int main(int arc, char* const argv[]) {

int arr[] = {5, 4, 1, 3, 6}; bubbleSort(arr, 5); int i;

for(i = 0; i < 5; i++)

printf("%4d", arr[i]); }

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）

元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

#include <stdio.h> int main() { int a[]={2,3,4,5,1,7,0,9}; int len=sizeof(a)/sizeof(a[0]); select_sort(a,len); for(int i=0;i<len;i++) { printf("%d ",a[i]); } return 0; }

…… …… 余下全文

C语言常用算法模块的总结

一、最大值，最小值问题   教材page13/1.6、page36/2.4（2）、（3）、page98例5.1、5.2

二、连乘连加问题   page113、114、115  page129/6.3  page129/6.4、6.5

三、闰年算法       page17、  page107

四、连续小数相加减 page18、  page124

五、素数、整除问题 page18、  page124、  page126、  page127

六、大小写字母转换、密码问题 page51、 page87、 page89/4.9、 page104、 page67、 page128

七、格式化字符提醒 起于page 76

八、三角形面积问题 page86

九、一元二次方程   page87、 page89/4.8、 page108

十、分段一元函数   page100、 page110、 page111/5.5、5.6

十一、位运算       page112/5.7、 page129/6.2、6.3

十二、公约数公倍数 page129/6.1

十三、迭代法、二分法 page129-130/6.11-13

C语言常用算法模块的总结

一、最大值，最小值问题  

教材page13/1.6、page36/2.4（2）、（3）、page98例5.1、5.2

主要思想：替换+中转  关联习语： if句

   int a,b,c,max;                              多余的一个max是承载中转的容器

…… …… 余下全文

C语言排序方法

学的排序算法有：插入排序，合并排序，冒泡排序，选择排序，希尔排序，堆排序，快速排序，计数排序，基数排序，桶排序（没有实现）。比较一下学习后的心得。

我不是很清楚他们的时间复杂度，也真的不知道他们到底谁快谁慢，因为书上的推导我确实只是小小了解，并没有消化。也没有完全理解他们的精髓，所以又什么错误的还需要高手指点。呵呵。

1.普及一下排序稳定，所谓排序稳定就是指：如果两个数相同，对他们进行的排序结果为他们的相对顺序不变。例如A={1,2,1,2,1}这里排序之后是A = {1,1,1,2,2} 稳定就是排序后第一个1就是排序前的第一个1，第二个1就是排序前第二个1，第三个1就是排序前的第三个

1。同理2也是一样。这里用颜色标明了。不稳定呢就是他们的顺序不应和开始顺序一致。也就是可能会是A={1,1,1,2,2}这样的结果。

2.普及一下原地排序：原地排序就是指不申请多余的空间来进行的排序，就是在原来的排序数据中比较和交换的排序。例如快速排序，堆排序等都是原地排序，合并排序，计数排序等不是原地排序。

3.感觉谁最好，在我的印象中快速排序是最好的，时间复杂度：n*log(n)，不稳定排序。原地排序。他的名字很棒，快速嘛。当然快了。我觉得他的思想很不错，分治，而且还是原地排序，省去和很多的空间浪费。速度也是很快的，n*log(n)。但是有一个软肋就是如果已经是排好的情况下时间复杂度就是n*n,不过在加入随机的情况下这种情况也得以好转，而且他可以做任意的比较，只要你能给出两个元素的大小关系就可以了。适用范围广，速度快。

4.插入排序：n*n的时间复杂度，稳定排序，原地排序。插入排序是我学的第一个排序，速度还是很快的，特别是在数组已排好了之后，用它的思想来插入一个数据，效率是很高的。因为不用全部排。他的数据交换也很少，只是数据后移，然后放入要插入的数据。（这里不是指调用插入排序，而是用它的思想）。我觉得，在数据大部分都排好了，用插入排序会给你带来很大的方便。数据的移动和交换都很少。

…… …… 余下全文