1. Dotcpp
  2. 题解列表
  3. 1117题题解

K-进制数 （C语言代码） 仿深度优先搜索

5008 阅读 15 评论
原题链接：K-进制数

参考代码:

#include<stdio.h>
#include<math.h>
int N,K,sum;
void dfs(int x,int step);
int main()
{
    scanf("%d%d",&N,&K);
    dfs(1,1);    //从最高位开始从左到右插空
    printf("%d\n",sum);
    return 0;
}
void dfs(int x,int step)
{
    int next[2]={1,2};    //向右移动一位或两位
    int tx,i;
    if(x==N)  //个位不为0时
    {
        sum+=pow(K-1,step);    //step等于非零数的个数，（K-1）^step即为K进制数个数
        return;
    }
    if(x==N+1)  //个位为0时
    {
        sum+=pow(K-1,step-1);  //此时已经越界，需要减去多出的步数
        return;
    }
    for(i=0;i<=1;i++)
    {
        tx=x+next[i];
        dfs(tx,step+1);  //尝试下一个空
    }
}

解题思路:

题中N位的K进制数，除了最高位一定不为0外，剩下（N-1）位数都可能为0或非零数，而且相邻两位数不能同时为0。这道题可以看作一个插空问题，从首位开始从左到右按顺序插空，因为本题对0有不相邻限制，因此这里我们以非零数为对象插空，只要两个靠近的非零数之间的0不超过1个即可。

以4位二进制数为例：我们插入第一个非零数（首位）后，二进制数可写作1xxx（x表示还没插入的空位），考虑到两个0不能相邻，第二个非零数的位置可以在第二位或第三位，即插入第二个非零数后，该二进制数变为了11xx或者101x（没有插入默认为零），如此循环下去，最终找到所有符合条件的4位二进制数为：1111、1110、1101、1011、1010，共5个。

如此我们可以仿深度优先搜索对所有情况遍历，找到所有符合条件的插入方式。

注意事项:
1.除二进制数之外，单位非零数都不只有1个，个数为（K-1）。假设一个合适的插入方式包含了t个非零数，那么它包含的K进制数为（K-1）^t个。

2.因为我们插入的数都为非零数，所以当我们需要在个位填入0时（如111x变为1110），可以先给个位延伸一位填入非零数（11101），最后计算的时候少计算一位非零位即可。

3.算法改进：如果在搜索的时候记录从第n位开始遍历的结果个数并标记，下次搜索到该位时就可以直接套用记录的结果，这样可以减少递归次数并算出所有符合要求的1-N位K进制数个数。

点赞(12)
　

0.0分

24 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

编写题解 2810: 鸡尾酒疗法
编写题解 2810: 鸡尾酒疗法
C语言训练-计算1~N之间所有奇数之和
C语言训练-计算1~N之间所有奇数之和
循环实现斐波那契数列or递归函数
循环实现斐波那契数列or递归函数
2845: 求10000以内n的阶乘
2845: 求10000以内n的阶乘

评论列表 共有 15 条评论

SavenNeer 5年前 回复TA 
深搜+打表//ans[k][n]
int ans[][9]={{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,2,3,5,8,13,21,34},
{0,0,6,16,44,120,328,896,2448},
{0,0,12,45,171,648,2457,9315,35316},
{0,0,20,96,464,2240,10816,52224,252160},
{0,0,30,175,1025,6000,35125,205625,1203750},
{0,0,42,288,1980,13608,93528,642816,4418064},
{0,0,56,441,3479,27440,216433,1707111,13464808},
{0,0,72,640,5696,50688,451072,4014080,35721216},
{0,0,90,891,8829,87480,866781,8588349,85096170}
};
WE戴戴AK 5年前 回复TA 
@酷酷流浪猫 @009527 你的算法超时了
DemoZ 6年前 回复TA 
没看懂
酷酷流浪猫 6年前 回复TA 
@酷酷流浪猫 j函数是自定义k进制加法
酷酷流浪猫 6年前 回复TA 
#include"stdio.h"
void j(int a[],int k,int n)
{
	if(a[n]>=k)
	{
		a[n]=0;
		a[n+1]++;
		j(a,k,n+1);
	}
}

int main()
{
	int n,k,o=0,i,a[18]={0};
	scanf("%d%d",&n,&k);
	a[n-1]=1;
	while(a[n]==0)
	{
		for(i=1;i<n;i++)
		{
			if((a[i-1]==0)&&(a[i]==0)) break;
			if(i==n-1) o++;
		}
			a[0]++;
			j(a,k,0);
	}
	printf("%d",o);
	return 0;
}
使用数值位比较进行计数