题目描述
考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0. 考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0. 例:
1010230 是有效的7位数
1000198 无效
0001235 不是7位数, 而是4位数. 给定两个数N和K, 要求计算包含N位数字的有效K-进制数的总数. 假设2 <= K <= 10; 2 <= N; 4 <= N+K <= 18. 输入
两个十进制整数N和K 输出
十进制表示的结果 样例输入
2
10
样例输出
90
//K进制 递推牛逼
#include<stdio.h>
int k;
int f(int n)
{
if(n == )
{
return k-;
}
else if(n == )
{
return (k-)*k;
}
else
{
return f(n-)*(k-) + f(n-)*(k-) ; }
}
int main()
{
int n;
scanf("%d%d", &n, &k);
printf("%d\n",f(n));
return ;
}
不能连续两个0 与第一位不能为0，存在递推关系
实际上是一个深搜问题 dfs
1.最高位不能是0
#include<iostream>
using namespace std; int n,k;//n是位数，k是进制数
char s[];
int total;
void dfs(int cur){
char temp;
if(cur==n)
total++;
else
for(int i=;i<k;i++){
temp = i+'';
if((cur== && temp == '') || (temp == '' && s[cur-] == ''))
continue;
s[cur] = i+'';
dfs(cur+);
}
} int main(){
cin>>n>>k;
dfs();
cout<<total<<endl;
}