原题链接：K-进制数
题目描述：
一个合法的n位K进制数定义如下： 它是一个首位不为0的K进制数。 它不包含连续的两个0。对于输 入的K，n。求出满足上述条件的K进制数个数。
解题思路：
这个题应该是一个递推题。可以用f[i]表示i位(最高位是第i位)K进制数的总数，那么就应该有：f[i]=(f[i-1]+f[i-2])*(k-1)。
解释一下：f[i]也就是i位K进制数的总数应该等于：第i-1位为0与第i-1位不为0的情况的和乘以第i位的情况数(1..k-1)
(1)第i-1位为0的情况应该等于i-2位不为0的情况总数，即f[i-2]
(2)第i-1位不为0的情况应该等于f[i-1]
所以f[i]=(f[i-1]+f[i-2])*(k-1)
参考代码:
#include<stdio.h>
int k;
int f(int n)
{
if(n == 1)
{
return k-1;
}
else if(n == 2)
{
return (k-1)*k;
}
else
{
return f(n-1)*(k-1) + f(n-2)*(k-1) ; }
}
int main()
{
int n;
scanf("%d%d", &n, &k);
printf("%d\n",f(n));
return 0;
}欢迎留言
0.0分
10 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复