mingming

用户名：fumingming

访问量：1149

签　名：

等　　级
排　　名	32182
经　　验	474
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校	重庆邮电大小
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2014年第五届真题-兰顿蚂蚁-题解(C++代码)
浏览：227

你可能喜欢

K-进制数-题解(C++代码)

　　作者: mingming　　　　发表时间：2020-03-02 12:09:22 浏览：269　|　评论：0　

原题链接：K-进制数

# 解法

使用排列组合的方式解答该算法。题目要求N位K进制数不能出现连续两个0，并且首位数不能为零。由此满足题目要求的N位K进制数有以下几种情况：
1. 该数不含有0：满足情况的数的数目为num[0]=pow(k-1,n);
2. 该数含有一个0：满足情况的数的数目为num[1]=（n-1）*pow(k-1,n-1);
3. 该数含有两个以上的0：这种情况较为复杂，可以用插入法来求解。现介绍含有i个零的情况的解法，其他情况类似。
由于首位不能为零，可单独把首位取出来，首位有k-1种情况。其余为不为零的数为n-i-1。当n-i大于等于i时，则明显存在可以满足题目要求的数；当n-i小于i，则所有包含i个0的数都不满足条件。不为0的数有n-i-1个，故其他为0的数可以插入的位置为n-i个，根据排列组合可知，总共插入情形有(n-i)*(n-i-1)*...*(n-2*i)/(i!)个。其余不为零的数的情形有pow(k-1,n-i)。因此含有i个零满足条件的数的个数为num[i] = pow(k-1,n-i)*(n-i)*(n-i-1)*...*(n-2*i)/(i!)。
由以上分析可知总数为 num = num[0]+num[1]+...+num[k] (n-k>=k);

```cpp
#include<iostream>
#include<math.h>
using namespace std;
int pailie(int a, int b)//排列组合算法
{
	int e;
	int d = 1;
	int f = 1;
	for (int i = 1; i <= b; i++)
	{
		d = d * (a-i+1);
	}
	for (int j = 1; j <= b; j++)
	{
		f = f * j;
	}
	e = d / f;
	return(e);
}

int main()
{
	int n, k;
	int d = 1;
	int num;
	while (cin >> n >> k)
	{
		num = pow(k - 1, n) + (n - 1)*pow(k - 1, n - 1);//含有0个和1个零的num数
		n = n - 1;
		for (int i = 2; (2 * i - n) < 2; i++)//含有i个零的num数的计算过程
		{
			d = pailie(n - i + 1, i);//排列数
			num = num + d * pow(k - 1, n + 1 - i);//含有i个零的num数
			d = 1;//将排列数置位
		}
		cout << num << endl;//输出num
	}
}

```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

mingming

TA的其他文章

你可能喜欢

C语言训练-尼科彻斯定理（C语言代码）

交换Easy （Java代码）

人见人爱A+B （C++代码）

明明的随机数（C++代码）

不知道哪里错了

K-进制数-题解(C++代码)

评论区

精彩推荐

【偶数求和】（C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

九宫重排（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

输入输出格式练习（C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

小O的乘积（C++代码）

mingming

TA的其他文章

你可能喜欢

C语言训练-尼科彻斯定理 （C语言代码）

交换Easy （Java代码）

人见人爱A+B （C++代码）

明明的随机数 （C++代码）

不知道哪里错了

K-进制数-题解(C++代码)

评论区

精彩推荐

【偶数求和】 （C++代码）

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

九宫重排 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

输入输出格式练习 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

小O的乘积 （C++代码）

C语言训练-尼科彻斯定理（C语言代码）

明明的随机数（C++代码）

　　评论区

【偶数求和】（C++代码）

九宫重排（C++代码）

输入输出格式练习（C语言代码）

小O的乘积（C++代码）