黑马程序员技术交流社区

标题: 在入学题的时候碰到一个难题,到现在我都没有想通 [打印本页]
作者: 石头-剪刀    时间: 2014-9-15 21:03
标题: 在入学题的时候碰到一个难题,到现在我都没有想通
本帖最后由 石头-剪刀 于 2014-9-16 23:18 编辑

      原题已经不再了,不过大概内容还记得:
      100!,求结果中有多少个0.想了好久都没有一个准确的解法,不过有大概的思路:
           创建一个数组,数组里面用来存储每一位的值,例如25*2：arr[0]=5,arr[1]=2;  arr[0]*2=10;if(arr[0]>9) {arr[1] = arr[1] + arr[0]/10}
      不知道大家有没有好的思路?一起分享

作者: hejinzhong    时间: 2014-9-15 21:15
* (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. }
复制代码

作者: 石头-剪刀    时间: 2014-9-15 21:34
hejinzhong 发表于 2014-9-15 21:15
* (1)由于1000！的结果太大，无法直接用一个基本数据类型的变量来存储，所以定义一个数组来分别存计算结果 ...

是的,跟我当初的想法一样oh year
作者: 刘宣超    时间: 2014-9-15 21:37
此问题我也遇见过，数据实在太了，想了半天也没解决，感谢解答。



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