1203

用户名：dotcpp0602064

访问量：1366

签　名：

时间是你最大的敌人

等　　级
排　　名	3295
经　　验	1888
参赛次数	0
文章发表	21
年　　龄	19
在职情况	学生
学　　校	中山大学
专　　业	软件工程

　　自我简介：

TA的其他文章

C/C++，高精度模板题（加法、减法、乘法、除法），会套就行~~
浏览：91

C/C++，高精度模板题（加法、减法、乘法、除法），会套就行~~
浏览：35

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

C语言，三种方法，简单的递归，组合数或迭代，详细推导过程

　　作者: 1203　　　　发表时间：2022-11-16 16:12:08 浏览：41　|　评论：0　

原题链接：K-进制数

组合数的方法也可以做，但是递归应该更好理解，暴力求解容易时间超限

递归推导：
![](/image_editor_upload/20221116/20221116031330_68426.png)

组合数推导：（奇数情况类似，不想画图了）
![](/image_editor_upload/20221116/20221116043319_83654.png)

思路理顺，就可以自己尝试敲代码了

// 递归版
	int n, k;
	int Fun(int n)
	{
		if (n == 0)return 1;// 多思考一下边界条件
		if (n == 1)return k - 1;
		return (Fun(n - 1) + Fun(n - 2)) * (k - 1);
	}
	int main()
	{
		scanf("%d\n%d", &n, &k);
		printf("%d", Fun(n));
		return 0;
	}
	
	// 组合数版
	int Combinatorial(int n, int m)// 计算组合数
	{
		if (n <= 1 || !m)return 1;
		if (m < n - m)m = n - m;
		int ret = 1;
		for (int i = m + 1; i <= n; i++)ret *= i;
		for (int i = 1; i <= n - m; i++)ret /= i;
		return ret;
	}
	int main()
	{
		int n, k;
		scanf("%d\n%d", &n, &k);
		int sum = 0;
		if (n % 2)// 奇数情况
		{
			for (int i = n / 2 + 1; i <= n; i++)sum += Combinatorial(i, n - i) * pow(k - 1, i);
		}
		else// 偶数情况
		{
			for (int i = n / 2; i <= n; i++)sum += Combinatorial(i, n - i) * pow(k - 1, i);
		}
		printf("%d", sum);
		return 0;
	}
	// 迭代版
	int main()
	{
		int n, k;
		scanf("%d\n%d", &n, &k);
		int a = 1, b = k - 1, c = 0;// 初始化，a = f(0)，b = f(1)
		for (int i = 2; i <= n; i++)
		{
			c = (a + b) * (k - 1);// 也即是 f(n) = [f(n - 1) + f(n - 2)] * (k - 1)
			a = b;
			b = c;
		}
		printf("%d", c);
		return 0;
	}
	暴力解法就不写了。。。

0.0分

1 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

1203

TA的其他文章

你可能喜欢

不同单词个数统计（C语言代码）

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

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

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

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

C语言，三种方法，简单的递归，组合数或迭代，详细推导过程

评论区

精彩推荐

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

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

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

WU-格式化数据输出（C语言代码）

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

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

【计算直线的交点数】（C语言代码）

Minesweeper （C语言描述，蓝桥杯）

母牛的故事（C语言代码）

矩形面积交（C++代码）

1203

TA的其他文章

你可能喜欢

不同单词个数统计 （C语言代码）

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

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

2006年春浙江省计算机等级考试二级C 编程题(2) （C++代码）直接打表啊8以上值不变hhh

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

C语言，三种方法，简单的递归，组合数或迭代，详细推导过程

评论区

精彩推荐

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

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

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

WU-格式化数据输出 （C语言代码）

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

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

【计算直线的交点数】 （C语言代码）

Minesweeper （C语言描述，蓝桥杯）

母牛的故事 （C语言代码）

矩形面积交 （C++代码）

不同单词个数统计（C语言代码）

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

　　评论区

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

WU-格式化数据输出（C语言代码）

【计算直线的交点数】（C语言代码）

母牛的故事（C语言代码）

矩形面积交（C++代码）