1,strcpy//返回的是目標(biāo)串的地址，這樣支持連續(xù)的運(yùn)算表達(dá)式，已測試char *strcpy(char *strDest, const char *strSrc){//源串一定要const修飾assert((strDest!=NULL)&&(strSrc!=NULL));//此類題型基本判斷，指針是否空if(strDest==strSrc)return strDest;//編程題型的基本判斷，相等時可直接返回char *tempptr=strDest;//因?yàn)閭鬟M(jìn)來的指針在復(fù)制時會移動，因此先備份while((*strDest++=*strSrc++)!=’/0’);//空循環(huán)，如是其它條件一定注意’/0’的處理return tempptr;//上一行的while中(*strDest++=*strSrc++)括號不能少}2,memcpy//對內(nèi)存塊的復(fù)制，需要著重考慮的是，內(nèi)存塊重疊的情況，已測試void memcpy(void *pDest, const void *pSrc, size_t size){assert((pDest!=NULL)&&(pSrc!=NULL)); //此類題型基本判斷，指針是否空//任何對void*指針的運(yùn)算，都需要先類型轉(zhuǎn)換！if((pDest>pSrc)&&((char *)pSrc+size>pDest)){//有重疊，且目標(biāo)內(nèi)存塊在后char* pstrSrc=( char*)pSrc+size-1;//一定要注意-1，因?yàn)槿绻鹲ize是1char* pstrDest=( char*)pDest+size-1;//則不需要加，因此注意要-1while(size--)//直接用size控制循環(huán)，另一處用size是else中，不可能同時會執(zhí)行* pstrDest --=* pstrSrc --;//自減用的是pstrSrc，而不是pSrc}else{//無重疊或者有重疊但目標(biāo)內(nèi)存塊在前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){//當(dāng)兩表都不空時確定結(jié)點(diǎn)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;//只一個結(jié)點(diǎn)q=p->next;p->next=NULL;//一定要有這句，否則逆序后找不到尾了if(q->next==NULL){q->next=p; return q;//只兩個結(jié)點(diǎn)}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);//根進(jìn)棧NODE *p=NULL;while(!s.empty()){while((p=s.top())!=NULL)s.push(p->pLeft);//左一直進(jìn)棧，空的也進(jìn)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;//先訪問自己再左子樹進(jìn)棧，這是與中序的唯一區(qū)別s.push(p->pLeft);}s.pop();//此處會彈出空指針if(!s.empty()){p=s.top();s.pop();s.push(p->pRight);}}}void PostOrderTraverse(NODE* root){//后序，需要增加目前已經(jīng)訪問是左或右的標(biāo)記stack<stackNODE> s;stackNODE x;NODE* p=root;do{while(p!=NULL){//非空左子樹一直進(jìn)棧，并標(biāo)記為已訪問左子樹，直達(dá)最左葉子x.ptr=p;x.tag='L';s.push(x);p=p->pLeft;}while(!s.empty()&&s.top().tag=='R'){//如果棧中元素已經(jīng)訪問過右子樹，則訪問根x=s.top();s.pop();cout<<x.ptr->chValue;}if(!s.empty()){//進(jìn)入棧中元素的右子樹，只是賦值，右子樹是否空，交由外層循環(huán)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>endint 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,e,mid+1,end);}6，最大公約數(shù)，已測試int gcb(int a,int b){ //輾轉(zhuǎn)相除法if(a<b)swap(a,b);//先判斷大小，估計(jì)a大于bif(b==0)return a;//如果小的數(shù)為0返回a，不管a是不是0int r=a%b;//否則求余while(r!=0){//余數(shù)不為零時一直循環(huán)，至余數(shù)為0為止a=b;b=r;r=a%b;}return b;//余數(shù)為0則返回兩數(shù)中較小的}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）如果用鏈表的話，插刪表頭，如果用數(shù)組的話，用base,top保存數(shù)組下標(biāo)最簡單實(shí)現(xiàn)如下：已測試，但未必充分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，隊(duì)列操作（入隊(duì)出隊(duì)），已測試typedef struct QNode{int data;struct QNode *next;}QNode,*QueuePtr;typedef struct{QueuePtr front,rear;//隊(duì)首尾指針}LinkQueue;void InitQueue(LinkQueue &Q){//初始化只分配一個不存元素的空頭結(jié)點(diǎn)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;//刪最后一個結(jié)點(diǎn)的情況下，必須處理，以防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，各種排序算法，已驗(yàn)證（一）堆排序int heapSize = 0;int Parent(int index) { //返回父母的下標(biāo)，左孩子的父母除2即可，右孩子除后-1return (index % 2) ? (index >> 1) : ((index >> 1) - 1);}int Left(int index) { //返回左孩子下標(biāo)，乘2之后+1return ((index << 1) + 1);}int Right(int index) { //返回右孩子下標(biāo)，乘2后+2return ((index << 1) + 2);}//主要函數(shù)一，堆調(diào)整，調(diào)整index為根的子樹，前提是，index的左右子樹已經(jīng)調(diào)整過。void maxHeapify(int * array, int index) {int largest = 0;int left = Left(index);int right = Right(index);//第一步，先找到根與左右孩子中最大者的下標(biāo)if ((left <= heapSize) && (array[left] > array[index]))//heapSize來控制是否到葉子了largest = left;elselargest = index;if ((right <= heapSize) && (array[right] > array[largest]))largest = right;if (largest != index) {//第二步，如果最大的不是根，則交換最大者與根，遞歸調(diào)整swap(&array[index], &array[largest]);maxHeapify(array, largest);}}//主要函數(shù)二，建堆void buildMaxHeap(int * array, int length) {int i;heapSize = length;//初始化堆大小for (i = (length >> 1); i >= 0; i--)//從有孩子的結(jié)點(diǎn)開始，調(diào)整至樹根為止即建好了maxHeapify(array, i);}//主要函數(shù)三，排序，調(diào)用前兩個函數(shù)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--;//堆大小減1maxHeapify(array, 0);//只需要調(diào)整樹根}return 0;}（二）快速排序int part(int *a,int low,int high){//劃分函數(shù)int x=a[low];//此處是a[low]而不是a[0]，我自己寫代碼時犯了此錯誤//int i=low,j=high;不需要，直接用low,highwhile(low<high){while((a[high]>=x)&&(low<high))--high;//要重復(fù)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 low,int high){//遞歸函數(shù)if(low<high){//這是遞歸終結(jié)條件，即在只有一個元素時或者low>high時，不排序！int mid=part(a,low,high);quickSort(a,low,mid-1);quickSort(a,mid+1,high);}}快速排序擴(kuò)展：（1），隨機(jī)化版本，即每次進(jìn)行劃分之前，隨機(jī)生成一個low至high之間的下標(biāo)，將此下標(biāo)中元素與a[low]交換，然后再進(jìn)行劃分；（2）快排的第二次遞歸非必須，可用尾遞歸技術(shù)，用循環(huán)代替遞歸，代碼如下：while(low<high){int mid=part(a,low,high);quickSort(a,low,mid-1);low=mid+1;}（3）在劃分不均衡時，會導(dǎo)致遞歸深度為n，解決方法是，每次劃分后，小的一段先遞歸，可使棧深度最大為logn，或者小的一段用遞歸而大的一段用循環(huán)，參考“尾遞歸”方法；（4）快速排序的非遞歸版本思想：1)將low,high包裝為position結(jié)構(gòu)體，先將初始position(low,high)進(jìn)棧2)while(棧不空){彈出棧頂?shù)膒osition，如果low<high，則q=partition(a,low,high);if(q>low+1)將(low,q-1)包裝成position進(jìn)棧if(high>q+1)將(q+1,high)包裝成position進(jìn)棧}原理是，每次棧中有較長的序列，都會彈出，分成更小的序列，直至某序列少到一個元素時，不再push進(jìn)新的position。具體代碼如下，已驗(yàn)證：void quickSort2(int *a,int low,int high){MyStack<position> stack(150);//這個棧是自己寫的，只有pop,push,empty及析構(gòu)函數(shù)position pos;//自己定義的結(jié)構(gòu)體pos.x=low;pos.y=high;stack.push(pos);//初始上下界進(jìn)棧while(!stack.empty()){position poped=stack.pop();//棧不空進(jìn)，彈出棧頂元素if(poped.x<poped.y){//如果可劃分，則劃分成兩段int q=part(a,poped.x,poped.y);if(q>poped.x+1){//劃后的第一段可進(jìn)棧否？position lowpart;lowpart.x=poped.x;lowpart.y=q-1;stack.push(lowpart);}if(poped.y>q+1){//劃分的第二段可進(jìn)棧否？position highpart;highpart.x=q+1;highpart.y=poped.y;stack.push(highpart);}}}}（三）插入排序，遞歸算法void insertSort(int *a,int n){//其中n代表待排序元素的個數(shù)if(n>1){//遞歸的邊界條件insertSort(a,n-1);//先遞歸調(diào)用一下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循環(huán)，條件為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;}}（四）選擇排序：每次從余下的數(shù)中，選擇一個最小的放在當(dāng)前位置，當(dāng)前位置后移一位；初始時，余下數(shù)為n個，當(dāng)前位置為0。（五）冒泡排序：思想是每次一個大數(shù)沉底。具體C代碼如下：void bubbleSort(int *a,int n){//每次一個大數(shù)沉底for(int i=n-1;i>=0;i--)//每次比較時，要到達(dá)的下標(biāo)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){//主要輔助函數(shù)一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 *b,int left,int right){//遞歸輔助函數(shù)二while(left<=right){a[left]=b[left];left++;}}//遞歸主算法void mergeSort(int *a,int *b,int left,int right){//b數(shù)組是輔助空間if(left<right){//至少2個元素int i=(left+right)/2;mergeSort(a,b,left,i);mergeSort(a,b,i+1,right);merge(a,b,left,i,right);//合并到數(shù)組bcopy(a,b,left,right);//復(fù)制回?cái)?shù)組a}}//非遞歸主要輔助函數(shù)一void mergePass(int *a,int *b,int s,int n){//合并大小為s的相鄰2段子數(shù)組int i=0;while(i<=n-2*s){//先合并前若干對長度為s的相鄰子數(shù)組merge(a,b,i,i+s-1,i+2*s-1);i+=2*s;}if(i+s<n)merge(a,b,i,i+s-1,n-1);//剩下的數(shù)少于2*s個，如是>s個情況else for(int j=i;j<=n-1;j++)b[j]=a[j];//剩下不足s個}//非遞歸主函數(shù)void mergeSort2(int *a,int n){int *b=new int[n];int s=1;while(s<n){mergePass(a,b,s,n);//合并數(shù)組到bs+=s;mergePass(b,a,s,n);//合并數(shù)組到as+=s;}}（七）計(jì)數(shù)排序。它假設(shè)輸入的n個元素是介于0…k之間的整數(shù)，此處k為某個整數(shù)，當(dāng)k=O(n)時，計(jì)數(shù)排序的運(yùn)行進(jìn)行為O(n)，它需要k個用來存放計(jì)數(shù)的空間C[0…k]及n個存放結(jié)果的區(qū)間，偽代碼如下：countSort(A,B,k){//A為待排數(shù)組，B為結(jié)果數(shù)組，k的意義如前所述for(i=0…k)C[i]=0;//初始化計(jì)數(shù)器for(j=0…length(A))C[A[j]]=C[A[j]]+1;//計(jì)數(shù)for(i=1…k)C[i]=C[i]+C[i-1];//C[i]表示值所有小于或等于i的元素個數(shù)for(j=length(A) downto 1){B[C[A[j]]]=A[j];//所有小于等于A[j]的元素有x個，便把A[j]放在位置xC[A[j]]--;//然后把小于等于A[j]元素的元素?cái)?shù)減1}}（八）希爾排序，已驗(yàn)證：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 n,int *dlta,int t){//dlta為步長數(shù)組，t為dlta長度for(int k=0;k<t;++k){//步長數(shù)組shellInsert(a,n,dlta[k]);//步長數(shù)組生成方法不同，效率也不同常見的有}//...9,5,3,2,1 dlta[k]=2^(t=k)+1等等，總之，最后一個一定是1，而且}//應(yīng)該使增量序列中的值沒有除1之外的公因子（九）基數(shù)排序，偽代碼Radix-Sort(A,d){//最大有d位數(shù)for(i=1…d)對每一個數(shù)字，以第i位進(jìn)行排序（調(diào)用任何一種穩(wěn)定排序算法）}效率為O((n+k)*d)//其中n表示待排序數(shù)字?jǐn)?shù)目，d表示位數(shù)，k表示進(jìn)制?；鶖?shù)排序?qū)?nèi)存要求更高，無法原地排序，而且不能有效利用緩存，故對大數(shù)據(jù)量排序時，顯然不如快排，但數(shù)據(jù)量不大時，誰更快一些，取決于底層機(jī)器實(shí)現(xiàn)特性。11，KMP算法int Index_KMP(char *S,char *T,int pos){//利用模式串T的next函數(shù)求T在S中S[pop]//字符之后的位置的KMP算法，其中T非空，1<pos<S.lengthint 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;//找到了串的位置，退出時應(yīng)該j==tLengthelse return 0;}void get_next(char *T,int *next){//這個函數(shù)是重點(diǎn)int i=0, j=-1;//j在前，i在后，next[i]存的是i之前的串的最長公共前后綴長度next[0]=-1;//初始時計(jì)算i=0，即考慮第0個字符，此時j應(yīng)設(shè)為-1，next[i]=-1表i之前//的串沒有公共前后綴while(i<strlen(T)){if(j==-1||T[i]==T[j]){++i;++j;next[i]=j;}//j先自增所以next[i]至少=0else j=next[j];//j最小=-1，利用已求得的next部分}}12，尋找質(zhì)數(shù)（打印小于x的所有質(zhì)數(shù)）常規(guī)方法：2為質(zhì)數(shù)，從3至x，每個能被2整除的數(shù)不是質(zhì)數(shù)，余下的可能質(zhì)數(shù)中緊臨2的為下一質(zhì)數(shù)（這里是3），再從4至x，把被個能被3整除的數(shù)置為非質(zhì)數(shù)……。最后留下的為質(zhì)數(shù)，代碼如下：for(int i=3;i<=n;i+=2)a[i]=true;//去掉2的倍數(shù)，認(rèn)為3以后的奇數(shù)是質(zhì)數(shù)for(i=2;i*i<=n;i++){//對已找出來的每個數(shù)，第一次時是2if(a[i]){//如果i是質(zhì)數(shù)for(int j=i;j*i<=n;j++)a[j*i]=false;//為什么是j=i,而不是j=1呢？因?yàn)樾∮趇*i的數(shù)//一定是小于i的因子可供分解。}}另一方法（摘自維基百科）是：根據(jù)質(zhì)數(shù)分布特性，把x除以6得余數(shù)，有：x=6n+0偶數(shù)；x=6n+1可能是質(zhì)數(shù)；x=6n+2;偶數(shù)；x=6n+3能被3整除；x=6n+4偶數(shù)；x=6n+5可能是質(zhì)數(shù)。因此，只需要考慮6n+1，6n+5及2，3，5三個數(shù)即可，搜索空間一下減少了2/3，運(yùn)行時間是常規(guī)方法的一半，代碼如下：findPrime(){int LIMIT=1000000int nLIMIT=LIMIT-6for(int i=7;i<=nLIMIT;i+=6){sieve[i]=true;//6n+1sieve[i+2]=false;//6n+3sieve[i+4]=true;}int p=5;//2，3不考慮，從5開始while(int j=(p*p)<LIMIT){//從p*p開始，因?yàn)樾∮趐*p的數(shù)一定有一因子小于pp2=p<<1;//每次加2p，因?yàn)閜為奇數(shù)，加p之后是偶數(shù)，不用考慮，這表已知質(zhì)數(shù)while(j<=LIMIT){//j表示p的倍數(shù)，每次增2psieve[j]=false;//j+=p2;}do{p+=2;}while(sieve[p]==false)//找下一質(zhì)數(shù)}}13，八皇后問題（n后問題），代碼已測試對第i個棋子（肯定是在第i行）進(jìn)行放置的時候，x[i]表示第i列是否已經(jīng)放置棋子，而對于兩個對角線，有如下規(guī)律：主對角線上的兩個元素，其x,y坐標(biāo)之差相等，副對角線上的元素，其x,y坐標(biāo)之和相等，即x1-y1=x2-y2或x1+y1=x2+y2，這兩個式子分別等價(jià)于x1-x2=y1-y2和x1-x2=y2-y1。因此，只要abs(x1-x2)==abs(y1-y2)就表示有對角線已經(jīng)放置棋子了，此問題不可放。由此可得解n后問題的遞歸回溯算法如下：void Queeen(int t,int *x){//當(dāng)前在第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++){//這個循環(huán)保證找到所有解，而不是一個解時退出x[t]=i;//int *x用來記錄結(jié)果i,x[i]分別表示第i行棋子放置在x[i]列if(place(t))Backtrack(t+1);//如果放置合法，則繼續(xù)遍歷}}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;}用循環(huán)代替遞歸的回溯法代碼如下：void Queue(int *x){x[1]=0;//列的初始值在第一列之左int k=1;//行的初始值在第一行while(k>0){//當(dāng)未回溯到根以上時，持續(xù)找解x[k]+=1;//列++，這也是為什么初始列設(shè)為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;}//試下一行，列號歸為0else k--;//當(dāng)前方式在第k行找不到最優(yōu)解了，回溯；注意x[k]不用置0，(1)處會接//著往后找可放置的位子。}}初始時，調(diào)用Queue(1,x)即可。這里的代碼省去了初始化等問題，x的下標(biāo)從1開始。14，大整數(shù)乘法void reverse(char chr[],int l){//顛倒數(shù)組 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[]){//函數(shù)返回值是乘積的長度 int la,lb,lresult;//a,b及result的位數(shù)-1int i,j;//循環(huán)控制變量int temp; la=strlen(a)-1;//初始化最后一位lasta,lastblb=strlen(b)-1; reverse(a,la);//將a,b顛倒，下面從個位數(shù)開始算起reverse(b,lb); for(i=0;i <= la;i++)for(j=0;j <= lb;j++){//精華所在，+=用于處理進(jìn)位result[i+j]+=(a[i]-48)*(b[j]-48);//-48是減去字符'0'的ASCII值result[i+j+1]+=result[i+j]/10;//進(jìn)位result[i+j]%=10;//自己留的數(shù)}lresult=i+j+1;//結(jié)果長度最多為i+j+1while(result[lresult] == 0) lresult--;//沒有達(dá)到長度最多的情況，逆序，高位在后if(lresult < 0 ){result[0]=0;lresult=0;}//如果是0for(i=0;i <= lresult/2;i++){ //返回正序的結(jié)果temp=result[i];result[i]=result[lresult-i];result[lresult-i]=temp;} return lresult; }15，一臺計(jì)算機(jī)，只能進(jìn)行賦值，+1，固定次數(shù)的循環(huán)三種原子操作，只能操作0和正整數(shù)。請用偽代碼寫出四則運(yùn)算的實(shí)現(xiàn)。1）加法：add1(x){return x+1;}//+1為原子運(yùn)算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和正整數(shù)，則令0-1=0ret=0; //不能直接用if(x==0)判斷，因?yàn)閕f不是原子操作for(i=2…x)ret=add1(x);return ret;}sub(x,y){ //因?yàn)?-1=0，因此x<y時，令x-y=0for(i=1…y)x=sub1(x);return x;}4）除法：div(x,y){ //令某數(shù)除以0仍為原數(shù)quotient=0; //保存除的結(jié)果tmp=add1(x); //先x增1，運(yùn)算時，每一個x-y結(jié)果不為0時，除的結(jié)果增1for(i=1…x) //最多只可能循環(huán)x次，因?yàn)槌=0的情況，每次至少減1tmp=sub(tmp,y);//如果y=0，則每次tmp都不為0，會加x次1得原數(shù) quotient=add(quotient,sgn(tmp));//如果y!=0，則tmp到0之前quotient都會增return quotient;}sgn(x){ //在x=0時返回0，否則返回1ret=0;for(i=1…x){ret=1;}return ret;}16，memset函數(shù)實(shí)現(xiàn)。加速原理：32位機(jī)器一次傳四個字節(jié)與傳一個字節(jié)耗時差不多#define CPU_ALIGN_MASK 0x03//用來判斷所分內(nèi)存地址是否對齊（4的倍數(shù)） #define CPU_BYTE 4//機(jī)器字節(jié)數(shù)為4，表32位機(jī)器//整數(shù)長度一般是機(jī)器上的字長，已測試void memset(void *paddr, unsigned int size, char value){char *pcaddr = 0; //按字節(jié)復(fù)制時用到的指針unsigned int *piaddr = (unsigned int *)paddr;//按一個個整數(shù)復(fù)制時，用到的指針unsigned int iValue = 0;//iValue表示按一個個整數(shù)復(fù)制時的值int iValueTmp = (unsigned int)value;//iValueTmp表示一個字節(jié)中的值unsigned int iPtrNumber = (unsigned int )paddr;if( iPtrNumber & CPU_ALIGN_MASK ){//看地址是否對齊（4的倍數(shù)）pcaddr = ( char* )piaddr;while( size > 0 ){*pcaddr++ = value;-- size;}//while}//ifiValue |= iValueTmp;//將iValueTmp賦給第一個字節(jié)，0|x，結(jié)果為x #if CPU_BYTE > 1//采用條件編譯iValue |= iValueTmp<<8;//將iValueTmp賦給第二個字節(jié) #if CPU_BYTE > 2iValue |= iValueTmp<<16;//將iValueTmp賦給第三，第四個字節(jié)iValue |= iValueTmp<<24; #if CPU_BYTE > 4iValue |= iValueTmp<<32;iValue |= iValueTmp<<40;iValue |= iValueTmp<<48;iValue |= iValueTmp<<56; #endif #endif #endifwhile( size >= CPU_BYTE ){//之前判斷過地址是4的倍數(shù)（對齊）*piaddr++ = iValue;//一個個整數(shù)賦值size -= CPU_BYTE;} }//memset17，全排列問題遞歸方法：perm(int a[],int k,int m){//產(chǎn)生a[k…m]之間所有的全排列，已驗(yàn)證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]);//回溯}}非遞歸方法思路：第一次拿一個數(shù)，一種排法，第二個數(shù)有兩種（在第一個數(shù)的左/右），第三個數(shù)有三種……，總共有n!種排法，編程實(shí)現(xiàn)偽碼為：for(i=1…n!){//n!種排列，一個i值可對應(yīng)一種排列第一個數(shù)放1for(j=2…n){if(i%j==0)j插到原隊(duì)列尾 //每種排列的計(jì)算方法else j插到第i%j個位置之前i=i/j;}}18，棋盤覆蓋問題，分治法void ChessBoard(int tr,int tc,int dr,int dc,int size){//tr，tc表示棋盤左上角方格的行列號；dr,dcif(size==1)return;//表示特殊方格的行列號，size表示棋盤大小int t=tile++;//L型骨牌編號，tile是全局變量，初始為1s=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,tc,tr+s-1,tc+s-1,s);}….//其實(shí)三個四分之一類似處理…打印出ChessBoard即可看到解！}19，生產(chǎn)者消費(fèi)者問題；哲學(xué)家進(jìn)餐問題；讀者寫者問題生產(chǎn)者消費(fèi)者偽代碼：Var mutex=1,empty=n,full=0//分別表示互斥信號量，可用空間及已生產(chǎn)產(chǎn)品數(shù)var buffer[o…n-1];//存放產(chǎn)品的緩沖區(qū)var in=0,out=0;//存放生產(chǎn)者放產(chǎn)品的指針及消費(fèi)者取產(chǎn)品的指針，用隊(duì)列的形式producer: while(true){produce a item next;;wait(empty);//P先看是否有空間存放，沒有就一直掛起，等消費(fèi)者signal的消息wait(mutex);//實(shí)現(xiàn)對緩沖區(qū)的互斥訪問buffer[in]=nextp;in=(in+1)%n;signal(mutex);signal(full);//進(jìn)行V操作，通知消費(fèi)者，也即full++}consumer:while(true){wait(full);wait(mutex);nextc=buffer[out];out=(out+1)%n;signal(mutex);signal(empty);consumer the item in nextc;}哲學(xué)家進(jìn)餐問題的解決方法為：方法一，奇數(shù)號先拿左邊的筷子，偶數(shù)號先拿右邊的筷子；方法二，兩個筷子都可用才能拿讀者寫者問題用偽碼描述如下：Var rmutex=1,wmutex=1//用來實(shí)現(xiàn)對讀寫變量的互斥訪問var Readcount=0;Reader:while(true){wait(rmutex);//對Readcount的互斥訪問if readcount=0 then wait(wmutex);//如果沒有人讀，則還需要對wmutex進(jìn)行P操作Readcount=Readcount+1;signal(rmutex);…..進(jìn)行讀操作…….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，來自于多米諾牌完美覆蓋的組合數(shù)學(xué)知識。下面給出通解。臺階問題：某樓梯有n級臺階,某人一步最多邁三級,問有多少種不同的方式上樓?引進(jìn)遞歸思想，我們就可找到簡單的方法：設(shè)上ｎ級臺階的方法有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;同時規(guī)定f(0)=1。更一般情況：一般臺階問題：某樓梯有ｎ(ｎ≥1)級臺階，某人一步最多邁ｍ(ｎ≥ｍ≥1)級,有多少種不同的方案上樓。設(shè)上ｎ級臺階的方案有f(n)種，則f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(n-m) (ｎ≥ｍ)，且有f(0)=1;f(1)=1;f(2)=2;...;f(k)=f(0)+f(1)+f(2)+...+f(k-1);22，Tribonaci數(shù)列，斐波那契數(shù)列斐波那契數(shù)列，遞歸時，會重復(fù)計(jì)算，遞推則不會，不過要一數(shù)組來存儲結(jié)果。遞歸時也可以采用備忘錄的方法避免重復(fù)計(jì)算。另一方法是利用矩陣，先整理出如下公式：由此公式遞推有(Fn Fn-1)=(Fn-1 Fn-2)*A=(Fn-2 Fn-3)*A^2=……=（F1 F0）*A^(n-1)剩下的問題，就是求解矩陣A的方冪n。矩陣的冪，在冪n很大時，可采用如下方法進(jìn)行加速，將乘的次數(shù)，從n減少到log2n，用二進(jìn)制表示n:舉個例子：由于以上分析，可得偽代碼如下：class Matrix;//假設(shè)我們已經(jīng)有了實(shí)現(xiàn)乘法操作的矩陣類Matrix MatrixPow(const Matrix& m,int n){//求解矩陣m的n次方Matrix result=Matrix::Identity;//賦初值為單位矩陣Matrix tmp=m;//tmp每次循環(huán)都會增長，依次表示A1,A2,A4,A8for(;n;n>>=1){// 每次右移一位，即依次判斷每位二進(jìn)制是否是1if(n&1)result*=tmp;//如果最低位是1，tmp*=tmp;}}int Fibnacci(int n){Matrix an=MatrixPow(A,n-1);//調(diào)用上面的方法return F1*an(0,0)+F0*an(1,0);//an(0,0)表示an矩的元素（0,0）}Tribonaci數(shù)列求解方式類似，只是增加了一項(xiàng)。23，快速尋找滿足條件的兩個數(shù)，即從數(shù)組中找出兩個數(shù)，使其和等于指定值方法，首先對數(shù)組排序，時間復(fù)雜度為O（nlgn）；然后令i,j分別指向數(shù)組首尾，看a[i]+a[j]是否等于指定的值n，是則返回，否則，比較a[i]+a[j]，如果大于n則j--，如果小于n則i++，循環(huán)結(jié)束條件為i>=j。另一擴(kuò)展的類似問題： 已經(jīng)兩個已經(jīng)排好序的,且長度都為N的數(shù)組,找出兩個數(shù)組合起來第N大的數(shù),即找出它們的中間大數(shù)字，如:x數(shù)組: 1, 7,9,10,30 y數(shù)組:3,5,8,11，12中間大數(shù)為: 8 解法為：先比較兩個數(shù)組的中間元素，如果一個比另一個大，如x[mid]<y[mid], 則y[mid+1...end]和x[0...mid-1]可排除掉，因?yàn)榈贜大數(shù)不可能在這些數(shù)中間，再對剩余的元素x[mid...end]和y[0...mid]調(diào)用相同的過程，即在它們之中尋找第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; //這類題的常規(guī)步驟char *needle;//方法是，初始時dest為src，每次循環(huán)用strstr從中找到oldstr的位置char *temp;//然后把它之前的部分，newstr部分以及之后的部分連接起來放到temp里面dest=src; //循環(huán)末了把temp中復(fù)制為dest(用庫函數(shù)strdup)while(needle=strstr(dest,oldstr)){ //strstr函數(shù)返回串中找到的第一個子串的char*地址temp=(char *)malloc(strlen(dest)+strlen(newstr)-strlen(oldstr)+1);//三截共需內(nèi)存長度strncpy(temp,dest,needle-dest);//第一截，strncpy把源串中的n個字符復(fù)制到目標(biāo)串temp[needle-dest]=’/0’;//標(biāo)識串的結(jié)束, 從中間截?cái)嗟臎]有帶’/0’，所以要處理strcat(temp,newstr);//第二截，newstr自己帶了’/0’strcat(temp,needle+strlen(oldstr));//第三截dest=strdup(temp);//strdup()會另辟一塊內(nèi)存，并不會釋放temp的內(nèi)存free(temp);//strstr函數(shù)}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{//已經(jīng)開始了多行注釋的情況下，找結(jié)尾int mulLinePosEnd=s.find("*/");if(mulLinePosEnd!=string::npos){//如果找到，則輸出余下字符s=s.substr(mulLinePosEnd+2,s.size());if(s.size()!=0)out<<s<<"/n";//如果更智能化start=false;}//未找到則沒有輸出，該行認(rèn)為是注釋掉了}}return 0;}26，大數(shù)階乘的估算公式如求10的7次方階乘的位數(shù)，此題其實(shí)是純粹的數(shù)學(xué)問題。 由斯特林[striling]公式可得： lnN!=NlnN－N+0.5ln(2N*pi) ，而10的7次方階乘的位數(shù)等于： log10(N!)取整后加1 ， log10(N!)=lnN!/ln(10) ，C代碼如下：#include <stdlib.h>#include <math.h>#define N 10000000#define PI 3.14159265int main(int argc,char *argv){int len;len=ceil((N*log(N))-N+0.5log(2*N*PI)/log(10));printf(“%d”,len);// 結(jié)果是65657060return 0;}27，數(shù)的補(bǔ)碼的求法：（1）正數(shù)的補(bǔ)碼：與原碼相同。例如，+9的補(bǔ)碼是00001001。 （2）負(fù)數(shù)的補(bǔ)碼：符號位為1，其余位為該數(shù)絕對值的原碼按位取反；然后整個數(shù)加1。 例如，-7的補(bǔ)碼：因?yàn)槭秦?fù)數(shù)，則符號位為“1”,整個為10000111；其余7位為-7的絕對值+7的原碼0000111按位取反為1111000；再加1，所以-7的補(bǔ)碼是11111001。已知一個數(shù)的補(bǔ)碼，求原碼的操作分兩種情況： （1）如果補(bǔ)碼的符號位為“0”，表示是一個正數(shù)，所以補(bǔ)碼就是該數(shù)的原碼。 （2）如果補(bǔ)碼的符號位為“1”，表示是一個負(fù)數(shù)，求原碼的操作可以是：符號位為1，其余各位取反，然后再整個數(shù)加1。 例如，已知一個補(bǔ)碼為11111001，則原碼是10000111（-7）：因?yàn)榉栁粸椤?”，表示是一個負(fù)數(shù)，所以該位不變，仍為“1”；其余7位1111001取反后為0000110；再加1，所以是10000111。28，二叉排序樹中的查找和插入刪除bool SearchBST(BiTree T,int key,BiTree f,BiTree &p){//二叉排序樹查找//在根T所指二叉排序樹中找關(guān)鍵字為key的節(jié)點(diǎn)，找到則p指向該結(jié)果并返回true//否則p指向查找路徑上訪問的最后一個結(jié)點(diǎn)并返回false，f指向T的雙親，初始為NULLif(!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,key,T,p);}bool InsertBST(BiTree &T,int e){//二叉排序樹插入//當(dāng)二叉排序樹中不存在關(guān)鍵字e時插入e并返回true，否則返回falseif(!SearchBST(T,e,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;}elsereturn false;}bool DeleteBST(BiTree &T,int key){//二叉查找樹中如存在關(guān)鍵字key則刪除之，返回trueif(!T)return false;//不存在關(guān)鍵字等于key的數(shù)據(jù)元素else{if(key==t->data)return Delete(T);else if(key<T->data)return DeleteBST(T->lchild,key);else return DeleteBST(T->rchild,key);}}//DeleteBSTbool Delete(BiTree &p){//從二叉排序樹中刪除結(jié)點(diǎn)p，并重接它的左或右子樹if(!p->rchild){//作了Delete（p）后刪除了結(jié)點(diǎn)p，并p指向代替p的結(jié)點(diǎn)q=p;p=p-> lchild;free(q);//右子樹空則只需要重接它的左子樹}else if(!p->lchild){q=p;p=p-> rchild;free(q);}else{q=p;s=p->lchild;//找前驅(qū)代替p，往左一步，然后一直往右while(s->rchild){q=s;s=s->rchild};//前驅(qū)一定是只有一個子樹的！！！p->data=s->data;//把p的值用它前驅(qū)的值代替if(q!=p)q->rchild=s->lchild;//p的左孩子有右子樹else q->lchild=s->lchild;//表示p往左一步之后，p的左孩子沒有右子樹free(s);}}29，哈希表的查找與插入！（各種處理沖突的方法要理解）int hashsize[]={997,…};//哈希表容量遞增表，一個合適的素?cái)?shù)列表typedef struct{//哈希表結(jié)構(gòu)體ElemType *elem;//存儲元素的數(shù)組int count;//當(dāng)前含有元素個數(shù)int sizeindex;//hashsize[sizeindex]為當(dāng)前容量}HashTable;Status SearchHash(HashTable H,KeyType K,int &p,int &c){在H中查找關(guān)鍵碼為K的元素p=Hash(K);//求得哈希地址，哈希地址一般即為數(shù)組元素下標(biāo)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表示沖突次數(shù)，初始為0else return UNSUCCESS;}Status InsertHash(HashTable &H,Elemtype e){ //查找不成功時，插入數(shù)據(jù)e到哈希表中 c=0;if(SearchHash(H,e.key,p,c))return DUPLICATE;//查找成功else if(c<MAXC){//如果沖突次數(shù)未達(dá)到最大H.elem[p]=e;++H.count;return OK;//p值在SearchHash函數(shù)中已經(jīng)定位好}else{RecreateHashTable(H);return UNSUCCESS;}//沖突到上限，重建Hash表}30，B樹查找過程的偽碼：int SearchBTree(BTree T,int K){//在T中找關(guān)鍵字K，返回結(jié)點(diǎn)或返回K應(yīng)插入的位置p=T;q=NULL;found=FALSE;i=0;//p指向待查找結(jié)點(diǎn)，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,i,1);//1表示在p結(jié)點(diǎn)的第i個key處找到了else return(q,i,0);//0表示在q結(jié)點(diǎn)的第i個key處應(yīng)該插入K}每個結(jié)點(diǎn)的形狀如下所示：(n,A0,K1,A1,K2,…,Kn,An)//Ai表示指針，也即p->ptr[i]中的ptr[i]。Ki表示關(guān)鍵字，即p->key[1..n]中的k[i]，n表示該結(jié)點(diǎn)中有的關(guān)鍵字的個數(shù)。B樹的插入刪除情況，看《數(shù)據(jù)結(jié)構(gòu)》，要能夠畫出圖。31，求二叉樹中節(jié)點(diǎn)的最大距離（遞歸，思考非遞歸如何實(shí)現(xiàn)）根據(jù)相距最遠(yuǎn)的兩個節(jié)點(diǎn)一定是葉子結(jié)點(diǎn)這個規(guī)律，我們可以分兩種情況：如果經(jīng)過根結(jié)點(diǎn)，則該兩個結(jié)點(diǎn)U和V一定是左右子樹中離根結(jié)點(diǎn)最遠(yuǎn)的結(jié)點(diǎn)；如果不經(jīng)過根結(jié)點(diǎn)，則它們一定屬于左右子樹之一，問題遞歸。根據(jù)以上分析，可用分治法來解，代碼如下：struct NODE{NODE* pLeft;//左孩子NODE* pRight;//右孩子int nMaxleft;//左子樹中的葉子到根最長距離int nMaxright;//右子樹中的葉子到根最長距離char chValue;//本結(jié)點(diǎn)的值};int nMaxLen=0;//尋找樹中最長的兩段距離void FindMaxLen(NODE* pRoot){if(pRoot==NULL)return;//如果是葉子結(jié)點(diǎn)，返回if(pRoot->pLeft==NULL)pRoot->nMaxLeft=0;//左子樹葉子到根最長距離為0if(pRoot->pRight==NULL)pRoot->nMaxRight=0;//右子樹為空情況if(pRoot->pLeft!=NULL)FindMaxLen(pRoot->pLeft);//左右子樹不空時分別遞歸if(pRoot->pRight!=NULL)FindMaxLen(pRoot-> pRight);// 遞歸時可能會改變nMaxLenif(pRoot->pLeft!=NULL){//計(jì)算左子樹葉子到根最長距離int nTempMax=0;if(pRoot->pLeft->nMaxLeft> pRoot->pLeft->nMaxRight)nTempMax= pRoot->pLeft->nMaxLeft;elsenTempMax= pRoot->pLeft->nMaxRight;pRoot->nMaxLeft=nTempMax+1;//取左子樹的左右子樹中較長者加1}if(pRoot-> pRight!=NULL){//計(jì)算右子樹葉子到根最長距離int nTempMax=0;if(pRoot-> pRight ->nMaxLeft> pRoot-> pRight ->nMaxRight)nTempMax= pRoot-> pRight ->nMaxLeft;elsenTempMax= pRoot-> pRight ->nMaxRight;pRoot->nMaxLeft=nTempMax+1;//取右子樹左右子樹中較長者加1}if(pRoot->nMaxLeft+pRoot->nMaxRight>nMaxLen)//更新最長距離nMaxLennMaxLen=(pRoot->nMaxLeft+pRoot->nMaxRight;}32，由前序中序或者中后序建二叉樹（遞歸，思考非遞歸實(shí)現(xiàn)）給定前序中序序列，要求重建二叉樹。方法是：先掃前序的第一個字符，建根，然后以前序的第一個字符為分界，把中序劃成兩段，分別遞歸。代碼如下：#define TREELEN 6//為后序調(diào)用實(shí)現(xiàn)簡單，直接用宏定義結(jié)點(diǎn)數(shù)目struct NODE{NODE* pLeft;NODE* pRight;char chValue;};void ReBuild(char* pPreOrder,char* pInOrder,int nTreeLen,NODE** pRoot){//已經(jīng)驗(yàn)證if(pPreOrder==NULL||pInOrder==NULL)return;//檢查邊界條件，前中序是否有一為空NODE* pTemp=new NODE;pTemp->chValue=*pPreOrder;pTemp->pLeft=NULL;pTemp->pRight=NULL;if(*pRoot==NULL)*pRoot=pTemp;//如果節(jié)點(diǎn)為空，把當(dāng)前結(jié)點(diǎn)復(fù)制到根結(jié)點(diǎn)if(nTreeLen==1)return;//如果當(dāng)前樹長度為1，那么已經(jīng)是最后一個結(jié)點(diǎn)了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);//計(jì)算左子樹長度int nRightLen=0;nRightLen=nTreeLen-nLeftLen-1;//計(jì)算右子樹長度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，分層遍歷二叉樹（用隊(duì)列）void PrintNodeByLevel(NODE* root){//已驗(yàn)證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){//經(jīng)過測試的，呵呵，不錯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){//由哈夫曼構(gòu)造哈夫曼編碼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;//從葉子開始往根走，對應(yīng)編碼從尾往前int c,f;//c表示當(dāng)前結(jié)點(diǎn)，f表示其父親for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){//當(dāng)其父不是樹根時退出if(HT[f].lchild==c)cd[--start]='0';//如是其父的左孩子，置’0’else cd[--start]='1';否則置1}for(j=0;j<n&&cd[j]=='*';j++);//去掉未滿的編碼內(nèi)存HC[i]=(char*)&cd[j];}delete cd;return HC;}35，打十槍中90環(huán)的各種可能性打印解答：方法一，用10層的循環(huán)；方法二，用遞歸。用一個全局的數(shù)組store[10]存儲每次的環(huán)數(shù)，一個全局整數(shù)sum記錄可能性的種數(shù)。代碼如下：//代碼已驗(yàn)證#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表示剩余的環(huán)數(shù)，num表剩余可打的槍數(shù)，初值是9if(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，求一個串的各所有子集輸出（組合）算法四步：第一步，從首字符到尾字符循環(huán)；第二步，循環(huán)到的當(dāng)前字符加到out串尾，輸出當(dāng)前的out串；第三步，如果循環(huán)到的字符i后面還有字符，遞歸，后面的字符為起始字符，重復(fù)二三步；第四步，如果循環(huán)到的字符i后面沒有其它字符了，退出循環(huán)。void combine(char in[],char out[],int length,int rec int start){ //代碼已驗(yàn)證//in[],out[]為輸入輸出串，length為輸入串的長度，rec為當(dāng)前遞歸時,out串尾位置//start為本次遞歸時in[]的循環(huán)開始位置int i;//start表示此次遞歸，只考慮in[start]后的元素for(i=start;i<length;i++){out[rec]=in[i];//選擇的起點(diǎn)為i時，輸出，然后遞歸，完事后起點(diǎn)后移out[rec+1]=’/0’;//標(biāo)記串尾，為輸出用。起點(diǎn)后移時rec并未移，因此printf(“%s”,out);if(i<length-1)combine(in,out,length,rec+1,i+1);}}37，輸m，n兩個數(shù)，從數(shù)列1，2，3，……中隨意選幾個數(shù)，使其和為m求所有的可能，并輸出之（0-1背包類似，重量（可取的數(shù)的個數(shù)）不限，只要求價(jià)值總和等于m）void calFun(int m,int n){ //代碼已驗(yàn)證if(m<1||n<1||(n==1&&m!=1))return;//遞歸退出條件if(m==n){//如果找到了一個解（n本身即為m）pOut[n]=1;//pOut[i]=1表示整數(shù)i選，為0表不選，初始全為0for(int i=1;i<=nVal;i++)if(pOut[i])cout<<i<<”,”;cout<<endl;pOut[n]=0;//回溯，因要求所有可能，而pOut[]為全局變量，所以不能影響后續(xù)求解}calFun(m,n-1);//不取n時進(jìn)行遞歸，因?yàn)槌跏紁Out[n]=0，所以不需要管pOut[n]=1;//取n，如果m==n，這里遞歸也會在下一輪時因?yàn)閙<1返回，所以沒關(guān)系calFun(m-n,n-1);//進(jìn)行遞歸pOut[n]=0;//回溯，防止影響后續(xù)求解}38，漢諾塔的非遞歸，遞歸實(shí)現(xiàn)遞歸實(shí)現(xiàn)，不需要多說： void Hannoi(int n,char a,char b,char c) {if(n==1)Move(1,a,c);else{Hannoi(n-1,a,c,b);Move(n,a,c);Hannoi(n-1,b,a,c);} } 非遞歸實(shí)現(xiàn)的方法思想：當(dāng)盤子的個數(shù)為n時，移動的次數(shù)應(yīng)等于2^n - 1（有興趣的可以自己證明試試看）。后來一位美國學(xué)者發(fā)現(xiàn)一種出人意料的簡單方法，只要輪流進(jìn)行兩步操作就可以了。首先把三根柱子按順序排成品字型，把所 有的圓盤按從大到小的順序放在柱子A上，根據(jù)圓盤的數(shù)量確定柱子的排放順序：若n為偶數(shù)，按順時針方向依次擺放 A B C；若n為奇數(shù)，按順時針方向依次擺放 A C B。 （1）按順時針方向把圓盤1從現(xiàn)在的柱子移動到下一根柱子，即當(dāng)n為偶數(shù)時，若圓盤1在柱子A，則把它移動到B；若圓盤1在柱子B，則把它移動到C；若圓盤1在柱子C，則把它移動到A。 （2）接著，把另外兩根柱子上可以移動的圓盤移動到新的柱子上。即把非空柱子上的圓盤移動到空柱子上，當(dāng)兩根柱子都非空時，移動較小的圓盤。這一步?jīng)]有明確規(guī)定移動哪個圓盤，你可能以為會有多種可能性，其實(shí)不然，可實(shí)施的行動是唯一的。 （3）反復(fù)進(jìn)行（1）（2）操作，最后就能按規(guī)定完成漢諾塔的移動。代碼如下： struct st{//用來表示每根柱子的信息，其實(shí)就是棧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為偶數(shù)，按順時針方向依次擺放 A B Cif (n%2 == 0){ta[1].name = 'B';ta[2].name = 'C';}else{ //若n為奇數(shù)，按順時針方向依次擺放 A C Bta[1].name = 'C';ta[2].name = 'B';}}void Hannuota(st ta[], long max){int k = 0; //累計(jì)移動的次數(shù)int i = 0;int ch;while (k < max){//按順時針方向把圓盤1從現(xiàn)在的柱子移動到下一根柱子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){ //把非空柱子上的圓盤移動到空柱子上，當(dāng)兩根柱子都空時，移動較小的圓盤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; //輸入圓盤的個數(shù)st ta[3]; //三根柱子的信息用結(jié)構(gòu)數(shù)組存儲Creat(ta, n); //給結(jié)構(gòu)數(shù)組設(shè)置初值long max = Pow(2, n) - 1;//動的次數(shù)應(yīng)等于2^n - 1Hannuota(ta, max);//移動漢諾塔的主要函數(shù)return 0;}39，謎宮求解typedef struct{int ord;//通道塊在路徑上的序號PopType seat;//通道在謎宮中的坐標(biāo)位置int di;//從此通道塊走向下一塊通道塊的“方向”}SElemType;bool MazePath(MazeType maze,PosType start,PosType end){//找謎宮maze從start到end的路InitStack(S);curpos=start;//設(shè)定當(dāng)前位置為startcurstep=1;//探索的第一步do{if(Pass(curpos)){//如果當(dāng)前位置是可通過的FootPrint(curpos)//留下路跡，打印一下遍歷過程，這行可不要e= SElemType (curstep,curpos,1);push(S,e);//加入到路徑棧中if(curpos==end)return true;//到達(dá)出口curpos=NextPos(curpos,1);//下一位置是當(dāng)前位置的東鄰curstep++;}else{//如果當(dāng)前位置是不可通過的，看棧頂元素再作決定if(!StackEmpty(S)){//如果棧上有元素pop(s,e);while(e.di==4&&! StackEmpty(S)) pop(s,e);//直到棧頂元素有下一方向?yàn)橹筰f(e.di<4){//如果棧中彈出的元素有方向可走e.di++;push(S,e);//標(biāo)記為探索下一個方面curpos=NextPos(e.seat,e.di);//將該方向上的相鄰塊置為當(dāng)前塊}}}while(!StackEmpty(S));}return false;}40，后綴表達(dá)式求值OperandType EvaluateExpression(){InitStack(OPTR);Push(OPTR,’#’);//初始化符號棧InitStack(OPND);c=getchar();//初始化操作數(shù)棧while(c!=’#’||GetTop(OPTR)!=’#’){如果得到的不是結(jié)束符if(!In(c,OP)){Push(OPND,c);c=getchar();}//如果不是操作符，則直接進(jìn)棧elseswitch(Precede(GetTop(OPTR),c)){//如是操作符則比較它與棧頂符的優(yōu)先級case ‘<’:Push(OPTR,c);c=getchar();break;//棧頂元素優(yōu)先級低case ‘=’:Pop(OPTR,x);c=getchar();break;//如果是括號，則消去一對case ‘>’:Pop(OPTR,theta);//如果優(yōu)先級大則原來的部分先運(yùn)行Pop(OPND,Operate(a,theta,b)); //注意此處沒有g(shù)etchar();break;//所以會繼續(xù)判斷所得符號與棧頂元素的優(yōu)先級}}//whilereturn GetTop(OPND);//返回最后的操作數(shù)棧頂元素，正確時應(yīng)該棧只有一個元素}41，十進(jìn)制數(shù)N轉(zhuǎn)為d進(jìn)制數(shù)，一個簡單的實(shí)現(xiàn)方法基于如下原理：N=(N/d)*d+N%d，代碼借助棧實(shí)現(xiàn)如下：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的所有子串中的最大的質(zhì)數(shù)。如 n=5617，則為617。int maxPrimeSub(int n){// 明顯應(yīng)該從最長的串開始判斷起！先是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的偶數(shù)else for(int i=3;i*i<=n;i+=2){if(n%i==0)return false;}return true;}另：EMC筆試題，求一個非負(fù)整型數(shù)組非鄰接子序列的最大和，要求O(N)一遍掃瞄，記住前兩個位置的解f(i)=max（a[i]+f(i-2),f(i-1)）43，一棵樹，每個節(jié)點(diǎn)有三個域，data域，child域指向孩子節(jié)點(diǎn)，next域指向右邊最近的兄弟節(jié)點(diǎn)。 寫程序，將所有的堂兄弟節(jié)點(diǎn)都 連起來。（比如一個節(jié)點(diǎn)A及其右兄弟節(jié)點(diǎn)B，A的子節(jié)點(diǎn)有CDEF，B的子節(jié)點(diǎn)有GH，初始狀態(tài)是沒有F到G的指針的，現(xiàn)在讓你把這樣的空缺都連起來）。劉光遠(yuǎn)寫出遞歸的形式，讓改成非遞歸的。用層序遍歷的隊(duì)列方式。44， 有一個矩形區(qū)域，分成N*M個格子，求從最左上角的格子走到最右下角的格子的最短時間，不能斜著走，只能豎著或者橫著走，而且格子與格子之間花費(fèi)的時間是不同的 。同樣，不讓用遞歸。三種方法：一，遞歸，右下角的一定是通過前兩個格子中最小路徑得到的；二，是用動態(tài)規(guī)劃的填表法；三，這其實(shí)是一個求單源最短路徑的問題，因此可用dijstra最短路徑遞增的貪心算法，用圖表示寫代碼可能會難一點(diǎn)，動態(tài)規(guī)劃的填表法更易寫代碼。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為模式串，帶有正則表達(dá)式符號，t為待匹配字符串//匹配成功返回位置，否則返回-1if(t==NULL||p==NULL)return -1;//對空串的處理，當(dāng)然也可以其它處理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,i,anych);}//如果是*else if(p[j]=='*'&&p[j-1]!='.'){i+=next(t,i,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循環(huán)寫成遞歸的形式，就是對于t的每一個后綴串，看是否某個串的前綴能完全匹配p，循環(huán)到第一個這樣的后綴時，返回此后綴首下標(biāo)；遞歸中判斷當(dāng)前字符，以決定跳若干步之后再遞歸調(diào)用。為保留next函數(shù)中可訪問p[i-1]的內(nèi)容，可在遞歸時，把p[i-1]的地址作為參數(shù)。46, 兩個相同長度的整型數(shù)組A、B，長度為n?，F(xiàn)從兩個數(shù)組中，各抽出S個數(shù)，形成兩個新的數(shù)組C、D。實(shí)現(xiàn)一個算法，保證數(shù)組CD的內(nèi)積最大，并分析時間和空間復(fù)雜度。題目其實(shí)就是要求在兩個數(shù)組中找出積最大的前S對數(shù)：1. 對兩個數(shù)組按降序排列，2. 設(shè)置兩對指針，分別指向兩個數(shù)組的首尾元素，3. 計(jì)算首尾指針對指向元素的積，比較兩個積的大小，取乘積較大的兩個元素，4. 指向乘積較大的元素對的指針向前移動（或往回移動，對于尾指針對），元素對計(jì)數(shù)器加15. 重復(fù)1－4，直到找到S對元素。這是基于在給定數(shù)組中，對于所有正數(shù)，兩個最大正數(shù)的乘積必定是最大，對于所有負(fù)數(shù)，兩個最小負(fù)數(shù)的乘積必定是最大，但是它們哪個更大則不確定；至于時間復(fù)雜度主要看排序算法47，一個網(wǎng)頁，在每天記錄一個訪問量，然后給你一個時間區(qū)間，找出這個時間區(qū)間內(nèi)訪問量最多的那一天?？赡芙?jīng)常做這個查詢操作，而且區(qū)間大小是隨意的。請問如果設(shè)計(jì) 以保證高性能。（歐陽劉彬說對時間做B+索引）。我想到的一個方法是：RMQ(Range Minimum/Maximum Query)問題是求區(qū)間最值問題。你當(dāng)然可以寫個O(n)的,但是萬一要詢問最值1000000遍，估計(jì)你就要掛了。這時候你可以放心地寫一個線段樹（前提是不寫錯）O（logn)的復(fù)雜度應(yīng)該不會掛。但是，這里有更牛的算法，就是ST算法，它可以做到O(nlogn)的預(yù)處理，O(1)地回答每個詢問。來看一下ST算法是怎么實(shí)現(xiàn)的(以最大值為例）： 首先是預(yù)處理，用一個DP解決。設(shè)a[i]是要求區(qū)間最值的數(shù)列，f[i,j]表示從第i個數(shù)起連續(xù)2^j個數(shù)中的最大值。例如數(shù)列3 2 4 5 6 8 1 2 9 7 ,f[1，0]表示第1個數(shù)起，長度為2^0=1的最大值，其實(shí)就是3這個數(shù)。f[1，2]=5，f[1，3]=8，f[2，0]=2，f[2，1]=4……從這里可以看出f[i,0]其實(shí)就等于a[i]。這樣，Dp的狀態(tài)、初值都已經(jīng)有了，剩下的就是狀態(tài)轉(zhuǎn)移方程。我們把f[i，j]平均分成兩段（因?yàn)閒[i，j]一定是偶數(shù)個數(shù)字），從i到i+2^(j-1)-1為一段，i+2^(j-1)到i+2^j-1為一段(長度都為2^（j-1）)。用上例說明，當(dāng)i=1，j=3時就是3,2,4,5 和 6,8,1,2這兩段。f[i，j]就是這兩段的最大值中的最大值。于是我們得到了動規(guī)方程F[i,j]=max（F[i，j-1],F[i+2^(j-i)，j-1]）。接下來是得出最值，也許你想不到計(jì)算出f[i，j]有什么用處，一般毛想想計(jì)算max還是要O(logn)，甚至O(n)。但有一個很好的辦法，做到了O（1）。還是分開來。如在上例中我們要求區(qū)間[2，8]的最大值，就要把它分成[2,5]和[5,8]兩個區(qū)間，因?yàn)檫@兩個區(qū)間的最大值我們可以直接由f[2，2]和f[5，2]得到。擴(kuò)展到一般情況，就是把區(qū)間[l，r]分成兩個長度為2^n的區(qū)間（保證有f[i，j]對應(yīng)）。直接給出表達(dá)式：k:=ln((r-l+1)/ln(2)); ans:=max(F[l，k],F[r-2^k+1,k]);這樣就計(jì)算了從i開始，長度為2^t次的區(qū)間和從r-2^i+1開始長度為2^t的區(qū)間的最大值（表達(dá)式比較煩瑣，細(xì)節(jié)問題如加1減1需要仔細(xì)考慮48，有一個整數(shù)n，將n分解成若干個整數(shù)之和，問如何分解能使這些數(shù)的乘積最大，輸出這個乘積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最好。解答： 假設(shè)輸入為N，可以分解成為K個相同的數(shù)R以及一個余數(shù)W的集合。N = K*R + W;那么問題轉(zhuǎn)化為求：Val = R^K * W的極值問題，條件是N=K*R+W。為使問題簡化，先不考慮W，之后再作討論。于是問題轉(zhuǎn)化為：條件為N1=K*R時，求Val=R^K的極值（心中應(yīng)該記住，終極任務(wù)是求R，因此K可以試著換成N1/R表示，也即，在Val中，只把R當(dāng)成變量）。Val= R^K; 兩邊取對數(shù)，有l(wèi)n(Val) = (N1/R)ln(R) ，令F(R) = (N1/R)ln(R),對這個式子取導(dǎo)數(shù)利用求導(dǎo)公式(u/v)'=(u'v-uv')/v^2，得到下式 ：f(R) = N1*(1-lnR)/(R^2) ，當(dāng)這個f(R) 為零的時候，F(R)取到極值 。因此，當(dāng)R = e 的時候，取到極值（e= 2.7*****），因此取到R =3現(xiàn)考慮余數(shù)情況，因除數(shù)為3，余數(shù)只有兩種情況，1或2，當(dāng)為1時，顯示應(yīng)該讓其中一個數(shù)為4，而當(dāng)余數(shù)為2時，顯示應(yīng)該把2提出來，乘以其余分解得到的3。因?yàn)?*3>2+349，數(shù)據(jù)結(jié)構(gòu)134頁中序遍歷線索二叉樹，及二叉樹的中序線索化！bool InOrderTraverse_Thr(BiThrTree T){// 中序遍歷線索二叉樹p=T->lchild;//T指向頭結(jié)點(diǎn)，p指向根結(jié)點(diǎn)while(p!=T){while(p->LTag==’LINK’)p->plchild;//中序的第一個結(jié)點(diǎn)，第一個沒有左子樹的結(jié)點(diǎn)if(!visit(p))return false;//訪問自己while(p->RTag==’Thread’&&p->rchild!=T){//若右子樹無則用線索訪問p=p->rchild;visite(p);}p=p->rchild;//至某個有右子樹的結(jié)點(diǎn)后，移到右子樹上，繼續(xù)回到第一步循環(huán)return true;}}bool InOrderThreading(BiThrTree &Thrt,BiThrTree T){//中序遍歷二叉樹T并完成中序線索化，Thrt指向線索化后的頭結(jié)點(diǎn)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指向前驅(qū)InThreading(T);//中序遍歷進(jìn)行線索化pre->rchild=Thrt;pre->RTag=Thread;//pre指向最后一結(jié)點(diǎn)，最后一個結(jié)點(diǎn)線索化Thrt->rchild=pre;//Thrt與末結(jié)點(diǎn)互指}return true;}void InThreading(BiThrTree p){if(p){InThreading(p->lchild);//左子樹線索化if(!p->lchild){p->LTag=Thread;p->lchild=pre;}//前驅(qū)線索化if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}//后繼線索化pre=p;//切換前驅(qū)InThreading(p->rchild);//右子樹線索化}}50，電話號碼對應(yīng)英語單詞number[i]存放電話電碼的第i個數(shù)字；answer[i]用來存放這個電話在按鍵中的第幾個字母；c[10][10]={“”,””,”ABC”,”DEF”,”GHI”,”JKL”,”MNO”,”PQRS”,”TUV”,”WXYZ”};int total[10]={0,0,3,3,3,3,3,4,3,4};如果電話號碼第一位數(shù)字是4，answer[0]是0，c[number[0]][answer[0]]=G;于是遍歷各種可能的字母串的代碼如下：while(true){ //代碼已驗(yàn)證//n為電話號碼長度,初始化answer[n]數(shù)組各元素均為0for(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的號碼的可能對應(yīng)的字符換一下，繼續(xù)輸出，輸出后k=n-1}else{answer[k]=0;k--;//把a(bǔ)nswer[k]置0，然后，開始考慮前一個電話號碼，注//意此處無break;}}if(k<0)break;}遞歸算法也許更好理解：void RecursiveSearch(int *number,int *answer,int index,int n){//已經(jīng)讀取到了number[index]if(index==n){//下標(biāo)最大為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);//考慮當(dāng)前字符各種情況，然后遞歸//注意用answer[n]數(shù)組來保存遞歸時各種分支的選擇，傳給葉子}}51，編程之美：不要被階乘嚇倒階乘(Fctorial)N！。問題為：1)，給定一個整數(shù)N，那么N！末尾有多少個零呢？例如N=10，N！=3628800，答案為2；2），求N！中二進(jìn)制表示中最低位1的位置解答：（1）規(guī)律是，每出現(xiàn)一個能被5整除的數(shù)，便會往末尾貢獻(xiàn)一個0，因?yàn)?之前肯定出現(xiàn)了2，4等數(shù)字，相乘之后一定是10的倍數(shù)，每出現(xiàn)一個能被5^2整除的數(shù)貢獻(xiàn)兩個0……。因此，表示為公式是：Z=[N/5]+[N/5^2]+[N/5^3]+……[N/5]表示小于N的數(shù)中，能被5整除的數(shù)的個數(shù)，[N/5^2] 表示小于N的數(shù)中，能被5^2整除的數(shù)的個數(shù)……。代碼求解零的個數(shù)如下：ret=0;while(N){ret+=N/5;//N/5表示小于N的數(shù)中，5的倍數(shù)有多少個N/=5;//N/=5之后第二輪循環(huán)計(jì)算的是小于N的數(shù)中5^2的倍數(shù)}解答：（2）問題與（1）一樣，只是數(shù)制變?yōu)?進(jìn)制，代碼如下：int lowerstOne(int N){int Ret=0;while(N){N>>=1;//順序跟上面不一樣，上面也可以寫成這樣，結(jié)果是一樣的Ret+=N;}return Ret;}52，編程之美：1的數(shù)目（十進(jìn)制里面，分個位數(shù)，十位數(shù)，百位數(shù)等一個個分析，得出規(guī)律），第二問記住答案！問題是：（1），寫一個函數(shù)f(N)，返回1到N之間，出現(xiàn)的“1”的個數(shù)，比如f(12)=5；（2）在32位整數(shù)范圍內(nèi)，滿足條件”f(N=N)”的最大的N是多少？解答：（1）分析如下，假設(shè)N=abcde，如現(xiàn)在需要計(jì)算百位數(shù)上出現(xiàn)1的次數(shù)，分三種情況：如果百位數(shù)上為0，則可知道百位數(shù)上可能出現(xiàn)1的次數(shù)由更高位決定，比如12013，百位數(shù)上出現(xiàn)1的情況可能是100—199，1100—1199，2100—2199，……共1200個。也就是由比百分位高的部分的數(shù)字12所決定，并且等于12*100（百位數(shù)代表的值）；如果百位數(shù)上為1，則可知百位上出現(xiàn)1的情況不僅包括剛才的，還包括百位數(shù)為1時的情況，比如12113比12013多了12100—12113這14個1，這是受低位決定的，等于低位數(shù)字的值+1（13+1）。如果百位上的數(shù)字大于1（即為2—9），則百位上可能出現(xiàn)1的情況也只由高位數(shù)字決定，為（高位數(shù)字+1）*100。由于以上分析，代碼如下：long Sum1s(ulong n){ulong iCount=0;//1的個數(shù)計(jì)數(shù)器ulong iFactor=1;//iFactor每次循環(huán)按10，100，1000等遞增ulong iLowerNum=0;//低位數(shù)字，即從當(dāng)前位往右的所有數(shù)字之值ulong iCurrNum=0;//當(dāng)前位ulong iHigerNum=0;//高位數(shù)字，即從當(dāng)前位往左的所有數(shù)字之值while(n/iFactor!=0){//n大于iFactoriLowerNum=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;//每次循環(huán)改變當(dāng)前位數(shù)}return iCount;}53，編程之美：子數(shù)組中N-1項(xiàng)的最大乘積(掃瞄一遍，記住符號，最小負(fù)數(shù)，0的個數(shù)等，分析符號即可得解)54，判斷鏈表相交的幾種方法：尾結(jié)點(diǎn)是否相同；結(jié)點(diǎn)的地址計(jì)數(shù)；一個尾鏈到另一個首，看是否會出現(xiàn)環(huán)；55，將中綴表達(dá)式轉(zhuǎn)換為逆波蘭式，方法：1） 構(gòu)造一運(yùn)算符棧，此棧中運(yùn)算符遵循越往棧頂，優(yōu)先級越高的原則。2） 中綴表達(dá)式首尾為’#’字符，優(yōu)先級最低，各符號的優(yōu)先級關(guān)系必須有個優(yōu)先級表。3） 從左到右分析中綴串，如遇數(shù)字，則輸出；如遇運(yùn)算符，則比較優(yōu)先關(guān)系，：如果該運(yùn)算符優(yōu)先級高于棧頂元素則入棧，否則將棧頂元素彈出并輸出，直至棧頂元素優(yōu)先級低于掃到的運(yùn)算符，再將掃到的運(yùn)算符進(jìn)棧。4） 重復(fù)3）直至串尾，最后連續(xù)將棧退空。56，整數(shù)分割問題。將一個正整數(shù)表示為一系列整數(shù)之和，如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有： 65+14+2，4+1+13+3，3+2+1，3+1+1+12+2+2，2+2+1+1，2+1+1+1+1+11+1+1+1+1+1共11種表示方法。解答：用q(n,m)表示找出n劃分為不大于m的整數(shù)的劃分種數(shù)，如：q(6,4)=9遞歸式有：1 m=1或n=1q(n,n) n<mq(n,m)= 1+q(n,n-1) n=mq(n,m-1)+q(n-m,m) n>m>157，歸并排序求逆序?qū)λ枷?#xff1a;歸并排序的同時，記錄逆序?qū)Φ臄?shù)目，每次將某兩相鄰字段s1和s2進(jìn)行插入歸并時，若所選最小元素來自于s2的第j個元素(記作s2j)時，逆序?qū)?shù)目Total+=s1.length-i（其中i為歸并時s1中當(dāng)前的下標(biāo)），因?yàn)閟1中i之后的元素也必與s2中的j元素是逆序?qū)?#xff08;比s2j大）。58，1，0序列生成（有道難題）一個二進(jìn)制序列由下面的偽代碼生成： String A = "0" While (A的長度小于等于n)創(chuàng)建一個和A一樣長度的字符串BFor i=0,1,...length(A)-1If (i 是完全平方數(shù))B[i] = 1-A[i]ElseB[i] = A[i]令A(yù) = A + B (即將B拼接在A后面) End While Return A 請注意，在上面的偽代碼中，A[i]和B[i]分別表示字符串A和B中下標(biāo)為 i 的字符（下標(biāo)編號從0開始）。對“完全平方數(shù)”的定義是，對于整數(shù) i，存在整數(shù) j，使得 i = j * j，則稱 i 為完全平方數(shù)。下面具體說明序列生成的過程：如果n=7，則在每一輪迭代中，A的取值依次為：0, 01, 0110, 01101010，所以最終產(chǎn)生的二進(jìn)制序列就是0,1,1,0,1,0,1,0 請返回上述序列中下標(biāo)為n的數(shù)字（該序列的下標(biāo)從0開始）n=0 輸出0 n=1 輸出1 如果n不是2的冪時，它會夾在兩個2的冪中間，設(shè)為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);}}以下部分主要為動態(tài)規(guī)劃：59，矩陣連乘問題此類問題屬于動態(tài)規(guī)劃法解決范圍。動態(tài)規(guī)劃法能解決的問題，基本上都可以用遞歸方法解決。使用動態(tài)規(guī)劃法的好處在于，動態(tài)規(guī)劃法是自底向上計(jì)算，在計(jì)算過程中保存子問題的解，避免了重復(fù)計(jì)算，直接的遞歸調(diào)用則會導(dǎo)致重復(fù)計(jì)算，浪費(fèi)時間。因此，動態(tài)規(guī)劃法的兩個重要特點(diǎn)是：最優(yōu)子結(jié)構(gòu)的遞歸特性和重疊子問題。遞歸方法解決時，可以采用備忘錄的方法，同樣達(dá)到動態(tài)規(guī)劃的目的。動態(tài)規(guī)劃法的另一個重要特征是“選擇”，每一步都是作一次選擇，在前一次已經(jīng)計(jì)算過子問題的最優(yōu)選擇的基礎(chǔ)上，當(dāng)前選擇如何得到（可能通過一次循環(huán)來嘗試各個值），以及如何將這一選擇描述成問題的解。根據(jù)這些問題的特點(diǎn)可知。求解動態(tài)規(guī)劃法類型的問題，第一步就是抽象成數(shù)學(xué)表示并列出遞歸式，有了遞歸式，便可寫出偽代碼。矩陣連乘問題抽象成數(shù)學(xué)問題：第一步，使用一個數(shù)學(xué)式子來表示最優(yōu)解。令m[i][j]表示矩陣A[i…j]連乘時，所需要的最小相乘次數(shù)，p[n+1]存儲的是每個矩陣的行數(shù)及最后一個矩陣的列數(shù)。第二步，由第一步可得遞歸式為：第三步，寫出（偽）代碼：void MatrixChain(int *p,int n,int **m,int **s){//s用來保存m[i][j]的劃分點(diǎn)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為每個鏈?zhǔn)?#xff0c;最后一個鏈?zhǔn)资莕-r+1int j=i+r-1;//j為鏈尾，因?yàn)閜下標(biāo)從0開始，所以m下標(biāo)從1開始m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//對每個鏈，賦初始劃分值為在鏈?zhǔn)讋澐謘[i][j]=i;//存儲劃分點(diǎn)for(int k=i+1;k<j;k++){//依次考察從其它點(diǎn)劃分的情況int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){ //如果從k點(diǎn)劃分更優(yōu)，則更新解并記下劃分點(diǎn)m[i][j]=t;s[i][j]=k;}}}}}第四步，構(gòu)造最優(yōu)解。第三步的算法，只是記錄了最優(yōu)時的運(yùn)算次數(shù)，并不知從哪劃分，不過由二維數(shù)組s可構(gòu)造出最優(yōu)解；void TraceBack(int i,int j,int **s){//構(gòu)造A[i…j]連乘時的各個矩陣運(yùn)算次序if(i==j)return;TraceBack(i,s[i][j],s);//s[i][j]記錄的是A[i…j]中間的那個劃分點(diǎn)kTraceBack(s[i][j]+1,j,s);cout<<”乘A”<<i<<”,”<<s[i][j]<<”和A”<<s[i][j]+1<<”,”<<j<<endl;}補(bǔ)充一，遞歸解法偽代碼：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; //上一行最后一項(xiàng)會不斷加起來，而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;}補(bǔ)充二，備忘錄解法，也是用遞歸，過程與遞歸解法一樣只是增加判斷及記錄兩樣int MemorizedMatrixChain(int n,int **m,int **s){for(int i=1;i<=n;i++)for(int i=1;i<=n;i++)m[i][j]=0;//初始化，遞歸時，判斷到m[i][j]>0則表示計(jì)算過，直接返回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; //上一行最后一項(xiàng)會不斷加起來，而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數(shù)組記錄中間結(jié)果return u;}時間效率，動態(tài)規(guī)劃解法為O（n^3），遞歸解法為O(2^n)。60，最長公共子序列問題最長公共子序列中，子序列的定義是一個給定序列的子序列，是在該序列中刪去若干元素后得到的序列。問題為，求給定序列X{x1,x2,…,xm}和Y{y1,y2,…yn}，求解其最長的公共子序列。動態(tài)規(guī)劃法第一步，抽象出數(shù)學(xué)公式并給出遞歸結(jié)構(gòu)表示。c[i][j]用來表示x1,x2,…xi與y1,y2,…yj的最長公共子序列，則遞歸式表示為：第二步，寫出（偽）代碼：void LCSLength(int m,int n,char *x,char *y, int **c,char ** b){int i,j;//寫出遞歸解法是容易的，但動態(tài)規(guī)劃用的是自底向上的方式，也即求c[i][j]for(i=1;i<=m;i++)c[i][0]=0;//c數(shù)組長度為[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]=’<’;}}}第三步，構(gòu)造最優(yōu)解void LCS(int i,int j,char *x,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,j,x,b);else LCS(i,j-1,x,b);}61，求數(shù)組的最大子段和（及二維情況的解答思想）最大子段和的遞歸式思想：每次從中間mid劃開，分別遞歸求兩邊最大子段和，再從中間開始，分別往左右遍歷，得到從…mid和mid+1…（包括mid和mid+1）的最大子段和，二者相加，看它比前兩個遞歸結(jié)果是否大，三者取最大者即為解，分治法（遞歸）偽代碼如下：int MaxSubSum(int *a,int left,int right){//調(diào)用MaxSumSum(a,1,n)即為整個數(shù)組最大子段和if(left==right)return a[left];else{int mid=(left+right)/2;int leftsum=MaxSubSum(a,left,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);}}動態(tài)規(guī)劃法算法分析如下。第一步，數(shù)學(xué)表示及導(dǎo)出遞歸表示。記b[j] (1<=j<=n)表示以元素j結(jié)尾的最大子段和，也即由b[j]往左加可得的最大子段和。于是，題目要求的解即是：max(b[j]) (1<=j<=n)。由b[j]的定義易知，當(dāng)b[j-1]>0時b[j]=b[j-1]+a[j]，否則b[j]=a[j]。由此可得計(jì)算b[j]的動態(tài)規(guī)劃遞歸式：b[j]=max{b[j-1]+a[j],a[j]} , 1<=j<=n;據(jù)此，可得最大子段和的動態(tài)規(guī)劃算法。int MaxSum(int n,int *a){int sum=0;//如果最大子段和是負(fù)數(shù)，則返回0b=0;//b初始時為0for(int i=1;i<=n;i++){if(b>0)b+=a[i];//因?yàn)閎初始為0所以，第一步執(zhí)行時，會執(zhí)行elseelse b=a[i];//第一次執(zhí)行時，會將a[1]賦給bif (b>sum);sum=b;//只用一個b即可代替b[]的作用，因?yàn)槊總€b[j]只引用b[j-1]}return sum;}時間復(fù)雜度僅為O（n）。如果是二維的情況，則需要用兩重循環(huán)來確定其中一維的上下邊界。復(fù)雜度為O(n*m^2)。62，編程之美：求數(shù)組中最長遞增子序列動態(tài)規(guī)劃法求解的遞歸表示為：LIS[i+1]=max{1,LIS[k]+1},array[i+1]>array[k],for any k<=i;其中LIS[i]表示以array[i]結(jié)尾的最長遞增公共子序列的長度，公式意思為，求以array[i+1]結(jié)尾的遞增子序列，等于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;//初始時的值，遞增子序列長度至少為1for(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數(shù)組中的最大值}63，計(jì)算串的相似度（編輯距離計(jì)算）第一步，數(shù)學(xué)表示：設(shè)六種操作代價(jià)分別為c1…c6，令c[i][j]表示為由xj,…,xm變到y(tǒng)i,…,yn的最小代價(jià)，從m，n往左匹配，可有如下規(guī)律：若當(dāng)前操作為delete則此前操作xj+1,…,xm變到y(tǒng)i,…,yn的代價(jià)最小；若為replace或copy則之前xj+1,…,xm變到y(tǒng)i+1,…,yn的代價(jià)最小；若為insert則表示此前xj,…,xm變到y(tǒng)i+1,…,yn的代價(jià)最小；twiddle（交換相鄰字符）操作之前xj+2,…,xm變到y(tǒng)i+2,…,yn的代價(jià)最小，因?yàn)槊看味际俏暹x一（kill為邊界條件，計(jì)算時決定），所以每步都是比較5種操作的代價(jià)，選最小者。第二步，遞歸式為：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}另設(shè)一k[i][j]用來記錄c[i][j]最小時，的操作序號ci(1<=i<=5)顯然，c[i][j]遞歸式的邊界條件有三個：1， c[i][m+1]=(n-i+1)*c4;//源串為空，則變?yōu)槟繕?biāo)串需要插入n-i+1次2， [n+1][j]=(m-i+1)*c1;//目標(biāo)串為空，則源串需要刪除m-i+1次，即kill操作3， c[n+1][m+1]=0;//源與目標(biāo)串均空，不需要操作64，汽車裝配問題，算法導(dǎo)論P(yáng)195動態(tài)規(guī)劃法求解第一步，數(shù)學(xué)表示及遞歸公式如下：這個公式變量含義如下：e1，e2分別表示初始時裝配上1號2號線的時間，a1,j和a2,j分別表示產(chǎn)品在1，2號線上的j個結(jié)點(diǎn)上加工的時間，f1[j]和f2[j]分別記錄產(chǎn)品推進(jìn)到1，2號線上的第j個結(jié)點(diǎn)時所費(fèi)最少時間。t1[j]和t2[j]分別表示從1，2號線的結(jié)點(diǎn)j切換到另一線所耗費(fèi)的時間。由遞歸式，寫出偽代碼解法如下：FATEST-WAY(a,t,e,x,n){//e表示e1,e2；x表示x1,x2，分別表示初始上線及最后下線的代價(jià)f[1][1]=e1+a[1][1];//初始化邊界條件，即第一個結(jié)點(diǎn)的情況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個結(jié)點(diǎn)加工的產(chǎn)品上一結(jié)點(diǎn)是哪條線}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個結(jié)點(diǎn)加工的產(chǎn)品上一結(jié)點(diǎn)是哪條線}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)){//處理最后一個結(jié)點(diǎn)，x1表示從線1卸下的時間finish_cost=f[1][n]+x1;//如果從線1結(jié)束的時間比從線2早，則在線一完成line_finish=1;}else{//如果從線2結(jié)束時間比從線1早，則在線二完成finish_cost=f[2][n]+x2;line_finish=2;}} }構(gòu)造最優(yōu)解PRINT-STATIONS(l,line_finish,n){int i=line_finish;print “l(fā)ine”+i+”,station”+nfor(j=n downto 2){i=l[i][j];print “l(fā)ine”+i+”,station”+j-1;}}65，雙調(diào)旅行商問題：對平面上給定的n個點(diǎn)，確定一條連接各點(diǎn)的最短閉合旅程的問題。這是NP完全的，有人提議只考慮“雙調(diào)旅程”來簡化問題。即先從最左到最右，再回到最左。換言之，設(shè)兩個A，B從最左，以不同路徑到達(dá)最右，求此路徑之和的最小值。嚴(yán)格從左至右，即到某點(diǎn)i時，i左邊的點(diǎn)已經(jīng)全部走過了。假設(shè)兩人A，B，不失一般性，設(shè)A在B后，Pij表示A走到點(diǎn)i而B走到點(diǎn)j時的最短路徑，根據(jù)假設(shè)有i<=j，設(shè)b[i][j]表示最短雙調(diào)路徑Pij的長度，d[i][j]表示i,j之間的距離。則：b[1][2]=d[1][2];當(dāng)i=j時，即A，B處在同一點(diǎn)，b[i][j]=b[i][i]=b[i-1][i]+d[i-1][i];當(dāng)i=j-1時，即A在B相鄰的靠左一點(diǎn)，b[i][j]=b[j-1][j]=min{b[k][j-1]+d[k][j]}1<=k<=j-1當(dāng)i<j-1時，即A在B后的多個點(diǎn)處b[i][j]=b[i][j-1]+d[j-1][j]。此為動態(tài)規(guī)劃法。67，漂亮打印問題：考慮在一張紙上打印一段文章，正文為n個分別長為l1,l2,…,ln的單詞構(gòu)成的序列，漂亮打印的標(biāo)準(zhǔn)為，如果一行包括從第i到第j個單詞（i<j），且單詞之間只留一個空格，則每行末多余空格數(shù)立方和最小。用動態(tài)規(guī)劃法求解：記單詞為w1,w2,…,wn，記Pi為將wi至wn的單詞漂亮打印出來的方案，則本題為求P1。對任意的Pi，若在wj處結(jié)尾（該行包括從i到j(luò)所有單詞），則Pi中，對于wj+1,wj+2,…,wn即Pj+1是最優(yōu)的，符合最優(yōu)子結(jié)構(gòu)性質(zhì)。容易發(fā)現(xiàn)重疊子問題（重復(fù)計(jì)算）也存在。使用動態(tài)規(guī)劃法從Pn求到P1，求Pi時，只用處理與wi可能在同一行的所有情況，而求同一行的情況與行寬M相關(guān)，所以，求單個Pi的時間為O（M），整個算法的時間復(fù)雜度為O(m*n)，遞歸條件（自底向上的起始條件）為，Pn=0；68，計(jì)劃一個公司聚會算法導(dǎo)論P(yáng)219公司的管理層次結(jié)構(gòu)可用樹形結(jié)構(gòu)表示，每個雇員有一個喜歡聚會的程度（實(shí)數(shù)表示），為每大家都喜歡這個聚會，總裁不希望一個雇員和他的直接上司同時參加。樹的結(jié)構(gòu)用左子女，右兄弟表示法。樹中每個結(jié)點(diǎn)除了包含指針，還包含了雇員的名字及該雇員喜歡聚會程度的排名。描述一個算法，它生成一張客人列表，使得喜歡聚會的程度之總和為最大。用動態(tài)規(guī)劃法解答：轉(zhuǎn)化為樹的著色問題，如果點(diǎn)x著紅色，代表參加，白色代表不參加，則從葉子起，記住每個結(jié)點(diǎn)著（不著色）時的喜歡程度總和，遞歸定義如下：求max（T（root,WHITE）,T(root,RED)）即為解。69，0-1背包問題的動態(tài)規(guī)劃算法：有n件物品和一個容量為c的背包。第i件物品的費(fèi)用是w[i]，價(jià)值是v[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。基本思路：這是最基礎(chǔ)的背包問題，特點(diǎn)是：每種物品僅有一件，可以選擇放或不放。遞歸關(guān)系公式表示為：其中m(i,j)表示，選的物品范圍為i,…,n，而剩余容量為j。用動態(tài)規(guī)劃求解的（偽）代碼如下：void Knapsack(int *v,int *w,int c,int n,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個時，如能裝下，則計(jì)算矩陣值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];//處理第一個，因是數(shù)組，所以所有值都填！if(c>=w[1])m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]);//如果是裝得下，則對這些數(shù)組元素賦值}構(gòu)造最優(yōu)解：void Traceback(int **m,int w,int c,int n,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背包動態(tài)規(guī)劃的另一種解法（從第0個物品開始考慮起）遞歸式為：偽代碼如下：for(j=0…W)m[0][j]=0;//大寫W表背包總?cè)萘縡or(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];//可裝得下的最大價(jià)值，構(gòu)造最優(yōu)解的方向，也應(yīng)與考慮時方向一致0-1背包問題擴(kuò)展之一。數(shù)組分割，要求將長度為2n的數(shù)組分割成兩個長度為n的數(shù)組，并使它們之間的和最接近。假設(shè)S=(a[1]+a[2]+...+a[n]+a[n+1]+...+a[2n])/2，那么這是個和0-1背包類似的動態(tài)規(guī)劃問題，區(qū)別之處就是取的個數(shù)受到限制，必須得取足n個元素。用dp(i,j,c)來表示從前i個元素中取j個、且這j個元素之和不超過c的最佳(大)方案，在這里i>=j,c<=S 狀態(tài)轉(zhuǎn)移方程： dp(i,j,c)=max{dp(i-1,j-1,c-a)，dp(i-1,j,c)}dp(2n,n,S)就是題目的解。 整體復(fù)雜度是O(S*n^2)0-1問包問題擴(kuò)展之二。最優(yōu)裝載，要把n個重量分別為wi的物品，裝到2艘船上，使之完成裝載，2艘船的載重分別為c1，c2。容易證明，如果給定的一人裝載問題有解，則采用如下的策略一定能得到一個最優(yōu)裝載方案：1、 首先將第一艘船盡可能地裝滿；2、 然后將剩余的物品裝到第二艘船上。這樣，便演化成了0-1背包問題。0-1背包問題擴(kuò)展之三?；厮莘ń?-1背包void Backtrack(int i){if(i>n){bestp=cp;return;}//如果找到了一個最優(yōu)解，則返回if(cw+w[i]<=c){//嘗試裝x[i]=1（如果裝得下）cw+=w[i];//重量加c[p]+=p[i];//價(jià)值加Backtrack(i+1);//遞歸調(diào)用cw-=w[i];//一定要復(fù)位，因?yàn)閏w和cp是共用的變量cp-=p[i];}//其實(shí)所謂回溯，就是遞歸調(diào)用，加了一個剪枝步，Bound(int i)判斷把余下的}//按單位價(jià)值排序后依次裝上，零頭也裝上，是否能得到更優(yōu)的解，也即估上界if(Bound(i+1)>bestp)Backtrack(i+1);//不裝x[i]=0}70，編程之美：買書問題令F（Y1,Y2,Y3,Y4,Y5）表示買五冊書分別為Y1,…,Y5時所花的最少價(jià)格。其中Y1>Y2…>Y5。每次求解之前，都要對那五個數(shù)進(jìn)行排列，大的放前面。動態(tài)規(guī)劃解法的遞歸式為：F（Y1,Y2,Y3,Y4,Y5）=0 (Y1=Y2=Y3=Y4=Y5=0)F（Y1,Y2,Y3,Y4,Y5）=min(5*8*(1-25%)+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5-1),//如果Y5>14*8*(1-20%)+F(Y1-1,Y2-1,Y3-1,Y4-1,Y5), //如果Y4>13*8*(1-10%)+F(Y1-1,Y2-1,Y3-1,Y4,Y5), //如果Y3>12*8*(1-5%)+F(Y1-1,Y2-1,Y3,Y4,Y5), //如果Y2>18+ F(Y1-1,Y2,Y3,Y4,Y5)) //如果Y1>1以下部分主要為圖與幾何相關(guān)部分71，圖的基本數(shù)據(jù)結(jié)構(gòu)，主要表示方法（鄰接表），深度優(yōu)先遍歷算法，廣度優(yōu)先遍歷算法與層序遍歷樹一樣，用隊(duì)列！#define MAX_VERTEX_NUM 20typedef struct ArcNode{//弧結(jié)構(gòu)體int adjvex;//該弧所指向的頂點(diǎn)位置struct ArcNode *nextarc;//下一條弧int weight;//權(quán)重}ArcNode;typedef struct VNode{int data;//頂點(diǎn)信息ArcNode *firstArc;//指向第一條依附該結(jié)點(diǎn)的弧的指針}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList vertices;//結(jié)點(diǎn)數(shù)組int vexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)int kind;//圖的種類標(biāo)志}Graph;void DFS(Graph G,int v){//深度優(yōu)先遍歷結(jié)點(diǎn)vvisited[v]=true;cout<<v<<endl;//訪問函數(shù)for(ArcNode *w=G.vertices[v].firstArc;w!=NULL;w=w->nextarc)if(!visited[w->adjvex])DFS(G,w->adjvex);}void DFSTraverse(Graph G){//深度優(yōu)先遍歷圖for(int v=0;v<G.vexnum;v++)visited[v]=false;for(v=0;v<G.vexnum;v++)if(!visited[v])DFS(G,v);}圖的連通性判斷。無向圖只需要只以一個結(jié)點(diǎn)出發(fā)進(jìn)行一種（深度或廣度）遍歷，然后檢查是否所有結(jié)點(diǎn)均被visited了即可，有向圖則采用如下算法：（1）對圖調(diào)用深度優(yōu)先遍歷，并記住每個頂點(diǎn)完成時間（比如用棧）（2）對圖轉(zhuǎn)置為GT（3）從最晚完成的頂點(diǎn)開始，對GT調(diào)用深度優(yōu)先遍歷，當(dāng)找不到新頂點(diǎn)時，從余下頂點(diǎn)中選一個最晚完成的頂點(diǎn)繼續(xù)，直到全部完成；每次換選一個頂點(diǎn)之前得到的頂點(diǎn)集即為一個強(qiáng)連通分支。圖的拓?fù)渑判?。入度?的結(jié)點(diǎn)入隊(duì)，當(dāng)隊(duì)不空時循環(huán)：彈出隊(duì)首，并對隊(duì)首元素可達(dá)的每個頂點(diǎn)入度減1，將此輪減1后入度為0者插入隊(duì)尾。最后出隊(duì)順序即拓?fù)溆行?。最小生成樹算法。普里姆算?prim)，從某一點(diǎn)出發(fā)，每次從余下的點(diǎn)集中選擇離它最近的點(diǎn)作為下一點(diǎn)，并入已選點(diǎn)集中(設(shè)置距離為0)并更新已選點(diǎn)集與未選點(diǎn)集的距離（如果因新加入的點(diǎn)引起了變化的話），時間復(fù)雜度為n^2，與邊無關(guān)；克魯斯卡爾(Kruskal)算法，每次從屬于不同的兩個點(diǎn)集中的兩點(diǎn)所連的邊中選擇一條最短者，然后將此兩點(diǎn)集合并，直至所有點(diǎn)集同屬一個集合即完成算法，初始點(diǎn)集數(shù)為n，每個集一個點(diǎn)，時間復(fù)雜度為eloge。由以上分析可知，前者適用于點(diǎn)少邊多的圖，后者則相反。圖的單源最短路徑算法。迪杰斯特拉(dijstra)算法，按最短路徑遞增的方式求單源最短路徑，偽碼如下：Dijstra(G,w,s){//s為源點(diǎn)，w為權(quán)值矩陣init();//初始化d[s]=0;其余d[v]=MAXINTQ=V(G)-s;//未用來計(jì)算最短路徑的點(diǎn)集S=s；//已用來計(jì)算最短路徑的點(diǎn)集while(Q!=NULL){u=extract-min(Q)//從Q中選擇d[u]最小的點(diǎn)(并從Q中刪除該點(diǎn))S=S并u;for each vertex v in Adj[u];//對于u可達(dá)的每個頂點(diǎn)Relax(u,v,w);}}Relax(u,v,w){if(d[u]+w[w][v]<d[v])d[v]= d[u]+w[w][v];}圖的每對頂點(diǎn)間最短路徑。方法一，執(zhí)行n次單源最短路徑算法，復(fù)雜度O(n^3)；方法二，Floy-Warshall算法，復(fù)雜度O(n^3)；對任意兩個點(diǎn)i,j給定k表示i,j之間，所有經(jīng)過的頂點(diǎn)序號不大于k的時候，i,j之間的最短路徑，考慮已經(jīng)求出k-1時的情況，對于k：（1） 若k在i,j最短路徑中，則路徑為（2） 如果k不是i,j最短路徑中，則k-1的解即為k的解，用數(shù)學(xué)形式表示為：由此得Floy-Warshall算法偽代碼：Floy-Warshall(W){n=rows(W);D0=W;//D代表每輪計(jì)算之后的權(quán)值矩陣Wfor(k=1…n)for(i=1…n)for(j=1…n);return Dn;}有向圖的傳遞閉包問題。即要求兩點(diǎn)i,j（任意）是否可達(dá)。方法：對每條邊賦值1，若運(yùn)行Floy-Warshall之后dij<n則可達(dá)，否則為不可達(dá)；改進(jìn)之處，在求Floyd時公式改為：;進(jìn)行或運(yùn)算即可關(guān)鍵路徑求法。AOV網(wǎng)加上權(quán)值便得AOE(Activity On Edge)網(wǎng)，對AOE網(wǎng)的一項(xiàng)典型計(jì)算是計(jì)算關(guān)鍵路徑，即從源點(diǎn)到終點(diǎn)的最長路徑，關(guān)鍵路徑上的活動延期會影響整個工程！求關(guān)鍵路徑的方法是：（1）從源點(diǎn)開始，求各個活動的最早發(fā)生時間（事先拓?fù)渑判?#xff09;；入一棧中為第二步作準(zhǔn)備（2）從終點(diǎn)開始向前，求各個活動的最晚發(fā)生時間；（3）輸出最早發(fā)生時間等于最晚發(fā)生時間的活動，便是關(guān)鍵活動。72，尋找最近點(diǎn)對！一維情況，用排序，然后掃瞄一遍即可；二維時的算法偽代碼：bool cpair2(s,&d){n=|s|;if(n<2){d=MAXINT;return false;}m=s中各點(diǎn)x坐標(biāo)的中位數(shù)；由x=m分割點(diǎn)集s為s1,s2;cpair2(s1,d1);cpair2(s2,d2);dm=min(d1,d2);設(shè)p1為s1中與x=m小于dm的所有點(diǎn)集設(shè)p2為s2中與x=m小于dm的所有點(diǎn)集將p1和p2中的點(diǎn)按y值排序，結(jié)果為X，Y對X中的每個頂點(diǎn)，檢查Y中與其在y軸上投影距離小于dm的所有頂點(diǎn)（最多6個），最終求得的最小距離為dl；d=min(dm,dl);return true;}73，九宮格，可以上下左右方向走，不可斜走，任意走n步（1<=n<=8）且不可以已經(jīng)走過的方格，只要走的步數(shù)不一樣，或者走的路線不一樣，就算一種走法，問題是任意給一格作為起點(diǎn)，請問有多少走走法？/* 0 1 23 4 56 7 8 ********/#include <iostream>using namespace std;int ninemap[9][4]={{1,3,-1,-1},{0,2,4,-1},{1,5,-1,-1},{0,4,6,-1},{1,3,5,7},{2,4,8,-1},{3,7,-1,-1},{4,6,8,-1},{5,7,-1,-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; // 表示我已經(jīng)來過這里gonePath[goneNum]=source;// 當(dāng)前狀態(tài)下路徑位置if(goneNum==9) return;int nextPoint=-1;for(int i=0;i<4;i++){nextPoint =ninemap[source][i];if (nextPoint!=-1&&gone[nextPoint]!=1){// 存在下一頂點(diǎn)，且之前沒有走過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<<"請輸入九宮格的初始節(jié)點(diǎn)(0-8,結(jié)束請輸入-1)"<<endl;int source;cin>>source;if(source==-1){return 0;}while(source<0 || source>8){cout<<"輸入?yún)?shù)不規(guī)范，請重新輸入"<<endl;cout<<"請輸入九宮格的初始節(jié)點(diǎn)(0-8,結(jié)束請輸入-1)"<<endl;cin>>source;}while(source>-1 && source <9){int goneNum=0;// 當(dāng)前節(jié)點(diǎn)位置int gonePath[9]={-1,-1,-1,-1,-1,-1,-1,-1,-1}; // 保存走過的路徑int sum=0;// 解法個數(shù)int gone[9]={0,0,0,0,0,0,0,0,0};// 走過該節(jié)點(diǎn)否，1走過，0未走findPathNum(source,ninemap,gone,goneNum,sum,gonePath);cout<<"以"<<source<<"為起點(diǎn)的解法共有"<<sum<<"個"<<endl;cout<<"請輸入九宮格的初始節(jié)點(diǎn)(0-8,結(jié)束請輸入-1)"<<endl;cin>>source;}return 0;}74，計(jì)算凸包Graham掃瞄法：第一步，選取y值最小的點(diǎn)P0，其余點(diǎn)以P0為原點(diǎn)按逆時針掃過的順序排序；第二步，按序P1，P2進(jìn)棧；第三步，對于余下的每個Pi，按序依次{while(next-to-top(Stack),top(Stack),Pi三點(diǎn)（兩線段）非左拐)pop(Stack);push(Pi,Stack);}javis法：第一步，與Graham一樣選取P0；第二步，對于剩下的點(diǎn)，按逆時針掃過的第一個點(diǎn)為P1；第三步，P1為新端點(diǎn)，除P0,P1外，以新端點(diǎn)逆時針掃過的第一個點(diǎn)為P2；……到最高點(diǎn)時，右鏈掃瞄完畢，第四步，左鏈由P0開始與右鏈對稱執(zhí)行一次，兩鏈合并即完成掃瞄。75，確定兩線段是否相交，看算法導(dǎo)論筆記知識一，兩點(diǎn)P1（x1,y1），P2（x2,y2）的叉積定義為：x1*y2-x2*y1。如果叉積P1×P2為正數(shù)，則相對于原點(diǎn)（0，0）來說，P1在P2的順時針方向，如果是負(fù)數(shù)則表示在逆時針方向，如果是0則表示這兩個向量是共線的。確定連續(xù)線段是向左轉(zhuǎn)還是向右轉(zhuǎn)？給定點(diǎn)p0,p1,p2求線段p1p2在p0p1之后是向左轉(zhuǎn)了還是向右轉(zhuǎn)了。方法就是求p0p2和p0p1這兩個向量的叉積。確定兩線段是否相交，有兩種情況：一是，每個線段都跨越包含了另一線段的直線；二是，一個線段的某一端點(diǎn)位于另一線段上。（這一情況來自于邊界情況）SEGMENTS-INTERSECT(p1,p2,p3,p4){//判斷p1p2和p3p4是否相交d1=DIRECTION(p3,p4,p1);//計(jì)算p3p4與p3p1的叉積d2=DIRECTION(p3,p4,p2);d3=DIRECTION(p1,p2,p3);d4=DIRECTION(p1,p2,p4);if((d1*d2<0)&&(d3*d4<0))return true;else if((d1==0)&&ON-SEGMENT(p3,p4,p1))return true;//d1=0表在p1在p3p4的直線上else if((d2==0)&&ON-SEGMENT(p3,p4,p2))return true;//是否在線段上，仍需要判斷else if((d3==0)&&ON-SEGMENT(p1,p2,p3))return true;//ON-SEGMENT判斷范圍即可else if((d4==0)&&ON-SEGMENT(p1,p2,p4))return true;//else return false;}DIRECTION(pi,pj,pk){//計(jì)算pipj與pipk的叉積return (pk-pi)×(pj-pi)}ON-SEGMENT（pi,pj,pk）{//計(jì)算點(diǎn)pk是否在線段pipj上，因之前已經(jīng)判斷了在直線上if((min(xi,xj)<=xk<=max(xi,xj))&&(min(yi,yj)<=yk<=max(yi,yj)))return true;else return false;}76，求給定的一組線段中，是否有相交的方法大意：第一步，將線段所有端點(diǎn)排序（按x值，相同時再按y值）第二步，設(shè)一掃瞄線，從左到右掃瞄每一個端點(diǎn)。對于每個掃到的端點(diǎn)，若其為左端點(diǎn)，則將線段加入到掃瞄線線段集中，判斷此時緊臨其掃瞄線上方或下方存在的線段，若有與之相交的，則返回true；若其為右端點(diǎn)，則判斷掃瞄線此時其上下方均有線段并相關(guān)時返回true，否則從掃瞄線線段集中刪除該右端點(diǎn)所在的線段。以下主要為幾個矩陣輸出題77，void Matrix(int n) 打印出如下一個矩陣：n=55 6 3 4 54 7 2 7 63 2 1 2 36 7 2 7 45 4 3 6 5n=77 8 9 4 5 6 76 13 10 3 12 13 85 12 11 2 11 10 94 3 2 1 2 3 49 10 11 2 11 12 58 13 12 3 10 13 67 6 5 4 9 8 7....以此類推 n<20, n為奇數(shù)十字架，劃分成四個區(qū)域，然后各個區(qū)域再分別打印！void printMatrix2(int n){if(n>20||n<0||n%2==0)return;//偶數(shù)，及其它不符合條件的數(shù)返回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;//賦中心點(diǎn)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,0,center+1,center+2,center);//打印數(shù)組a的右上角四分之一printRightDownQuarter(a,center+1,n-1,center+2,center);//打印數(shù)組a的右上角四分之一printLeftUpQuarter(a,center-1,0,center+2,center);//打印數(shù)組a的右上角四分之一printLeftDownQuarter(a,n-1,center-1,center+2,center);//打印數(shù)組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 start, int n) {//右上，其它三塊類似int i, j;//打印螺旋隊(duì)列的遞歸算法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, start, n-2); /* 遞歸 */}擴(kuò)展，打印螺旋隊(duì)列的非遞歸算法如下：void printRightUpQuarter(int **matrix, int x, int y, int start, 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=31 2 11 2 11 1 1n=41 2 2 11 2 2 11 2 2 11 1 1 1n=51 2 2 2 11 2 3 2 11 2 3 2 11 2 3 2 11 1 1 1 1n=61 2 2 2 2 11 2 3 3 2 11 2 3 3 2 11 2 3 3 2 11 2 3 3 2 11 1 1 1 1 1n=71 2 2 2 2 2 11 2 3 4 3 2 11 2 3 4 3 2 11 2 3 4 3 2 11 2 3 4 3 2 11 2 3 3 3 2 11 1 1 1 1 1 1....以此類推，//規(guī)律是分四類，第一行，最后一行，倒數(shù)第二行，其它void printMatrix( int n ) //已運(yùn)行驗(yà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;//給倒數(shù)第二行賦值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為奇數(shù)；n=5；1444414333140231112322223n=7；1444444143333314322231430123144412311111232222223提示：從外圍開始轉(zhuǎn)圈！代碼如下：void printMatrix3(int n){if(n>20||n<0||n%2==0)return;//偶數(shù)，及其它不符合條件的數(shù)返回int **a=new int*[n];for(int i=0;i<n;i++)a[i]=new int[n];int x,y;//一圈圈地轉(zhuǎn)，與螺旋隊(duì)列一樣，只是填的數(shù)不一樣而已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;}

總結(jié)

以上是生活随笔為你收集整理的算法--职前算法复习的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。