参考代码:
#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} };
#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; } 使用数值位比较进行计数
点我有惊喜!你懂得!浏览:2074 |
C二级辅导-求偶数和 (C语言代码)浏览:607 |
C语言程序设计教程(第三版)课后习题9.2 (C语言代码)浏览:703 |
C语言程序设计教程(第三版)课后习题10.1 (Java代码)浏览:1447 |
打水问题 (C语言代码)浏览:1072 |
简单的a+b (C语言代码)浏览:573 |
A+B for Input-Output Practice (II) (C语言代码)浏览:1000 |
C二级辅导-阶乘数列 (C语言代码)浏览:692 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:1162 |
WU-小九九 (C++代码)浏览:1684 |