长春电商网站建设哪家专业,免费算生辰八字算命,山东专业网站开发公司,注册成立公司的基本流程作者#xff1a;指针不指南吗 专栏#xff1a;蓝桥杯倒计时冲刺 #x1f43e;马上就要蓝桥杯了#xff0c;最后的这几天尤为重要#xff0c;不可懈怠哦#x1f43e; 文章目录1.母牛的故事2.魔板1.母牛的故事 题目 链接#xff1a; [递归]母牛的故事 - C语言网 (dotcpp.c… 作者指针不指南吗 专栏蓝桥杯倒计时冲刺 马上就要蓝桥杯了最后的这几天尤为重要不可懈怠哦 文章目录1.母牛的故事2.魔板1.母牛的故事 题目 链接 [递归]母牛的故事 - C语言网 (dotcpp.com) 有一头母牛它每年年初生一头小母牛。每头小母牛从第四个年头开始每年年初也生一头小母牛。请编程实现在第n年的时候共有多少头母牛 输入格式 输入数据由多个测试实例组成每个测试实例占一行包括一个整数n(0n55)n的含义如题目中描述。 n0表示输入数据的结束不做处理。 输出格式 对于每个测试实例输出在第n年的时候母牛的数量。 每个输出占一行。 样例输入 2
4
5
0样例输出 2
4
6第一次 AC 50% #includebits/stdc.h
using namespace std;int main()
{int n;while(cinn){int sum0;if(n0)return 0;for(int i1;in;i){if(i4)sum1;else sumi-3;}coutsumendl;}return 0;
}枚举了前几个数找的规律是错的 第二次 AC 50% 超时 50% #includebits/stdc.h
using namespace std;int f(int n)
{if(n4)return n;return f(n-2)f(n-3)f(n-4);
}int main()
{int n;while(scanf(%d,n)){if(n0)return 0;coutf(n)endl;}return 0;
}递归规律第二次递归的规律又找错了 第三次 AC 50% 50% 超时 #includebits/stdc.h
using namespace std;int f(int n)
{if(n4)return n;return f(n-1)f(n-3);
}int main()
{int n;while(scanf(%d,n)n) //记住这个当输入0时跳出循环{coutf(n)endl;}return 0;
}这次 规律对但还是 超时 第四次 AC 100% #includebits/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 i4;in;i) //使用数组递归{a[i]a[i-1]a[i-3];}couta[n]endl;}return 0;
}反思 找规律的题 不要局限在前后相邻的数不要只找一组就直接把规律定下来多找几组 找规律题中递归一开始根本没有往这方面想 How 找规律发散思维很有可能有递归看看前后几个数之间的关系递归函数可能会超时考试的时候就直接使用 数组来代替函数
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% #includebits/stdc.h
using namespace std;const int N1010;
int d[N];string FA(string a)
{string ba;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 ba;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 ba;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)
{queuestring q;q.push(st);unordered_mapstring,string mp;while(q.size()){auto nowq.front();q.pop();if(nowover){coutmp[now]endl;return ;}string ss;for(int i1;i3;i){switch(i){case 1:ssFA(now);if(!mp.count(ss)){q.push(ss);mp[ss]mp[now]A;}break;case 2:ssFB(now);if(!mp.count(ss)){q.push(ss);mp[ss]mp[now]B;}break;case 3:ssFB(now);if(!mp.count(ss)){q.push(ss);mp[ss]mp[now]C;}break;}}}}int main()
{string a,b;while(cinab){bfs(a,b);}return 0;
}一开始框架都写出来但是输出 转换的路径写不出来忘记咋写了 好像是倒推前几天写过题解中的是用的 STL 里面的 map 哪里出错了还没有看出来他没有输出 题解 #includebits/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_mapstring, stringmp; // 哈希表用于存储操作序列queuestringq; // 队列用于存储待搜索状态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 对于我来说这个题的难点不在于确定最少的步数是多少而是输出路径 学到了使用 switch 执行不同的函数我差点就使用函数数组了TvT 借助了 map 去重输出路径学到了 之前我以为路径都必须倒推很麻烦map 真的好用 我们再研究一下路径的记录再刷一两道题这个类型的题
