K-进制数

K-进制

题目描述

考虑包含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，那么有k-1种选择，_是除了0以外的数，所以有k-1种选择

所以可以一步步的进行推断，可以连着，但是0后面必须是

_表示已经确定出来的，0就表示这一位上是零，X表示未确定的位数

假设是五位数

一开始这一串数字就是_xxxx

分析图

之后这个题就可以用dfs深度优先搜索来解题：

public class K进制 {
//	求和sum
	static int sum=0;
//	位数
	static int n;
//	进制
	static int k;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		 n=sc.nextInt();
		 k=sc.nextInt();
		dfs(1,1);
		System.out.println(sum);
	}
//	length表示已经确定的长度（_，0都算），step代表_的个数
	private static void dfs(int length, int step) {
//		当length==n时，表明这一串已经确定好了（除了0就是_）
		if(length==n) {
			sum+=Math.pow(k-1, step);
			return;
		}
//	有一种情况当最后一位是X时，X变成0，就会出现一个X被0_代替,这个时候length会成为n+1,而step也会多出来一个_,
//	这时候step应当减一
		if(length==n+1) {
			sum+=Math.pow(k-1, step-1);
			return;
		}
//		深度优先搜索:
//			当X变成_时，length+1且step+1;
//		    当X变成0时，length+2,step+1 (因为0后面必定是_,所以length就直接确定两位，一位是0，另一位是_)
		for(int i=1;i<3;i++) {
			dfs(length+i, step+1);
		}
	}
}