算法--职前算法复习

前端之家收集整理的这篇文章主要介绍了算法--职前算法复习前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
1,strcpy//返回的是目标串的地址,这样支持连续的运算表达式,已测试

char *strcpy(char *strDest,const char *strSrc){//源串一定要const修饰

       assert((strDest!=NULL)&&(strSrc!=NULL));//此类题型基本判断,指针是否空

       if(strDest==strSrc)return strDest;//编程题型的基本判断,相等时可直接返回

       char *tempptr=strDest;//因为传进来的指针在复制时会移动,因此先备份

       while((*strDest++=*strSrc++)!=’/0’);//空循环,如是其它条件一定注意’/0’的处理

       return tempptr;//上一行的while中(*strDest++=*strSrc++)括号不能少

}

2,memcpy//对内存块的复制,需要着重考虑的是,内存块重叠的情况,已测试

void memcpy(void *pDest,const void *pSrc,size_t size){

       assert((pDest!=NULL)&&(pSrc!=NULL)); //此类题型基本判断,指针是否空

       //任何对void*指针的运算,都需要先类型转换!

       if((pDest>pSrc)&&((char *)pSrc+size>pDest)){//有重叠,且目标内存块在后

              char* pstrSrc=( char*)pSrc+size-1;//一定要注意-1,因为如果size是1

              char* pstrDest=( char*)pDest+size-1;//则不需要加,因此注意要-1

              while(size--)//直接用size控制循环,另一处用size是else中,不可能同时会执行

                     * pstrDest --=* pstrSrc --;//自减用的是pstrSrc,而不是pSrc

}else{//无重叠或者有重叠但目标内存块在前

              char* pstrSrc =(char*)pSrc;

              char* pstrDest =(char*)pDest;       

              while(size--)

                     * pstrDest ++=* pstrSrc ++;

}

}

3,链表建立,合并有序链表,链表逆置,已测试

typedef struct Node{

         int val;        Node *next;

}Node;

Node* createLink(){//建立一个有序链表

         int val;

         Node *head=NULL;

         while(true){

                   cin>>val;

                   if(val==-1)return head;

                   Node *tmp=new Node;

                   tmp->val=val;

                   tmp->next=NULL;

                   if(head==NULL)head=tmp;//空链表情况

                   else{

                            Node *q=NULL;

                            for(Node *p=head;p!=NULL&&(p->val<=tmp->val);q=p,p=p->next)        ;

                            if(q==NULL){tmp->next=head;head=tmp;}//插表头情况

                            else{

                                     tmp->next=p;//其它情况,表尾也包括在此中

                                     q->next=tmp;

                            }

                   }                

         }

         return head;

}

Node *mergeLink(Node *a,Node *b){//合并有序链表

         Node *p,*head;  

         if(a==NULL)return b;//这个边界条件一定要处理

         if(b==NULL)return a;

         if(a->val<=b->val){//确定表头

                   head=a;a=a->next;

         }else {

                   head=b;b=b->next;

         }

         p=head;

         while(a!=NULL&&b!=NULL){//当两表都不空时确定结点

                   if(a->val<b->val){

                            p->next=a;p=p->next;a=a->next;

                   }else {

                            p->next=b;p=p->next;b=b->next;

                   }

         }

         while(a!=NULL){//处理余下的一个链尾

                   p->next=a;

                   a=a->next;

         }

         while(b!=NULL){//处理另一链尾

                   p->next=b;

                   b=b->next;

         }

         return head;

}

Node *reverseLink(Node *head){ 

         if(head==NULL)return NULL;//空链表

         Node *p,*q,*r;

         p=head;

         if(p->next==NULL)return p;//只一个结点

         q=p->next;

         p->next=NULL;//一定要有这句,否则逆序后找不到尾了

         if(q->next==NULL){

                   q->next=p;         

                   return q;//只两个结点

         }

         r=q->next; 

         while(r!=NULL){//多于两个情况

                   q->next=p;

                   p=q;

                   q=r;

                   r=r->next;

         }

         q->next=p;//处理表尾情况

         return q;

}

4,二叉树的前中后序遍历的递归,非递归写法!已测试过

void InOrderTraverse(NODE* root){//中序非递归

         stack<NODE*> s;

         s.push(root);//根进栈

         NODE *p=NULL;

         while(!s.empty()){

                   while((p=s.top())!=NULL)s.push(p->pLeft);//左一直进栈,空的也进

                   s.pop();//弹出空指针

                   if(!s.empty()){

                            p=s.top();

                            s.pop();//弹出栈顶元素并访问之

                            cout<<p->chValue;

                            s.push(p->pRight);//往右一步

                   }

         }

}

void PreOrderTraverse(NODE* root){//前序非递归

         stack<NODE*> s;

         s.push(root);

         NODE *p=NULL;

         while(!s.empty()){

                   while((p=s.top())!=NULL){//此处会处理树空的情况

                            cout<<p->chValue;//先访问自己再左子树进栈,这是与中序的唯一区别

                            s.push(p->pLeft);

                   }

                   s.pop();//此处会弹出空指针

                   if(!s.empty()){

                            p=s.top();

                            s.pop();

                            s.push(p->pRight);

                   }

         }

}

void PostOrderTraverse(NODE* root){//后序,需要增加目前已经访问是左或右的标记

         stack<stackNODE> s;

         stackNODE x;

         NODE* p=root;

         do{

                   while(p!=NULL){//非空左子树一直进栈,并标记为已访问左子树,直达最左叶子

                            x.ptr=p;

                            x.tag='L';

                            s.push(x);

                            p=p->pLeft;

                   }

                   while(!s.empty()&&s.top().tag=='R'){//如果栈中元素已经访问过右子树,则访问根

                            x=s.top();

                            s.pop();

                            cout<<x.ptr->chValue;

                   }

                   if(!s.empty()){//进入栈中元素的右子树,只是赋值,右子树是否空,交由外层循环

                            s.top().tag='R';

                            p=s.top().ptr->pRight;

                   }

         }while(!s.empty());

}

5,折半查找

int halfSearch(int *a,int e,int start,int end){//二分查找,e为待找元素的值

         if(start>end)return -1;//处理找不到的情况,start=end最终也会递归到start>end

         int mid=(start+end)/2;

         if(a[mid]==e)return mid;

         else if(a[mid]>e)return halfSearch(a,e,start,mid-1);

         else return halfSearch(a,mid+1,end);

}

6,最大公约数,已测试

int gcb(int a,int b){       //辗转相除法

         if(a<b)swap(a,b);//先判断大小,估计a大于b

if(b==0)return a;//如果小的数为0返回a,不管a是不是0

         int r=a%b;//否则求余

         while(r!=0){//余数不为零时一直循环,至余数为0为止

                  a=b;

                   b=r;

                   r=a%b;

         }

         return b;//余数为0则返回两数中较小的

}

int gcb(int a,int b){// 递归算法

         if(a<b)swap(a,b);

         if(b!=0)return gcb(b,a%b);

         else return a;

}

7,栈的操作(InitStack,GetTop,Push,Pop)

如果用链表的话,插删表头,如果用数组的话,用base,top保存数组下标

最简单实现如下:已测试,但未必充分

template <typename T>

class MyStack{

private:

         int size;

         int top;

         int base;

         T *stack;

public:

         MyStack(int size=100){

                   this->size=size;

                   stack=new T[size];

                   top=base=0;

         }

         void push(T elem){

                   if(top<size-1)stack[top++]=elem;

         }

         T pop(){

                   if(!(top==base))

                            return stack[--top];

         }

~MyStack(){

                   delete []stack;

         }

};

8,队列操作(入队出队),已测试

typedef struct QNode{

         int data;

         struct QNode *next;

}QNode,*QueuePtr;

typedef struct{

         QueuePtr front,rear;//队首尾指针

}LinkQueue;

void InitQueue(LinkQueue &Q){//初始化只分配一个不存元素的空头结点

         Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

         if(!Q.front){printf("OVERFLOW");return;}

         Q.front->next=NULL;

}

void EnQueue(LinkQueue &Q,int e){

         QueuePtr p=( QueuePtr)malloc(sizeof(QNode));

         if(!p){printf("OVERFLOW");return;}

         p->data=e;

         p->next=NULL;

         Q.rear->next=p;

         Q.rear=p;

}

void DeQueue(LinkQueue &Q,int &e){

         if(Q.front==Q.rear){printf("Empty Queue!");return;}

         QueuePtr p=Q.front->next;

         e=p->data;

         Q.front->next=p->next;

         if(Q.rear==p)Q.rear=Q.front;//删最后一个结点的情况下,必须处理,以防rear指针悬空

         free(p);

}

9,破坏栈返回链的代码,已测试

void breakDown(){

         char str[3]=”/0”;//str放在栈上

         strcat(str,”AAAAA”);//越界的赋值把返回链顶乱了,因此程序崩溃

         return;

}

int main(int argc,char *argv[]){

         breakDown ();

         return 0;

}

10,各种排序算法,已验证

(一)堆排序

int heapSize = 0;

int Parent(int index) { //返回父母的下标,左孩子的父母除2即可,右孩子除后-1

    return (index % 2) ? (index >> 1) : ((index >> 1) - 1);

}

int Left(int index) {  //返回左孩子下标,乘2之后+1

    return ((index << 1) + 1);

}

int Right(int index) {    //返回右孩子下标,乘2后+2

    return ((index << 1) + 2);

}

//主要函数一,堆调整,调整index为根的子树,前提是,index的左右子树已经调整过。

void maxHeapify(int * array,int index) {

    int largest = 0;

    int left = Left(index);

    int right = Right(index);//第一步,先找到根与左右孩子中最大者的下标

    if ((left <= heapSize) && (array[left] > array[index]))//heapSize来控制是否到叶子了

        largest = left;

    else

        largest = index;

 

    if ((right <= heapSize) && (array[right] > array[largest]))

        largest = right;

    if (largest != index) {//第二步,如果最大的不是根,则交换最大者与根,递归调整

        swap(&array[index],&array[largest]);

        maxHeapify(array,largest);

    }

}

//主要函数二,建堆

void buildMaxHeap(int * array,int length) {

    int i;

    heapSize = length;//初始化堆大小

    for (i = (length >> 1); i >= 0; i--)//从有孩子的结点开始,调整至树根为止即建好了

        maxHeapify(array,i);

}

//主要函数三,排序,调用前两个函数

int heapSort(int * array,int length) {

    int i;

    buildMaxHeap(array,(length - 1));//建堆

    for (i = (length - 1); i >= 1; i--) {

                   printf("%d,",array[0]);//输出堆顶元素

        swap(&array[0],&array[i]);//交换它与堆的最末尾一个元素,排完序后a升序

        heapSize--;//堆大小减1

        maxHeapify(array,0);//只需要调整树根

    }

         return 0;

}

(二)快速排序

int part(int *a,int low,int high){//划分函数

         int x=a[low];//此处是a[low]而不是a[0],我自己写代码时犯了此错误

         //int i=low,j=high;不需要,直接用low,high

         while(low<high){

                   while((a[high]>=x)&&(low<high))--high;//要重复low<high这一条件!

                   a[low]=a[high];

                   while((a[low]<=x)&&(low<high))++low;

                   a[high]=a[low];                     

         }

         a[low]=x;//x最后是给a[low]

         return low;//返回的是low

}

void quickSort(int *a,int high){//递归函数

         if(low<high){//这是递归终结条件,即在只有一个元素时或者low>high时,不排序!

                   int mid=part(a,low,high);

                   quickSort(a,mid-1);

                   quickSort(a,high);

         }

}

快速排序扩展:(1),随机化版本,即每次进行划分之前,随机生成一个low至high之间的下标,将此下标中元素与a[low]交换,然后再进行划分;(2)快排的第二次递归非必须,可用尾递归技术,用循环代替递归,代码如下:

while(low<high){

         int mid=part(a,high);

         quickSort(a,mid-1);

         low=mid+1;

}

(3)在划分不均衡时,会导致递归深度为n,解决方法是,每次划分后,小的一段先递归,可使栈深度最大为logn,或者小的一段用递归而大的一段用循环,参考“尾递归”方法;(4)快速排序的非递归版本思想:

1)将low,high包装为position结构体,先将初始position(low,high)进栈

2)while(栈不空){

         弹出栈顶的position,如果low<high,则q=partition(a,high);

         if(q>low+1)将(low,q-1)包装成position进栈

         if(high>q+1)将(q+1,high)包装成position进栈

}原理是,每次栈中有较长的序列,都会弹出,分成更小的序列,直至某序列少到一个元素时,不再push进新的position。具体代码如下,已验证:

void quickSort2(int *a,int high){

         MyStack<position> stack(150);//这个栈是自己写的,只有pop,push,empty及析构函数

         position pos;//自己定义的结构体

         pos.x=low;

         pos.y=high;

         stack.push(pos);//初始上下界进栈

         while(!stack.empty()){

                   position poped=stack.pop();//栈不空进,弹出栈顶元素

                   if(poped.x<poped.y){//如果可划分,则划分成两段

                            int q=part(a,poped.x,poped.y);

                            if(q>poped.x+1){//划后的第一段可进栈否?

                                     position lowpart;

                                     lowpart.x=poped.x;

                                     lowpart.y=q-1;

                                     stack.push(lowpart);

                            }

                            if(poped.y>q+1){//划分的第二段可进栈否?

                                     position highpart;

                                     highpart.x=q+1;

                                     highpart.y=poped.y;

                                     stack.push(highpart);

                            }

                   }

         }

}

(三)插入排序,递归算法

void insertSort(int *a,int n){//其中n代表待排序元素的个数

         if(n>1){//递归的边界条件

                   insertSort(a,n-1);//先递归调用一下

                   int x=a[n-1];        //最末一个元素备份

                   int i=n-2;

                   for(i=n-2;i>=0;i--){

                            if(a[i]>x)a[i+1]=a[i];

                            else break;//一定要这句,也许用while循环,条件为a[i]>x&&i>=0,更清晰

                   }

                   a[i+1]=x;

         }

}

非递归算法

void insertSort2(int *a,int n){

         for(int i=1;i<n;i++){

                   int x=a[i];

                   for(int j=i-1;(j>=0)&&a[j]>x;j--)

                            a[j+1]=a[j];

                   a[j+1]=x;

         }

}

(四)选择排序:每次从余下的数中,选择一个最小的放在当前位置,当前位置后移一位;初始时,余下数为n个,当前位置为0。

(五)冒泡排序:思想是每次一个大数沉底。具体C代码如下:

void bubbleSort(int *a,int n){//每次一个大数沉底

         for(int i=n-1;i>=0;i--)//每次比较时,要到达的下标

                   for(int j=0;j<=i;j++)//每次从0到i之间比较

                            if(a[j]>a[j+1]){

                                     int temp=a[j];

                                     a[j]=a[j+1];

                                     a[j+1]=temp;

                            }      

}

(六)归并排序

void merge(int *a,int *b,int l,int m,int r){//主要辅助函数一

         int i=l,j=m+1,k=l;//合并a[l...m]和a[m+1...r]到b[l...r]

         while((i<=m)&&(j<=r))

                   if(a[i]<=a[j])b[k++]=a[i++];

                   else b[k++]=a[j++];

                   if (i>m)for(int q=j;q<=r;q++)

                            b[k++]=a[q];

                   else for(int q=i;q<=m;q++)

                            b[k++]=a[q];

}

void copy(int *a,int left,int right){//递归辅助函数二

         while(left<=right){

                   a[left]=b[left];left++;

         }

}

//递归主算法

void mergeSort(int *a,int right){//b数组是辅助空间

         if(left<right){//至少2个元素

                   int i=(left+right)/2;

                   mergeSort(a,b,left,i);

                   mergeSort(a,i+1,right);

                   merge(a,i,right);//合并到数组b

                   copy(a,right);//复制回数组a

         }

}

//非递归主要辅助函数一

void mergePass(int *a,int s,int n){//合并大小为s的相邻2段子数组

         int i=0;

         while(i<=n-2*s){//先合并前若干对长度为s的相邻子数组

                   merge(a,i+s-1,i+2*s-1);

                   i+=2*s;

         }

         if(i+s<n)merge(a,n-1);//剩下的数少于2*s个,如是>s个情况

         else for(int j=i;j<=n-1;j++)b[j]=a[j];//剩下不足s个

}

//非递归主函数

void mergeSort2(int *a,int n){

         int *b=new int[n];

         int s=1;

         while(s<n){

                   mergePass(a,s,n);//合并数组到b

                   s+=s;

                   mergePass(b,a,n);//合并数组到a

                   s+=s;

         }

}

(七)计数排序。它假设输入的n个元素是介于0…k之间的整数,此处k为某个整数,当k=O(n)时,计数排序的运行进行为O(n),它需要k个用来存放计数的空间C[0…k]及n个存放结果的区间,伪代码如下:

countSort(A,B,k){//A为待排数组,B为结果数组,k的意义如前所述

         for(i=0…k)C[i]=0;//初始化计数器

         for(j=0…length(A))C[A[j]]=C[A[j]]+1;//计数

         for(i=1…k)C[i]=C[i]+C[i-1];//C[i]表示值所有小于或等于i的元素个数

         for(j=length(A) downto 1){

                   B[C[A[j]]]=A[j];//所有小于等于A[j]的元素有x个,便把A[j]放在位置x

                   C[A[j]]--;//然后把小于等于A[j]元素的元素数减1

}

}

(八)希尔排序,已验证:

void shellInsert(int *a,int n,int dk){//dk为步长

         for(int i=dk;i<n;i++){//一趟希尔排序,对步长分成的若干子序列插入排序

                   if(a[i]<a[i-dk]){

                            int x=a[i];

                            for(int j=i-dk;j>=0&&(x<a[j]);j-=dk)

                                     a[j+dk]=a[j];

                            a[j+dk]=x;

                   }

         }

}

void shellSort(int *a,int *dlta,int t){//dlta为步长数组,t为dlta长度

         for(int k=0;k<t;++k){//步长数组

                   shellInsert(a,n,dlta[k]);//步长数组生成方法不同,效率也不同常见的有

         }//...9,5,3,2,1  dlta[k]=2^(t=k)+1等等,总之,最后一个一定是1,而且

}//应该使增量序列中的值没有除1之外的公因子

(九)基数排序,伪代码

Radix-Sort(A,d){//最大有d位数

         for(i=1…d)

         对每一个数字,以第i位进行排序(调用任何一种稳定排序算法)

}

效率为O((n+k)*d)//其中n表示待排序数字数目,d表示位数,k表示进制。

基数排序对内存要求更高,无法原地排序,而且不能有效利用缓存,故对大数据量排序时,显然不如快排,但数据量不大时,谁更快一些,取决于底层机器实现特性。

11,KMP算法

int Index_KMP(char *S,char *T,int pos){//利用模式串T的next函数求T在S中S[pop]

//字符之后的位置的KMP算法,其中T非空,1<pos<S.length

         int i=pos,j=0;

         int sLength=strlen(S);

         int tLength=strlen(T); 

         while(i<sLength&&j<tLength){

                   if(j==0||S[i]==T[j]){++i;++j;}

                   else j=next[j];//如果是穷举法,则此处next[j]=j++;

}

if(j>=tLength)return i-tLength;//找到了串的位置,退出时应该j==tLength

else return 0;

}

void get_next(char *T,int *next){//这个函数是重点

         int i=0,j=-1;//j在前,i在后,next[i]存的是i之前的串的最长公共前后缀长度

         next[0]=-1;//初始时计算i=0,即考虑第0个字符,此时j应设为-1,next[i]=-1表i之前

//的串没有公共前后缀

         while(i<strlen(T)){

                   if(j==-1||T[i]==T[j]){++i;++j;next[i]=j;}//j先自增所以next[i]至少=0

                   else j=next[j];//j最小=-1,利用已求得的next部分

         }

}

12,寻找质数(打印小于x的所有质数)

常规方法:2为质数,从3至x,每个能被2整除的数不是质数,余下的可能质数中紧临2的为下一质数(这里是3),再从4至x,把被个能被3整除的数置为非质数……。最后留下的为质数,代码如下:

for(int i=3;i<=n;i+=2)a[i]=true;//去掉2的倍数,认为3以后的奇数是质数

for(i=2;i*i<=n;i++){//对已找出来的每个数,第一次时是2

         if(a[i]){//如果i是质数

         for(int j=i;j*i<=n;j++)a[j*i]=false;//为什么是j=i,而不是j=1呢?因为小于i*i的数

//一定是小于i的因子可供分解。

}

}

另一方法(摘自维基百科)是:根据质数分布特性,把x除以6得余数,有:

x=6n+0偶数;x=6n+1可能是质数;x=6n+2;偶数;x=6n+3能被3整除;x=6n+4偶数;x=6n+5可能是质数。因此,只需要考虑6n+1,6n+5及2,3,5三个数即可,搜索空间一下减少了2/3,运行时间是常规方法的一半,代码如下:

findPrime(){

int LIMIT=1000000

int nLIMIT=LIMIT-6

for(int i=7;i<=nLIMIT;i+=6){

     sieve[i]=true;//6n+1

     sieve[i+2]=false;//6n+3

     sieve[i+4]=true;

}

int p=5;//2,3不考虑,从5开始

while(int j=(p*p)<LIMIT){//从p*p开始,因为小于p*p的数一定有一因子小于p

     p2=p<<1;//每次加2p,因为p为奇数,加p之后是偶数,不用考虑,这表已知质数

     while(j<=LIMIT){//j表示p的倍数,每次增2p

              sieve[j]=false;//

              j+=p2;

}

do{p+=2;}while(sieve[p]==false)//找下一质数

}

}

13,八皇后问题(n后问题),代码已测试

对第i个棋子(肯定是在第i行)进行放置的时候,x[i]表示第i列是否已经放置棋子,而对于两个对角线,有如下规律:主对角线上的两个元素,其x,y坐标之差相等,副对角线上的元素,其x,y坐标之和相等,即x1-y1=x2-y2或x1+y1=x2+y2,这两个式子分别等价于x1-x2=y1-y2和x1-x2=y2-y1。因此,只要abs(x1-x2)==abs(y1-y2)就表示有对角线已经放置棋子了,此问题不可放。由此可得解n后问题的递归回溯算法如下:

void Queeen(int t,int *x){//当前在第t行尝试放棋子

         if(t>n) for(int i=1;i<=n;i++)cout<<"("<<i<<","<<x[i]<<") ";cout<<endl;//得到一种解

         else for(int i=1;i<=n;i++){//这个循环保证找到所有解,而不是一个解时退出

                   x[t]=i;//int *x用来记录结果i,x[i]分别表示第i行棋子放置在x[i]列

                   if(place(t))Backtrack(t+1);//如果放置合法,则继续遍历

         }

}

bool place(int k){

         for(int j=1;j<k;j++){

                   if((abs(k-j)==abs(x[j]-x[k]))||(x[j]==x[k]))return false;                 

         }

         return true;

}

用循环代替递归的回溯法代码如下:

void Queue(int *x){

         x[1]=0;//列的初始值在第一列之左

         int k=1;//行的初始值在第一行

         while(k>0){//当未回溯到根以上时,持续找解

                   x[k]+=1;//列++,这也是为什么初始列设为0的原因

                   while((x[k]<=n)&&!(place(k)))x[k]+=1;//找目前第一个能放棋子的位置(1)

                   if(x[k]<=n)//如果找到

                            if(k==n) for(int i=1;i<=n;i++)cout<<"("<<i<<","<<x[i]<<") ";cout<<endl;//输出解

                            else{k++;x[k]=0;}//试下一行,列号归为0

                   else k--;//当前方式在第k行找不到最优解了,回溯;注意x[k]不用置0,(1)处会接//着往后找可放置的位子。

}

}

初始时,调用Queue(1,x)即可。这里的代码省去了初始化等问题,x的下标从1开始。

14,大整数乘法

void reverse(char chr[],int l){//颠倒数组   

    int i;

    char temp;

    for(i=0;i <= l/2;i++){//首尾交换

        temp=chr[i];

        chr[i]=chr[l-i];

        chr[l-i]=temp;

    }

}

int multiple(char a[],char b[],int result[]){//函数返回值是乘积的长度 

    int la,lb,lresult;//a,b及result的位数-1

    int i,j;//循环控制变量

    int temp;   

    la=strlen(a)-1;//初始化最后一位lasta,lastb

    lb=strlen(b)-1;   

    reverse(a,la);//将a,b颠倒,下面从个位数开始算起

    reverse(b,lb);   

    for(i=0;i <= la;i++)

                   for(j=0;j <= lb;j++){

                            //精华所在,+=用于处理进位

                            result[i+j]+=(a[i]-48)*(b[j]-48);//-48是减去字符'0'的ASCII值

                            result[i+j+1]+=result[i+j]/10;//进位

                            result[i+j]%=10;//自己留的数

                   }

    lresult=i+j+1;//结果长度最多为i+j+1

    while(result[lresult] == 0) lresult--;//没有达到长度最多的情况,逆序,高位在后

    if(lresult < 0 ){result[0]=0;lresult=0;}//如果是0

    for(i=0;i <= lresult/2;i++){ //返回正序的结果

        temp=result[i];

        result[i]=result[lresult-i];

        result[lresult-i]=temp;

    }  

    return lresult;  

}

15,一台计算机,只能进行赋值,+1,固定次数的循环三种原子操作,只能操作0和正整数。请用伪代码写出四则运算的实现。

1)加法:add1(x){return x+1;}//+1为原子运算

        add(x,y){

                            for(i=1…y)x=add1(x);

                            return x;

}

2)乘法:mul(x,y){

         ret=0;

         for(i=1…y) ret=add(ret,x);

         return ret;

}

3)减法:sub1(x){     //只能操作0和正整数,则令0-1=0

         ret=0;         //不能直接用if(x==0)判断,因为if不是原子操作

         for(i=2…x)

                   ret=add1(x);

         return ret;

}

                   sub(x,y){             //因为0-1=0,因此x<y时,令x-y=0

                            for(i=1…y)x=sub1(x);

                            return x;

}

4)除法:div(x,y){     //令某数除以0仍为原数

                            quotient=0;         //保存除的结果

                            tmp=add1(x);      //先x增1,运算时,每一个x-y结果不为0时,除的结果增1

                            for(i=1…x)          //最多只可能循环x次,因为除去y=0的情况,每次至少减1

                                     tmp=sub(tmp,y);//如果y=0,则每次tmp都不为0,会加x次1得原数                                     quotient=add(quotient,sgn(tmp));//如果y!=0,则tmp到0之前quotient都会增

                            return quotient;

}

         sgn(x){       //在x=0时返回0,否则返回1

                   ret=0;

                   for(i=1…x){

         ret=1;

}

return ret;

}

16,memset函数实现。加速原理:32位机器一次传四个字节与传一个字节耗时差不多

#define cpu_ALIGN_MASK 0x03//用来判断所分内存地址是否对齐(4的倍数)
#define cpu_BYTE       4//机器字节数为4,表32位机器

 //整数长度一般是机器上的字长,已测试

void memset(void *paddr,unsigned int size,char value){
     char *pcaddr = 0;   //按字节复制时用到的指针
     unsigned int *piaddr = (unsigned int *)paddr;//按一个个整数复制时,用到的指针
     unsigned int iValue = 0;//iValue表示按一个个整数复制时的值

 int iValueTmp = (unsigned int)value;//iValueTmp表示一个字节中的值
     unsigned int iPtrNumber = (unsigned int )paddr;

     if( iPtrNumber & cpu_ALIGN_MASK ){//看地址是否对齐(4的倍数)
         pcaddr = ( char* )piaddr;
        while( size > 0 ){
          *pcaddr++ = value;
          -- size;
     }//while
   }//if

     iValue |= iValueTmp;//将iValueTmp赋给第一个字节,0|x,结果为x
#if cpu_BYTE > 1//采用条件编译
     iValue |= iValueTmp<<8;//将iValueTmp赋给第二个字节
#if cpu_BYTE > 2
     iValue |= iValueTmp<<16;//将iValueTmp赋给第三,第四个字节
     iValue |= iValueTmp<<24;
#if cpu_BYTE > 4
     iValue |= iValueTmp<<32;
     iValue |= iValueTmp<<40;
     iValue |= iValueTmp<<48;
     iValue |= iValueTmp<<56;
#endif
#endif
#endif

    while( size >= cpu_BYTE ){//之前判断过地址是4的倍数(对齐)
      *piaddr++ = iValue;//一个个整数赋值
        size -= cpu_BYTE;
     }
}//memset

17,全排列问题

递归方法:

perm(int a[],int k,int m){//产生a[k…m]之间所有的全排列,已验证

         if(k==m)输出a[0…m];

         else for(int i=k;i<=m;i++){

                   swap(a[i],a[k]);//大家轮流来做这个位子,大家都坐过了,也就代表都排过了

                   perm(a,k+1,m);

                   swap(a[i],a[k]);//回溯

}

}

非递归方法思路:第一次拿一个数,一种排法,第二个数有两种(在第一个数的左/右),第三个数有三种……,总共有n!种排法,编程实现伪码为:

for(i=1…n!){//n!种排列,一个i值可对应一种排列

         第一个数放1

         for(j=2…n){

                   if(i%j==0)j插到原队列尾    //每种排列的计算方法

                   else j插到第i%j个位置之前

                   i=i/j;

}

}

18,棋盘覆盖问题,分治法

void ChessBoard(int tr,int tc,int dr,int dc,int size){//tr,tc表示棋盘左上角方格的行列号;dr,dc

         if(size==1)return;//表示特殊方格的行列号,size表示棋盘大小

         int t=tile++;//L型骨牌编号,tile是全局变量,初始为1

         s=size/2;

         //处理左上

         if(dr<tr+s&&dc<tc+s){//如果特殊方格在左上角

                   ChessBoard(tr,tc,dr,dc,s);//递归处理左上的四分之一块

}else{//如果不在,则填充左上四分之一块中的最右下角,然后递归处理

         Board[tr+s-1][tc+s-1]=t;

         ChessBoard(tr,tr+s-1,tc+s-1,s);

}

….//其实三个四分之一类似处理

…打印出ChessBoard即可看到解!

}

19,生产者消费者问题;哲学家进餐问题;读者写者问题

生产者消费者伪代码:

Var mutex=1,empty=n,full=0//分别表示互斥信号量,可用空间及已生产产品数

var buffer[o…n-1];//存放产品的缓冲区

var in=0,out=0;//存放生产者放产品的指针及消费者取产品的指针,用队列的形式

producer:   while(true){

                   produce a item next;;

                   wait(empty);//P先看是否有空间存放,没有就一直挂起,等消费者signal的消息

                   wait(mutex);//实现对缓冲区的互斥访问

                   buffer[in]=nextp;

                   in=(in+1)%n;

                   signal(mutex);

                   signal(full);//进行V操作,通知消费者,也即full++

}

consumer:while(true){

                   wait(full);

                   wait(mutex);

                   nextc=buffer[out];

                   out=(out+1)%n;

                   signal(mutex);

signal(empty);

consumer the item in nextc;

}

哲学家进餐问题的解决方法为:方法一,奇数号先拿左边的筷子,偶数号先拿右边的筷子;方法二,两个筷子都可用才能拿

读者写者问题用伪码描述如下:

Var rmutex=1,wmutex=1//用来实现对读写变量的互斥访问

var Readcount=0;

Reader:while(true){

                   wait(rmutex);//对Readcount的互斥访问

                   if readcount=0 then wait(wmutex);//如果没有人读,则还需要对wmutex进行P操作

                   Readcount=Readcount+1;

                   signal(rmutex);

                   …..进行读操作…….

                   wait(rmutex);//对Readcount的互斥访问

                   if readcount=0 then signal(wmutex);//如果没有人读,指示别人可写了

                   Readcount=Readcount-1;

                   signal(rmutex);

}

Writer:while(true){

                   wait(wmutex);

                   perform write operation;

                   signal(wmutex);

}

20,来自于多米诺牌完美覆盖的组合数学知识。下面给出通解。

台阶问题:某楼梯有n级台阶,某人一步最多迈三级,问有多少种不同的方式上楼?引进递归思想,我们就可找到简单的方法:设上n级台阶的方法有f(n)种,某人第1步可迈一至三级。第1步迈一级,而后上n-1级,有f(n-1)种上法;第1步迈二级,而后上n-2级,有f(n-2)种上法;第1步迈三级,而后上n-3级,有f(n-3)种上法。从而得f(n)=f(n-1)+f(n-2)+f(n-3)且f(1)=1;f(2)=2,f(3)=4;同时规定f(0)=1。

更一般情况:一般台阶问题:某楼梯有n(n≥1)级台阶,某人一步最多迈m(n≥m≥1)级,有多少种不同的方案上楼。设上n级台阶的方案有f(n)种,则

f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(n-m) (n≥m),且有

f(0)=1;f(1)=1;f(2)=2;...;f(k)=f(0)+f(1)+f(2)+...+f(k-1);

22,Tribonaci数列,斐波那契数列

斐波那契数列,递归时,会重复计算,递推则不会,不过要一数组来存储结果。递归时也可以采用备忘录的方法避免重复计算。

另一方法是利用矩阵,先整理出如下公式:



由此公式递推有(Fn  Fn-1)=(Fn-1  Fn-2)*A=(Fn-2  Fn-3)*A^2=……=(F1  F0)*A^(n-1)

剩下的问题,就是求解矩阵A的方幂n。矩阵的幂,在幂n很大时,可采用如下方法进行加速,将乘的次数,从n减少到log2n,用二进制表示n:



举个例子:



由于以上分析,可得伪代码如下:

class Matrix;//假设我们已经有了实现乘法操作的矩阵类

Matrix MatrixPow(const Matrix& m,int n){//求解矩阵m的n次方

         Matrix result=Matrix::Identity;//赋初值为单位矩阵

         Matrix tmp=m;//tmp每次循环都会增长,依次表示A1,A2,A4,A8

         for(;n;n>>=1){// 每次右移一位,即依次判断每位二进制是否是1

                   if(n&1)result*=tmp;//如果最低位是1,

                   tmp*=tmp;

}

}

int Fibnacci(int n){

         Matrix an=MatrixPow(A,n-1);//调用上面的方法

         return F1*an(0,0)+F0*an(1,0);//an(0,0)表示an矩的元素(0,0)

}

Tribonaci数列求解方式类似,只是增加了一项。

23,快速寻找满足条件的两个数,即从数组中找出两个数,使其和等于指定值

方法,首先对数组排序,时间复杂度为O(nlgn);然后令i,j分别指向数组首尾,看a[i]+a[j]是否等于指定的值n,是则返回,否则,比较a[i]+a[j],如果大于n则j--,如果小于n则i++,循环结束条件为i>=j。

另一扩展的类似问题: 已经两个已经排好序的,且长度都为N的数组,找出两个数组合起来第N大的数,即找出它们的中间大数字,如:x数组: 1,7,9,10,30      y数组:3,8,11,12

中间大数为: 8 

解法为:先比较两个数组的中间元素,如果一个比另一个大,如x[mid]<y[mid],则y[mid+1...end]和x[0...mid-1]可排除掉,因为第N大数不可能在这些数中间,再对剩余的元素x[mid...end]和y[0...mid]调用相同的过程,即在它们之中寻找第N/2大的元素

24,字符串替换(王丙林整理)已测试

//用新子串newstr替换源字符串src中的oldstr子串
         // @return char* dest  返回新串的地址 

char *strreplace(char *dest,char *src,const char *oldstr,const char *newstr){

         if (dest==src)return dest;                //这类题的常规步骤

         char *needle;//方法是,初始时dest为src,每次循环用strstr从中找到oldstr的位置

char *temp;//然后把它之前的部分,newstr部分以及之后的部分连接起来放到temp里面

dest=src;    //循环末了把temp中复制为dest(用库函数strdup)

while(needle=strstr(dest,oldstr)){  //strstr函数返回串中找到的第一个子串的char*地址

         temp=(char *)malloc(strlen(dest)+strlen(newstr)-strlen(oldstr)+1);//三截共需内存长度

         strncpy(temp,dest,needle-dest);//第一截,strncpy把源串中的n个字符复制到目标串

         temp[needle-dest]=’/0’;//标识串的结束,从中间截断的没有带’/0’,所以要处理

         strcat(temp,newstr);//第二截,newstr自己带了’/0’

         strcat(temp,needle+strlen(oldstr));//第三截

         dest=strdup(temp);//strdup()会另辟一块内存,并不会释放temp的内存

         free(temp);//strstr函数

}

return dest;

}

25,要把cpp原文件中的注释去掉,存入到新文件中,要求写出完整代码

#include<fstream>//一定要有

#include<string>

using namespace std;

int main(int argc,char *argv[]){

         ifstream in("findPrime.cpp");

         ofstream out("findPrime2.cpp");

         string s;

         bool start=false;

         while(getline(in,s)){

                   if(!start){//如果没有开始多行注释,则找注释开始

                            int oneLinePos=s.find("//");

                            int mulLinePosStart=s.find("/*");

                            //两个注释都有时要看哪种注释开始得早?或者只有其中一种注释开始

                            if(((oneLinePos!=string::npos)&&(mulLinePosStart!=string::npos)&&

(oneLinePos<mulLinePosStart))||

((oneLinePos!=string::npos)&&(mulLinePosStart==string::npos))){

                                     s=s.substr(0,oneLinePos);//子串不包括oneLinePos元素

                            }else if(((oneLinePos!=string::npos)&&(mulLinePosStart!=string::npos)&&

(mulLinePosStart<oneLinePos))||

((oneLinePos==string::npos)&&(mulLinePosStart!=string::npos))){

                                     s=s.substr(0,mulLinePosStart);                                 

                                     start=true;

                            }                         

                            if(s.size()!=0)out<<s<<"/n";

                   }else{//已经开始了多行注释的情况下,找结尾

                            int mulLinePosEnd=s.find("*/");

                            if(mulLinePosEnd!=string::npos){//如果找到,则输出余下字符

                                     s=s.substr(mulLinePosEnd+2,s.size());

                                     if(s.size()!=0)out<<s<<"/n";//如果更智能化

                                     start=false;

                            }//未找到则没有输出,该行认为是注释掉了

                   }

         }

         return 0;

}

26,大数阶乘的估算公式

如求10的7次方阶乘的位数,此题其实是纯粹的数学问题。 由斯特林[striling]公式可得: 
lnN!=NlnN-N+0.5ln(2N*pi) ,而10的7次方阶乘的位数等于: log10(N!)取整后加1 ,
log10(N!)=lnN!/ln(10) ,C代码如下:

#include <stdlib.h>

#include <math.h>

#define N 10000000

#define PI 3.14159265

int main(int argc,char *argv){

         int len;

         len=ceil((N*log(N))-N+0.5log(2*N*PI)/log(10));

         printf(“%d”,len);// 结果是65657060

         return 0;

}

27,数的补码的求法:(1)正数的补码:与原码相同。例如,+9的补码是00001001。 

(2)负数的补码:符号位为1,其余位为该数绝对值的原码按位取反;然后整个数加1。 

例如,-7的补码:因为是负数,则符号位为“1”,整个为10000111;其余7位为-7的绝对值+7的原码0000111按位取反为1111000;再加1,所以-7的补码是11111001。

  已知一个数的补码,求原码的操作分两种情况: 

 (1)如果补码的符号位为“0”,表示是一个正数,所以补码就是该数的原码。 

 (2)如果补码的符号位为“1”,表示是一个负数,求原码的操作可以是:符号位为1,其余各位取反,然后再整个数加1。 例如,已知一个补码为11111001,则原码是10000111(-7):因为符号位为“1”,表示是一个负数,所以该位不变,仍为“1”;其余7位1111001取反后为0000110;再加1,所以是10000111。

28,二叉排序树中的查找和插入删除

bool SearchBST(BiTree T,int key,BiTree f,BiTree &p){//二叉排序树查找

         //在根T所指二叉排序树中找关键字为key的节点,找到则p指向该结果并返回true

         //否则p指向查找路径上访问的最后一个结点并返回false,f指向T的双亲,初始为NULL

         if(!T){p=f;return false;}

         else if(T->data==key){p=T;return true;}

         else if(key<T->data)return SearchBST(T->lchild,key,T,p);

         else return SearchBST(T->rchild,p);

}

bool InsertBST(BiTree &T,int e){//二叉排序树插入

         //当二叉排序树中不存在关键字e时插入e并返回true,否则返回false

         if(!SearchBST(T,NULL,p)){

                   s=(BiTree)malloc(sizeof(BiTNode));

                   s->data=e;s->lchild=s->rchild=NULL;

                   if(!p)T=s;//如果是空树

                   else if(e<p->data)p->lchild=s;//插入的位置一定是叶子

                   else p->rchild=s;

                   return true;

}else

return false;

}

bool DeleteBST(BiTree &T,int key){//二叉查找树中如存在关键字key则删除之,返回true

         if(!T)return false;//不存在关键字等于key的数据元素

         else{

                   if(key==t->data)return Delete(T);

                   else if(key<T->data)return DeleteBST(T->lchild,key);

                   else return DeleteBST(T->rchild,key);

}

}//DeleteBST

bool Delete(BiTree &p){//从二叉排序树中删除结点p,并重接它的左或右子树

         if(!p->rchild){//作了Delete(p)后删除了结点p,并p指向代替p的结点

                   q=p;p=p-> lchild;free(q);//右子树空则只需要重接它的左子树

}else if(!p->lchild){

         q=p;p=p-> rchild;free(q);

}else{

         q=p;s=p->lchild;//找前驱代替p,往左一步,然后一直往右

         while(s->rchild){q=s;s=s->rchild};//前驱一定是只有一个子树的!!!

         p->data=s->data;//把p的值用它前驱的值代替

         if(q!=p)q->rchild=s->lchild;//p的左孩子有右子树

         else q->lchild=s->lchild;//表示p往左一步之后,p的左孩子没有右子树

         free(s);

}

}

29,哈希表的查找与插入!(各种处理冲突的方法要理解)

int hashsize[]={997,…};//哈希表容量递增表,一个合适的素数列表

typedef struct{//哈希表结构体

         ElemType *elem;//存储元素的数组

         int count;//当前含有元素个数

         int sizeindex;//hashsize[sizeindex]为当前容量

}HashTable;

Status SearchHash(HashTable H,KeyType K,int &p,int &c){在H中查找关键码为K的元素

         p=Hash(K);//求得哈希地址,哈希地址一般即为数组元素下标

         while(H.elem[p].key!=NULLKEY&&!EQ(K,H.elem[p].key))//如果没有找到,但值得再找

                   collision(p,++c);//求得下一哈希地址,如何解决冲突,有许多方法,如再哈希

         if(EQ(K,H.elem[p].key))return SUCCESS;//上一行c表示冲突次数,初始为0

         else return UNSUCCESS;

}

Status InsertHash(HashTable &H,Elemtype e){ //查找不成功时,插入数据e到哈希表中 

         c=0;

         if(SearchHash(H,e.key,p,c))return DUPLICATE;//查找成功

         else if(c<MAXC){//如果冲突次数未达到最大

                   H.elem[p]=e;++H.count;return OK;//p值在SearchHash函数中已经定位好

}else{RecreateHashTable(H);return UNSUCCESS;}//冲突到上限,重建Hash表

}

30,B树查找过程的伪码:

int SearchBTree(BTree T,int K){//在T中找关键字K,返回结点或返回K应插入的位置

         p=T;q=NULL;found=FALSE;i=0;//p指向待查找结点,q指向p的双亲

         while(p&&!found){

                   i=Search(p,K);//在p->key[1…keynum]中查找

                   if(i>0&&p->key[i]==K)found=TRUE;

                   else{q=p;p=p->ptr[i];}

}      

if(found)return(p,1);//1表示在p结点的第i个key处找到了

else return(q,0);//0表示在q结点的第i个key处应该插入K

}

每个结点的形状如下所示:

(n,A0,K1,A1,K2,…,Kn,An)//Ai表示指针,也即p->ptr[i]中的ptr[i]。Ki表示关键字,即p->key[1..n]中的k[i],n表示该结点中有的关键字的个数。B树的插入删除情况,看《数据结构》,要能够画出图。

31,求二叉树中节点的最大距离(递归,思考非递归如何实现)

根据相距最远的两个节点一定是叶子结点这个规律,我们可以分两种情况:

如果经过根结点,则该两个结点U和V一定是左右子树中离根结点最远的结点;

如果不经过根结点,则它们一定属于左右子树之一,问题递归。

根据以上分析,可用分治法来解,代码如下:

struct NODE{

         NODE* pLeft;//左孩子

         NODE* pRight;//右孩子

         int nMaxleft;//左子树中的叶子到根最长距离

         int nMaxright;//右子树中的叶子到根最长距离

         char chValue;//本结点的值

};

int nMaxLen=0;

//寻找树中最长的两段距离

void FindMaxLen(NODE* pRoot){

         if(pRoot==NULL)return;//如果是叶子结点,返回

         if(pRoot->pLeft==NULL)pRoot->nMaxLeft=0;//左子树叶子到根最长距离为0

         if(pRoot->pRight==NULL)pRoot->nMaxRight=0;//右子树为空情况

         if(pRoot->pLeft!=NULL)FindMaxLen(pRoot->pLeft);//左右子树不空时分别递归

         if(pRoot->pRight!=NULL)FindMaxLen(pRoot-> pRight);// 递归时可能会改变nMaxLen

         if(pRoot->pLeft!=NULL){//计算左子树叶子到根最长距离

                   int nTempMax=0;

                   if(pRoot->pLeft->nMaxLeft> pRoot->pLeft->nMaxRight)

                            nTempMax= pRoot->pLeft->nMaxLeft;

                   else

                            nTempMax= pRoot->pLeft->nMaxRight;

                   pRoot->nMaxLeft=nTempMax+1;//取左子树的左右子树中较长者加1

}

if(pRoot-> pRight!=NULL){//计算右子树叶子到根最长距离

                   int nTempMax=0;

                   if(pRoot-> pRight ->nMaxLeft> pRoot-> pRight ->nMaxRight)

                            nTempMax= pRoot-> pRight ->nMaxLeft;

                   else

                            nTempMax= pRoot-> pRight ->nMaxRight;

                   pRoot->nMaxLeft=nTempMax+1;//取右子树左右子树中较长者加1

}

if(pRoot->nMaxLeft+pRoot->nMaxRight>nMaxLen)//更新最长距离nMaxLen

nMaxLen=(pRoot->nMaxLeft+pRoot->nMaxRight;

}

32,由前序中序或者中后序建二叉树(递归,思考非递归实现)

给定前序中序序列,要求重建二叉树。方法是:先扫前序的第一个字符,建根,然后以前序的第一个字符为分界,把中序划成两段,分别递归。代码如下:

#define TREELEN 6//为后序调用实现简单,直接用宏定义结点数目

struct NODE{

         NODE* pLeft;

         NODE* pRight;

         char chValue;

};

void ReBuild(char* pPreOrder,char* pInOrder,int nTreeLen,NODE** pRoot){//已经验证

         if(pPreOrder==NULL||pInOrder==NULL)return;//检查边界条件,前中序是否有一为空

         NODE* pTemp=new NODE;

         pTemp->chValue=*pPreOrder;

         pTemp->pLeft=NULL;

         pTemp->pRight=NULL;

         if(*pRoot==NULL)*pRoot=pTemp;//如果节点为空,把当前结点复制到根结点

         if(nTreeLen==1)return;//如果当前树长度为1,那么已经是最后一个结点了

         char* pOrgInOrder=pInOrder;//记录初始中序串起始位置

         char*pLeftEnd=pInOrder;//记录中序序列中树以左最末的位置

         int nTempLen=0;//临时记录左子树的长度

         while(*pPreOrder!=*pLeftEnd){

                   if(pPreOrder==NULL||pLeftEnd==NULL)return;

                   nTempLen++;

                   if(nTempLen>nTreeLen)break;

                   pLeftEnd++;

}      

int nLeftLen=0;

nLeftLen=(int)(pLeftEnd-pOrgInOrder);//计算左子树长度

int nRightLen=0;

nRightLen=nTreeLen-nLeftLen-1;//计算右子树长度

if(nLeftLen>0)ReBuild(pPreOrder+1,pInOrder,nLeftLen,&((*pRoot)->pLeft));

if(nRightLen>0)ReBuild(pPreOrder+nLeftLen+1,pInOrder+nLeftLen+1,nRightLen,&((*pRoot)->pRight));//想想为什么pRoot是NODE**类型?

}

33,分层遍历二叉树(用队列)

void PrintNodeByLevel(NODE* root){//已验证

         if(root==NULL)return;

         vector<NODE*>vec;

         vec.push_back(root);

         int cur=0;

         int last=1;

         while(cur<vec.size()){

                   last=vec.size();

                   while(cur<last){

                            cout<<vec[cur]->chValue<<” “;

                            if(vec[cur]->pLeft)vec.push_back(vec[cur]->pLeft);

                            if(vec[cur]->pRight)vec.push_back(vec[cur]->pRight);

                            cur++;

}

cout<<endl;

}

}

34,哈夫曼编码算法,已测试

void buildHuffmanTree(HTNode *HT,int n){//经过测试的,呵呵,不错

         for(int i=n;i<2*n-1;i++){//得到哈夫曼树

                   int s1,s2;

                   select(HT,i-1,s1,s2);//从HT的前i-1个元素中,选择parent为0的最小两个

                   HT[s1].parent=i;HT[s2].parent=i;

                   HT[i].lchild=s1;HT[i].rchild=s2;

                   HT[i].val=HT[s1].val+HT[s2].val;

         }

}

string* buildHCode(HTNode *HT,int n){//由哈夫曼构造哈夫曼编码

         string *HC=new string[n];

         char *cd=new char[n];

         for(int j=0;j<n-1;j++)cd[j]='*';//初始化

         cd[n-1]='/0';//字符串尾

         for(int i=0;i<n;i++){

                   int start=n-1;//从叶子开始往根走,对应编码从尾往前

                   int c,f;//c表示当前结点,f表示其父亲

                   for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){//当其父不是树根时退出

                            if(HT[f].lchild==c)cd[--start]='0';//如是其父的左孩子,置’0’

                            else cd[--start]='1';否则置1

                   }

                   for(j=0;j<n&&cd[j]=='*';j++);//去掉未满的编码内存

                   HC[i]=(char*)&cd[j];

         }

         delete cd;

         return HC;

}

35,打十枪中90环的各种可能性打印

解答:方法一,用10层的循环;

方法二,用递归。用一个全局的数组store[10]存储每次的环数,一个全局整数sum记录可能性的种数。代码如下://代码已验证

#include <iostream>

using namespace std;

int sum=0;

int store[10];

void output(){

         sum++;

         for(int i=0;i<10;i++)cout<<store[i]<<’ ’ ;cout<<endl;

}

void compute(int score,int num){//score表示剩余的环数,num表剩余可打的枪数,初值是9

         if(score<0||score>(num+1)*10)return;

         if(num==0){store[num]=score;;output();return;}

         for(int i=0;i<=10;i++){

                   store[num]=i;

                   compute(score-i,num-1);

}

}

36,求一个串的各所有子集输出(组合)

算法四步:

第一步,从首字符到尾字符循环;

第二步,循环到的当前字符加到out串尾,输出当前的out串;

第三步,如果循环到的字符i后面还有字符,递归,后面的字符为起始字符,重复二三步;

第四步,如果循环到的字符i后面没有其它字符了,退出循环。

void combine(char in[],char out[],int length,int rec int start){ //代码已验证

         //in[],out[]为输入输出串,length为输入串的长度,rec为当前递归时,out串尾位置

         //start为本次递归时in[]的循环开始位置

         int i;//start表示此次递归,只考虑in[start]后的元素

         for(i=start;i<length;i++){

                   out[rec]=in[i];//选择的起点为i时,输出,然后递归,完事后起点后移

                   out[rec+1]=’/0’;//标记串尾,为输出用。起点后移时rec并未移,因此

                   printf(“%s”,out);

                   if(i<length-1)combine(in,out,length,rec+1,i+1);

}

}

37,输m,n两个数,从数列1,2,3,……中随意选几个数,使其和为m求所有的可能,并输出之(0-1背包类似,重量(可取的数的个数)不限,只要求价值总和等于m)

void calFun(int m,int n){ //代码已验证

         if(m<1||n<1||(n==1&&m!=1))return;//递归退出条件

         if(m==n){//如果找到了一个解(n本身即为m)

                   pOut[n]=1;//pOut[i]=1表示整数i选,为0表不选,初始全为0

for(int i=1;i<=nVal;i++)

         if(pOut[i])cout<<i<<”,”;

cout<<endl;

pOut[n]=0;//回溯,因要求所有可能,而pOut[]为全局变量,所以不能影响后续求解

}

calFun(m,n-1);//不取n时进行递归,因为初始pOut[n]=0,所以不需要管

pOut[n]=1;//取n,如果m==n,这里递归也会在下一轮时因为m<1返回,所以没关系

calFun(m-n,n-1);//进行递归

pOut[n]=0;//回溯,防止影响后续求解

}

38,汉诺塔的非递归,递归实现

递归实现,不需要多说:
void Hannoi(int n,char a,char b,char c)
{
    if(n==1)
             Move(1,c);
    else
    {
          Hannoi(n-1,c,b);
            Move(n,c);
            Hannoi(n-1,c);
    }
}
非递归实现的方法思想:当盘子的个数为n时,移动的次数应等于2^n - 1(有兴趣的可以自己证明试试看)。后来一位美国学者发现一种出人意料的简单方法,只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型,把所 有的圆盘按从大到小的顺序放在柱子A上,根据圆盘的数量确定柱子的排放顺序:若n为偶数,按顺时针方向依次摆放 A B C;若n为奇数,按顺时针方向依次摆放 A C B。
(1)按顺时针方向把圆盘1从现在的柱子移动到下一根柱子,即当n为偶数时,若圆盘1在柱子A,则把它移动到B;若圆盘1在柱子B,则把它移动到C;若圆盘1在柱子C,则把它移动到A。
(2)接着,把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上,当两根柱子都非空时,移动较小的圆盘。这一步没有明确规定移动哪个圆盘,你可能以为会有多种可能性,其实不然,可实施的行动是唯一的。
(3)反复进行(1)(2)操作,最后就能按规定完成汉诺塔的移动。代码如下:
struct st{//用来表示每根柱子的信息,其实就是栈

      int s[MAX]; //柱子上的圆盘存储情况

      int top; //栈顶,用来最上面的圆盘

      char name; //柱子的名字,可以是A,B,C中的一个

      int Top(){//取栈顶元素     

            return s[top];

      }

      int Pop(){//出栈     

            return s[top--];

      }

      void Push(int x){//入栈     

            s[++top] = x;

      }

};

void Creat(st ta[],int n){

      ta[0].name = 'A';

      ta[0].top = n-1;

     //把所有的圆盘按从大到小的顺序放在柱子A上

      for (int i=0; i<n; i++)

            ta[0].s[i] = n - i;

      //柱子B,C上开始没有没有圆盘

      ta[1].top = ta[2].top = 0;

      for (i=0; i<n; i++)

            ta[1].s[i] = ta[2].s[i] = 0;

     //若n为偶数,按顺时针方向依次摆放 A B C

      if (n%2 == 0){

            ta[1].name = 'B';

            ta[2].name = 'C';

      }else{  //若n为奇数,按顺时针方向依次摆放 A C B

            ta[1].name = 'C';

            ta[2].name = 'B';

      }

}

void Hannuota(st ta[],long max){

          int k = 0; //累计移动的次数

          int i = 0;

          int ch;

          while (k < max){

                   //按顺时针方向把圆盘1从现在的柱子移动到下一根柱子

            ch = ta[i%3].Pop();

            ta[(i+1)%3].Push(ch);

            cout << ++k << ": " <<

                             "Move disk " << ch << " from " << ta[i%3].name <<

                             " to " << ta[(i+1)%3].name << endl;

            i++;

            //把另外两根柱子上可以移动的圆盘移动到新的柱子上

            if (k < max){    

                            //把非空柱子上的圆盘移动到空柱子上,当两根柱子都空时,移动较小的圆盘

                            if (ta[(i+1)%3].Top() == 0 ||

                                     ta[(i-1)%3].Top() > 0 &&

                                     ta[(i+1)%3].Top() > ta[(i-1)%3].Top()){

                                               ch =  ta[(i-1)%3].Pop();

                                               ta[(i+1)%3].Push(ch);

                                               cout << ++k << ": " << "Move disk "

                                                         << ch << " from " << ta[(i-1)%3].name

                                                         << " to " << ta[(i+1)%3].name << endl;

                            }else {

                                        ch =  ta[(i+1)%3].Pop();

                                        ta[(i-1)%3].Push(ch);

                                        cout << ++k << ": " << "Move disk "

                                                        << ch << " from " << ta[(i+1)%3].name

                                                        << " to " << ta[(i-1)%3].name << endl;

                            }//else

                   }//if

         }//while

}

int main(void){

      int n;

      cin >> n; //输入圆盘的个数

      st ta[3]; //三根柱子的信息用结构数组存储

      Creat(ta,n); //给结构数组设置初值

      long max = Pow(2,n) - 1;//动的次数应等于2^n - 1

      Hannuota(ta,max);//移动汉诺塔的主要函数

      return 0;

}

39,谜宫求解

typedef struct{

         int ord;//通道块在路径上的序号

         PopType seat;//通道在谜宫中的坐标位置

         int di;//从此通道块走向下一块通道块的“方向”

}SElemType;

bool MazePath(MazeType maze,PosType start,PosType end){//找谜宫maze从start到end的路

         InitStack(S);curpos=start;//设定当前位置为start

         curstep=1;//探索的第一步

         do{

                   if(Pass(curpos)){//如果当前位置是可通过的

                            FootPrint(curpos)//留下路迹,打印一下遍历过程,这行可不要

                            e= SElemType (curstep,curpos,1);

                            push(S,e);//加入到路径栈中

                            if(curpos==end)return true;//到达出口

                            curpos=NextPos(curpos,1);//下一位置是当前位置的东邻

                            curstep++;

}else{//如果当前位置是不可通过的,看栈顶元素再作决定

                   if(!StackEmpty(S)){//如果栈上有元素

                            pop(s,e);

                            while(e.di==4&&! StackEmpty(S)) pop(s,e);//直到栈顶元素有下一方向为止

                            if(e.di<4){//如果栈中弹出的元素有方向可走

                                     e.di++;push(S,e);//标记为探索下一个方面

                                     curpos=NextPos(e.seat,e.di);//将该方向上的相邻块置为当前块

}

}

}while(!StackEmpty(S));

}return false;

}

40,后缀表达式求值

OperandType EvaluateExpression(){

         InitStack(OPTR);Push(OPTR,’#’);//初始化符号栈

         InitStack(OPND);c=getchar();//初始化操作数栈

         while(c!=’#’||GetTop(OPTR)!=’#’){如果得到的不是结束符

                   if(!In(c,OP)){Push(OPND,c);c=getchar();}//如果不是操作符,则直接进栈

                   else

                            switch(Precede(GetTop(OPTR),c)){//如是操作符则比较它与栈顶符的优先级

                                     case ‘<’:Push(OPTR,c);c=getchar();break;//栈顶元素优先级低

                                     case ‘=’:Pop(OPTR,x);c=getchar();break;//如果是括号,则消去一对

                                     case ‘>’:Pop(OPTR,theta);//如果优先级大则原来的部分先运行

                                                  Pop(OPND,Operate(a,theta,b)); //注意此处没有getchar();

                                                  break;//所以会继续判断所得符号与栈顶元素的优先级

}

}//while

return GetTop(OPND);//返回最后的操作数栈顶元素,正确时应该栈只有一个元素

}

41,十进制数N转为d进制数,一个简单的实现方法基于如下原理:

N=(N/d)*d+N%d,代码借助栈实现如下:

void conversion(){

         stack<int> s;

         int N;

         cin>>N;

         while(N){

                   s.push(N%8);

                   N=N/8;

}      

while(!s.empty()){

         cout<<s.top();

         s.pop();

}

}

42,int maxPrimeSub(int n);  n<10,000,000。求n的所有子串中的最大的质数。如 n=5617,则为617。

int maxPrimeSub(int n){// 明显应该从最长的串开始判断起!先是n,然后减去首尾递归

         if(isPrime(n))return n;

         else{

                   int higher=n/10;

                   int lower;

                   int highest=1;

                   while((lower=n/highest)!=0)

                            highest*=10;

                   lower=n-n/(highest/10)*(highest/10);

                   lower=maxPrimeSub(lower);

                   higher=maxPrimeSub(higher);

                   return lower>higher?lower:higher;

         }

}

bool isPrime(int n){

         if(n%2==0&&n>2)return false;//大于2的偶数

         else for(int i=3;i*i<=n;i+=2){

                   if(n%i==0)return false;

         }

         return true;

}

另:EMC笔试题,求一个非负整型数组非邻接子序列的最大和,要求O(N)

一遍扫瞄,记住前两个位置的解f(i)=max(a[i]+f(i-2),f(i-1))

43,一棵树,每个节点有三个域,data域,child域指向孩子节点,next域指向右边最近的兄弟节点。 写程序,将所有的堂兄弟节点都      连起来。(比如一个节点A及其右兄弟节点B,A的子节点有CDEF,B的子节点有GH,初始状态是没有F到G的指针的,现在让你把这样的空缺都连起来)。刘光远写出递归的形式,让改成非递归的。用层序遍历的队列方式。

44, 有一个矩形区域,分成N*M个格子,求从最左上角的格子走到最右下角的格子的最短时间,不能斜着走,只能竖着或者横着走,而且格子与格子之间花费的时间是不同的 。同样,不让用递归。

三种方法:一,递归,右下角的一定是通过前两个格子中最小路径得到的;二,是用动态规划的填表法;三,这其实是一个求单源最短路径的问题,因此可用dijstra最短路径递增的贪心算法,用图表示写代码可能会难一点,动态规划的填表法更易写代码。

45,匹配字符串,模式串为正则串,待匹配串为一长字符串,如果待匹配串中包含模式串,则返回1,否则返回0; 正则串包含字母,'.' 匹配任意字符,'*"匹配0或者任意多个前一个字符。我的非递归解法:

int next(const char *t,int pos,char anych){

         //在串t之后找第一个不等于anych的位置距pos的长度

         for(int i=pos;i<strlen(t);i++)

                   if(t[i]!=anych)

                            break;

         return i-pos;

}

int match(const char *t,const char *p){  //p为模式串,带有正则表达式符号,t为待匹配字符串

         //匹配成功返回位置,否则返回-1

         if(t==NULL||p==NULL)return -1;//对空串的处理,当然也可以其它处理

         while(*p==’*’)p++;//之前必须增加对p中若第一个是*号的跳过处理

         for(int i=0;i<strlen(t);i++){

                   int oldi=i;

                   char anych;

                   for(int j=0;j<strlen(p);j++){

                            if(t[i]==p[j]){i++;}//如果是普通字符相等

                            else if(p[j]=='.'){anych=t[i];i++;}//如果是任意字符跳一步

                            else if(p[j]=='*'&&p[j-1]=='.'){i+=next(t,anych);}//如果是*

                            else if(p[j]=='*'&&p[j-1]!='.'){i+=next(t,t[i-1]);}//则跳过若干字符

                            else break;

                   }                

                   if(j==strlen(p))return oldi;

                   i=oldi;

         }

         return -1;

}

int main(int argc,char *argv[]){

         cout<<match("fdasfldjaklfjaf","j*.f")<<endl;

         cout<<match("","")<<endl;

         cout<<match("ababbccddeefghijfg","ab.c*d..e*f")<<endl;

         cout<<match("ababcddeefgh","ab.c*d..e.*f")<<endl;

         cout<<match("sccas",".*c*")<<endl;

         cout<<match("aac341bb",".c.*...")<<endl;

         cout<<match("dfdcc234ad",".*c*...*")<<endl;

         return 0;

}

不难写成递归解法,把里面一个for循环写成递归的形式,就是对于t的每一个后缀串,看是否某个串的前缀能完全匹配p,循环到第一个这样的后缀时,返回此后缀首下标;递归中判断当前字符,以决定跳若干步之后再递归调用。为保留next函数中可访问p[i-1]的内容,可在递归时,把p[i-1]的地址作为参数。

46,两个相同长度的整型数组A、B,长度为n。现从两个数组中,各抽出S个数,形成两个新的数组C、D。实现一个算法,保证数组CD的内积最大,并分析时间和空间复杂度。

题目其实就是要求在两个数组中找出积最大的前S对数:

         1. 对两个数组按降序排列,

         2. 设置两对指针,分别指向两个数组的首尾元素,

         3. 计算首尾指针对指向元素的积,比较两个积的大小,取乘积较大的两个元素,

         4. 指向乘积较大的元素对的指针向前移动(或往回移动,对于尾指针对),元素对计数器加1

         5. 重复1-4,直到找到S对元素。

         这是基于在给定数组中,对于所有正数,两个最大正数的乘积必定是最大,对于所有负数,两个最小负数的乘积必定是最大,但是它们哪个更大则不确定;至于时间复杂度主要看排序算法

47,一个网页,在每天记录一个访问量,然后给你一个时间区间,找出这个时间区间内访问量最多的那一天。可能经常做这个查询操作,而且区间大小是随意的。请问如果设计 以保证高性能。(欧阳刘彬说对时间做B+索引)。我想到的一个方法是:RMQ(Range Minimum/Maximum Query)问题是求区间最值问题。你当然可以写个O(n)的,但是万一要询问最值1000000遍,估计你就要挂了。这时候你可以放心地写一个线段树(前提是不写错)O(logn)的复杂度应该不会挂。但是,这里有更牛的算法,就是ST算法,它可以做到O(nlogn)的预处理,O(1)地回答每个询问。
       来看一下ST算法是怎么实现的(以最大值为例):       
       首先是预处理,用一个DP解决。设a[i]是要求区间最值的数列,f[i,j]表示从第i个数起连续2^j个数中的最大值。例如数列3 2 4 5 6 8 1 2 9 7,f[1,0]表示第1个数起,长度为2^0=1的最大值,其实就是3这个数。f[1,2]=5,f[1,3]=8,f[2,0]=2,f[2,1]=4……从这里可以看出f[i,0]其实就等于a[i]。这样,Dp的状态、初值都已经有了,剩下的就是状态转移方程。我们把f[i,j]平均分成两段(因为f[i,j]一定是偶数个数字),从i到i+2^(j-1)-1为一段,i+2^(j-1)到i+2^j-1为一段(长度都为2^(j-1))。用上例说明,当i=1,j=3时就是3,4,5 和 6,1,2这两段。f[i,j]就是这两段的最大值中的最大值。于是我们得到了动规方程F[i,j]=max(F[i,j-1],F[i+2^(j-i),j-1])。

接下来是得出最值,也许你想不到计算出f[i,j]有什么用处,一般毛想想计算max还是要O(logn),甚至O(n)。但有一个很好的办法,做到了O(1)。还是分开来。如在上例中我们要求区间[2,8]的最大值,就要把它分成[2,5]和[5,8]两个区间,因为这两个区间的最大值我们可以直接由f[2,2]和f[5,2]得到。扩展到一般情况,就是把区间[l,r]分成两个长度为2^n的区间(保证有f[i,j]对应)。直接给出表达式:

k:=ln((r-l+1)/ln(2));               ans:=max(F[l,k],F[r-2^k+1,k]);

这样就计算了从i开始,长度为2^t次的区间和从r-2^i+1开始长度为2^t的区间的最大值(表达式比较烦琐,细节问题如加1减1需要仔细考虑

48,有一个整数n,将n分解成若干个整数之和,问如何分解能使这些数的乘积最大,输出这个乘积m。例如:n=12

(1)分解为1+1+1+…+1,12个1,m=1*1*1……*1=1

(2)分解为2+2+…+2,6个2, m=64

(3)分解为3+3+3+3,4个3, m=81

(4)分解为4+4+4,3个4, m=64

。。。。。。。。。。。。。。。

显然,3最好。

解答: 假设输入为N,可以分解成为K个相同的数R以及一个余数W的集合。

 N = K*R + W;

 那么问题转化为求:Val = R^K * W的极值问题,条件是N=K*R+W。

为使问题简化,先不考虑W,之后再作讨论。于是问题转化为:

条件为N1=K*R时,求Val=R^K的极值(心中应该记住,终极任务是求R,因此K可以试着换成N1/R表示,也即,在Val中,只把R当成变量)。

Val= R^K; 两边取对数,有

ln(Val) = (N1/R)ln(R) ,令F(R) = (N1/R)ln(R),对这个式子取导数利用求导公式(u/v)'=(u'v-uv')/v^2,得到下式 :

f(R) = N1*(1-lnR)/(R^2) ,当这个f(R) 为零的时候,F(R)取到极值 。

因此,当R = e 的时候,取到极值(e= 2.7*****),因此取到R =3

现考虑余数情况,因除数为3,余数只有两种情况,1或2,当为1时,显示应该让其中一个数为4,而当余数为2时,显示应该把2提出来,乘以其余分解得到的3。因为2*3>2+3

49,数据结构134页中序遍历线索二叉树,及二叉树的中序线索化!

bool InOrderTraverse_Thr(BiThrTree T){// 中序遍历线索二叉树

         p=T->lchild;//T指向头结点,p指向根结点

         while(p!=T){

                   while(p->LTag==’LINK’)p->plchild;//中序的第一个结点,第一个没有左子树的结点

if(!visit(p))return false;//访问自己

while(p->RTag==’Thread’&&p->rchild!=T){//若右子树无则用线索访问

         p=p->rchild;visite(p);

}

p=p->rchild;//至某个有右子树的结点后,移到右子树上,继续回到第一步循环

return true;

}

}

bool InOrderThreading(BiThrTree &Thrt,BiThrTree T){

         //中序遍历二叉树T并完成中序线索化,Thrt指向线索化后的头结点

         if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);

         Thrt->LTag=”Link”;Thrt->RTag=”Thread”;//左孩子指向根

         Thrt->rchild=Thrt;//右孩子指针对性先回指,

         if(!T)Thrt->lchild=Thrt;//如果树空,则左孩子指针也回指

         else{

                   Thrt->lchild=T;pre=Thrt;//pre指向前驱

                   InThreading(T);//中序遍历进行线索化

                   pre->rchild=Thrt;pre->RTag=Thread;//pre指向最后一结点,最后一个结点线索化

                   Thrt->rchild=pre;//Thrt与末结点互指

}return true;

}

void InThreading(BiThrTree p){

         if(p){

                   InThreading(p->lchild);//左子树线索化

                   if(!p->lchild){p->LTag=Thread;p->lchild=pre;}//前驱线索化

                   if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}//后继线索化

                   pre=p;//切换前驱

                   InThreading(p->rchild);//右子树线索化

}

}

50,电话号码对应英语单词

number[i]存放电话电码的第i个数字;answer[i]用来存放这个电话在按键中的第几个字母;c[10][10]={“”,””,”ABC”,”DEF”,”GHI”,”JKL”,”MNO”,”PQRS”,”TUV”,”WXYZ”};

int total[10]={0,4};

如果电话号码第一位数字是4,answer[0]是0,c[number[0]][answer[0]]=G;

于是遍历各种可能的字母串的代码如下:

while(true){ //代码已验证

         //n为电话号码长度,初始化answer[n]数组各元素均为0

                   for(int i=0;i<n;i++)cout<<ca[number[i]][answer[i]];//先输出一种可能

                   cout<<endl;

                   int k=n-1;//从最后一位电话号码的各个可能answer[i]开始遍历起

                   while(k>=0){

                            if(answer[k]<total[number[k]]-1){

                                     answer[k]++;

                                     break;//把第k的号码的可能对应的字符换一下,继续输出输出后k=n-1

                            }else{

answer[k]=0;k--;//把answer[k]置0,然后,开始考虑前一个电话号码,注//意此处无break;

                            }

                   }

                   if(k<0)break;

         }

递归算法也许更好理解:

void RecursiveSearch(int *number,int *answer,int index,int n){//已经读取到了number[index]

         if(index==n){//下标最大为n-1,所以为n时表找到一个解,直接输出,并且返回

                   for(int i=0;i<n;i++)printf(“%c”,c[number[i]][answer[i]]);

                   printf(“/n”);

                   return;

         }

         for(answer[index]=0;answer[index]<total[number[i]];answer[index]++){

                   RecursiveSearch(number,answer,index+1,n);//考虑当前字符各种情况,然后递归

                   //注意用answer[n]数组来保存递归时各种分支的选择,传给叶子

}

}

51,编程之美:不要被阶乘吓倒

阶乘(Fctorial)N!。问题为:1),给定一个整数N,那么N!末尾有多少个零呢?例如N=10,N!=3628800,答案为2;2),求N!中二进制表示中最低位1的位置

解答:(1)规律是,每出现一个能被5整除的数,便会往末尾贡献一个0,因为5之前肯定出现了2,4等数字,相乘之后一定是10的倍数,每出现一个能被5^2整除的数贡献两个0……。因此,表示为公式是:Z=[N/5]+[N/5^2]+[N/5^3]+……

[N/5]表示小于N的数中,能被5整除的数的个数,[N/5^2] 表示小于N的数中,能被5^2整除的数的个数……。

代码求解零的个数如下:

ret=0;

while(N){

         ret+=N/5;//N/5表示小于N的数中,5的倍数有多少个

         N/=5;//N/=5之后第二轮循环计算的是小于N的数中5^2的倍数

}

解答:(2)问题与(1)一样,只是数制变为2进制,代码如下:

int lowerstOne(int N){

         int Ret=0;

         while(N){

                   N>>=1;//顺序跟上面不一样,上面也可以写成这样,结果是一样的

                   Ret+=N;

}

return Ret;

}

52,编程之美:1的数目(十进制里面,分个位数,十位数,百位数等一个个分析,得出规律),第二问记住答案!

问题是:(1),写一个函数f(N),返回1到N之间,出现的“1”的个数,比如f(12)=5;

(2)在32位整数范围内,满足条件”f(N=N)”的最大的N是多少?

解答:(1)分析如下,假设N=abcde,如现在需要计算百位数上出现1的次数,分三种情况:

如果百位数上为0,则可知道百位数上可能出现1的次数由更高位决定,比如12013,百位数上出现1的情况可能是100—199,1100—1199,2100—2199,……共1200个。也就是由比百分位高的部分的数字12所决定,并且等于12*100(百位数代表的值);如果百位数上为1,则可知百位上出现1的情况不仅包括刚才的,还包括百位数为1时的情况,比如12113比12013多了12100—12113这14个1,这是受低位决定的,等于低位数字的值+1(13+1)。

如果百位上的数字大于1(即为2—9),则百位上可能出现1的情况也只由高位数字决定,为(高位数字+1)*100。由于以上分析,代码如下:

long Sum1s(ulong n){

         ulong iCount=0;//1的个数计数器

         ulong iFactor=1;//iFactor每次循环按10,100,1000等递增

         ulong iLowerNum=0;//低位数字,即从当前位往右的所有数字之值

         ulong iCurrNum=0;//当前位

         ulong iHigerNum=0;//高位数字,即从当前位往左的所有数字之值

         while(n/iFactor!=0){//n大于iFactor

                   iLowerNum=n-(n/iFactor)*iFactor;

                   iCirrNum=(n/iFactor)%10;

                   iHigerNum=n/(iFactor*10);

                   switch(iCurrNum){

                            case 0:

                                     iCount+=iHigerNum*iFactor;break;

case 1:

                                     iCount+=iHigerNum*iFactor+iLowerNum+1;break;

                            default:

                                     iCount+=(iHigerNum+1)*iFactor;break;

}

iFactor*=10;//每次循环改变当前位数

}

return iCount;

}

53,编程之美:子数组中N-1项的最大乘积(扫瞄一遍,记住符号,最小负数,0的个数等,分析符号即可得解)

54,判断链表相交的几种方法:尾结点是否相同;结点的地址计数;一个尾链到另一个首,看是否会出现环;

55,将中缀表达式转换为逆波兰式,方法:

1)   构造一运算符栈,此栈中运算符遵循越往栈顶,优先级越高的原则。

2)   中缀表达式首尾为’#’字符,优先级最低,各符号的优先级关系必须有个优先级表。

3)   从左到右分析中缀串,如遇数字,则输出;如遇运算符,则比较优先关系,:

如果该运算符优先级高于栈顶元素则入栈,否则将栈顶元素弹出并输出,直至栈顶元素优先级低于扫到的运算符,再将扫到的运算符进栈。

4)   重复3)直至串尾,最后连续将栈退空。

56,整数分割问题。将一个正整数表示为一系列整数之和,如3=3,3=1+2,3=1+1+1有3种表示法,4=4,4=3+1,4=2+1+1,4=2+2,4=1+1+1+1共有5种表示法。

6有:        6

                   5+1

                   4+2,4+1+1

                   3+3,3+2+1,3+1+1+1

                   2+2+2,2+2+1+1,2+1+1+1+1+1

                   1+1+1+1+1+1共11种表示方法。

解答:用q(n,m)表示找出n划分为不大于m的整数的划分种数,如:q(6,4)=9

递归式有:

1           m=1或n=1

q(n,n)                  n<m

q(n,m)=      1+q(n,n-1)           n=m

                   q(n,m-1)+q(n-m,m)  n>m>1

57,归并排序求逆序对思想:归并排序的同时,记录逆序对的数目,每次将某两相邻字段s1和s2进行插入归并时,若所选最小元素来自于s2的第j个元素(记作s2j)时,逆序对数目Total+=s1.length-i(其中i为归并时s1中当前的下标),因为s1中i之后的元素也必与s2中的j元素是逆序对(比s2j大)。

58,1,0序列生成(有道难题)一个二进制序列由下面的伪代码生成:
String A = "0"
While (A的长度小于等于n)
 创建一个和A一样长度的字符串B
 For i=0,...length(A)-1
  If (i 是完全平方数)
   B[i] = 1-A[i]
  Else
   B[i] = A[i]
 令A = A + B (即将B拼接在A后面)
End While
Return A
请注意,在上面的伪代码中,A[i]和B[i]分别表示字符串A和B中下标为 i 的字符(下标编号从0开始)。对“完全平方数”的定义是,对于整数 i,存在整数 j,使得 i = j * j,则称 i 为完全平方数。

下面具体说明序列生成的过程:如果n=7,则在每一轮迭代中,A的取值依次为:0,01,0110,01101010,所以最终产生的二进制序列就是0,0
请返回上述序列中下标为n的数字(该序列的下标从0开始)

n=0 输出0
n=1 输出1
如果n不是2的幂时,它会夹在两个2的幂中间,设为k<n<m,那么n就是由位于(n-k)的字符变化而来,所以可以先得到(n-k),再取n。

public int getValue(int n){   
  if(n==0)  return 0;
  else if(n==1)  return 1;
  else{
                  long h = 1;
                   while(h < n) h=h<<1;

int m = (int)(n-(h>>1));   
if(isSquare(m))    return 1-getValue(m);
 else   return getValue(m);

}

}

 

以下部分主要为动态规划:

 

59,矩阵连乘问题

此类问题属于动态规划法解决范围。动态规划法能解决的问题,基本上都可以用递归方法解决。使用动态规划法的好处在于,动态规划法是自底向上计算,在计算过程中保存子问题的解,避免了重复计算,直接的递归调用则会导致重复计算,浪费时间。因此,动态规划法的两个重要特点是:最优子结构的递归特性和重叠子问题。递归方法解决时,可以采用备忘录的方法,同样达到动态规划的目的。

动态规划法的另一个重要特征是“选择”,每一步都是作一次选择,在前一次已经计算过子问题的最优选择的基础上,当前选择如何得到(可能通过一次循环来尝试各个值),以及如何将这一选择描述成问题的解。

根据这些问题的特点可知。求解动态规划法类型的问题,第一步就是抽象成数学表示并列出递归式,有了递归式,便可写出伪代码。

矩阵连乘问题抽象成数学问题:

第一步,使用一个数学式子来表示最优解。令m[i][j]表示矩阵A[i…j]连乘时,所需要的最小相乘次数,p[n+1]存储的是每个矩阵的行数及最后一个矩阵的列数。

第二步,由第一步可得递归式为:



第三步,写出(伪)代码:

void MatrixChain(int *p,int **m,int **s){//s用来保存m[i][j]的划分点

         for(int i=1;i<=n;i++)m[i][i]=0;//初始化边界条件

         for(int r=2;r<=n;r++){//链长从2到n时,依次考虑,即自底向上

                   for(int i=1;i<=n-r+1;i++){//i为每个链首,最后一个链首是n-r+1

                            int j=i+r-1;//j为链尾,因为p下标从0开始,所以m下标从1开始

                            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//对每个链,赋初始划分值为在链首划分

                            s[i][j]=i;//存储划分点

                            for(int k=i+1;k<j;k++){//依次考察从其它点划分的情况

                                     int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];

                                     if(t<m[i][j]){ //如果从k点划分更优,则更新解并记下划分点

m[i][j]=t;s[i][j]=k;

}

}

}

}

}

第四步,构造最优解。第三步的算法,只是记录了最优时的运算次数,并不知从哪划分,不过由二维数组s可构造出最优解;

void TraceBack(int i,int j,int **s){//构造A[i…j]连乘时的各个矩阵运算次序

         if(i==j)return;

         TraceBack(i,s[i][j],s);//s[i][j]记录的是A[i…j]中间的那个划分点k

         TraceBack(s[i][j]+1,j,s);

         cout<<”乘A”<<i<<”,”<<s[i][j]<<”和A”<<s[i][j]+1<<”,”<<j<<endl;

}

补充一,递归解法伪代码:

int RecurMatrixChain(int i,int j){

         if(i==j)return 0;//递归边界条件

         int u=RecurMatrixChain(i,i)+ RecurMatrixChain(i+1,j)+ p[i-1]*p[i]*p[j];

         s[i][j]=i; //上一行最后一项会不断加起来,而0是递归边界

         for(int k=i+1;k<j;k++){

                   int t= RecurMatrixChain(i,k)+ RecurMatrixChain(k+1,j)+ p[i-1]*p[k]*p[j];

                   if(t<u){u=t;s[i][j]=k;}

}

return u;

}

补充二,备忘录解法,也是用递归,过程与递归解法一样只是增加判断及记录两样

int MemorizedMatrixChain(int n,int **s){

         for(int i=1;i<=n;i++)

                   for(int i=1;i<=n;i++)

                            m[i][j]=0;//初始化,递归时,判断到m[i][j]>0则表示计算过,直接返回

         return LookupChain(1,n);

}

int LookupChain(int i,int j){

         if(m[i][j]>0)return m[i][j];//判断!

         if(i==j)return 0;

         int u= LookupChain (i,i)+ LookupChain (i+1,j)+ p[i-1]*p[i]*p[j];

         s[i][j]=i; //上一行最后一项会不断加起来,而0是递归边界

         for(int k=i+1;k<j;k++){

                   int t= LookupChain (i,k)+ LookupChain (k+1,j)+ p[i-1]*p[k]*p[j];

                   if(t<u){u=t;s[i][j]=k;}

}

m[i][j]=u;//记录!递归时没有m数组记录中间结果

return u;

}

时间效率,动态规划解法为O(n^3),递归解法为O(2^n)。

60,最长公共子序列问题

最长公共子序列中,子序列的定义是一个给定序列的子序列,是在该序列中删去若干元素后得到的序列。问题为,求给定序列X{x1,x2,xm}和Y{y1,y2,…yn},求解其最长的公共子序列。动态规划法第一步,抽象出数学公式并给出递归结构表示。

c[i][j]用来表示x1,…xi与y1,…yj的最长公共子序列,则递归式表示为:



第二步,写出(伪)代码:

void LCSLength(int m,char *x,char *y,int **c,char ** b){

         int i,j;//写出递归解法是容易的,但动态规划用的是自底向上的方式,也即求c[i][j]

         for(i=1;i<=m;i++)c[i][0]=0;//c数组长度为[m+1]*[n+1]。

for(i=1;i<=n;i++)c[0][i]=0;//先初始化其中一个串为0时的解

for(i=1;i<=m;i++)

         for(j=1;j<=n;j++){

                   if(x[i]==y[j]){

                            c[i][j]=c[i-1][j-1]+1;

                            b[i][j]=’↖’;//b[i][j]用来记录c[i][j]是由哪个子问题得来

}else if(c[i-1][j]>=c[i][j-1]){

         c[i][j]=c[i-1][j];

         b[i][j]=’^’;

}else{

         c[i][j]=c[i][j-1];

         b[i][j]=’<’;

}

}

}

第三步,构造最优解

void LCS(int i,char **b){

         if(i==0||b==0)return;

         if(b[i][j]==’↖’){

                   LCS(i-1,j-1,x,b);cout<<x[i];

}else if(b[i][j]==’^’)LCS(i-1,b);

else LCS(i,b);

}

61,求数组的最大子段和(及二维情况的解答思想)

最大子段和的递归式思想:每次从中间mid划开,分别递归求两边最大子段和,再从中间开始,分别往左右遍历,得到从…mid和mid+1…(包括mid和mid+1)的最大子段和,二者相加,看它比前两个递归结果是否大,三者取最大者即为解,分治法(递归)伪代码如下:

int MaxSubSum(int *a,int right){//调用MaxSumSum(a,n)即为整个数组最大子段和

         if(left==right)return a[left];

         else{
                   int mid=(left+right)/2;

                   int leftsum=MaxSubSum(a,center);

                   int rightsum=MaxSubSum(a,center+1,right);

                   int maxl=maxLeftWithCenter(a,center);//从a[center]往前遍历求和,记下最大者

                   int maxr=maxRightWithCenter(a,center+1);//从a[center+1]往后求和,记下最大者

                   return max(leftsum,rightsum,max1+maxr);

}

}

动态规划法算法分析如下。

第一步,数学表示及导出递归表示。

记b[j]  (1<=j<=n)表示以元素j结尾的最大子段和,也即由b[j]往左加可得的最大子段和。于是,题目要求的解即是:max(b[j])  (1<=j<=n)。由b[j]的定义易知,当b[j-1]>0时b[j]=b[j-1]+a[j],否则b[j]=a[j]。由此可得计算b[j]的动态规划递归式:

b[j]=max{b[j-1]+a[j],a[j]},1<=j<=n;

据此,可得最大子段和的动态规划算法。

int MaxSum(int n,int *a){

         int sum=0;//如果最大子段和是负数,则返回0

         b=0;//b初始时为0

         for(int i=1;i<=n;i++){

                   if(b>0)b+=a[i];//因为b初始为0所以,第一步执行时,会执行else

                   else b=a[i];//第一次执行时,会将a[1]赋给b

                   if (b>sum);sum=b;//只用一个b即可代替b[]的作用,因为每个b[j]只引用b[j-1]

}

return sum;

}

时间复杂度仅为O(n)。如果是二维的情况,则需要用两重循环来确定其中一维的上下边界。复杂度为O(n*m^2)。

62,编程之美:求数组中最长递增子序列

动态规划法求解的递归表示为:LIS[i+1]=max{1,LIS[k]+1},array[i+1]>array[k],for any k<=i;

其中LIS[i]表示以array[i]结尾的最长递增公共子序列的长度,公式意思为,求以array[i+1]结尾的递增子序列,等于i+1之前的所有递增子序列加上array[i+1](如果加上之后子序列仍是增的话)之后中最长者,或者1(初始时的值)。代码如下:

int LIS(int *array,int n){

         int *LIS=new int[n];

         for(int i=0;i<n;i++){

                   LIS[i]=1;//初始时的值,递增子序列长度至少为1

                   for(int j=0;j<i;j++){

                            if(array[i]>array[j]&&LIS[j]+1>LIS[i])LIS[i]=LIS[j]+1;

}

}

return Max(LIS);//取LIS数组中的最大值

}

63,计算串的相似度(编辑距离计算)

第一步,数学表示:设六种操作代价分别为c1…c6,令c[i][j]表示为由xj,xm变到yi,yn的最小代价,从m,n往左匹配,可有如下规律:若当前操作为delete则此前操作xj+1,yn的代价最小;若为replace或copy则之前xj+1,xm变到yi+1,yn的代价最小;若为insert则表示此前xj,yn的代价最小;twiddle(交换相邻字符)操作之前xj+2,xm变到yi+2,yn的代价最小,因为每次都是五选一(kill为边界条件,计算时决定),所以每步都是比较5种操作的代价,选最小者。

第二步,递归式为:

c[i][j]=min{c[i][j+1]+c1,c[i+1][j+1]+c2,c[i+1][j+1]+c3,c[i+1][j]+c4,c[i+2][j+2]+c5}

另设一k[i][j]用来记录c[i][j]最小时,的操作序号ci(1<=i<=5)

显然,c[i][j]递归式的边界条件有三个:

1,   c[i][m+1]=(n-i+1)*c4;//源串为空,则变为目标串需要插入n-i+1次

2,   [n+1][j]=(m-i+1)*c1;//目标串为空,则源串需要删除m-i+1次,即kill操作

3,   c[n+1][m+1]=0;//源与目标串均空,不需要操作

64,汽车装配问题,算法导论P195

动态规划法求解第一步,数学表示及递归公式如下:



这个公式变量含义如下:

e1,e2分别表示初始时装配上1号2号线的时间,a1,j和a2,j分别表示产品在1,2号线上的j个结点上加工的时间,f1[j]和f2[j]分别记录产品推进到1,2号线上的第j个结点时所费最少时间。t1[j]和t2[j]分别表示从1,2号线的结点j切换到另一线所耗费的时间。

由递归式,写出伪代码解法如下:

FATEST-WAY(a,t,n){//e表示e1,e2;x表示x1,x2,分别表示初始上线及最后下线的代价

         f[1][1]=e1+a[1][1];//初始化边界条件,即第一个结点的情况

         f[2][1]=e2+a[2][1];

         for j=2…n{

                   if((f[1][j-1]+a[1][j])<=(f[2][j-1]+t[2][j-1]+a[1][j])){

f[1][j]=f[1][j-1]+a[1][j];

                            l[1][j]=1;//l[1][j]表示在线1上第j个结点加工的产品上一结点是哪条线

}

                   else {

f[1][j]= f[2][j-1]+t[2][j-1]+a[1][j];

                            l[1][j]=2;

                   }

                   if((f[2][j-1]+a[2][j])<=(f[1][j-1]+t[1][j-1]+a[2][j])){

f[2][j]=f[2][j-1]+a[2][j];

                            l[1][j]=2;//l[2][j]表示在线2上第j个结点加工的产品上一结点是哪条线

}

                   else {

f[2][j]= f[1][j-1]+t[1][j-1]+a[2][j];

                            l[1][j]=1;

                   }

                   if((f[1][n]+x1)<=(f[2][n]+x2)){//处理最后一个结点,x1表示从线1卸下的时间

                            finish_cost=f[1][n]+x1;//如果从线1结束的时间比从线2早,则在线一完成

                            line_finish=1;

}else{//如果从线2结束时间比从线1早,则在线二完成

                            finish_cost=f[2][n]+x2;

                            line_finish=2;

}

}      

}

构造最优解

PRINT-STATIONS(l,line_finish,n){

         int i=line_finish;

         print “line”+i+”,station”+n

         for(j=n downto 2){

                   i=l[i][j];

print “line”+i+”,station”+j-1;

}

}

65,双调旅行商问题:对平面上给定的n个点,确定一条连接各点的最短闭合旅程的问题。这是NP完全的,有人提议只考虑“双调旅程”来简化问题。即先从最左到最右,再回到最左。换言之,设两个A,B从最左,以不同路径到达最右,求此路径之和的最小值。严格从左至右,即到某点i时,i左边的点已经全部走过了。

假设两人A,B,不失一般性,设A在B后,Pij表示A走到点i而B走到点j时的最短路径,根据假设有i<=j,设b[i][j]表示最短双调路径Pij的长度,d[i][j]表示i,j之间的距离。则:

b[1][2]=d[1][2];

当i=j时,即A,B处在同一点,b[i][j]=b[i][i]=b[i-1][i]+d[i-1][i];

当i=j-1时,即A在B相邻的靠左一点,b[i][j]=b[j-1][j]=min{b[k][j-1]+d[k][j]}1<=k<=j-1

当i<j-1时,即A在B后的多个点处b[i][j]=b[i][j-1]+d[j-1][j]。

此为动态规划法。

67,漂亮打印问题:考虑在一张纸上打印一段文章,正文为n个分别长为l1,l2,ln的单词构成的序列,漂亮打印的标准为,如果一行包括从第i到第j个单词(i<j),且单词之间只留一个空格,则每行末多余空格数立方和最小。用动态规划法求解:

记单词为w1,w2,wn,记Pi为将wi至wn的单词漂亮打印出来的方案,则本题为求P1。对任意的Pi,若在wj处结尾(该行包括从i到j所有单词),则Pi中,对于wj+1,wj+2,wn即Pj+1是最优的,符合最优子结构性质。容易发现重叠子问题(重复计算)也存在。

使用动态规划法从Pn求到P1,求Pi时,只用处理与wi可能在同一行的所有情况,而求同一行的情况与行宽M相关,所以,求单个Pi的时间为O(M),整个算法的时间复杂度为O(m*n),递归条件(自底向上的起始条件)为,Pn=0;

68,计划一个公司聚会算法导论P219

公司的管理层次结构可用树形结构表示,每个雇员有一个喜欢聚会的程度(实数表示),为每大家都喜欢这个聚会,总裁不希望一个雇员和他的直接上司同时参加。树的结构用左子女,右兄弟表示法。树中每个结点除了包含指针,还包含了雇员的名字及该雇员喜欢聚会程度的排名。描述一个算法,它生成一张客人列表,使得喜欢聚会的程度之总和为最大。

用动态规划法解答:

转化为树的着色问题,如果点x着红色,代表参加,白色代表不参加,则从叶子起,记住每个结点着(不着色)时的喜欢程度总和,递归定义如下:

求max(T(root,WHITE),T(root,RED))即为解。

69,0-1背包问题的动态规划算法:有n件物品和一个容量为c的背包。第i件物品的费用是w[i],价值是v[i]。求解将哪些物品装入背包可使价值总和最大。

基本思路:这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

递归关系公式表示为:



其中m(i,j)表示,选的物品范围为i,n,而剩余容量为j。

用动态规划求解的(伪)代码如下:

void Knapsack(int *v,int *w,int c,int **m){

         int jMax=min(w[n]-1,c);//jMax为下面的初始化时用,jMax表所剩容量的一个边界值

//一开始试第n个时,容器装不下n或者剩余容量j在jMax以下时,初始化该情况

         for(int j=0;j<=jMax;j++)m[n][j]=0;

         for(int j=w[n];j<=c;j++)m[n][j]=v[n];//一开始试第n个时,如能装下,则计算矩阵值

         for(int i=n-1;i>1;i--){//从第n-1个物品考察起,直至第2个

                   jMax=min(w[i]-1,c);//考察第i个物品时,c装不下它,或者j(所剩容量)在它之下

         for(int j=0;j<=jMax;j++)m[i][j]=m[i+1][j];//这些j都装不下

         for(int j=w[i];j<=c;j++){

                   m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);//这些j都装得下

}

}

m[1][c]=m[2][c];//处理第一个,因是数组,所以所有值都填!

if(c>=w[1])

         m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);//如果是装得下,则对这些数组元素赋值

}

构造最优解:

void Traceback(int **m,int w,int *x){

         for(int i=1;i<n;i++){//生成一个x[1…n]向量,用1表示该物品选了,否则表示未选

                   if(m[i][c]==m[i+1][c])x[i]=0;

                   else{

         x[i]=1;

         c-=w[i];

}

x[n]=(m[n][c])?1:0;

}

}

0-1背包动态规划的另一种解法(从第0个物品开始考虑起)

递归式为:



伪代码如下:

for(j=0…W)m[0][j]=0;//大写W表背包总容量

for(i=1…n){

         m[i][0]=0;

         for(j=1…W){

                   if(w[i]<j){//装得下时,看哪个选择好

                            if(v[i]+m[i-1][j-w[i]]>m[i-1][j])

                   m[i][j]= v[i]+m[i-1][j-w[i]];

         else m[i][j]= m[i-1][j];

}

else m[i][j]= m[i-1][j];//装不下

}

}

return m[0][W];//可装得下的最大价值,构造最优解的方向,也应与考虑时方向一致

0-1背包问题扩展之一。数组分割,要求将长度为2n的数组分割成两个长度为n的数组,并使它们之间的和最接近。

假设S=(a[1]+a[2]+...+a[n]+a[n+1]+...+a[2n])/2,那么这是个和0-1背包类似的动态规划问题,区别之处就是取的个数受到限制,必须得取足n个元素。用dp(i,c)来表示从前i个元素中取j个、且这j个元素之和不超过c的最佳(大)方案,在这里i>=j,c<=S 状态转移方程: dp(i,c)=max{dp(i-1,c-a),dp(i-1,c)}

dp(2n,S)就是题目的解。 整体复杂度是O(S*n^2)

0-1问包问题扩展之二。最优装载,要把n个重量分别为wi的物品,装到2艘船上,使之完成装载,2艘船的载重分别为c1,c2。

容易证明,如果给定的一人装载问题有解,则采用如下的策略一定能得到一个最优装载方案:

1、   首先将第一艘船尽可能地装满;

2、   然后将剩余的物品装到第二艘船上。

这样,便演化成了0-1背包问题。

0-1背包问题扩展之三。回溯法解0-1背包

void Backtrack(int i){

         if(i>n){bestp=cp;return;}//如果找到了一个最优解,则返回

         if(cw+w[i]<=c){//尝试装x[i]=1(如果装得下)

                   cw+=w[i];//重量加

                   c[p]+=p[i];//价值加

                   Backtrack(i+1);//递归调用

                   cw-=w[i];//一定要复位,因为cw和cp是共用的变量

                   cp-=p[i];

                   }//其实所谓回溯,就是递归调用,加了一个剪枝步,Bound(int i)判断把余下的

}//按单位价值排序后依次装上,零头也装上,是否能得到更优的解,也即估上界

if(Bound(i+1)>bestp)Backtrack(i+1);//不装x[i]=0

}

70,编程之美:买书问题

令F(Y1,Y2,Y3,Y4,Y5)表示买五册书分别为Y1,Y5时所花的最少价格。其中Y1>Y2…>Y5。每次求解之前,都要对那五个数进行排列,大的放前面。动态规划解法的递归式为:

F(Y1,Y5)=0       (Y1=Y2=Y3=Y4=Y5=0)

F(Y1,Y5)=

min(5*8*(1-25%)+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5-1),//如果Y5>1

 4*8*(1-20%)+F(Y1-1,Y5),//如果Y4>1

 3*8*(1-10%)+F(Y1-1,//如果Y3>1

 2*8*(1-5%)+F(Y1-1,//如果Y2>1

8+ F(Y1-1,Y5)) //如果Y1>1

 

以下部分主要为图与几何相关部分

71,图的基本数据结构,主要表示方法(邻接表),深度优先遍历算法,广度优先遍历算法与层序遍历树一样,用队列!

#define MAX_VERTEX_NUM 20

typedef struct ArcNode{//弧结构体

         int adjvex;//该弧所指向的顶点位置

         struct ArcNode *nextarc;//下一条弧

         int weight;//权重

}ArcNode;

typedef struct VNode{

         int data;//顶点信息

         ArcNode *firstArc;//指向第一条依附该结点的弧的指针

}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{

         AdjList vertices;//结点数组

         int vexnum,arcnum;//图的当前顶点数和弧数

         int kind;//图的种类标志

}Graph;

void DFS(Graph G,int v){//深度优先遍历结点v

         visited[v]=true;

         cout<<v<<endl;//访问函数

         for(ArcNode *w=G.vertices[v].firstArc;w!=NULL;w=w->nextarc)

                   if(!visited[w->adjvex])DFS(G,w->adjvex);

}

void DFSTraverse(Graph G){//深度优先遍历图

         for(int v=0;v<G.vexnum;v++)visited[v]=false;

         for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v);

}

图的连通性判断。无向图只需要只以一个结点出发进行一种(深度或广度)遍历,然后检查是否所有结点均被visited了即可,有向图则采用如下算法:

(1)对图调用深度优先遍历,并记住每个顶点完成时间(比如用栈)(2)对图转置为GT(3)从最晚完成的顶点开始,对GT调用深度优先遍历,当找不到新顶点时,从余下顶点中选一个最晚完成的顶点继续,直到全部完成;每次换选一个顶点之前得到的顶点集即为一个强连通分支。

图的拓扑排序。入度为0的结点入队,当队不空时循环:弹出队首,并对队首元素可达的每个顶点入度减1,将此轮减1后入度为0者插入队尾。最后出队顺序即拓扑有序。

最小生成树算法。普里姆算法(prim),从某一点出发,每次从余下的点集中选择离它最近的点作为下一点,并入已选点集中(设置距离为0)并更新已选点集与未选点集的距离(如果因新加入的点引起了变化的话),时间复杂度为n^2,与边无关;克鲁斯卡尔(Kruskal)算法,每次从属于不同的两个点集中的两点所连的边中选择一条最短者,然后将此两点集合并,直至所有点集同属一个集合即完成算法,初始点集数为n,每个集一个点,时间复杂度为eloge。由以上分析可知,前者适用于点少边多的图,后者则相反。

图的单源最短路径算法。迪杰斯特拉(dijstra)算法,按最短路径递增的方式求单源最短路径,伪码如下:

Dijstra(G,w,s){//s为源点,w为权值矩阵

         init();//初始化d[s]=0;其余d[v]=MAXINT

         Q=V(G)-s;//未用来计算最短路径的点集

         S=s;//已用来计算最短路径的点集

         while(Q!=NULL){

                   u=extract-min(Q)//从Q中选择d[u]最小的点(并从Q中删除该点)

                   S=S并u;

                   for each vertex v in Adj[u];//对于u可达的每个顶点

                            Relax(u,v,w);

}

}

Relax(u,w){

         if(d[u]+w[w][v]<d[v])d[v]= d[u]+w[w][v];

}

图的每对顶点间最短路径。

方法一,执行n次单源最短路径算法,复杂度O(n^3);

方法二,Floy-Warshall算法,复杂度O(n^3);

对任意两个点i,j给定k表示i,j之间,所有经过的顶点序号不大于k的时候,i,j之间的最短路径,考虑已经求出k-1时的情况,对于k:

(1)         若k在i,j最短路径中,则路径为

(2)         如果k不是i,j最短路径中,则k-1的解即为k的解,用数学形式表示为:



由此得Floy-Warshall算法伪代码:

Floy-Warshall(W){

         n=rows(W);

         D0=W;//D代表每轮计算之后的权值矩阵W

         for(k=1…n)

                   for(i=1…n)

                            for(j=1…n);

         return Dn;

}

有向图的传递闭包问题。即要求两点i,j(任意)是否可达。方法:对每条边赋值1,若运行Floy-Warshall之后dij<n则可达,否则为不可达;改进之处,在求Floyd时公式改为:

;进行或运算即可

关键路径求法。AOV网加上权值便得AOE(Activity On Edge)网,对AOE网的一项典型计算是计算关键路径,即从源点到终点的最长路径,关键路径上的活动延期会影响整个工程!

求关键路径的方法是:

(1)从源点开始,求各个活动的最早发生时间(事先拓扑排序);入一栈中为第二步作准备(2)从终点开始向前,求各个活动的最晚发生时间;(3)输出最早发生时间等于最晚发生时间的活动,便是关键活动。

72,寻找最近点对!

一维情况,用排序,然后扫瞄一遍即可;

二维时的算法伪代码:

bool cpair2(s,&d){

         n=|s|;

         if(n<2){d=MAXINT;return false;}

         m=s中各点x坐标的中位数;

         由x=m分割点集s为s1,s2;

         cpair2(s1,d1);

         cpair2(s2,d2);

         dm=min(d1,d2);

         设p1为s1中与x=m小于dm的所有点集

         设p2为s2中与x=m小于dm的所有点集

         将p1和p2中的点按y值排序,结果为X,Y

对X中的每个顶点,检查Y中与其在y轴上投影距离小于dm的所有顶点(最多6个),最终求得的最小距离为dl;

d=min(dm,dl);

return true;

}

73,九宫格,可以上下左右方向走,不可斜走,任意走n步(1<=n<=8)且不可以已经走过的方格,只要走的步数不一样,或者走的路线不一样,就算一种走法,问题是任意给一格作为起点,请问有多少走走法?

/* 0 1 2

3 4 5

6 7 8 ********/

#include <iostream>

using namespace std;

int ninemap[9][4]={

 {1,-1,-1},{0,{1,6,7},{2,{3,{4,{5,-1}

};

 

void findPathNum(int source,int ninemap[9][4],int gone[],int &goneNum,int&sum,int gonePath[])

{

         if(gonePath[0]!=-1){

                   for(int i=0;i<9;i++)

                            if(gonePath[i]!=-1)cout<<gonePath[i];

                                     cout<<endl;      

                sum++;

         }

         gone[source]=1;  // 表示我已经来过这里

         gonePath[goneNum]=source;// 当前状态下路径位置

         if(goneNum==9) return;

         int nextPoint=-1;

         for(int i=0;i<4;i++){

                   nextPoint =ninemap[source][i];

                   if (nextPoint!=-1&&gone[nextPoint]!=1){// 存在下一顶点,且之前没有走过

                            gone[nextPoint]=1;

                            ++goneNum;

                            gonePath[goneNum]=nextPoint;

                            findPathNum(nextPoint,ninemap,gone,goneNum,sum,gonePath); //递归

                            gonePath[goneNum]=-1;

                            --goneNum;

                            gone[nextPoint]=0;

                   }

         }

         gonePath[goneNum]=-1; // 重置位

         gone[source]=0;// 重置位

}

int main(){

         cout<<"请输入九宫格的初始节点(0-8,结束请输入-1)"<<endl;

         int source;

         cin>>source;

         if(source==-1){

                   return 0;

         }

         while(source<0 || source>8){

                   cout<<"输入参数不规范,请重新输入"<<endl;

                   cout<<"请输入九宫格的初始节点(0-8,结束请输入-1)"<<endl;

                   cin>>source;

         }

         while(source>-1 && source <9){

                   int goneNum=0;// 当前节点位置

                   int gonePath[9]={-1,-1}; // 保存走过的路径

                   int sum=0;// 解法个数

                   int gone[9]={0,0};// 走过该节点否,1走过,0未走

                   findPathNum(source,gonePath);

                   cout<<"以"<<source<<"为起点的解法共有"<<sum<<"个"<<endl;

                   cout<<"请输入九宫格的初始节点(0-8,结束请输入-1)"<<endl;

                   cin>>source;

         }

         return 0;

}

74,计算凸包

Graham扫瞄法:

第一步,选取y值最小的点P0,其余点以P0为原点按逆时针扫过的顺序排序;

第二步,按序P1,P2进栈;

第三步,对于余下的每个Pi,按序依次

{

         while(next-to-top(Stack),top(Stack),Pi三点(两线段)非左拐)pop(Stack);

         push(Pi,Stack);

}

javis法:

第一步,与Graham一样选取P0;

第二步,对于剩下的点,按逆时针扫过的第一个点为P1;

第三步,P1为新端点,除P0,P1外,以新端点逆时针扫过的第一个点为P2;

……

到最高点时,右链扫瞄完毕,

第四步,左链由P0开始与右链对称执行一次,两链合并即完成扫瞄。

75,确定两线段是否相交,看算法导论笔记

知识一,两点P1(x1,y1),P2(x2,y2)的叉积定义为:x1*y2-x2*y1。如果叉积P1×P2为正数,则相对于原点(0,0)来说,P1在P2的顺时针方向,如果是负数则表示在逆时针方向,如果是0则表示这两个向量是共线的。

确定连续线段是向左转还是向右转?给定点p0,p1,p2求线段p1p2在p0p1之后是向左转了还是向右转了。方法就是求p0p2和p0p1这两个向量的叉积。

确定两线段是否相交,有两种情况:

一是,每个线段都跨越包含了另一线段的直线;

二是,一个线段的某一端点位于另一线段上。(这一情况来自于边界情况)

SEGMENTS-INTERSECT(p1,p2,p3,p4){//判断p1p2和p3p4是否相交

         d1=DIRECTION(p3,p4,p1);//计算p3p4与p3p1的叉积

         d2=DIRECTION(p3,p2);

         d3=DIRECTION(p1,p3);

         d4=DIRECTION(p1,p4);

         if((d1*d2<0)&&(d3*d4<0))return true;

         else if((d1==0)&&ON-SEGMENT(p3,p1))return true;//d1=0表在p1在p3p4的直线上

else if((d2==0)&&ON-SEGMENT(p3,p2))return true;//是否在线段上,仍需要判断

else if((d3==0)&&ON-SEGMENT(p1,p3))return true;//ON-SEGMENT判断范围即可

else if((d4==0)&&ON-SEGMENT(p1,p4))return true;//

else return false;

}

DIRECTION(pi,pj,pk){//计算pipj与pipk的叉积

         return (pk-pi)×(pj-pi)

}

ON-SEGMENT(pi,pk){//计算点pk是否在线段pipj上,因之前已经判断了在直线上

         if((min(xi,xj)<=xk<=max(xi,xj))&&(min(yi,yj)<=yk<=max(yi,yj)))return true;

         else return false;

}

76,求给定的一组线段中,是否有相交的

方法大意:

第一步,将线段所有端点排序(按x值,相同时再按y值)

第二步,设一扫瞄线,从左到右扫瞄每一个端点。对于每个扫到的端点,若其为左端点,则将线段加入到扫瞄线线段集中,判断此时紧临其扫瞄线上方或下方存在的线段,若有与之相交的,则返回true;若其为右端点,则判断扫瞄线此时其上下方均有线段并相关时返回true,否则从扫瞄线线段集中删除该右端点所在的线段。

 

以下主要为几个矩阵输出题

77,void Matrix(int n) 打印出如下一个矩阵:

n=5

5  6  3  4  5

4  7  2  7  6

3  2  1  2  3

6  7  2  7  4

5  4  3  6  5

n=7

7  8   9  4   5  6  7

6  13 10  3  12 13  8

5  12 11  2  11 10  9

4  3   2  1   2  3  4

9  10 11  2  11 12  5

8  13 12  3  10 13  6

7  6   5  4   9  8  7

....

以此类推 n<20,n为奇数

十字架,划分成四个区域,然后各个区域再分别打印!

void printMatrix2(int n){

         if(n>20||n<0||n%2==0)return;//偶数,及其它不符合条件的数返回

         int **a=new int*[n];

         for(int i=0;i<n;i++)

                   a[i]=new int[n];

         int center=n>>1;

         a[center][center]=1;//赋中心点

         int j;

         for(i=center+1,j=2;i<n;i++,j++){//赋十字架

                   a[center][i]=j;//十字架的右

                   a[i][center]=j;//十字架的下

                   a[n-i-1][center]=j;//十字架的上

                   a[center][n-i-1]=j;//十字架的左

         }

         printRightUpQuarter(a,center+2,center);//打印数组a的右上角四分之一

         printRightDownQuarter(a,n-1,center);//打印数组a的右上角四分之一

         printLeftUpQuarter(a,center-1,center);//打印数组a的右上角四分之一

         printLeftDownQuarter(a,center);//打印数组a的右上角四分之一

         for( int s = 0; s < n ; ++s )

         {

                   for( int j = 0; j < n ; ++j )

                   cout<< a[s][j]<< "/t" ;

                   cout<< endl;

         }

         delete []a;

}

void printRightUpQuarter(int **matrix,int x,int y,int n) {//右上,其它三块类似

       int i,j;//打印螺旋队列的递归算法

       if (n <= 0) return;

       if (n == 1) {

              matrix[x][y] = start;

              return;

       }

       for (j = y; j < y + n; j++)          /* 上部 */

              matrix[x][j] = start++;

       for (i = x+1; i < x + n; i++)          /* 右边 */

              matrix[i][y+n-1] = start++;

       for (j = y+n-2; j >= y; j--)              /* 底部 */

              matrix[x+n-1][j] = start++;

       for (i = x+n-2; i > x; i--)              /* 左边 */

              matrix[i][y] = start++;

       printRightUpQuarter(matrix,x+1,y+1,n-2);     /* 递归 */

}

扩展,打印螺旋队列的非递归算法如下:

void printRightUpQuarter(int **matrix,int n) {//右上

         if (n <= 0)return;

         if (n == 1) {

                   matrix[x][y] = start;

                   return;

         }  

         int round=1;

         for(round=1;round<=n/2;round++){

                   for (int j = y+round-1; j < y + n-round+1; j++)          //* 上部

                            matrix[x+round-1][j] = start++;

                   for (int i = x+round; i < x + n-round+1; i++)         //* 右边

                            matrix[i][y+n-round] = start++;

                   for (j = y+n-1-round; j >= y+round-1; j--)              //* 底部

                            matrix[x+n-round][j] = start++;

                   for (i = x+n-1-round; i > x+round-1; i--)              //* 左边

                            matrix[i][y+round-1] = start++;

         }

}

78,有道笔试题。打印矩阵

void printmatrix(int n) n<20

打印出如下一个矩阵:

n=3

1  2  1

1  2  1

1  1  1

n=4

1  2  2  1

1  2  2  1

1  2  2  1

1  1  1  1

n=5

1  2  2  2  1

1  2  3  2  1

1  2  3  2  1

1  2  3  2  1

1  1  1  1  1

n=6

1  2  2  2  2  1

1  2  3  3  2  1

1  2  3  3  2  1

1  2  3  3  2  1

1  2  3  3  2  1

1  1  1  1  1  1

n=7

1  2  2  2  2  2  1

1  2  3  4  3  2  1

1  2  3  4  3  2  1

1  2  3  4  3  2  1

1  2  3  4  3  2  1

1  2  3  3  3  2  1

1  1  1  1  1  1  1

....

以此类推,

//规律是分四类,第一行,最后一行,倒数第二行,其它

void printMatrix( int n ) //已运行验证

{

         if(n<2)return;//边界条件

         int **a=new int*[n];//=int[n][n]不行!

         for(int k=0;k<n;k++)a[k]=new int[n];

         a[0][0]=1;//以下三行代码给第一行赋值

         a[0][n-1]=1;

         for(int j=1;j<n-1;j++)a[0][j]=2;

         for(j=0;j<n;j++)a[n-1][j]=1;//给最后行赋值

         for(j=0;j<3;j++)a[n-2][j]=j+1;//给倒数第二行赋值

         for(j=3;(j<=n-4)&&j<(n/2+n%2);j++)a[n-2][j]=3;

         for(j=n-1;(j>n-4)&&j>=(n/2+n%2);j--)a[n-2][j]=n-j;//

         for(int i=1;i<n-2;i++){//赋其它行

                   for(j=0;j<(n/2+n%2);j++)a[i][j]=j+1;

                   for(j=n-1;j>=(n/2+n%2);j--)a[i][j]=n-j;

         }

         for( int s = 0; s < n ; ++s )

         {

                   for( int j = 0; j < n ; ++j )

                   cout<< a[s][j]<< "   " ;

                   cout<< endl;

         }

         delete []a;

}

79,输出矩阵,n<20;n为奇数;

     n=5;

     14444

     14333

     14023

     11123

     22223

     n=7;

     1444444

     1433333

     1432223

     1430123

     1444123

     1111123

     2222223

提示:从外围开始转圈!代码如下:

void printMatrix3(int n){

         if(n>20||n<0||n%2==0)return;//偶数,及其它不符合条件的数返回

         int **a=new int*[n];

         for(int i=0;i<n;i++)

                   a[i]=new int[n];

         int x,y;//一圈圈地转,与螺旋队列一样,只是填的数不一样而已

         int filledNumber=1;

         a[n/2][n/2]=0;

         for(int round=1;round<=n/2;round++){

                   for(x=round-1;x<n-round;x++)//左边

                            a[x][round-1]=filledNumber;

                   if(filledNumber<4)filledNumber++;

                   else filledNumber=1;

                   for(y=round-1;y<n-round;y++)//下边

                            a[n-round][y]=filledNumber;

                   if(filledNumber<4)filledNumber++;

                   else filledNumber=1;

                   for(x=n-round;x>round-1;x--)//右边

                            a[x][n-round]=filledNumber;

                   if(filledNumber<4)filledNumber++;

                   else filledNumber=1;

                   for(y=n-round;y>round-1;y--)//上边

                            a[round-1][y]=filledNumber;                  

         }

         for( int s = 0; s < n ; ++s )

         {

                   for( int j = 0; j < n ; ++j )

                   cout<< a[s][j]<< "/t" ;

                   cout<< endl;

         }

         delete []a;

}

猜你在找的正则表达式相关文章