k进制数
k-进制数
1.题目：
考虑包含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
2.思路：
比如 n等于2 k = 10 表示2位10进制数 但是不能包含两个连续的0 问一共有多少种有效的数字
当为2为时 我们可以确定第一位 因为首位不能为0 所以可以从1-9 所以首位种数为（k-1) 为9
而第二个数可以为0 所以可以从0 - 9 一共有10种 两个数组合起来一共就有90种组合
当n = 1 有效数字为9种
当n = 2 有效数字为90种
当n = 3 有效数字为821种
通过上面我们发现一个规律就是当N大于2时 它的有效数字组合是前两项的和乘以（k-1)
因为当为3位时 首位我们是可以确定的 只有k-1位 而第二位可以为0 或者1
（1）当为0的时候 第三位必须为1 所以它的组合数就是 当n = 2 时候的组合数
（2）当为1的时候，第三位必须为0 所以它的组合数就是当 n= 1时候的组合数
所以n大于2的时候 我们只需要把前两项和加起来乘（k-1)
3.具体代码实现(java)
(1)用数组做法
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int [] arr = new int[n+1];
for(int i = 1 ; i <arr.length;i++) {
if(i == 1) {
arr[i] = k - 1;//当为一位的时候首位又不能为0 所以只有1-9 一共9个有效数字
} else if(i==2) {
arr[i] = k*(k-1);//首位是（k-1)为 当k = 10 时 第一位就是9种 而第二位可以是从0到9 一共10种 所以一共就有90 种有效数字
} else {
arr[i] =( arr[i-1]+arr[i-2])*(k-1);//当n大于2时 有效数字时前两项之和乘首位总和 9
}
}
System.out.println(arr[n]);
}
(2)我们可以用递归
public static int K(int n ,int k) {
if(n == 1) {
return (k-1) ;
} else if(n==2) {
return k*(k-1);
} else {
return (K(n-1,k)+K(n-2,k))*(k-1);
}
}
4.联系方式
qq：2061302791
微信：xie2061302791
电话：15284524485
个人网站：https://xieyingpeng.github.io/
Github：https://github.com/xieyingpeng/
博客园：https://www.cnblogs.com/Xieyingpengz
知乎：https://www.zhihu.com/people/nan-qiao-12-73