蓝桥杯问题 1117: K-进制数（递归）

题目链接

题目描述

考虑包含N位数字的K-进制数. 定义一个数有效, 如果其K-进制表示不包含两连续的0.

考虑包含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

分析：

递归找出当前这个k进制的n位数的所有可能的情况，每次的话只考虑当前位，如果当前是第一位的话肯定不能为0，如果不是第一位的话，当前位和前一位不能全部为0，这是不合法的。

排除掉这两种情况，剩下的所有的情况都是合法的。

代码：

#include<stdio.h>

#include<iostream>

using namespace std;

int a[20],n,k;

int cnt;

void dfs(int s)

{

    if(s==n)

    {

        cnt++;

        return;

    }

    for(int i=0; i<k; i++)

    {

        //首位为0的情况  当前位和前一位都为0的情况  都是不需要考虑的

        if((s==0&&i==0)||(s>0&&i==0&&a[s-1]==0))

            continue;

        a[s]=i;

        dfs(s+1);

    }

}

int main()

{

    while(~scanf("%d%d",&n,&k))

    {

        cnt=0;

        dfs(0);

        printf("%d\n",cnt);

    }

    return 0;

}

巴特西

蓝桥杯问题 1117: K-进制数（递归）

最新文章

热门文章

巴特西

蓝桥杯 问题 1117: K-进制数 （递归）

最新文章

热门文章

蓝桥杯问题 1117: K-进制数（递归）