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; }