算法课外思考题二

问题一

问题描述

给出不同策略求两个整数的最大公约数GCD(m,n)；并进行分析

问题分析

本问题求两数的最大公约数，第一个想法是暴力枚举法；

在数学上，能够证明：$m、n\neq0,GCD(m,n)=GCD(n,mmodn)$，递归出最大公约数，也就是欧几里得算法，上述等式是欧几里得算法的数学基础；

对于两数的最大公约数$GCD(m,n)$，有：

$m<n,GCD(m,n)=GCD(n,m)$

$ mis ~even、nis~even,GCD(m,n)=2*GCD(m/2,n/2)$

$ mis ~even、nis~odd,GCD(m,n)=GCD(m/2,n)$

$ mis ~odd、nis~even,GCD(m,n)=GCD(m,n/2)$

$ mis ~odd、nis~odd,GCD(m,n)=GCD(n,m-n)$

基于上述理论进行递归，也就是二进制算法。

算法思路

对于暴力枚举法，确定两数中最小值，从1~最小值进行循环，使用一个变量更新能被共同整除的数，循环结束时，返回变量的最新值；

对于欧几里得算法，编写GCD函数，两数都不为零时，按照规则递归调用GCD函数；

对于二进制算法，编写GCD函数，对m、n进行上述规则判断，然后进行递归调用GCD函数。

算法代码与分析

#include<iostream>
using namespace std;

//暴力枚举法
int Min(int m, int n);
int GCD1(int m, int n) {
	int num = 0;
	for (int i = 1; i <= Min(m, n); i++) {
		if (m % i == 0 && n % i == 0) {
			num = i;
		}
	}
	return num;
}
int Min(int m, int n) {
	return m > n ? n : m;
}

//欧几里得算法
int GCD2(int m, int n) {
	if (n == 0) {
		return m;
	}
	return GCD2(n, m % n);
}

//二进制算法
int GCD3(int m, int n) {
	if (m == 0) {
		return n;
	}
	if (n == 0) {
		return m;
	}

	if (m % 2 == 0 && n % 2 == 0) {
		return 2 * GCD3(m / 2, n / 2);
	}
	else if (m % 2 == 0 && n % 2 == 1) {
		return GCD3(m / 2, n);
	}
	else if (m % 2 == 1 && n % 2 == 0) {
		return GCD3(m, n / 2);
	}
	else {
		return GCD3(Min(m, n), abs(m - n));
	}
}
int main() {

	int m = 197456;
	int n = 400000;
	cout << GCD1(m, n) << endl;
	cout << GCD2(m, n) << endl;
	cout << GCD3(m, n) << endl;
	system("pause");
	return 0;
}

后续查资料得知，GCD3函数并没有体现真正的二进制算法，没有避免大量取模运算，改进如下：

int GCD3(int m,int n){
    if(m==0){
        return n;
    }
    if(n==0){
        return m;
    }
    
    if((m&1)==0&&(n&1)==0){
        return GCD3(m>>1,n>>1)<<1;
    }
    else if((m&1)==0&&(n&1)!=0){
        return GCD3(m>>1,n);
    }
    else if((m&1)!=0&&(n&1)==0){
        return GCD3(m,n>>1);
    }
    else{
        return GCD3(Min(m,n),abs(m-n));
    }
}

对于数值较小的两数来说，三种方法的速度相差不大，默认$m>n$

则对于枚举法，其时间复杂度是$O(n)$；

对于欧几里得算法，其时间复杂度是$O(log_2n)$；

对于二进制算法，其时间复杂度是$O(log_2(m+n))$；

所以，对于大数来说，后两种算法的处理速度更快；针对后两种算法，改进的二进制算法避免了大量的取余运算。

问题二

问题描述

给出方案返回一可以动态变化的序列（可增可减）中的最大值，并对你的方案进行分析

问题分析

本序列是动态变化的，可以采用顺序栈的数据结构，对于求取序列最大值，采用辅助栈的方式处理；

算法思路

建立两个栈，一个栈存取元素，另一个栈存最大元素；

算法代码与分析

#include<iostream>
#define STACK_INIT_SIZE 100
#define LIST_SIZE 100
using namespace std;
typedef int SElemType;

//栈结构
typedef struct {
	SElemType* base;
	SElemType* top;
	int stacksize;
}SqStack;

typedef struct {
	SqStack Data;
	SqStack MaxData;
}Maxstack;

void InitStack(SqStack* s) {
	s->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	s->top = s->base;
	s->stacksize = STACK_INIT_SIZE;
}

void Push(SqStack* s, SElemType e) {
	if (s->top - s->base >= s->stacksize) {
		s->base = (SElemType*)realloc(s->base, (s->stacksize + 10) * sizeof(SElemType));
		s->top = s->base + s->stacksize;
		s->stacksize += 10;
	}
	*s->top++ = e;
}

void Pop(SqStack* s, SElemType* e) {
	*e = *--s->top;
}

SElemType GetTop(SqStack s) {
	return *(--s.top);
}

void DestroyStack(SqStack* s) {
	free(s->base);
	s->base = NULL;
	s->top = NULL;
	s->stacksize = 0;
}

void MaxInit(Maxstack* maxstack) {
	InitStack(&(maxstack->Data));
	InitStack(&(maxstack->MaxData));
}

void MaxDestroy(Maxstack* maxstack) {
	DestroyStack(&maxstack->Data);
	DestroyStack(&maxstack->MaxData);
}

void MaxPush(Maxstack* maxstack, SElemType e) {
	Push(&maxstack->Data, e);
	if (maxstack->MaxData.base == maxstack->MaxData.top) {
		Push(&maxstack->MaxData, e);
	}
	else {
		if (e >= GetTop(maxstack->MaxData)) {
			Push(&maxstack->MaxData, e);
		}
	}
}

void MaxPop(Maxstack* maxstack, SElemType* e) {
	if (GetTop(maxstack->Data) == GetTop(maxstack->MaxData)) {
		Pop(&maxstack->Data, e);
		Pop(&maxstack->MaxData, e);
		return;
	}
	Pop(&maxstack->Data, e);
}

SElemType GetMax(Maxstack* maxstack) {
	return GetTop(maxstack->MaxData);
}





int main() {
	Maxstack maxstack;
	SElemType e;
	MaxInit(&maxstack);

	MaxPush(&maxstack, 1);
	MaxPush(&maxstack, 2);
	MaxPush(&maxstack, 3);
	MaxPush(&maxstack, 1);

	cout << GetMax(&maxstack) << endl;
}

对于栈方式存储动态序列以及求取最大值比较容易实现，对于最大值引入最大栈用空间换时间，时间复杂度达到$O(1)$，但是不够对于序列的操作不够灵活，只能在栈顶进行操作。