一步一步写算法(之n!中末尾零的个数统计)

原文:一步一步写算法(之n!中末尾零的个数统计)

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】

    在很多面试的题目中,求n!结果中零的个数也是经常遇到的一道题目。那么这道题目的解决方法究竟是什么呢?我愿意在此和大家分享一下我自己的一些看法,有不同见解的朋友欢迎多提意见。

    求n!中零的个数主要在于乘数中有没有能被2和5整除的数,只要能找到被2和5整数的乘数即可,所以,我的代码流程是这样的:

    (1)查找当前数据中有没有可以整除2的整数,同时修改整数的数值

    (2)查找当前数据中有没有可以整除5的整数,同时修改整数的数值

    (3)如果1、2的条件同时满足,表示已经有一个零了,count++

    (4)重复1、2的过程,直到1、2中有一个条件为假

    说了这么多,那么代码应该怎么书写呢?下面是我个人写的一个例子,欢迎大家写出自己的想法:

int count_zero_number(int value)
{
	int count;
	int index;
	int* pData;
	int flag_two;
	int flag_five;
	if(value <= 0)
		return 0;

	pData = (int*)malloc(sizeof(int) * value);
	assert(NULL != pData);
	memset(pData, 0, sizeof(int) * value);

	for(index = 0; index < value; index ++){
		pData[index] = index + 1;
	}

	count = 0;
	do{
		/* reset the flag value */
		flag_two = 0;
		flag_five = 0;

		for(index = 0; index < value; index ++){
			if( 0 == (pData[index] % 2)){
				pData[index] /= 2;
				flag_two = 1;
				break;
			}
		}

		if(!flag_two)
			break;

		for(index = 0; index < value; index ++){
			if( 0 == (pData[index] % 5)){
				pData[index] /= 5;
				flag_five = 1;
				count ++;
				break;
			}
		}

	}while(flag_five);

	free(pData);
	return count;
}

【预告: 下一篇博客主要介绍随机扑克牌的算法】

时间: 2025-01-02 17:58:14

一步一步写算法(之n!中末尾零的个数统计)的相关文章

一步一步写算法(之挑选最大的n个数)

原文:一步一步写算法(之挑选最大的n个数) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     从一堆数据中挑选n个最大的数,这个问题是网上流传的比较广的几个问题之一.具体来说,它的意思就是:假设我们有100个数据,我们需要挑选出最大的n个数据(n < 100),那么有没有办法实现这样一个目标呢?在这里,我想从排序的角度看看有没有什么办法可以实现这样一个目标.     在前面的博客当中,我们实现的排序算法有下面几种:     (1)

一步一步写算法(之二叉树深度遍历)

原文:一步一步写算法(之二叉树深度遍历) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     深度遍历是软件开发中经常遇到的遍历方法.常用的遍历方法主要有下面三种:(1)前序遍历:(2)中序遍历:(3)后序遍历.按照递归的方法,这三种遍历的方法其实都不困难,前序遍历就是根-左-右,中序遍历就是左-根-右,后续遍历就是左-右-根.代码实现起来也不复杂.     1)前序遍历 void preorder_traverse(TREE_NOD

一步一步写算法(之克鲁斯卡尔算法 下)

原文:一步一步写算法(之克鲁斯卡尔算法 下) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     前面在讨论克鲁斯卡尔的算法的时候,我们分析了算法的基本过程.基本数据结构和算法中需要解决的三个问题(排序.判断.合并).今天,我们继续完成剩下部分的内容.合并函数中,我们调用了两个基本函数,find_tree_by_index和delete_mini_tree_from_group,下面给出详细的计算过程. MINI_GENERATE_T

一步一步写算法(之线性结构的处理)

原文:一步一步写算法(之线性结构的处理) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     我们知道,在内存中的空间都是连续的.也就是说,0x00000001下面的地址必然是0x00000002.所以,空间上是不会出现地址的突变的.那什么数据结构类型是连续内部空间呢,其实就是数组,当然也可以是堆.数组有很多优势,它可以在一段连续空间内保存相同类型的数据,并且对这些数据进行管理.所以从这个意义上说,掌握了数组才能说明你数据结构入门了.

一步一步写算法(之排序二叉树线索化)

原文:一步一步写算法(之排序二叉树线索化) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     前面我们谈到了排序二叉树,还没有熟悉的同学可以看一下这个,二叉树基本操作.二叉树插入.二叉树删除1.删除2.删除3.但是排序二叉树也不是没有缺点,比如说,如果我们想在排序二叉树中删除一段数据的节点怎么办呢?按照现在的结构,我们只能一个一个数据查找验证,首先看看在不在排序二叉树中,如果在那么删除:如果没有这个数据,那么继续查找.那么有没有方法

一步一步写算法(之字符串查找 中篇)

原文:一步一步写算法(之字符串查找 中篇) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     昨天我们编写了简单的字符查找函数.虽然比较简单,但是也算能用.然而,经过我们仔细分析研究一下,这么一个简单的函数还是有改进的空间的.在什么地方改进呢?大家可以慢慢往下看.     下面的代码是优化前的代码,现在再贴一次,这样分析起来也方便些: char* strstr(const char* str, char* data) { int i

一步一步写算法(之非递归排序)

原文:一步一步写算法(之非递归排序) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]        在上面一篇博客当中,我们发现普通查找和排序查找的性能差别很大.作为一个100万的数据,如果使用普通的查找方法,那么每一个数据查找平均下来就要几十万次,那么二分法的查找呢,20多次就可以搞定.这中间的差别是非常明显的.既然排序有这么好的效果,那么这篇博客中,我们就对排序算做一个总结.     按照我个人的理解,排序可以分为两种:一种是非递归排

一步一步写算法(之大数计算)

原文:一步一步写算法(之大数计算) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     我们知道在x86的32位cpu上面,int表示32位,如果核算成整数的话,大约是40多亿.同样,如果在64位cpu上面,能表示的最大整数就是64位二进制,表示的数值要大得多.那么在32位如果想表示大整数怎么办呢?那只能靠我们自己想办法了.     首先我们回顾一下我们手算整数的加减.乘除法是怎么做到的:     (1)记住9*9之间的乘法口诀   

一步一步写算法(之寻找丢失的数)

原文:一步一步写算法(之寻找丢失的数) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     假设我们有一个1亿个数据,其中数据的范围是0~1亿,也就是100M的数据.但是这个数组中丢了一些数据,比如说少了5啊,少了10啊,那么有什么办法可以把这些丢失的数据找回来呢?这个题目不难,但是它可以帮助我们拓展思路,不断提高算法的运行效率.     对于这个问题,我们一个最简单的思路就是对各个数据进行flag判断,然后依次输出数据. void