抛锚

用户名：mpc20000202

访问量：1725

签　名：

一个字，就是干。

等　　级
排　　名	15243
经　　验	795
参赛次数	0
文章发表	4
年　　龄	21
在职情况	学生
学　　校	武汉工程科技学院
专　　业	软件工程

　　自我简介：

三无

TA的其他文章

2300题解——外卖店优先级
浏览：505

你可能喜欢

1117题解——[递归]K-进制数

　　作者: 抛锚　　　　发表时间：2021-03-23 15:24:45 浏览：781　|　评论：0　

原题链接：K-进制数

**题解分析**： 使用递归求解
			此题可以使用排列组合来解决
			就是0和1 ~ k-1组成的N位数，并满足以上要求![在这里插入图片描述](https://img-blog.csdnimg.cn/20210323144040332.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDk0OTE1MA==,size_16,color_FFFFFF,t_70)
当最后一位数不为2（即为叶子节点）时，为一种组合方式；
每种组合方式的个数为：（以11101为例）k-1的4次方个

**代码如下：**
```java
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();//K进制 
		int K = sc.nextInt();
		//用数组012的方式表示一种组合方式（1:表示可取1~k,0:表示此位固定为0,2:表示还未知）
		int[] arr = new int[N];
		for (int i = 1; i < arr.length; i++) {
			arr[i] = 2;//将数组值全部赋为2
		}
		arr[0] = 1;//首位只能为非0
		int count = fun(arr, 0, K);
		System.out.println(count);
	}
	//使用递归推出所有的组合方式并求总个数（end:数组已知尾数的下标）
	public static int fun(int[] arr, int end, int k) {
		//结束条件：当数组的最后一位都已知时，表示一种组合已形成
		if (arr[arr.length-1] != 2) {
			int count = 0;//记录此种组合中1的数量
			for (int i : arr) {
				count += i;
			}
			//返回此种组合的个数
			return (int)Math.pow(k-1, count);
		}
		//否则：推出未知位
		int[] arr1 = new int[arr.length];
		int[] arr2 = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			arr1[i] = arr2[i] = arr[i];
		}
		/**
		*假如此时arr:12222（下标从0开始）
		*那么可以得出第1位的2可以为1或0
		*  当为1时：11222
		*  当为0时：10122（第2位必须为1）
		*/
		arr1[end+1] = 1;
		arr2[end+1] = 0;
		//为0时，下一位必须为1，还需要考虑是否会下标越界
		if (end+1 < arr.length-1) {
			arr2[end+2] = 1;
		}
		//递推公式:arr=arr1+arr2
		return fun(arr1, end+1, k)+fun(arr2, end+2, k);
	}
}
```

0.0分

5 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

抛锚

TA的其他文章

你可能喜欢

勾股数（Java代码）

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

蛇行矩阵（C语言代码）

C二级辅导-计负均正（C语言代码）

拆分位数（C++代码）用char简单粗暴，嗯

1117题解——[递归]K-进制数

评论区

精彩推荐

【计算球体积】（C语言代码）

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

C二级辅导-计负均正（C语言代码）

C语言训练-计算一个整数N的阶乘（C语言代码）

拆分位数（C语言代码）

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

简单的a+b （C语言代码）

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

矩形面积交（C语言代码）

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

抛锚

TA的其他文章

你可能喜欢

勾股数 （Java代码）

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

蛇行矩阵 （C语言代码）

C二级辅导-计负均正 （C语言代码）

拆分位数 （C++代码）用char简单粗暴，嗯

1117题解——[递归]K-进制数

评论区

精彩推荐

【计算球体积】 （C语言代码）

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

C二级辅导-计负均正 （C语言代码）

C语言训练-计算一个整数N的阶乘 （C语言代码）

拆分位数 （C语言代码）

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

简单的a+b （C语言代码）

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

矩形面积交 （C语言代码）

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

勾股数（Java代码）

蛇行矩阵（C语言代码）

C二级辅导-计负均正（C语言代码）

拆分位数（C++代码）用char简单粗暴，嗯

　　评论区

【计算球体积】（C语言代码）

C二级辅导-计负均正（C语言代码）

C语言训练-计算一个整数N的阶乘（C语言代码）

拆分位数（C语言代码）

矩形面积交（C语言代码）