黑马程序员技术交流社区

标题: 基础测试之1000！中0的个数！求更简洁思路。 [打印本页]
作者: hejinzhong    时间: 2014-8-1 00:49
标题: 基础测试之1000！中0的个数！求更简洁思路。
本帖最后由 hejinzhong 于 2014-8-1 01:06 编辑

* (1)由于1000！的结果太大，无法直接用一个基本数据类型的变量来存储，所以定义一个数组来分别存计算结果的每一位数字。
* (2)计算过程：让每个角标上的数字和相应的乘数相乘并加上前一位的进位。（细节参看 下面calculator 函数）
* (3)遍历数组，查询0的个数。
*
* 举个例子说明计算过程
* 3024 x 15 = 45360（计算器计算结果）
* 每次开始计算进位都为0
* 角标     元素           乘数           上位进位                   运算后该角标值               该位产生的进位
*  0          4       x        15      +         0        =  60                  0                                       6
*  1          2       x        15      +         6       =  36                   6                                       3
*  2          0       x        15      +         3        =  03                  3                                       0
*  3         3        x        15      +        0        =  45                   5                                       4//3024已经算完了,还有进位，多算3位
*  4        0         x        15      +        4        =  04                    4                                       0
*  5        0         x        15      +        0        =  00                     0                                      0
*  6        0        x         15      +        0        =  00                      0                                     0
*  这样在数组中的元素倒着看即为 0045360，当去掉前面0，即为我们需要的运算结果。
*  

  2. public class Test9
  3. {
  4.         private static final int MAX_BOUNDS = 3000;//当角标越界时，可调大该数值
  5.         
  6.         public static void main(String[] args)
  7.         {
  8.                 factorial(1000);//求1000的阶乘
  9.         }
  10.         
  11.         public static void factorial(int num)
  12.         {        
  13.                 int[] arr = new int[MAX_BOUNDS];
  14.                 calculator(arr,num);//计算num的阶乘
  15.                 checkZero(arr);//统计结果中0的个数
  16.         }
  17.         
  18.         private static int[] calculator(int[] arr,int num)
  19.         {
  20.                 arr[0]=1;//将数组中0位元素设为1，任何数和1相乘不影响结果.
  21.                
  22.                 for(int i=1;i<=num;i++)
  23.                 {        
  24.                         int temp = 0,carry = 0;
  25.                         int max = max(arr);
  26.                         
  27.                         for(int j=0;j<max+4;j++)//乘以1000以内的数，增加的长度不超过3，多向后检测3位。
  28.                         {
  29.                                 temp=arr[j]*i+carry;
  30.                                 arr[j]=temp%10;//当前角标值
  31.                                 carry=temp/10;//进位
  32.                         }
  33.                 }
  34.                 return arr;
  35.         }
  36.         
  37.         private static void checkZero(int[] arr)//检测数组中一共有多少个0,最高位开始
  38.         {
  39.                 int count = 0;
  40.                 for(int i=max(arr);i>=0;i--)
  41.                 {
  42.                         if(arr[i]==0)
  43.                                 count++;
  44.                 }
  45.                 System.out.println("共包含0个数："+count);
  46.         }
  47.         
  48.         private static int max(int[] arr)//检测数组中非0的最大角标
  49.         {
  50.                 for(int max= MAX_BOUNDS-1;max>0;max--)
  51.                 {
  52.                         while(arr[max]!=0)
  53.                                 return max;
  54.                 }
  55.                 return 0;
  56.         }

  58. }
复制代码
作者: fantacyleo    时间: 2014-8-1 00:55
这是我写的http://bbs.itheima.com/thread-133474-1-1.html，思路其实差不多。不用BigInteger的话，我觉得这已经是最简单的思路了，除非从数学上去考虑怎么给出两数相乘的积包含几个0的一般公式。
作者: fantacyleo    时间: 2014-8-1 00:56
还有就是，这个思路的效率其实还挺让人满意的。至少在算1000！时感觉不出比用BigInteger慢
作者: hejinzhong    时间: 2014-8-1 00:57
fantacyleo 发表于 2014-8-1 00:56
还有就是，这个思路的效率其实还挺让人满意的。至少在算1000！时感觉不出比用BigInteger慢 ...

我也写了代码，感觉还行，核心点和你基本一样把。代码插不上来。你用的什么浏览器。
作者: hejinzhong    时间: 2014-8-1 00:59
fantacyleo 发表于 2014-8-1 00:56
还有就是，这个思路的效率其实还挺让人满意的。至少在算1000！时感觉不出比用BigInteger慢 ...

数学考虑只算结尾就简单，但是问题是中间的0产生的可能有点多。
作者: fantacyleo    时间: 2014-8-1 01:01
hejinzhong 发表于 2014-8-1 00:57
我也写了代码，感觉还行，核心点和你基本一样把。代码插不上来。你用的什么浏览器。 ...

火狐。我怀疑跟浏览器没关系，是论坛的bug。你用“纯文字”模式，直接操作html标签就不会出代码粘贴丢失的问题了
作者: 烟海    时间: 2014-8-1 22:45
大概看懂了一点。。。不错。。。。牛人。。。
作者: zxdanshui    时间: 2014-8-1 23:06
看看                             
作者: 张周飞    时间: 2014-8-27 09:19
学习了  楼主  大爱
作者: 戏言丶    时间: 2014-8-27 11:20
都是大神啊，学习了
作者: 妖精斩月    时间: 2014-8-27 12:13
谢谢分享
作者: 桂何钢    时间: 2014-8-27 14:12
本帖最后由 桂何钢 于 2017-3-25 13:30 编辑

1111111111111
作者: 何艳梅    时间: 2014-8-27 15:22
楼主思路不错啊！
作者: snowaves    时间: 2014-8-28 00:20
{:3_68:}只要求出每个数能否被5整除，能整除几次，然后记录这个次数，加在一起就是0的个数，因为2×5=10，而2的个数是绝对够用的。
作者: 天使也掉毛    时间: 2015-9-10 01:36
烟海 发表于 2014-8-1 22:45
大概看懂了一点。。。不错。。。。牛人。。。

厉害
!!!!!



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2