Toggle navigation
C语言网
教程
博客
团队
训练
训练
题库
题集
状态
排名
比赛
比赛
标准
自主
考试
网课
AI助手
AI助手
代码解释
语言转换
编程助手
时人
私信TA
用户名:17633532082
访问量:3135
签 名:
等 级
P3
排 名
11201
经 验
969
参赛次数
0
文章发表
9
年 龄
0
在职情况
学生
学 校
河南大学
专 业
自我简介:
TA的其他文章
蓝桥杯2013年第四届真题-危险系数-题解(Java代码)邻接表+深度优先搜索+桶思想
浏览:
129
思路简单的暴力解法
浏览:
222
你可能喜欢
C语言程序设计教程(第三版)课后习题3.7 (C++代码)
浏览:
985
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)
浏览:
688
C二级辅导-计负均正 (C语言代码)
浏览:
646
C二级辅导-进制转换 (C语言代码)
浏览:
615
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)
浏览:
609
优质题解
K-进制数-题解(Java代码)超详细
作者:
时人
发表时间:2021-01-23 22:50:54
浏览:1108 | 评论: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
0.0分
15 人评分
分享
收藏
递归
深度优先算法
C语言网推出会员服务,提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源,享受丰富的技术学习到变现的乐趣,
以含金量和学习效果勇敢挑战同类辅导
! 点击了解开通
评论区
«
»
提交
精彩推荐
C语言训练-计算一个整数N的阶乘 (C语言代码)
浏览:
920
C语言程序设计教程(第三版)课后习题1.5 (C++代码)
浏览:
755
C语言程序设计教程(第三版)课后习题7.5 (C语言代码)
浏览:
517
WU-C语言程序设计教程(第三版)课后习题11.12 (C++代码)(想学链表的小伙伴可以看看)
浏览:
894
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)
浏览:
610
C语言程序设计教程(第三版)课后习题5.4 (C语言代码)
浏览:
551
小九九 (C语言描述,不看要求真坑爹)
浏览:
980
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)
浏览:
662
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)
浏览:
656
C语言程序设计教程(第三版)课后习题8.4 (C语言代码)
浏览:
565
有问题
,
问问AI
代码解释
语言转换
编程助手