题目描述：
考虑包含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
解题思路：排除前导为0的数和当前位为0且前一位也为0的数
#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int n,k; int cnt; int a[1010]; void dfs(int x)// { if(x==n) { cnt++; return ; } for(int i=0;i<k;i++) { ///首位为0 当前位为0且前一位也为零 if(x==0&&i==0||(x>0&&i==0&&a[x-1]==0)) continue; a[x]=i; dfs(x+1); } } int main() { while(~scanf("%d%d",&n,&k)) { memset(a,0,sizeof(a)); cnt=0; dfs(0); printf("%d\n",cnt); } return 0; }
