数据结构代码集训day15（适合考研、自学、期末和专升本）
本份题目来自B站up：白话拆解数据结构
今日题目如下;
（1）编写算法，实现十进制转十六进制；
（2）汉诺塔（Hanoi Tower），又称河内塔，源于印度一个古老传说。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。问应该如何操作？
（3）假设你正在玩跳格子（所有格子排成一个纵列）游戏。需要跳完n 个格子你才能抵达终点。每次你可以跳 1 或 2 个格子。你有多少种不同的方法可以到达终点呢？
题1
进制转换有个公式N = （N / d) + N mod d，就是下面这个过程（举个例子）
上面那个里子是十进制转八进制，16进制也一样的过程，将被除数不断和16整除，余数（取模得到）压入栈中，再依次出栈即可。
有一点不一样的就是，16进制到十之后含有字母ABCD等，所以超过10的数要单独处理一下。
int func(int m,int n){ // m为传入的数，n为要转换的进制
bool flag=false;
if(m<0) { // 负数单独处理
m=abs(m);
flag=true;
}
stack<int> s;
int temp1,temp2;
while(m>0){
temp1=m%n; // 余数压栈
s.push(temp1);
m=m/n;
}
if (flag) printf("-");
while(!s.empty()){ // 依次出栈
temp2=s.top();
if(temp2<10) printf("%d",temp2);
else printf("%c",temp2-10+'A'); // 单独处理
s.pop();
}
return 0;
}
实践一下：
将44转为16进制
将-38转为16进制
完整代码如下：
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
// 十进制转十六进制
int func(int m,int n){
bool flag=false;
if(m<0) {
m=abs(m);
flag=true;
}
stack<int> s;
int temp1,temp2;
while(m>0){
temp1=m%n;
s.push(temp1);
m=m/n;
}
if (flag) printf("-");
while(!s.empty()){
temp2=s.top();
if(temp2<10) printf("%d",temp2);
else printf("%c",temp2-10+'A');
s.pop();
}
return 0;
}
int main(){
int m,n;
cin>>m>>n;
func(m,n);
return 0;
}题2
图示一下过程，我第一次读也没咋读懂。
这是一道标准的递归题目，我们逐步拆解，假设只有一个盘子（也就是递归出口），直接放到c盘就行了。
当有两个盘子的时候，先将一号盘放到b盘里，然后把2号盘放到c盘里，最后把1号盘放到c里就行了。
关键来了，当有三个盘的时候，我们可以把上面两个视为一个整体，然后就是上面那种情况的变式了。
就是将上面整体移动到B柱，然后将A柱最底下的盘子移到C柱，最后将B柱上的整体移动到C柱。看似好像因为不符合题意不可能完成，实际上 ① 和 ③将两个盘子移动另一个柱子上。而这恰恰是当n=2时，移动2个盘子的情况。
当n=4时，有4个盘子时。同样的道理，将A柱上的3个盘子当做整体，然后依次完成以上三个步骤，就可实现目标。
同理，类比到n，当有n个盘子时，可将A柱上的n-1个盘子作为一个整体，然后分别执行以上三个步骤，就可实现目标。
建议大家画一下n=3或者n=4的情况，可以加深理解。当n不等于1时，其实是有两个递归过程的。下面是c++的类，也可以称为一种方法，里面有两个公共的成员函数，可以通过调用hanota函数来实现功能。
class Solution{
public:
void hanota(stack<int> &a,stack<int> &b,stack<int> &c){
int n=a.size();
move(n,a,b,c); //将a通过b移到c
}
void move(int n,stack<int> &a,stack<int> &b,stack<int> &c){
if(n==1){
int m=a.top();
a.pop();
c.push(m);
return;
}
move(n-1,a,c,b); //将a通过c移到b
int s=a.top();
a.pop();
c.push(s);
move(n-1,b,a,c); //将b通过a移到c
}
};
实践一下：
这里我们是通过三个栈来实现的，我们先将栈a赋值，然后在调用hanota函数后，观察一下栈内元素大小变化，来判断是否转移了。
完整代码如下：
#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
// 汉诺塔
class Solution{
public:
void hanota(stack<int> &a,stack<int> &b,stack<int> &c){
int n=a.size();
move(n,a,b,c);
}
void move(int n,stack<int> &a,stack<int> &b,stack<int> &c){
if(n==1){
int m=a.top();
a.pop();
c.push(m);
return;
}
move(n-1,a,c,b);
int s=a.top();
a.pop();
c.push(s);
move(n-1,b,a,c);
}
};
int main(){
stack<int> a,b,c;
for (int i = 6; i >= 1; --i) {
int b;
cin>>b;
a.push(b);
}
printf("stack a value are:");
for(int i=6;i>=1;--i){
int s=a.top();
printf("%d ",s);
a.pop();
}
for (int i = 6; i >= 1; --i) {
int b;
cin>>b;
a.push(b);
}
Solution cc;
cc.hanota(a,b,c);
printf("stack a length:%d\n",a.size());
printf("stack b length:%d\n",b.size());
printf("stack c length:%d\n",c.size());
printf("stack c value are:");
for(int i=6;i>=1;--i){
int a=c.top();
printf("%d ",a);
c.pop();
}
return 0;
}题3
这题我第一遍读以为是DP，不过他问的是方案没让我打印具体路线，那递归也能做。等后面学完dp再来会会这道题。
两个递归出口就行了。
int countWays(int n) {
// 基本情况
if (n == 0) return 1; // 跳到第0格只有1种方法，即什么都不做
if (n == 1) return 1; // 跳到第1格只有1种方法
// 递归计算
return countWays(n - 1) + countWays(n - 2);
}
实践一下：n=4时有5种方案。
完整代码如下：
#include <iostream>
using namespace std;
int countWays(int n) {
// 基本情况
if (n == 0) return 1; // 跳到第0格只有1种方法，即什么都不做
if (n == 1) return 1; // 跳到第1格只有1种方法
// 递归计算
return countWays(n - 1) + countWays(n - 2);
}
int main() {
int n;
cout << "Enter the number of steps (n): ";
cin >> n;
int ways = countWays(n);
cout << "Number of ways to reach step " << n << ": " << ways << endl;
return 0;
}