rain


私信TA

用户名:p1317994

访问量:5751

签 名:

(¬_¬)

等  级
排  名 10305
经  验 1023
参赛次数 1
文章发表 2
年  龄 20
在职情况 学生
学  校
专  业

  自我简介:

参考代码:

#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进制数个数。

 

0.0分

34 人评分

  评论区

深搜+打表//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}
};
2020-03-04 11:48:16
没看懂
2019-12-05 12:30:23
#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;
}
使用数值位比较进行计数
2019-09-13 01:10:43