解题思路:
我们可以用a[i]来表示位数i的K进制数的有效数的个数 。记最高位是第i位,最低位是第1位
那么很显然第i位的数不可能为0,只能是1到K-1,一共有K-1种
我们只要找到除第i位数之外的所有位数的K进制数的有效数的个数,再乘以K-1,显然就是我们要求的a[i]
现在我们看第i-1位数,对于它,可能是0,可能不是0,因此有两种情况,当第i-1位数是0时,可以表示的数的个数为a[i-2],即第i-2位不为0的总个数
当第i-1位数不是0时,可以表示的数的个数为a[i-1]
因此我们可以得到a[i]=(a[i-1]+a[i-2])*(K-1)这样的递推式 (i>2)
再初始化一下:a[1]=K-1 ,a[2]=K*(K-1)即可
注意事项:
参考代码:
#include<bits/stdc++.h>
using namespace std;
int N,K;
int a[30];
int main(){
scanf("%d%d",&N,&K);
a[1]=K-1;
a[2]=K*(K-1);
if(N<3) cout<<a[N];
else {
for(int i=3;i<=N;i++) a[i]=(a[i-1]+a[i-2])*(K-1);
cout<<a[N];
}
return 0;
}
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:601 |
Hello, world! (C语言代码)浏览:1202 |
字符串输入输出函数 (Java代码)浏览:1440 |
九宫重排 (C++代码)浏览:2160 |
大神老白 (C语言代码)浏览:645 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:545 |
WU-输入输出格式练习 (C++代码)浏览:1082 |
WU-判定字符位置 (C++代码)浏览:1406 |
字符逆序 (C语言代码)浏览:646 |
1017题解浏览:605 |