程序员三大浪漫:操作系统,计算机图形学,汇编语言。
现在操作系统内核的设计主流主要分为两个:微内核和宏内核。两个流派的操作系统分别为Unix/Linux和Windows/Minix。
它们设计的区别是,宏内核将大多数事情交由自己完成;而微内核只要求内核实现基本的系统功能,(操作系统-宏内核和微内核的区别)然后其他功能可以通过外层的服务调用内核功能去完成。
从大一开始自己就想编辑一个属于自己的操作系统。开始动工。
我对这个内核操作系统命名为Tiám:初遇某人时眼里闪烁的光芒(我觉得这个单词很美好便用它来做我的操作系统名字)
目标如下:
1.构建运行在32位i386架构平台的IBM PC上
2.能够运行在ubuntu虚拟机上
3.能实现分页机制
4.实现底层对I/O的操作
5.对于内存管理器(MM)和文件管理器(FS)有一个初步的建立
用此来总结我的大学生活吧。

6.1 堆

最大堆:A[PARENT(i)]>=A[i]
最小堆:A[PARENT(i)]<=A[i]


6.2 维护堆的性质

void HeapAdjust(int H[],int s, int length)  
{  
    int tmp  = H[s];  
    int child = 2*s+1; //左孩子结点的位置。(i+1)为当前调整结点的右孩子结点的位置
    while (child < length) {  
        if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)  
            ++child ;  
        }  
        if(H[s]<H[child]) {  // 如果较大的子结点大于父结点  
            H[s] = H[child]; // 那么把较大的子结点往上移动,替换它的父结点  
            s = child;       // 重新设置s ,即待调整的下一个结点的位置  
            child = 2*s+1;  
        }  else {            // 如果当前待调整结点大于它的左右孩子,则不需要调整,直接退出  
             break;  
        }  
        H[s] = tmp;         // 当前待调整的结点放到比其大的孩子结点位置上
}  


6.3 建堆

void BuildingHeap(int H[], int length)  
{   
    //最后一个有孩子的节点的位置 i = (length -1) / 2  
    for (int i = (length -1) / 2 ; i >= 0; --i)  
        HeapAdjust(H,i,length);  
} 


6.4 堆排序

void HeapSort(int H[], int length)  
{  
    //初始堆  
    BuildingHeap(H, length);  
    //从最后一个元素开始对序列进行调整  
    for (int i = length - 1; i > 0; --i)  
    {  
        //交换堆顶元素H[0]和堆中最后一个元素  
        int temp = H[i]; H[i] = H[0]; H[0] = temp;  
        //每次交换堆顶元素和堆中最后一个元素之后,都要对堆进行调整  
        HeapAdjust(H, 0, i);
     }  
} 

6.5 优先队列

HeapExtractMax:去掉并返回S中的具有最大键字的元素
int HeapExtractMax(int H[], int length)  
{
    if (length < 1)
        return -1;
    int max = H[0];
    H[0] = H[length-1]
    HeapAdjust(H, 0, length - 1)
    return max;
}

HeapIncreaseKey:将元素x的关键字值增加到key
void HeapIncreaseKey(int H[], int length, int i, int key)  
{
    if (key < H{i])
        return;
    H[i] = key
    while (i > 0 && H[(i-1)/2] < H[i]){
        H[i] = H[(i-1)/2];
        H[(i-1)/2] = key;
        i = (i-1)/2;
    }
}

MaxHeapInsert:将新元素x插入到集合S中
int[] MaxHeapInsert(int H[], int length, int key){
    int newH[] = new int[length + 1];
    for (int i  = 0; i <= length; i++)
        newH[i] = H[i];
    newH[length] = -1;
    length++;
    HeapIncreaseKey(H, length, length - 1, key);
}

贪 心

简单贪心

贪心法是求解一类最优化问题的方法,它总是考虑在当前状态下局部最优(或较优)的策略,来使全局的结果达到最优(或较优)。显然,如果采取较优而非最优的策略(最优策略可能不存在或是不易想到),得到的全局结果也无法是最优的。而要获得最优结果,则要求中间的每步策略都是最优的,因此严谨使用贪心法来求解最优化问题需要对采取的策略进行证明。证明的一般思路是使用反证法及数学归纳法,即假设策略不能导致最优解,然后通过一系列系列推导来得到矛盾,以此证明策略是最优的,最后用数学归纳法保证全局最优。不过对平常使用来说,也许没有时间或不太容易对想到的策略进行严谨的证明(贪心的证明往往比贪心本身更难),因此一般来说, 如果在想到某个似乎可行的策略,并且自己无法举出反例,那么就勇敢地实现它。
PAT1024B

#include<iostream>
#include<algorithm>
using namespace std;
struct mooncake{
    double store;
    double sell;
    double price;
}cake[1010];
bool cmp(mooncake a,mooncake b){
    return a.price>b.price;
} 
int main(){
    int n;
    double D;
    scanf("%d%lf",&n,&D);
    for(int i=0;i<n;i++){
        scanf("%lf",&cake[i].store);
    }
    for(int i=0;i<n;i++){
        scanf("%lf",&cake[i].sell);
        cake[i].price=cake[i].sell/cake[i].store;
    }
    sort(cake,cake+n,cmp);
    double ans=0;
    for(int i=0;i<n;i++){
        if(cake[i].store<=D){
            D-=cake[i].store;
            ans+=cake[i].sell;
        }else{
            ans+=cake[i].price*D;
            break;
        }
    }
    printf("%.2f\n",ans);
    return 0;
}

区间贪心
区间不相交问题:给出N个开区间(x,y),从中选择尽可能多的开区间,使得这些开区间两两没有交集。
如果开区间i1被开区间i2包含,那么显然选择i1是最好的选择。所以总是选择左端最大的区间。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=110;
struct Inteval{
    int x,y;
}I[maxn];
bool cmp(Inteval a,Inteval b){
    if(a.x!=b.x) return a.x>b.x;
    else return a.y<b.y;
}
int main(){
    int n;
    while(scanf("%d",&n),n!=0){
        for(int i=0;i<n;i++){
            scanf("%d%d",&I[i].x,&I[i].y);
        }
        sort(I,I+n,cmp);
        int ans=1,lastX=I[0].x;
        for(int i=1;i<n;i++){
            if(I[i].y<=lastX){
                lastX=I[i].x;
                ans++; 
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

区间选点问题:给出N个闭区间[x,y],求最少需要确定多少个点,才能使没个闭区间中都至少存在一个点。例如对闭区间[1,4]、[2,6]、[5,7]来说,需要两个点才能保证每个闭区间都至少存在一个点。事实上,这个问题和区间不相交问题策略是一样的。

贪心是用来解决一类最优化问题,并希望由局部最优策略来推得全局最优结果的算法思想。贪心算法适用的问题一定满足最优子结构性质,即一个问题的最优解可以由它的子问题的最优解有效地构造出来。

第一章:算法在计算机中的作用

  本章是本书的开篇,介绍了什么是算法,为什么要学习算法,算法在计算机中的地位及作用。

  算法(algorithm)简单来说就是定义良好的计算机过程,它取一个或一组值作为输入,并产生出一个或一组值作为输出。即算法就是一系列的计算步骤,用来将输入数据转换成输出数据。

  书中有一句话非常好:

  Having a solid base of algorithm knowledge and technique is one characteristic that separates the truly skilled programmers from the novices.

  是否具有扎实的算法知识和技术基础,是区分真正熟练的程序员与新手的一项重要特征。

以这句话激励自己要努力学习算法,夯实基础,成为真正熟练的程序员。

第二章:算法入门

本章通过介绍插入排序和归并排序两种常见的排序算法来说明算法的过程及算法分析,在介绍归并排序算法过程中引入了分治(divide-and-conquer)算法策略。

1、插入排序

void insert_sort(int *datas,int length)
 {
     int i,j;
     int key,tmp;
     //判断参数是否合法
     if(NULL == datas || 0==length)
     {
         printf("Check datas or length.\n");
         exit(1);
     }
     //数组下标是从0开始的,从第二个元素(对应下标1)开始向前插入
     for(j=1;j<length;j++)
     {
         key = datas[j];  //记录当前要插入的元素
         i = j-1;  //前面已经有序的元素
       //寻找待插入元素的位置,从小到到排序,如果是从大到小改为datas[i]<key
         while(i>=0 && datas[i] > key)
         {
             /×tmp = datas[i+1];
             datas[i+1] = datas[i];
             datas[i] = tmp;*/这个过程不需要进行交换,因为要插入的值保存在key中,没有被覆盖掉
             datas[i+1] = datas[i];
             i--;   //向前移动
         }
         datas[i+1] = key;  //最终确定待插入元素的位置
   }
}

  输入:n个数(a1,a2,a3,...,an)

  输出:输入序列的一个排列(a1',a2',a3',...an')使得(a1'≤a2'≤a3'≤...≤an')。

  插入排序的基本思想是:将第i个元素插入到前面i-1个已经有序的元素中。具体实现是从第2个元素开始(因为1个元素是有序的),将第2个元素插入到前面的1个元素中,构成两个有序的序列,然后从第3个元素开始,循环操作,直到把第n元素插入到前面n-1个元素中,最终使得n个元素是有序的。该算法设计的方法是增量方法。书中给出了插入排序的为代码,并采用循环不变式证明算法的正确性。我采用C语言实插入排序,完整程序如下:

插入排序算法的分析

  算法分析是对一个算法所需的资源进行预测,资源是指希望测度的计算时间。插入排序过程的时间与输入相关的。插入排序的最好情况是输入数组开始时候就是满足要求的排好序的,时间代价为θ(n),最坏情况下,输入数组是按逆序排序的,时间代价为θ(n^2)。

2、归并排序

  归并排序采用了算法设计中的分治法,分治法的思想是将原问题分解成n个规模较小而结构与原问题相似的小问题,递归的解决这些子问题,然后再去合并其结果,得到原问题的解。分治模式在每一层递归上有三个步骤:

分解(divide):将原问题分解成一系列子问题。

解决(conquer):递归地解答各子问题,若子问题足够小,则直接求解。

合并(combine):将子问题的结果合并成原问题的解。

归并排序(merge sort)算法按照分治模式,操作如下:

分解:将n个元素分解成各含n/2个元素的子序列

解决:用合并排序法对两个序列递归地排序

合并:合并两个已排序的子序列以得到排序结果

  在对子序列排序时,长度为1时递归结束,单个元素被视为已排序好的。归并排序的关键步骤在于合并步骤中的合并两个已经有序的子序列,引入了一个辅助过程,merge(A,p,q,r),将已经有序的子数组A[p...q]和A[q+1...r]合并成为有序的A[p...r]。书中给出了采用哨兵实现merge的伪代码,课后习题要求不使用哨兵实现merge过程。在这个两种方法中都需要引入额外的辅助空间,用来存放即将合并的有序子数组,总的空间大小为n。现在用C语言完整实现这两种方法,程序如下:

//采用哨兵实现merge
 #define MAXLIMIT    65535
 void merge(int *datas,int p,int q,int r)
 {
     int n1 = q-p+1;  //第一个有序子数组元素个数
     int n2 = r-q;      //第二个有序子数组元素个数
     int *left = (int*)malloc(sizeof(int)*(n1+1));
     int *right = (int*)malloc(sizeof(int)*(n2+1));
     int i,j,k;
     //将子数组复制到临时辅助空间
     for(i=0;i<n1;++i)
         left[i] = datas[p+i];
     for(j=0;j<n2;++j)
         right[j] = datas[q+j+1];
     //添加哨兵
     left[n1] = MAXLIMIT;
     right[n2] = MAXLIMIT;
     //从第一个元素开始合并
     i = 0;
     j = 0;
     //开始合并
     for(k=p;k<=r;k++)
     {
         if(left[i] < right[j])
         {
             datas[k] = left[i];
             i++;
         }
         else
         {
             datas[k] = right[j];
             j++;
         }
     }
     free(left);
     free(right);
 }

不采用哨兵实现,需要考虑两个子数组在合并的过程中哪一个先合并结束,剩下的那个子数组剩下部分复制到数组中,程序实现如下:

int merge(int *datas,int p,int q,int r)
 {
     int n1 = q-p+1;
     int n2 = r-q;
     int *left = (int*)malloc(sizeof(int)*(n1+1));
     int *right = (int*)malloc(sizeof(int)*(n2+1));
     int i,j,k;
     memcpy(left,datas+p,n1*sizeof(int));
     memcpy(right,datas+q+1,n2*sizeof(int));
     i = 0;
     j = 0;
     for(k=p;k<=r;++k)
     {
         if(i <n1 && j< n2)  //归并两个子数组
         {
             if(left[i] < right[j])
             {
                 datas[k] = left[i];
                 i++;
             }
             else
             {
                 datas[k] = right[j];
                 j++;
             }
         }
         else
          break;
     }
     //将剩下的合并到数组中
     while(i != n1)
         datas[k++] = left[i++];
     while(j != n2)
         datas[k++] = right[j++];
     free(left);
     free(right);
 }

merge过程的运行时间是θ(n),现将merge过程作为归并排序中的一个子程序使用,merge_sort(A,p,r),对数组A[p...r]进行排序,实例分析如下图所示:

C语言实现如下:

归并排序算法分析:

void merge_sort(int *datas,int p,int r)
 {
     int q;
     if(p < r)
     {
         q = (p+r)/2;   //分解,计算出子数组的中间位置                merge_sort(datas,p,q);  //对第一个子数组排序;
         merge_sort(datas,q+1,r);  //对第二个子数组排序
          merge(datas,p,q,r);  //合并;
     }
 }

  算法中含有对其自身的递归调用,其运行时间可以用一个递归方程(或递归式)来表示。归并排序算法分析采用递归树进行,递归树的层数为lgn+1,每一层的时间代价是cn,整棵树的代价是cn(lgn+1)=cnlgn+cn,忽略低阶和常量c,得到结果为θ(nlg n)。

3、课后习题

  有地道题目比较有意思,认真做了做,题目如下:

方法1:要求运行时间为θ(nlgn),对于集合S中任意一个整数a,设b=x-a,采用二分查找算法在S集合中查找b是否存在,如果b存在说明集合S中存在两个整数其和等于x。而二分查找算起的前提是集合S是有序的,算法时间为θ(lgn),因此先需要采用一种时间最多为θ(nlgn)的算法对集合S进行排序。可以采用归并排序算法,这样总的运行时间为θ(nlgn),满足题目给定的条件。

具体实现步骤:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 //非递归二叉查找
 int binary_search(int *datas,int length,int obj)
 {
     int low,mid,high;
     low = 0;
     high = length;
     while(low < high)
     {
         mid = (low + high)/2;
         if(datas[mid] == obj)
             return mid;
         else if(datas[mid] > obj)
             high = mid;
         else
             low = mid+1;
     }
     return -1;
 }
 
 //递归形式二分查找
 int binary_search_recursive(int *datas,int beg,int end,int obj)
 {
     int mid;
     if(beg < end)
     {
         mid = (beg+end)/2;
         if(datas[mid] == obj)
             return mid;
         if(datas[mid] > obj)
             return binary_search_recursive(datas,beg,mid,obj);
         else
             return binary_search_recursive(datas,mid+1,end,obj);
 
     }
     return -1;
 }
 //合并子程序
 int merge(int *datas,int p,int q,int r)
 {
     int n1 = q-p+1;
     int n2 = r-q;
     int *left = (int*)malloc(sizeof(int)*(n1+1));
     int *right = (int*)malloc(sizeof(int)*(n2+1));
     int i,j,k;
     memcpy(left,datas+p,n1*sizeof(int));
     memcpy(right,datas+q+1,n2*sizeof(int));
     i = 0;
     j = 0;
     for(k=p;k<=r;++k)
     {
         if(i <n1 && j< n2)
         {
             if(left[i] < right[j])
             {
                 datas[k] = left[i];
                 i++;
             }
             else
             {
                 datas[k] = right[j];
                 j++;
             }
         }
         else
          break;
     }
     while(i != n1)
         datas[k++] = left[i++];
     while(j != n2)
         datas[k++] = right[j++];
     free(left);
     free(right);
 }
 //归并排序
 void merge_sort(int *datas,int beg,int end)
 {
     int pos;
     if(beg < end)
     {
         pos = (beg+end)/2;
         merge_sort(datas,beg,pos);
         merge_sort(datas,pos+1,end);
         merge(datas,beg,pos,end);
     }
 }
 
 int main(int argc,char *argv[])
 {
     int i,j,x,obj;
     int datas[10] = {34,11,23,24,90,43,78,65,90,86};
     if(argc != 2)
     {
         printf("input error.\n");
         exit(0);
     }
   x = atoi(argv[1]);
   merge_sort(datas,0,9);
   for(i=0;i<10;i++)
   {
       obj = x - datas[i];
       j = binary_search_recursive(datas,0,10,obj);
       //j = binary_search(datas,10,obj);
       if( j != -1 && j!= i)  //判断是否查找成功
       {
            printf("there exit two datas (%d and %d) which their sum is %d.\n",datas[i],datas[j],x);
            break;
       }
   }
   if(i==10)
       printf("there not exit two datas whose sum is %d.\n",x);
   exit(0);
}

1、采用归并排序算法对集合S进行排序

2、对集合S中任意整数a,b=x-a,采用二分查找算法b是否在集合S中,若在则集合S中存在两个整数其和等于x,如果遍历了S中所有的元素,没能找到b,即集合S中不存在两个整数其和等于x。

采用C语言实现如下:

  

程序执行结果如下:

方法2:网上课后习题答案上面给的一种方法,具体思想如下:

1、对集合S进行排序,可以采用归并排序算法

2、对S中每一个元素a,将b=x-a构造一个新的集合S',并对S’进行排序

3、去除S和S'中重复的数据

4、将S和S'按照大小进行归并,组成新的集合T,若干T中有两队及以上两个连续相等数据,说明集合S中存在两个整数其和等于x。

例如:S={7,10,5,4,2,5},设x=11,执行过程如下:

对S进行排序,S={2,4,5,5,7,10}。

S'={9,7,6,6,4,1},排序后S’={1,4,6,6,7,9}。

去除S和S'中重复的数据后S={2,4,5,7,10},S'={1,4,6,7,9}

归纳S和S'组成新集合T={1,2,4,4,5,6,7,7,9,10},可以看出集合T中存在两对连续相等数据4和7,二者存在集合S中,满足4+7=11。

第三章:函数的增长

  本章介绍了算法分析中的渐进分析符号,几个重要渐进记号的定义如下:

Θ(g(n))={ f(n): 存在正常数c1,c2和n0,使对所有的n>=n0,有0<=c1g(n)<=f(n)<=c2g(n) }

O(g(n))={ f(n): 存在正常数c和n0,使对所有n>=n0,有0<=f(n)<=cg(n) }

Ω(g(n))={ f(n): 存在正常数c和n0,使对所有n>=n0,有0<=cg(n)<=f(n) }

o(g(n))={ f(n): 对任意正常数c,存在常数n0>0,使对所有的n>=n0,有0<=f(n)<=cg(n) }

ω(g(n))={ f(n): 对任意正常数c,存在常数n0>0,使对所有的n>=n0,有0<=cg(n)<f(n) }

f(n)=Ω(g(n)),表示这个算法是有一个渐近下界的,这个渐近下界为g(n),算法的运行时间f(n)趋近并大于等于这个g(n)。
f(n)=Θ(g(n)),表示这个算法是有一个渐近确界的,这个渐近确界为g(n),算法的运行时间f(n)趋近g(n)。

f(n)=O(g(n)),表示这个算法是有一个渐近上界的,这个渐近上界为g(n),算法的运行时间f(n)趋近并小于等于这个g(n)