[数据结构与算法]【2021-09-23】每日总结

算法设计与分析习题

题解：数据小的情况下可以用程序运行出结果
递归算法，C++实现代码如下，

#include <iostream>
using namespace std;
using gg =long long; 
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
/*move方法一次移动一个盘子*/

void move(gg n,char A,char C){
	cout<<n<<":"<<A<<"->"<<C<<endl;
}

/*汉诺塔递归函数*/
void hanoi(gg n,char A,char B,char C){//n个盘子,b为辅助柱 
	if(n==1){
		move(1,A,C);//只有一个盘子时直接从A移到C 
	}
	else{
		hanoi(n-1,A,C,B);//把n-1个盘子从A移到B，借助C
		move(n,A,C);//把编号为n的盘子从A移到C
		hanoi(n-1,B,A,C);//把剩下的n-1个盘子从B移到C 
	}
}

int main(int argc, char** argv) {
	hanoi(4,'A','B','C'); 
	return 0;
}

但是n=64运算量过于庞大，只能通过列举找规律的方法推导（虽然这种方法一点也不严谨，但是这种一看起来就有规律的东西也不妨一试）

推导如下：

n Steps
1 1
2 3
3 7
4 15
5 31
6 63
… …
60 264-1

推导的结果就是n层汉诺塔的移动步数F(n)=2n-1
根据网上搜索到的数据，移动完64层汉诺塔一共需要264-1=18,446,744,073,709,551,615步
若一秒一步，移动完64层汉诺塔需要5845.54亿年

非递归算法：网上代码+自己的理解

void Myhanoi(gg n,char a,char b,char c){
	//struct student s[30]结构体数组声明方式 
	struct act{int flag;gg num;char x,y,z;} S[2000];//用数组实现栈，act为数组存储的元素 
	gg top=0LL,m;
	char ta,tb,tc;
	//首元素入栈
	S[0].flag=1;
	S[0].num=n;
	S[0].x=a;
	S[0].y=b;
	S[0].z=c;
	//进入循环，相当于中序遍历二叉树 
	while(top>=0LL){
		if(S[top].flag==0||S[top].num==1){
			cout<<S[top].num<<":"<<S[top].x<<"->"<<S[top].z<<endl;
			top--;
		}
		else{
			//获取栈顶元素,相当于根节点 
			m=S[top].num;
			ta=S[top].x;
			tb=S[top].y;
			tc=S[top].z;
//			top++;//??????
			//递归算法后操作的先入栈,覆盖栈顶元素,因为入栈的第一步操作不是将第m个圆盘从A移到C，而是将第m-1个圆盘从B移到C 
			S[top].flag=1;
			S[top].num=m-1;
			S[top].x=tb;
			S[top].y=ta;
			S[top].z=tc;
			top++;
			//遍历根节点
			S[top].flag=0;
			S[top].num=m;
			S[top].x=ta;
			S[top].y=tb;
			S[top].z=tc;
			top++;
			//最后不需要移动栈顶,下一个循环会移动 
			 S[top].flag=1;
			 S[top].num=m-1;
			 S[top].x=ta;
			 S[top].y=tc;
			 S[top].z=tb;
		}
	} 
}

2.4.14
名人问题

伪代码：

算法复杂度：
第一个循环语句执行了n-1次，第二个循环执行了2*(n-1)次，总共执行了3*（n-1）次，时间复杂度为O(n)

2.5.2

自己的理解：

代码实现：求斐波那契数列

#include <iostream>
using namespace std;
using gg =long long;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
/*斐波那契兔子问题*/
int main(int argc, char** argv) {
	gg n;
	cin>>n;
	gg a=0LL;
	gg b=0LL;
	gg c=0LL;
	for(int i=1;i<=n;i++){
		if(i==1){//第一天 
			a=1;
			c=a;
		}
		else if(i==2){//第2天 
			b=1;
			c=b;
		}
		else{
			c=a+b;
			a=b;
			b=c;
		}
	}
	cout<<c;
	return 0;
}