CSI The Programming Layer-7

7-解决问题和算法

rCSI

7.1

解决问题的步骤

算法

分治

7.2

这一部分先说了简单变量，他是不可分的。接着开始分析一个选择算法，今天穿什么。
首先写出一个大致的过程，再看该过程是否需要细化。

有循环的算法

循环可以分为两种，一种是通过循环变量的计数来控制，一种通过循环体中的事件来控制。

先说第一种
循环可以分为三个部分，首先初始化循环不变量，然后检查该值是否到达了预定值，最后将这个变量加1。（是不是和for很像？）书上举了一个读取值10次并计算总和的例子。

然后是第二种
还是分成三步，先初始化事件，检查该事件，然后更新该事件。举计算平方根为例。
这个算法大致如下，先猜测结果是什么，然后将这个猜测值平方，如果误差比较小，就将猜测值作为结果。
用这种方法更新guess的值，guess+（square/guess）/2.0
注意：gusee的初始值设为square/4更接近答案

7.4

选择排序

将所有元素分为已排序与未排序，在未排序的元素中找到最小的一个元素，将其放入到已排序中

void SelectionSort(int a[],int len){
    int i,j;  
    for(i = 0 ; i < len-1 ; i++){
        int min_index = i;     //存储最小值 
        for(j = i + 1 ; j < len; j++)            
            if(a[ min_index ] > a[j])//选出最小值
                min_index = j;
        if(min_index != i){ 
            int temp = a[i];  //若当前比较的a[i]>最小值，进行交换
            a[i] = a[min_index];  
            a[min_index] = temp;  
        }  
    }  
}

//插入排序

冒泡排序

从第一个元素开始，如果它比下一个元素大，就交换两个元素的位置，然后再比较下一个元素，一直到不能交换为止。
到最后得到一个已排序的数组。

void BubbleSort(int a[], int len)
{
    int i=0;
    int j=0;
    int key=1;//用于替换
    for(i = 0 ; i < len - 1 ; i++)
        {
        for(j = 0 ; j < len - i - 1 ; j++)
            if(a[j] > a[j+1])//比较a[j]和a[j+1],大的向上交换，直到这一次全部比完。然后i+1，比较下一次
            {
                key = a[j];
                a[j] = a[j+1];
                a[j+1] = key;
            }
        }
    return;
}

插入排序

将所有元素分为已排序与未排序，将未排序的元素的第一个元素插入到已排序的元素中

int InsertionSort(int a[],int len){
    int key=0;//用于交换
   for(int i=0;i<len-1;i++){
         int j=i;
         do{
             if(a[j]>a[j+1]){  //假设a[j]已排好，a[j]与a[j+1],若a[j+1]大于前一位，交换，否则不交换。若还有更前一位，再比较。
              key=a[j];
              a[j]=a[j+1];
              a[j+1]=key;
             }
             j-=1;  //j=j-1,若前一位存在，比较前一位
        } while(j>=0);                                                                                                  
      }   
      return ;
   }   

快速排序

使用分治的思想，将最后一个元素作为比对值，比这个元素小的放在他的左边，比这个元素大的放在他的右边，然后递归，最后得到排好序的数组。

int partition(int array[],int len){
    int x=array[len-1];
    int i=-1;
    for(int j=0;j<len-1;j++){//最后一个数内定了
        if(array[j]<=x){
            exchange(&array[i],&array[j]);
            i+=1;
        }
    }
    exchange(&array[i+1],&array[len-1]);
    i++;
    return i;
}

上面那个程序，第一没有考虑i=-1时访问了非法空间，第二交换的时候交换错了，应该是i+1以后再交换

int partition(int array[],int len){
    int x=array[len-1];
    int i=-1;
    for(int j=0;j<len-1;j++){//最后一个数内定了
        if(array[j]<=x){
            if(i==-1){
                i+=1;
            }+=1;
            else{
                exchange(&array[i],&array[j]);
            }
        }
    }
    i+=1;
    exchange(&array[i],&array[len-1]);
    return i;
}

顺序查找

一个元素一个元素去找

int search(int array[],int len,int x){
    int find=0;
    for(int i=0;i<len;i++){
        if(array[i]==x)
            find=1;
        if(find==1)
            break;
    }
    return find;
}

二分查找

使用了分治的思想，将一个数组分成两半（只能针对排好序的数组）
还可以分为递归与非递归

递归

非递归

int BinSearch(int sorted_arr[],int Len,int key)
{
    int low=0;
    int high=Len-1;
    int mid=-1;
    while (low<=high)
    {
           mid=(low+high)/2;
          if (sorted_arr[mid]>key)
             {
                high=mid-1;
             }
          if(sorted_arr[mid]<key)
             {
                low=mid+1;
             }
          if(sorted_arr[mid]==key)
             {
                 return mid;
             }
    }
    return -1;
}

最后提到隐藏信息

在不同的人眼中一条狗是不同的