时人

用户名：17633532082

访问量：3493

签　名：

等　　级
排　　名	11885
经　　验	1003
参赛次数	0
文章发表	9
年　　龄	0
在职情况	学生
学　　校	河南大学
专　　业

　　自我简介：

TA的其他文章

思路简单的暴力解法
浏览：261

你可能喜欢

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

K-进制数-题解（Java代码）超详细

　　作者: 时人　　　　发表时间：2021-01-23 22:50:54 浏览：1174　|　评论：0　

原题链接：K-进制数

### 思路：
对于一个K进制N位的数，我们用"\_"来代替某一位是（1~K-1）,用"0"表示某一位上是0，我们的任务就是找到所有种“\_”和“0”的符合题意的排列组合，然后把每一种排列的种数相加即可。很明显一种排列如"\_0\_0\_",它有三个"\_"，则这种排列的种数为(k-1)^3种，因此我们记录下每种排列的"\_"的个数即可，接下来我们就来看如何求每种排列。

**对于一个N位的数，采用从左到右插0的方法。**
1. 我们不妨先设一个待确定的数为 xxxx ,四位数，进制为K。
2. 首先第一位数不能取0，可以取（1~K-1）的数，那么我们认为这一位是确定的，有（K-1）种选择，那么现在的数就变成了 \_xxx。
3. 接下来第二位可以是0也可以是"\_",当是0时，则第三位必须是"\_",当是"\_"时，则不能确定第三位，这时N位数就变成了\_0\_x和\_\_xx,对于这两个数重复用刚才的方法就可以一直确定下去直到全部确定，这是一个递归的过程。
4. 从第三步我们可以看出，在确定位的时候有两种选择，一是一次确定一位，二是一次确定两位，"\_"的数量都是加一。
![](/image_editor_upload/20210123103903_22393.png)

### 编码实现：
```java
public class Main {
    public static int sum = 0; //记录最终结果
    public static int K;	//接收进制
    public static int N;	//接收位数
    public static void main(String[] args){
        Scanner reader = new Scanner(System.in);
            int n = reader.nextInt();
            int k = reader.nextInt();
            N = n;
            K = k;
            dfs(1,1);//第一次传入1，1,因为第一位已经确定
            System.out.println(sum);
    }
	//深度优先搜索算法，length表示以确定的长度，step记录"_"的个数
    public static void dfs(int length,int step){
		//next数组控制一次确定的位数，1代表选择确定一位，2选择确定两位
        int[] next = {1,2};
        int tlength,i;
		//当确定位数的长度等于N时，搜索完毕，求出这种排列的种数
        if(length==N){
            sum += Math.pow(K-1,step);
            return;
        }
		//可能会出先最后多确定一位的情况，这时最后一位为0，多出来一个"_"计算的时候要减掉1
        if(length==N+1){
            sum += Math.pow(K-1,step-1);
            return;
        }
		//当确定的位数不到N时,选择一种确定的方法进行递归
        for(i=0;i<next.length;i++){
            tlength = length+next[i];
            dfs(tlength,step+1);
        }
    }
}
```

0.0分

15 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

时人

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

三进制小数（C++代码）（第11位大于1.5才能进位）

【出圈】（C语言代码）

K-进制数-题解（Java代码）超详细

评论区

精彩推荐

A+B for Input-Output Practice （C++代码）

成绩转换（C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

核桃的数量（C语言代码）

愚蠢的摄影师（C++代码）

时人

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

三进制小数 （C++代码）（第11位大于1.5才能进位）

【出圈】 （C语言代码）

K-进制数-题解（Java代码）超详细

评论区

精彩推荐

A+B for Input-Output Practice （C++代码）

成绩转换 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

核桃的数量 （C语言代码）

愚蠢的摄影师 （C++代码）

三进制小数（C++代码）（第11位大于1.5才能进位）

【出圈】（C语言代码）

　　评论区

成绩转换（C语言代码）

核桃的数量（C语言代码）

愚蠢的摄影师（C++代码）