Chapter III after class exercises 24-33

3.24

int g(int m,int n);
int main()
{
    
	int m,n;
	cout<<" Please enter m and n Value ：";
	cin>>m>>n;
	if(n>=0) cout<<g(m,n)<<endl;
	else cout<<"No Solution！";
	return 0; 
}
int g(int m,int n)
{
    
	if(m>0)
		return (g(m-1,2*n)+n);
	else return 0;
}

3.25

#include <iostream.h>
#define N 20;
int main()
{
    
	int i;
	int a[N];
	int n;
	cout<<" Please enter n:";
	cin>>n;
	for(i=0;i<n+1;i++){
    
		if(i<1) a[i]=1;
		else a[i]=i*a[i/2];
	} 
	cout<<a[n]<<endl;
	return 0;
}

3.26. The iterative function for solving the square root is defined as follows ：

#include <iostream.h>
double Sqrt(double A,double p,double e);
int main()
{
    
	double A,p,e;
	cout<<" Please enter A p e:";
	cin>>A>>p>>e;
	cout<<Sqrt(A,p,e)<<endl;
	return 0; 
}
double Sqrt(double A,double p,double e)
{
    
	if((p*p-A)>-e&&(p*p-A)<e)
		return p;
	else
		return Sqrt(A,(p+A/p)/2,e);
}

（1） recursive

unsigned int akm(unsigned int m,unsigned int n)
{
    
	unsigned int g;
	if(m==0)
		return n+1;
	else
	 	if(n==0) return akm(m-1,1);
	 	else{
    
	 		g=akm(m,n-1);
			 return akm(m-1,g);	
		}
}

（2） Non recursive

int akm1(int m,int n)
{
    
	Stack s;
	InitStack(s);
	ElemType e,e1,d;
	e.mval=m;
	e.nval=n;
	do{
    
		while(e.mval){
    
			while(e.nval){
    
				e.nval--;
				Push(s,e);
			}
			e.mval--;e.nval=1;
		}
		if(StackLength(s)>1){
    
			e1.nval=e.nval;
			Pop(s,e);
			e.mval--;
			e.nval=e1.nval+1;
		}
	}while(StackLength(s)!=1||e.mval!=0);
	return e.nval+1; 
}

（3）

3.28

typedef int ElemType;
typedef struct NodeType{
    
	ElemType data;
	NodeType *next;
}QNode,*QPtr;
typedef struct{
    
	QPtr rear;
	int size;
}Queue;
Status InitQueue(Queue &q)
{
    
	q.rear=NULL;
	q.size=0;
	return OK;
}
Status EnQueue(Queue &q,ElemType e)
{
    
	QPtr p;
	p=new QNode;
	if(!p) return FALSE;
	p->data=e;
	if(!q.rear){
    
		q.rear=p;
		p->next=q.rear;
	}
	else{
    
		p->next=q.rear->next;
		q.rear->next=p;
		q.rear=p;
	}
	q.size++;
	return OK; 
}
Status Dequeue(Queue &q,ElemType &e)
{
    
	QPtr p;
	if(q.size==0) return FALSE;
	if(q.size==1){
    
		p=q.rear;
		e=p->data;
		q.rear=NULL;
		delete p;
	}
	else{
    
		p=q.rear->next;
		e=p->data;
		q.rear->next=p->next;
		delete p;
	}
	q.size--;
	return OK;
}

3.29

#define MaxQSize 4;
typedef int ElemType;
typedef struct{
    
	ElemType *base;
	int front;
	int rear;
	Status tag;
}Queue;
Status InitQueue(Queue &q)
{
    
	q.base=new ElemType[MaxQSize];
	if(!q.base) return FALSE;
	q.front=0;
	q.rear=0;
	q.tag=0;
	return OK;	
} 
Status EnQueue(Queue &q,ElemType e)
{
    
	if(q.front==q.rear&&q.tag) return FALSE;
	else{
    
		q.base[q.rear]=e;
		q.rear=(q.rear+1)%MaxQSize;
		if(q.rear==q.front) q.tag=1;
	}
	return OK;
}
Status DeQueue(Queue &q,ElemType &e)
{
    
	if(q.front==q.rear&&!q.tag) return FALSE;
	else{
    
		e=q.base[q.front];
		q.front=(q.front+1)%MaxQSize;
		q.tag=0;
	}
	return OK;
}

Set signs to save storage space , But it takes a long time ; conversely .

3.30

#define MaxQSize 4
typedef int ElemType;
typedef struct{
    
	ElemType *base;
	int rear;
	int length;
}Queue;
Status InitQueue(Queue &q)
{
    
	q.base=new ElemType[MaxQSize];
	if(!q.base) return false;
	q.rear=0;
	q.length=0;
	return ok;
}
status EnQueue(Queue &q,ElemType e)
{
    
	if((q.rear+1)%MaxQSize==(q.rear+MaxQSize-q.length)%MaxQSize)
		return false;
	else{
    
		q.base[q.rear]=e;
		q.rear=(q.rear+1)%MaxQSize;
		q.length++;
	}
	return OK;
}
Status DeQueue(Queue &q,ElemType &e)
{
    
	if((q.rear+MaxQSize-q.length)%MaxQSize==q.rear)
		return FALSE;
	else{
    
		e=q.base[(q.rear+MaxQSize-q.length)%MaxQSize];
		q.length--;
	}
	return ok;
}

3.31

Status SymmetryString(char *p)
{
    
	Queue q;
	if(!InitQueue(q)) return 0;
	Stack s;
	InitStack(s);
	ElemType e1,e2;
	while(*p){
    
		Push(s,*p);
		EnQueue(q,*p);
		p++;
	}
	while(!StackEmpty(s)){
    
		Pop(s,e1);
		DeQueue(q,e2);
		if(e1!=e2) return false;
	}
	return OK;
}

3.32

int Fibonacci(int k,int n)
{
    
	if(k<1) exit(OVERFLOW);
	Queue q;
	InitQueue(q,k);
	ElemType x,e;
	int i=0;
	while(i<=n){
    
		if(i<k-1){
    
			if(!EnQueue(q,0)) exit(OVERFLOW);
		}
		if(i==k-1){
    
			if(!EnQueue(q,1)) exit(OVERFLOW);
		}
		if(i>=k){
    // Queue summation  
			x=sum(q);
			DeQueue(q,e);
			EnQueue(q,x); 
		}
		i++;
	}
	return q.base[(q.rear+q.MaxSize-1)%q.MaxSize];
}

3.33

//Filename:Queue.h
typedef struct{
    
	ElemType *base;
	int front;
	int rear;
	Status tag;
	int MaxSize;
}DQueue;
Status InitDQueue(DQueue &q,int size)
{
    
	q.MaxSize=size;
	q.base=new ElemType[q.MaxSize];
	if(!q.base) return false;
	q.front=0;
	q.rear=0;
	q.tag-0;
	return ok;
}
status EnDQueue(DQueue &q,ElemType e)
{
    
	if(q.front==q.rear&&q.tag) return false;
	if(q.front==q.rear&&!q.tag){
    // Empty queue  
		q.base[q.rear]=e;
		q.rear=(q.rear+1)%q.MaxSize;
		if(q.rear==q.front) q.tag=1;
	}
	else{
    // Not empty or full  
		if(e<(q.base[q.front]+q.base[(q.rear+q.MaxSize-1)%q.MaxSize])/2){
    
			// From team leader to team 
			q.front=(q.front+q.MaxSize-1)%q.MaxSize;
			q.base[q.front]=e;
			if(q.rear==q.front) q.tag=1; 
		}
		else{
    // From the end to the end of the team  
			q.base[q.rear]=e;
			q.rear=(q.rear+1)%q.MaxSize;
			if(q.rear==q.front) q.tag=1; 
		}
	} 
	return ok;
}
Status DeDQueue(DQueue &q,ElemType &e)
{
    
	if(q.front==q.rear&&!q.tag) return false;
	else{
    // Non empty queue  
		e=q.base[q.front];
		q.front=(q.front+1)%q.MaxSize;
		q.tag=0; 
	} 
	return ok;
} 

#include <iostream.h>
#include <stdlib.h>
typedef int ElemType;
#include "D:\VC99\Queue.h"
int main()
{
    
	int t1,t2,t3,t4;
	ElemType e;
	cout<<" Please enter the job a1,a2,a3,a4 Execution time of :";
	cin>>t1>>t2>>t3>>t4;
	DQueue dq;
	InitDQueue(dq,5);
	EnDQueue(dq,t1);
	EnDQueue(dq,t2);
	EnDQueue(dq,t3);
	EnDQueue(dq,t4);
	while(dq.front!=dq.rear||dq.tag)
	{
    
		DeDQueue(dq,e);
		cout<<e<<endl;
	}
	return 0;
}