Zeray Rice

..

《算法导论》学习笔记-1&2.1

首先第一部分第一章 算法在计算机中的作用 这一章基本都是概念性的东西 列举一些生活中的算法应用的例子 以及算法效率的判断 不同的实际情况有不同的判断标准 还有说一些关于有效解法的问题 说到NP完全问题至今没有有效解法 很好奇这是个什么东西 慢慢看 长篇大论大家基本 都学过 so 此处略去

直接开第二章 第二章主要是用几个排序问题的算法做例子 来讲一下这整本书的框架 先从2.1 插入排序开始讲

这一节是以插入排序为例子 讲解伪代码、算法正确性的证明和排序问题这个算法是比较贴近生活的 就是根据打牌的时候 整理牌的方法 延伸出来的（果真算法是无处不在的）

伪代码

首先说下伪代码 伪代码的语法如下：

  1. 缩进：缩进就相当于Pascal里的Begin~End 这一点在C里面也有体现 但是C是用的大括号+缩进（当然你可以不要缩进 但是那样会让你的代码看起来很乱）

  2. 条件及循环结构：基本等同于 Pascal里 条件：if,then,else 循环：while,for,repeat 但是需要注意的是 Pascal里 for 循环中的计数器的值 在退出循环后是不保留的 但是在伪代码里 是保留的

  3. 注释：注释的符号是△（类似于这个符号 把这个符号逆时针旋转30度即可 我打不出来 谁能告诉我怎么打..） △后面的一行就是注释

  4. 赋值：伪代码里的赋值符号是← 比如 i←j 需要注意的是 像这样 i←j←k 的语句 意为 j←k i←j 运行的最终结果是 i j k的值均等于k的初值（能不能i←j←k←l←m←n…… 这样一直下去呢 书上没有说呢）

  5. 变量：变量是局部于给定过程的(C里面貌似没有过程吧) 一般情况下我们(《算》这本书里这样写的 这里的”我们”是局限于这本书呢还是伪代码通用的呢)不使用全局变量

  6. 数组：伪代码的数组下标是从1开始的(不像C 从0开始 这也造就了前文的那个笑话) 伪代码里的数组可以用”..”符号来表示一个取之范围 比如 A[1..j] 表示从A[1]到A[j]的所有元素

  7. 布尔运算符：布尔运算都具有短路能力(第一次听说这个东西 但是概念貌似以前接触过 是在asp里？) 就是说如果 and 前面的值为FALSE那么整个式子的值均为FALSE 就不再向下计算了 如果or前面的值为TRUE 也不再向下计算 直接返回TRUE

（参数 对象 属性和域没看懂 先不写了……）

插入排序

首先是插入排序的伪代码(第一行不算代码)

Insert Sort 
1
2
3
4
5
6
7
8
9

INSERTION-SORT(A)
  for j←2 to length[A]
     do key←A[j]
      △Insert A[j] into the sorted sequence A[i..j-1]
      i←j-1
      while i>0 and A[i]>key
         do A[i+1]←A[i]
          i←i-1
      A[i+1]←key

这个看起来蛮费劲的 我给改成了C 代码如下(MinGW测试通过 不过只包含相应子函数)

Insert Sort 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int InsertionSoft(int *a,int n)
{
  for(j=1;j<=n;j++)
  {
      key=a[j];
      i=j-1;
      while(i>=0&&a[i]>key)
      {
          a[i+1]=a[i];
          i--;
      }
      a[i+1]=key;
  }
  return 0;
}

说明：i,k为int型 a为待排序数组 n为数组个数（他不定义 我也不定义。。Hoho~~）

Comments