chenxizhan

用户名：chenxizhan

访问量：5248

签　名：

等　　级
排　　名	5762
经　　验	1497
参赛次数	0
文章发表	10
年　　龄	0
在职情况	待业
学　　校	山东大学
专　　业

　　自我简介：

TA的其他文章

虚张声势-题解(C语言代码)
浏览：876

[编程入门]成绩评定-题解(C语言代码),另类解法
浏览：612

[编程入门]字符串分类统计-题解(C语言代码)，值得一看
浏览：932

你可能喜欢

K-进制数-题解(C语言代码)

　　作者: chenxizhan　　　　发表时间：2019-11-23 08:46:38 浏览：301　|　评论：0　

原题链接：K-进制数

令 b[j] 表示 j 位有效 k 进制数的个数
数列 `{b[j] | j = 1,2,3,..., N}` 满足
1) 初值条件 `b[1] = k-1`, `b[2] = k(k-1)`
2）递推条件` b[j] = (k-1)(b[j-1]+b[j-2])`
题目条件可得 `N <= 16`, 所以用长为17的数组保存递推结果

```c
#include<stdio.h>
#include<string.h>
#define  N 17 // buffer size
unsigned long b[N];
int main(void){
    int n, k, km;
    scanf("%d %d", &n, &k);
    km = k-1;
    // 填表
    b[2] = k*km;
    b[1] = km;
    for (int i = 3; i<=n; i++){
        b[i] =  km*(b[i-1]+b[i-2]);
    }
    printf("%lu\n", b[n]);
}
```
推理一下递推公式：
设 b[n] 代表满足条件的 n 位 K 进制数的数量（n>=1),则
`b[1] = (k-1)` ; 除了0，都行
`b[2] = (k-1)*k` ; 第一位不是零，第二位可以是任意一位数
当 n >= 3 时，可以把 a[n] 分为两类：
	1）末位（也就是第n位）是零 
	2）末位不是零的
要确定这两类的数字个数，就要分析一下如何得到这两类数字。
A.要构造一个第n位是零的数，可以在长度为 n-2 的数字后面添加 X0，其中X是k-1位非零的数字中的任何一位，所以1）的数量是 `b[n-2]*(k-1)`;
B.要构造第n位不是零的数字，可以在n-1位数字后面填上一个非零数字X，所以2）的数量是`b[n-1]*(k-1)`。
根据上面的构造过程。所得到的长度位 n 的数字不重不漏：1）和2）末位数字不相同，所以不会重复计数；任何第n位是零的数字通过步骤A都可以得到，任何第n位不是零的数字通过步骤B都可以得到，所以A和B不会遗漏。
所以有递推关系 `b[j] = (k-1)(b[j-1]+b[j-2])`。
最后关于初值的设定，b[2]=k(k-1)很好理解；如果b[1]的初值不容易理解，就手动计算b[3]的值，然后从 n=4 开始利用递推公式也是一样的。（因为b1不会用到，所以它可以取任意值，我是从b2，b3和递推关系反推的b1）。

0.0分

0 人评分

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

chenxizhan

TA的其他文章

你可能喜欢

C语言训练-字符串正反连接（C语言代码）

前10名（Java代码）

C二级辅导-公约公倍（C语言代码）

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

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

K-进制数-题解(C语言代码)

评论区

精彩推荐

母牛的故事（C语言代码）

妹子杀手的故事（C语言代码）

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

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

C语言训练-素数问题（C语言代码）

C语言训练-计算1977！* （C++代码）

买不到的数目（C++代码）

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

【数组的距离】（C语言代码）

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

chenxizhan

TA的其他文章

你可能喜欢

C语言训练-字符串正反连接 （C语言代码）

前10名 （Java代码）

C二级辅导-公约公倍 （C语言代码）

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

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

K-进制数-题解(C语言代码)

评论区

精彩推荐

母牛的故事 （C语言代码）

妹子杀手的故事 （C语言代码）

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

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

C语言训练-素数问题 （C语言代码）

C语言训练-计算1977！* （C++代码）

买不到的数目 （C++代码）

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

【数组的距离】 （C语言代码）

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

C语言训练-字符串正反连接（C语言代码）

前10名（Java代码）

C二级辅导-公约公倍（C语言代码）

　　评论区

母牛的故事（C语言代码）

妹子杀手的故事（C语言代码）

C语言训练-素数问题（C语言代码）

买不到的数目（C++代码）

【数组的距离】（C语言代码）