【2022.7.25 星期一】考研日记：汉诺塔，栈+队列

上午：660题（210~225）+高数强化+线代
【重点：①微分方程，②利用微分方程解决罗尔定理证明题】
下午：408数据结构
晚上：200单词+英语翻译

数据结构知识积累：
①不使用递归，计算1个n层的汉诺塔，从A柱到C柱的所有步数

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>
int main()
{
	int num = 0;
	scanf("%d", &num);//塔数
	printf("%d层塔需要%d步n", num, (int)pow(2,num) - 1);
	return 0;
}
【pow是x的y次幂】

②使用递归，计算1个n层的汉诺塔，从A柱到C柱的所有步数

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
int Hanio_twice(int num)
{
	if(1 == num)
		return 1;
	else
		return 2 * Hanio_twice(num - 1) + 1;
}

int main()
{
	int num = 0;	
	scanf("%d", &num);//塔数
	int ret = Hanio_twice(num);
	printf("完成%d层的汉诺塔需要%d步n", num, ret);
	return 0;
}

③使用递归，打印1个n层的汉诺塔从A柱到C柱的所有步骤

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
void Hanio_Step(int n, char A, char B, char C)
{
	if (1 == n)
		printf("%c->%cn", A, C);
	else
	{
		Hanio_Step(n-1, A, C, B);
		printf("%c->%c", A, C);
		Hanio_Step(n-1, B, A, C);
	}
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	Hanio_Step(n, 'A', 'B', 'C');
	return 0;
}

④栈和堆（Stack & Heap）
操作系统OS中一个有趣的现象：参数和变量存放在栈（Stack）中，而动态分配的内存在堆（Heap）中

⑤"栈"实现括号匹配
【给定只有 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效】
【有效字符串需满足：】
【左括号必须用相同类型的右括号闭合。】
【左括号必须以正确的顺序闭合。】

char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}

bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {
        return false;
    }
    int stk[n + 1], top = 0;
    for (int i = 0; i < n; i++) {
        char ch = pairs(s[i]);
        if (ch) {
            if (top == 0 || stk[top - 1] != ch) {
                return false;
            }
            top--;
        } else {
            stk[top++] = s[i];
        }
    }
    return top == 0;
}