Cpp五条

这个屌丝很懒，什么也没留下！

热门标签

求职复习算法整理_poutgcb

作者：Cpp五条 | 2024-06-09 05:26:58

踩

poutgcb

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,e,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 low,int high){//递归函数

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

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

quickSort(a,low,mid-1);

quickSort(a,mid+1,high);

}

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

while(low<high){

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

quickSort(a,low,mid-1);

low=mid+1;

}

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

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

2)while(栈不空){

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

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

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

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

void quickSort2(int *a,int low,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 *b,int left,int right){//递归辅助函数二

while(left<=right){

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

}

//递归主算法

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

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);//合并到数组b

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

}

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

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

int i=0;

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

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);//剩下的数少于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,b,s,n);//合并数组到b

s+=s;

mergePass(b,a,s,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 n,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

    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,tc,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级台阶,某人一步最多迈三级,问有多少种不同的方式上楼?引进递归思想，我们就可找到简单的方法：设上ｎ级台阶的方法有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。

更一般情况：一般台阶问题：某楼梯有ｎ(ｎ≥1)级台阶，某人一步最多迈ｍ(ｎ≥ｍ≥1)级,有多少种不同的方案上楼。设上ｎ级台阶的方案有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数列，斐波那契数列

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

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

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

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

举个例子：

由于以上分析，可得伪代码如下：

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

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

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

Matrix tmp=m;//tmp每次循环都会增长，依次表示A¹,A²,A⁴,A⁸

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,5,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,key,T,p);

}

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

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

if(!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;

}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,i,1);//1表示在p结点的第i个key处找到了

else return(q,i,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,a,c);

    else

          Hannoi(n-1,a,c,b);

            Move(n,a,c);

            Hannoi(n-1,b,a,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,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循环写成递归的形式，就是对于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,2,4,5 和 6,8,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,0,3,3,3,3,3,4,3,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,1,...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,1,1,0,1,0,1,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 n,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 **m,int **s){

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,x2,…xi与y1,y2,…yj的最长公共子序列，则递归式表示为：

第二步，写出（伪）代码：

void LCSLength(int m,int n,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,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，求数组的最大子段和（及二维情况的解答思想）

最大子段和的递归式思想：每次从中间mid划开，分别递归求两边最大子段和，再从中间开始，分别往左右遍历，得到从…mid和mid+1…（包括mid和mid+1）的最大子段和，二者相加，看它比前两个递归结果是否大，三者取最大者即为解，分治法（递归）伪代码如下：

int MaxSubSum(int *a,int left,int right){//调用MaxSumSum(a,1,n)即为整个数组最大子段和

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

}

动态规划法算法分析如下。

第一步，数学表示及导出递归表示。

记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，计算串的相似度（编辑距离计算）

第一步，数学表示：设六种操作代价分别为c₁…c₆，令c[i][j]表示为由x_j,…,x_m变到y_i,…,y_n的最小代价，从m，n往左匹配，可有如下规律：若当前操作为delete则此前操作x_j+1,…,x_m变到y_i,…,y_n的代价最小；若为replace或copy则之前x_j+1,…,x_m变到y_i+1,…,y_n的代价最小；若为insert则表示此前x_j,…,x_m变到y_i+1,…,y_n的代价最小；twiddle（交换相邻字符）操作之前x_j+2,…,x_m变到y_i+2,…,y_n的代价最小，因为每次都是五选一（kill为边界条件，计算时决定），所以每步都是比较5种操作的代价，选最小者。

第二步，递归式为：

c[i][j]=min{c[i][j+1]+c₁,c[i+1][j+1]+c₂, c[i+1][j+1]+c₃,c[i+1][j]+c₄, c[i+2][j+2]+c₅}

另设一k[i][j]用来记录c[i][j]最小时，的操作序号c_i(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

动态规划法求解第一步，数学表示及递归公式如下：

这个公式变量含义如下：

e₁，e₂分别表示初始时装配上1号2号线的时间，a_1,j和a_2,j分别表示产品在1，2号线上的j个结点上加工的时间，f₁[j]和f₂[j]分别记录产品推进到1，2号线上的第j个结点时所费最少时间。t₁[j]和t₂[j]分别表示从1，2号线的结点j切换到另一线所耗费的时间。

由递归式，写出伪代码解法如下：

FATEST-WAY(a,t,e,x,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个分别长为l₁,l₂,…,l_n的单词构成的序列，漂亮打印的标准为，如果一行包括从第i到第j个单词（i<j），且单词之间只留一个空格，则每行末多余空格数立方和最小。用动态规划法求解：

记单词为w₁,w₂,…,w_n，记P_i为将w_i至w_n的单词漂亮打印出来的方案，则本题为求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 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个时，如能装下，则计算矩阵值

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 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背包动态规划的另一种解法（从第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,j,c)来表示从前i个元素中取j个、且这j个元素之和不超过c的最佳(大)方案，在这里i>=j,c<=S 状态转移方程： dp(i,j,c)=max{dp(i-1,j-1,c-a)，dp(i-1,j,c)}

dp(2n,n,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（Y₁,Y_2,Y_3,Y_4,Y₅）表示买五册书分别为Y1,…,Y5时所花的最少价格。其中Y1>Y2…>Y5。每次求解之前，都要对那五个数进行排列，大的放前面。动态规划解法的递归式为：

F（Y₁,Y_2,Y_3,Y_4,Y₅）=0 (Y₁=Y₂₌Y₃₌Y₄₌Y₅=0)

F（Y₁,Y_2,Y_3,Y_4,Y₅）=

min(5*8*(1-25%)+F(Y₁-1,Y₂-1_,Y₃-1_,Y₄-1_,Y₅-1),//如果Y5>1

4*8*(1-20%)+F(Y₁-1,Y₂-1_,Y₃-1_,Y₄-1_,Y₅), //如果Y4>1

3*8*(1-10%)+F(Y₁-1,Y₂-1_,Y₃-1_,Y_4,Y₅), //如果Y3>1

2*8*(1-5%)+F(Y₁-1,Y₂-1_,Y_3,Y_4,Y₅), //如果Y2>1

8+ F(Y₁-1,Y_2,Y_3,Y_4,Y₅)) //如果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）对图转置为G^T（3）从最晚完成的顶点开始，对G^T调用深度优先遍历，当找不到新顶点时，从余下顶点中选一个最晚完成的顶点继续，直到全部完成；每次换选一个顶点之前得到的顶点集即为一个强连通分支。

图的拓扑排序。入度为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,v,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);

D⁰=W;//D代表每轮计算之后的权值矩阵W

for(k=1…n)

for(i=1…n)

for(j=1…n) ;

return Dⁿ;

}

有向图的传递闭包问题。即要求两点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,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; // 表示我已经来过这里

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,-1,-1,-1,-1,-1,-1,-1}; // 保存走过的路径

int sum=0;// 解法个数

int gone[9]={0,0,0,0,0,0,0,0,0};// 走过该节点否，1走过，0未走

findPathNum(source,ninemap,gone,goneNum,sum,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,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){//计算pipj与pipk的叉积

return (pk-pi)×(pj-pi)

}

ON-SEGMENT（pi,pj,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,0,center+1,center+2,center);//打印数组a的右上角四分之一

printRightDownQuarter(a,center+1,n-1,center+2,center);//打印数组a的右上角四分之一

printLeftUpQuarter(a,center-1,0,center+2,center);//打印数组a的右上角四分之一

printLeftDownQuarter(a,n-1,center-1,center+2,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 start, 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, start, n-2); /* 递归 */

}

扩展，打印螺旋队列的非递归算法如下：

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=3

1 2 1

1 1 1

n=4

1 2 2 1

1 1 1 1

n=5

1 2 2 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 1 1 1 1 1

n=7

1 2 2 2 2 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;

}

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】