1203

用户名：dotcpp0602064

访问量：1908

签　名：

时间是你最大的敌人

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

　　自我简介：

TA的其他文章

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

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

你可能喜欢

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

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

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

　　作者: 1203　　　　发表时间：2022-11-16 16:12:08 浏览：42　|　评论：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 人评分

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

1203

TA的其他文章

你可能喜欢

用筛法求之N内的素数。（C语言代码）

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

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

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

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

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

评论区

精彩推荐

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

C语言考试练习题_排列（C++代码）

时间转换（Java代码）

Pascal三角（C语言代码）

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

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

WU-陶陶摘苹果2 （C++代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

IP判断（C语言代码）

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

1203

TA的其他文章

你可能喜欢

用筛法求之N内的素数。 （C语言代码）

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

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

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

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

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

评论区

精彩推荐

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

C语言考试练习题_排列 （C++代码）

时间转换 （Java代码）

Pascal三角 （C语言代码）

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

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

WU-陶陶摘苹果2 （C++代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

IP判断 （C语言代码）

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

用筛法求之N内的素数。（C语言代码）

　　评论区

C语言考试练习题_排列（C++代码）

时间转换（Java代码）

Pascal三角（C语言代码）

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

IP判断（C语言代码）