参考代码:
#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分
24 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
可以使用递归函数 #include <stdio.h> int fun(int n,int k); int main(){ int n,k,t; scanf("%d%d",&n,&k); t=fun(n,k); printf("%d",t); return 0; } int fun(int n,int k){ if(n==1) return k-1; else if(n==2) return (k-1)*k; else return (k-1)*(fun(n-1,k)+fun(n-2,k)); }在循环中思考： 1.首先判断是否完全相等，如果是相等就不需要计算了。 2.全体减半，由于大家都是偶数所以直接除以二就可以了。 3.全体成员加上前面哪个减半的数，相当于把自己的糖果分享给了自己左手边的小朋友，注意这里最后一个和第一个需要借助一个中间变量进行传递。 4.全体判断奇偶，如果是奇数就+1，同时创建一个计数器也+1，再度进行循环，等循环结束的时候输出计数器即可。//找出规定位数的有效进制的数的个数 #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)深搜+打表//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> 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%，哪里还没考虑到呢