| 等 级 | |
| 排 名 | 10558 |
| 经 验 | 1023 |
| 参赛次数 | 1 |
| 文章发表 | 2 |
| 年 龄 | 20 |
| 在职情况 | 学生 |
| 学 校 | |
| 专 业 |
自我简介：
TA的其他文章
你可能喜欢
2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）浏览：356 |
地宫取宝 （C语言代码）浏览：1395 |
C二级辅导-求偶数和 （C语言代码）浏览：603 |
C语言程序设计教程（第三版）课后习题12.6 （C语言代码）浏览：791 |
C语言程序设计教程（第三版）课后习题10.5 （C语言代码）浏览：719 |
参考代码:
#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 人评分
评论区
可以使用递归函数
#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%，哪里还没考虑到呢