离散数学及应用——算法、整数、矩阵

算法

算法是进行一项计算或解决一个问题的一组有限多条准确的指令。

搜索算法

线性搜索

二分搜索

排序

冒泡排序

冒泡排序是最简单的排序，但不是最有效的排序算法之一。
一次次比较相邻的元素，顺序不对，就交换相邻元素。
int[] a = {5,6,8,7};
设i为角标；
使用冒泡
i= 0;时
6587
6857
6875
i=1;
8675
8765
i=2;
8765

    for(int i=0;i<a.length-1;i++){
        for(int j=0;j<a.length-i-1;j++){
         int temp = a[j];
       if(a[j]<a[j+1])
  { a[j] =a[j+1]; a[j+1]=temp;}  
}

}
选择排序：
i= 0;时
8657
i=1;
8756
i=2;
8765

        for(int i=0;i<a.length-1;i++){
         int maxIndex = i;
       for(int j=i+1;j<a.length;j++){
        if(a[maxIndex]<a[j]){
         maxIndex = j;
}

}
int temp = a[i];
a[i] =a[maxIndex];
a[maxIndex]=temp;
}

插入排序

插入排序是一种简单的排序算法，但通常不是最有效的。
将指针指向某个元素，假设该元素左侧的元素全部有序，将该元素抽取出来，然后按照从右往左的顺序分别与其左边的元素比较，遇到比其大的元素便将元素右移，直到找到比该元素小的元素或者找到最左面发现其左侧的元素都比它大，停止；

  for(int i=1;i<a.length;i++){
    for(int j=i;j>0;j--){
    if(a[j]>a[j-1]){
        int temp = a[j-1];
        a[j-1] = a[j];
        a[j] = temp;
          }
     }
}

贪心算法

比如中国的货币，只看元，有1元2元5元10元20、50、100

如果我要16元，可以拿16个1元，8个2元，但是怎么最少呢？
如果用贪心算，就是我每一次拿那张可能拿的最大的。
比如16，我第一次拿20拿不起，拿10元，OK，剩下6元，再拿个5元，剩下1元
也就是3张 10、5、1。

每次拿能拿的最大的，就是贪心。

但是一定注意，贪心得到的并不是最优解，也就是说用贪心不一定是拿的最少的张数
贪心只能得到一个比较好的解，而且贪心算法很好想得到。
再注意，为什么我们的钱可以用贪心呢？因为我们国家的钱的大小设计，正好可以使得贪心算法算出来的是最优解（一般是个国家的钱币都应该这么设计）。如果设计成别的样子情况就不同了
比如某国的钱币分为 1元3元4元
如果要拿6元钱 怎么拿？贪心的话 先拿4 再拿两个1 一共3张钱
实际最优呢？ 两张3元就够了

停机问题 0AA68E92-6DD7-4a4e-9203-D349E55D4A1C.png

不存在一个程序可以判断另一程序是多久结束，是否停机。

整数

矩阵乘法

计算机中用的进制是二进制，就算时采用二进制的乘除法，要快一些。
矩阵也是在android 的图片操作中会遇到，英文名matrix

• 令A 为mk 矩阵，B为kn的矩阵。A和B的乘积AB是个m*n 的矩阵，其第（i,j）元素等于A的第i行与B的第j列
  对应元素乘积之和。
  475F4B4D-7B49-46f9-97B2-96117D151A60.png
  D91FD3B2-3B3A-4d65-A4CC-F49CF0E1DEB1.png

• 0-1矩阵

  
  0AA68E92-6DD7-4a4e-9203-D349E55D4A1C.png

• 布尔积

  
  D7B0B43B-004C-4060-95C0-462576E84FA5.png