1.1 数据结构+算法= 程序

1.2 算法复杂度

高斯求 100！的方法，比从1加到100要方便的多。

算法的特性

有穷性 :必须能停止

确定性 ：有确定的含义，无歧义

可行性：有限次的循环，求出结果

输入输出：有0或多个输入，一个或多个输出

好的算法标准

正确性 易读性 健壮性（能识别输入错误） 高效性 低存储性（空间复杂度）   

总之就是：高效率低存储

时间复杂度：算法运行需要的时间，一般是算法的执行次数

来看个小例子：

Sum  = 0；        //1次

Total = 0;           //I次

for(i = 1 ; i < n ; i++)  //n次

{                                    

    Sum = Sum +i ;         //n次

     for(j = 1 ; j <= n ; j++)   //n*n次

        Total = Total + i* j;      //n*n次
}

渐进时间复杂度：

注意：不是每个算法都能直接计算运行次数的

这就有了 ： 最好和最坏  和平均的情况

但是：通常是最坏情况来衡量算法的，这才有实际意义

空间复杂度：

辅助空间是关键因素

所以就是O(1)

1.3魔鬼序列

递归

#include <stdio.h>
//计算n的阶乘 factorial
int fac(int n)    //计算n的阶乘factorial
{
    if (n < 0)
    {
        printf("n < 0 ,data error");
        return -1;
    }
    else if (n == 0 || n == 1)
        return 1;
    else
        return n*fac(n - 1);

}
int main()
{
    int n = 15;
    long res = 0;
    res = fac(n);
    printf("The result is : %ld" , res);
    system("pause");
}

趣味故事：一棋盘的麦子

爆炸增量函数   会引起宕机 shutdown

故事2 ：神奇兔子

改进：

1.4马克思手稿中的数学

故事3：马克思手稿中的数学

故事4：爱因斯坦的阶梯

改进：思路 直接从7的倍数开始计算

故事5 ：哥德巴赫猜想

#include <iostream>
#include <cmath>
using namespace std;
int prime(int);//判断是否为素数
int main()
{
    int i, n;
    for (i = 4; i <= 20; i += 2) //对2000大于2的偶数分解判断，从4开始每次增加2
    {
      for (n = 2; n < i; n++)       //将偶数i分解为2个整数，一个整数n    ，一个是i-n
        if (prime(n))
        if (prime(i - n)) //判断第二个整数是否为素数
        {
            cout << i << " = " << n << "+" << i - n << endl; 
            break;  //有break 和 无break 结果是不一样的。
                  
        }

        if (n == i)
            cout << "******" << endl;
    }
    system("pause");
}

int prime(int i) //判读是否为素数
{
    int j = 0;
    if (i <= 1) return 0;
    if (i == 2)    return 1;
    for (j = 2; j <= (int)sqrt((double)i);j++)
              if (!(i%j))   return 0;
    return 1;
}

改进：

小提示：

素数又称质数。所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。

思路1)：因此判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。

思路2)：另外判断方法还可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~  之间的每一个整数去除就可以了。如果 m 不能被 2 ~  间任一整数整除，m 必定是素数。例如判别 17 是是否为素数，只需使 17 被 2~4 之间的每一个整数去除，由于都不能整除，可以判定 17 是素数。

原因：因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于 ，另一个大于或等于 。例如 16 能被 2、4、8 整除，16=2*8，2 小于 4，8 大于 4，16=4*4，4=√16，因此只需判定在 2~4 之间有无因子即可。

两种思路的代码请看解析。

思路1) 的代码：

1. #include <stdio.h>
2.  
3. int main(){
4. int a=0; // 素数的个数
5. int num=0; // 输入的整数
6.  
7. printf("输入一个整数：");
8. scanf("%d",&num);
9.  
10. for(int i=2;i<num;i++){
11. if(num%i==0){
12. a++; // 素数个数加1
13. }
14. }
15.  
16. if(a==0){
17. printf("%d是素数。\n", num);
18. }else{
19. printf("%d不是素数。\n", num);
20. }
21.  
22. return 0;
23. }

1. #include <stdio.h>
2. #include <math.h>
3. void main(){
4. int m; // 输入的整数
5. int i; // 循环次数
6. int k; // m 的平方根
7.  
8. printf("输入一个整数：");
9. scanf("%d",&m);
10.  
11. // 求平方根，注意sqrt()的参数为 double 类型，这里要强制转换m的类型
12. k=(int)sqrt( (double)m );
13. for(i=2;i<=k;i++)
14. if(m%i==0)
15. break;
16.  
17. // 如果完成所有循环，那么m为素数
18. // 注意最后一次循环，会执行i++，此时 i=k+1，所以有i>k
19. if(i>k)
20. printf("%d是素数。\n",m);
21. else
22. printf("%d不是素数。\n",m);
23.  
24. return 0;
25. }

输入一个整数：1
1是素数。

输入一个整数：97
97是素数。

输入一个整数：10
10不是素数。

1.5算法学习瓶颈

数据结构  

算法策略

1.6你怕什么

大视野

                                   程序就是蓝色的诗