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

样例输入

样例输出

💡思路

根据题意，要知道 N 位 K 进制并且 不能有连续两个 0 出现 还有首位不能为 0 的限制条件。

  本着由简到难的思想  ：

         假设是让你求 1 位 K 进制的满足条件的数，那么满足条件的数则有 1，2，3.....K-1 一共 K-1 个数对吧，

我们记作 res_1=K-1,那么不满足条件的数 只有 0 ，一共 1 个数 ，我们记作 res_0=1。

         假设是让你求 2 位 K 进制的满足条件的数，那么先考虑首位（也就是第 2 位），可以填的数为除去 0 的其他数，

有 1，2，3.....K-1 一共 K-1 个数对吧，而这第二位可以填的数 可以和第一位的所有数搭配，

以 1 为例，有 11，12，13,.....1(K-1),还有在第一位不满足条件的 0 搭配 10，也是满足条件的数，

所以 2 位 K 进制满足条件的数 res_1=（K-1）*(K-1+1),即 res_1=(K-1)*（res_1+res_0）,对吧，

再来看不满足条件的数 即 首位为 0 的 有 01，02，03.....0（K-1）,一共有 K-1 个也就是 res_0=K-1,即 res_0=res_1(上一个)。

第一位满足条件的数 res_1 对吧,因为不能连 0 ，虽然 00 也是不满足，但是 00 这种情况是绝对不满足，

而首位不满足的情况是相对不满足，绝对和相对 懂吧。

        那么继续，假设是让你求 3 位 K 进制的满足条件的数，同样先考虑首位（也就是第 3 位），

可以填的数为除去 0 的其他数，有 1，2，3.....K-1 一共 K-1 个数对吧，而这第 3 位可以填的数 

可以和 2 位 K 进制满足条件和（相对）不满足条件的数搭配，即 res_1=（K-1）*[(K-1)*(K-1+1)+(K-1)],

即 res_1=(K-1)*(res_1+res_0),不满足条件的数则是可以和 2 位 K 进制满足条件的数搭配，

res_0=（k-1）*(K-1+1),即 res_0=res_1。

  后面的位数就以此类推，再看看图解。

AC 代码：

#include<stdio.h>int main(){  int N,K,i,res_0,res_1;//res_1代表最高位非0  res_0代表最高位为0的结果   while(scanf("%d%d",&N,&K)!=EOF){      res_1=K-1,res_0=1;//如果只有一位时 K进制首位为1的可以填的为K-1个数去掉为0       for(i=2;i<=N;i++){       int last_res_1=res_1;//暂存       res_1=(K-1)*(res_1+res_0);//如果高位为1 则结果为上一次结果为1和为0的数的个数       res_0=last_res_1; //如果高位为0 则结果为上一次结果为1的数的个数       }      printf("%d\n",res_1);   }    return 0;}

​