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);
		}
	}
}