赵天泽

用户名：uq_99534628713

访问量：2351

签　名：

全体目光向我看齐，我宣布个事，我是个傻⚪

等　　级
排　　名	6893
经　　验	1308
参赛次数	2
文章发表	9
年　　龄	0
在职情况	学生
学　　校	sumhs
专　　业	大数据

　　自我简介：

已退站

TA的其他文章

蓝桥杯基础练习VIP-阶乘计算(C语言）
浏览：131

C语言解阶乘新问题，简单易理解，同时分享其他失败的思路
浏览：182

简单易懂的C语言动态规划算法（以及分享一下失败的递归算法）
浏览：387

你可能喜欢

C语言dp动态规划算法解阶乘新问题(但会遇到运行错误,只是分享思路,寻求题解可绕过)

　　作者: 赵天泽　　　　发表时间：2022-04-11 02:09:11 浏览：229　|　评论：1　

原题链接：阶乘新问题

在思考老师的解法时，突然产生个了新灵感。不过目前这个代码会遇到运行错误，但是在自己的软件中运行并没有问题，也不清楚哪出错了。等我发现并改正错误后会直接回来修改这个题解。（现在解决了，问题的答案是无解，除非改变思路，具体错误原因在下文）

正常做法肯定会面临时间超限或者数据溢出，所以只能找规律。会在末尾出现0，只可能是在相乘时出现了10的倍数，本质也就是找出现10的倍数的次数。但按10的倍数找肯定会出错，因为5×2也是10，而在阶乘中，在5之前肯定会有偶数出现，也就是说每个5的倍数，和偶数相乘后都一定可以成为10的倍数。这样也就把问题转化为了寻找5出现的次数。（复制于本题下我的另一篇题解）

本题本质是求n阶乘的阶乘末位0的个数，在这里用n!!表示n阶乘的阶乘，不难理解n!!=(n-1)!!*n!所以我们可以先求（n-1）!!，同理，求（n-1）!!可以由（n-2）!!求得，一直到2!!由1!!求得，这样每一步都包含了之前的步骤，正是动态规划的思想。

用b[i]表示i!!末位0的个数，这样可以得到通项b[i]=b[i-1]+k,k表示n!末尾0的个数。在求x，也就是n!末尾0的个数时，我发现又可以使用动态规划来求，用a[i]表示i! 末尾0的个数，得到通项a[i]=a[i-1]+x,x为i因子5的个数。这样的话，之前的那个通项就可以改为b[i]=b[i-1]+a[i]（但是用b [i]表示n!! 末尾0的个数，就代表n为多少，就需要n+1的数组大小，但在测试用例中，测试的数非常大，会大到问题出错）

得到代码：
```c
#include<stdio.h>
#include<stdlib.h>
int main()
{
	int n, i, k, x;
	int* a;
	int* b;
	scanf_s("%d", &n);
	a = (int*)malloc(sizeof(int) * (n+1));
	b = (int*)malloc(sizeof(int) * (n+1));
	for (i = 1; i <= n; i++)
	{
		x = 0;
		k = i;
		while (k % 5 == 0)
		{
			x++;
			k = k / 5;
		}
		a[i] = a[i - 1] + x;
	}
	for (i = 1; i <= n; i++)
	{
		b[i] = b[i - 1] + a[i];
	}
	printf("%d", b[n]);
	free(a);
	free(b);
	return 0;
}
```

由这个算法可以延申出递归算法的题解，大同小异，不过递归的效率会更低一些，还不如这个。

0.0分

1 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

木头

兄弟我也是运行错误，可是在自己开发环境运行的时候不报错

2022-04-19 23:37:21

赵天泽

TA的其他文章

你可能喜欢

不容易系列（C语言代码）

不知道哪里错了

大神老白（C语言代码）

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

三角形（C++代码）记忆化搜索

C语言dp动态规划算法解阶乘新问题(但会遇到运行错误,只是分享思路,寻求题解可绕过)

评论区

精彩推荐

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

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

妹子杀手的故事（C语言代码）

整除问题（C语言代码）

盐水的故事（C语言代码）

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

C二级辅导-分段函数（C语言代码）

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

简单的a+b （C语言代码）

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

赵天泽

TA的其他文章

你可能喜欢

不容易系列 （C语言代码）

不知道哪里错了

大神老白 （C语言代码）

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

三角形 （C++代码）记忆化搜索

C语言dp动态规划算法解阶乘新问题(但会遇到运行错误,只是分享思路,寻求题解可绕过)

评论区

精彩推荐

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

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

妹子杀手的故事 （C语言代码）

整除问题 （C语言代码）

盐水的故事 （C语言代码）

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

C二级辅导-分段函数 （C语言代码）

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

简单的a+b （C语言代码）

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

不容易系列（C语言代码）

大神老白（C语言代码）

三角形（C++代码）记忆化搜索

　　评论区

妹子杀手的故事（C语言代码）

整除问题（C语言代码）

盐水的故事（C语言代码）

C二级辅导-分段函数（C语言代码）