K-进制数 （C语言代码）使用递推很简单

题目描述：

         一个合法的n位K进制数定义如下： 它是一个首位不为0的K进制数。 它不包含连续的两个0。对于输         入的K，n。求出满足上述条件的K进制数个数。

解题思路：

         这个题应该是一个递推题。可以用f[i]表示i位(最高位是第i位)K进制数的总数，那么就应该有：f[i]=(f[i-1]+f[i-2])*(k-1)。

解释一下：f[i]也就是i位K进制数的总数应该等于：第i-1位为0与第i-1位不为0的情况的和乘以第i位的情况数(1..k-1)

(1)第i-1位为0的情况应该等于i-2位不为0的情况总数，即f[i-2]

(2)第i-1位不为0的情况应该等于f[i-1]

所以f[i]=(f[i-1]+f[i-2])*(k-1)

参考代码:

#include<stdio.h>
int k;
int f(int n)
{
    if(n == 1)
    {
        return k-1;
    }
    else if(n == 2)
    {
        return (k-1)*k;
    }
    else
    {
        return f(n-1)*(k-1) + f(n-2)*(k-1) ;    }
}
int main()
{
    int n;
    scanf("%d%d", &n, &k);
    printf("%d\n",f(n));
    return 0;
}

欢迎留言