作者：指针不指南吗
专栏：蓝桥杯倒计时冲刺

🐾马上就要蓝桥杯了，最后的这几天尤为重要，不可懈怠哦🐾

1.母牛的故事

• 题目

  链接： [递归]母牛的故事 - C语言网 (dotcpp.com)

  有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

  输入格式

  输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
  n=0表示输入数据的结束，不做处理。

  输出格式

  对于每个测试实例，输出在第n年的时候母牛的数量。
  每个输出占一行。

  样例输入

  2
  4
  5
  0
  

  样例输出

  2
  4
  6
  

• 第一次 AC 50%

  #include<bits/stdc++.h>
  using namespace std;
  
  int main()
  {
  	int n;
  	while(cin>>n)
  	{
  		int sum=0;
  		
  		if(n==0)
  			return 0;
  		for(int i=1;i<=n;i++)
  		{
  			if(i<=4)
  				sum+=1;
  			else 
  				sum+=i-3;
  		}
  		
  		cout<<sum<<endl;
  	}
  	
  	return 0;
  }
  

  枚举了前几个数，找的规律是错的

• 第二次 AC 50% + 超时 50%

  #include<bits/stdc++.h>
  using namespace std;
  
  int f(int n)
  {
  	if(n<=4)
  		return n;
  	return f(n-2)+f(n-3)+f(n-4);
  }
  
  int main()
  {
  	int n;
  	while(scanf("%d",&n))
  	{
  		if(n==0)
  			return 0;
  		
  		cout<<f(n)<<endl;
  	}
  	
  	return 0;
  }
  

  递归+规律，第二次递归的规律又找错了

• 第三次 AC 50% + 50% 超时

  #include<bits/stdc++.h>
  using namespace std;
  
  int f(int n)
  {
  	if(n<4)
  		return n;
  	return f(n-1)+f(n-3);
  }
  
  int main()
  {
  	int n;
  	while(scanf("%d",&n)&&n)  //记住这个，当输入0时，跳出循环
  	{
  		cout<<f(n)<<endl;
  	}
  	
  	return 0;
  }
  

  这次 规律对，但还是 超时

• 第四次 AC 100%

  #include<bits/stdc++.h>
  using namespace std;
  
  int main()
  {
  	int n;
  	while(scanf("%d",&n)&&n)
  	{
  		int a[60];
  		a[1]=1,a[2]=2,a[3]=3;
  		
  		for(int i=4;i<=n;i++)  //使用数组递归
  		{
  			a[i]=a[i-1]+a[i-3];
  		}
  		
  		cout<<a[n]<<endl;
  	}
  	
  	return 0;
  }
  

• 反思

  找规律的题：

  ​ 不要局限在前后相邻的数，不要只找一组，就直接把规律定下来，多找几组

  找规律题中+递归，一开始根本没有往这方面想

  How

  1. 找规律，发散思维，很有可能有递归，看看前后几个数之间的关系
  2. 递归函数，可能会超时，考试的时候，就直接使用 数组来代替函数

2.魔板

• 题目

  链接： 魔板 - C语言网 (dotcpp.com)

  在魔方风靡全球之后不久，Rubik先生发明了它的简化版――魔板。魔板 由8个同样大小的方块组成，每个方块颜色均不相同，可用数字1-8分别表示。任一时刻魔板的状态可用方块的颜色序列表示：从魔板的左上角开始，按顺时针方 向依次写下各方块的颜色代号，所得到的数字序列即可表示此时魔板的状态。例如，序列(1,2,3,4,5,6,7,8)表示魔板状态为：
  1 2 3 4
  8 7 6 5
  对于魔板，可施加三种不同的操作，具体操作方法如下：
  A: 上下两行互换,如上图可变换为状态87654321
  B: 每行同时循环右移一格,如上图可变换为41236785
  C: 中间4个方块顺时针旋转一格,如上图可变换为17245368
  给你魔板的初始状态与目标状态，请给出由初态到目态变换数最少的变换步骤，若有多种变换方案则取字典序最小的那种。

  输入格式

  每组测试数据包括两行，分别代表魔板的初态与目态。

  输出格式

  对每组测试数据输出满足题意的变换步骤。

  样例输入

  12345678
  17245368
  12345678
  82754631
  

  样例输出

  C
  AC
  

• 第一次 AC 0%

  #include<bits/stdc++.h>
  using namespace std;
  
  const int N=1010;
  int d[N];
  
  string FA(string a)
  {
  	string b=a;
  		
  	a[0]=b[4],a[1]=b[5],a[2]=b[6],a[3]=b[7];
  	a[4]=b[0],a[5]=b[1],a[6]=b[2],a[7]=b[3];
  	
  	return a;
  }
  
  string FB(string a)
  {
  	string b=a;
  		
  	a[0]=b[3],a[1]=b[0],a[2]=b[1],a[3]=b[2],a[4]=b[6];
  	a[5]=b[5],a[6]=b[4],a[7]=b[7];
  	
  	return a;
  }
  
  string FC(string a)
  {
  	
  	string b=a;
  		
  	a[0]=b[0],a[1]=b[5],a[2]=b[1],a[3]=b[3];
  	a[4]=b[4],a[5]=b[6],a[6]=b[2],a[7]=b[7];
  	
  	return a;
  }
  void bfs(string st,string over)
  {
  	queue<string> q;
  	q.push(st);
  	
  	unordered_map<string,string> mp;
  	
  	while(q.size())
  	{
  		auto now=q.front();
  		q.pop();
  		
  		if(now==over)
  		{
  			cout<<mp[now]<<endl;
  			return ;
  		}
  		
  		string ss;
  		for(int i=1;i<=3;i++)
  		{
  			switch(i)
  			{
  				case 1:
  					ss=FA(now);
  					if(!mp.count(ss))
  					{
  						q.push(ss);
  						mp[ss]=mp[now]+'A';
  					}
  					break;
  				case 2:
  					ss=FB(now);
  					if(!mp.count(ss))
  					{
  						q.push(ss);
  						mp[ss]=mp[now]+'B';
  					}
  					break;
  				case 3:
  					ss=FB(now);
  					if(!mp.count(ss))
  					{
  						q.push(ss);
  						mp[ss]=mp[now]+'C';
  					}
  					break;
  			}
  		}
  	}
  	
  }
  
  int main()
  {
  	string a,b;
  	while(cin>>a>>b)
  	{
  		bfs(a,b);
  	}
  	
  	return 0;
  }
  

  一开始，框架都写出来，但是输出 转换的路径写不出来，忘记咋写了

  好像是倒推，前几天写过，题解中的是用的 STL 里面的 map

  哪里出错了，还没有看出来，他没有输出

• 题解

  #include<bits/stdc++.h>
  using namespace std;
  // 定义两个变量s和f，代表起点状态和终点状态，其值由输入读入
  string s, f;
  // 操作A函数，将输入状态x按照操作A的规则进行变换
  string A(string x) {
      string s = x;
      for (int i = 0; i < 4; i++) {
          swap(s[i], x[7 - i]);
          swap(s[i + 4], x[3 - i]);
      }
      return s;
  }
  // 操作B函数，将输入状态x按照操作B的规则进行变换
  string B(string x) {
      string s = x;
      s[0] = x[3], s[1] = x[0];
      s[2] = x[1], s[3] = x[2];
      s[4] = x[5], s[5] = x[6];
      s[6] = x[7], s[7] = x[4];
      return s;
  }
  // 操作C函数，将输入状态x按照操作C的规则进行变换
  string C(string x) {
      string s = x;
      s[1] = x[6], s[2] = x[1];
      s[5] = x[2], s[6] = x[5];
      return s;
  }
  // 广搜函数，使用map进行去重，记录操作序列
  void bfs() {
      unordered_map<string, string>mp; // 哈希表，用于存储操作序列
      queue<string>q; // 队列，用于存储待搜索状态
      q.push(s); // 将初始状态入队
      while (!q.empty()) { // 只要队列不为空，就继续搜索
          string now = q.front(); // 取出队首元素
          q.pop(); // 将队首元素出队
          if (now == f) { // 当达到终点状态，输出操作序列
              cout << mp[now] << endl;
              return; // 搜索结束
          }
          string ts; // 操作后的状态
          // 按照题目要求，A、B、C操作依次搜索，保证字典序最小
          for (int i = 0; i < 3; i++) { // 依次搜索ABC操作，保证字典序最小
              switch (i) {
                  case 0: // A操作
                      ts = A(now); // 对当前状态进行A操作
                      if (!mp.count(ts)) { // 如果操作后的状态不在哈希表中
                          q.push(ts); // 将操作后的状态入队
                          mp[ts] = mp[now] + 'A'; // 更新哈希表，存储操作序列
                      }
                      break;
                  case 1: // B操作
                      ts = B(now); // 对当前状态进行B操作
                      if (!mp.count(ts)) { // 如果操作后的状态不在哈希表中
                          q.push(ts); // 将操作后的状态入队
                          mp[ts] = mp[now] + 'B';// 更新哈希表，存储操作序列
                      }
                      break;
                  case 2://C操作
                      ts = C(now); // 对当前状态进行B操作
                      if (!mp.count(ts)) { // 如果操作后的状态不在哈希表中
                          q.push(ts); // 将操作后的状态入队
                          mp[ts] = mp[now] + 'C';// 更新哈希表，存储操作序列
                      }
                      break;
              }
          }
      }
  }
  int main() {
      while (cin >> s >> f) {
          bfs();
      }
      return 0;
  }
  

• 反思

  通过三种不同的转化状态+最少变化步骤，我们可以确定是 BFS

  对于我来说，这个题的难点不在于确定最少的步数是多少，而是输出路径

  1. 学到了使用 switch 执行不同的函数，我差点就使用函数数组了TvT

  2. 借助了 map 去重+输出路径，学到了

  之前我以为路径都必须倒推，很麻烦，map 真的好用

  我们再研究一下，路径的记录，再刷一两道题这个类型的题