怎么进入网站管理系统,做网站找哪家,站长之家网址ip查询,新闻软文广告题目描述 Eric喜欢使用数字1,2,3,4作为密码#xff0c;而且他有个怪癖#xff0c;相邻数字不能相同#xff0c;且相差不能超过2。当然只用数字做密码#xff0c;会比较弱#xff0c;Eric想知道当长度为n时#xff0c;这样的密码有多少种#xff1f; 输入 第一行是一个整… 题目描述 Eric喜欢使用数字1,2,3,4作为密码而且他有个怪癖相邻数字不能相同且相差不能超过2。当然只用数字做密码会比较弱Eric想知道当长度为n时这样的密码有多少种 输入 第一行是一个整数T(1≤T≤45),表示样例的个数。 每行一个样例为整数n(1≤T≤45)。 输出 每行输出一个样例的结果。 样例输入 5
1
2
3
4
5样例输出 4
10
26
66
170 解题思路这题就用递推的方法来解。 何为递推顾名思义就是一步一步的推理~~答案是推出来的。 然后从 相邻数字不能相同且相差不能超过2 这个条件入手。
当长度n1时密码有几种情况? 秒答1、2、3、4 四种情况
那长度n2时有几种情况这时就已经要开始递推了。当第一位数字是1第二位数字可为 2、3当第一位数字是2第二位数字可为 1、3、4当第一位数字是3第二位数字可为 1、2、4当第一位数字是4第二位数字可为 2、3。 这是一共就是 2332种情况。
此时如果你能具有一定的敏感性懂得逆向思考一下这题已经解决了。如果我先规定第2位的数字然后再考虑前面的情况。规定是1那第一位只能是2、3规定是2那第一位只能是1、3、4........
推广先规定第n位的数字然后找到符合条件的第n-1位数和它匹配。 那就是 第n位是1的种类数等于第n-1位是2的种类数第n-1位是3的种类数第n位是2的种类数等于第n-1位是1的种类数第n-1位是3的种类数第n-1位是4的种类数........
现在你是否能得出答案。注意这种情况数字都很大往往要考虑是否会爆int
AC代码
#include stdio.hint T,N;
__int64 ak47[50][5];
__int64 ans;void slove()
{ak47[1][1] ak47[1][2] ak47[1][3] ak47[1][4] 1;for (int i 2; i 45; i ){ak47[i][1] ak47[i-1][2]ak47[i-1][3];ak47[i][2] ak47[i-1][1]ak47[i-1][3]ak47[i-1][4];ak47[i][3] ak47[i-1][1]ak47[i-1][2]ak47[i-1][4];ak47[i][4] ak47[i-1][2]ak47[i-1][3];}
}int main()
{slove(); // 递推scanf(%d,T);while ( T --){scanf(%d,N);ans ak47[N][1]ak47[N][2]ak47[N][3]ak47[N][4];printf(%I64d\n,ans);}return 0;
}
