rain


私信TA

用户名:p1317994

访问量:2285

签 名:

(¬_¬)

等  级
排  名 4743
经  验 718
参赛次数 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分

9 人评分

  评论区

在循环中思考:
        1.首先判断是否完全相等,如果是相等就不需要计算了。

        2.全体减半,由于大家都是偶数所以直接除以二就可以了。

        3.全体成员加上前面哪个减半的数,相当于把自己的糖果分享给了自己左手边的小朋友,注意这里最后一个和第一个需要借助一个中间变量进行传递。

        4.全体判断奇偶,如果是奇数就+1,同时创建一个计数器也+1,再度进行循环,等循环结束的时候输出计数器即可。
2020-06-05 16:29:52 | |
//找出规定位数的有效进制的数的个数
#include<stdio.h>
 int getSum(int N,int K); 
int main()
{
	int N,K,sum;
	scanf("%d%d",&N,&K);
	//当只有1位数的时候比较特殊,就只调用一次,且应该返回进制那么多,所以在原本调用的基础上+1,因为有0 
	 if(N==1)
	 {
	 	sum=getSum(N,K)+1;
	  } 
	else
	{
		sum=getSum(N,K)-getSum(N-1,K);
	 } 
	printf("%d",sum);
	return 0;
 } 
 //1位10进制:0-9:10个,最大的数字为9 
 //2为10进制:99-9:90,用2位十进制最大的数字-1为十进制最大的数字 
 //3为10进制:999-99,用3为十进制最大的数字-2位十进制最大的数字 
 int getSum(int N,int K)
2020-06-03 19:05:23 | |
很好
2020-06-03 19:04:54 | |
深搜+打表//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-05-11 01:45:43 | |
//找出规定位数的有效进制的数的个数
#include<stdio.h>
 int getSum(int N,int K); 
int main()
{
	int N,K,sum;
	scanf("%d%d",&N,&K);
	//当只有1位数的时候比较特殊,就只调用一次,且应该返回进制那么多,所以在原本调用的基础上+1,因为有0 
	 if(N==1)
	 {
	 	sum=getSum(N,K)+1;
	  } 
	else
	{
		sum=getSum(N,K)-getSum(N-1,K);
	 } 
	printf("%d",sum);
	return 0;
 } 
 //1位10进制:0-9:10个,最大的数字为9 
 //2为10进制:99-9:90,用2位十进制最大的数字-1为十进制最大的数字 
 //3为10进制:999-99,用3为十进制最大的数字-2位十进制最大的数字 
 int getSum(int N,int K)
 {
 	int max,i;
 	max=K-1;
	//获取到当前位数的最大值 
	for(i=0; i<N-1; i++)
	{
		max=max+(K-1)*10;
	 } 
	return max;
  } 


这样可以吗,但是正确率是67%,哪里还没考虑到呢
2020-03-31 14:48:47 | |
深搜+打表//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 | |
  • «
  • 1
  • »