黑马程序员技术交流社区

标题: 一到基础测试里的算法题，这题是不是给错了啊啊~ [打印本页]

---

作者: 银酱    时间: 2014-3-9 17:15
标题: 一到基础测试里的算法题，这题是不是给错了啊啊~


原题是：
求1000！的结果中包含多少个0
1000! = 1×2×3×4×5×...×999×1000

可网上的算法都是1000！的结尾有多少个0，这个不仅仅是看结尾有多少0，有什么算法~:'(

---

作者: ixiangfeng    时间: 2014-3-9 17:26
题是不会错的 不要往算法方面想， 去找BigDecimal和BigInteger两个类看看

---

作者: 银酱    时间: 2014-3-9 17:29

ixiangfeng 发表于 2014-3-9 17:26
题是不会错的 不要往算法方面想， 去找BigDecimal和BigInteger两个类看看

应该吧。BigInteger没听过啊？视频里提到过吗？ 好像找了个算法，用数组进位的方式做，还得慢慢研究:L

---

作者: ixiangfeng    时间: 2014-3-9 17:36

银酱 发表于 2014-3-9 17:29
应该吧。BigInteger没听过啊？视频里提到过吗？ 好像找了个算法，用数组进位的方式做，还得慢慢研究 ...

我做过的、、、怕被说透题就不给代码了 毕老师的视频没提到过 但是你看书就会有说到的 有很多东西老师都不一定能提得到 毕竟太多了 当你去用的时候需要某些功能的时候就去找API 一般你想到别人都会提供给你的 BigInteger就是专门处理大整型数据的类 用递归原理就行了

---

作者: 银酱    时间: 2014-3-9 17:39

ixiangfeng 发表于 2014-3-9 17:36
我做过的、、、怕被说透题就不给代码了 毕老师的视频没提到过 但是你看书就会有说到的 有很多东西老师都 ...

嗯，谢谢啦:)

---

作者: 银酱    时间: 2014-3-9 18:55

ixiangfeng 发表于 2014-3-9 17:36
我做过的、、、怕被说透题就不给代码了 毕老师的视频没提到过 但是你看书就会有说到的 有很多东西老师都 ...

我用数组的方法做出来有472个零，对不对呀~

---

作者: 王松松    时间: 2014-3-9 19:54

1. import java.math.BigInteger;
   
2. import java.util.regex.*;  
   
3. import java.util.*;  
   
4. class Test2{
   
5.        
   
6.         public static void main(String ars[]){
   
7.                 Test2 test2 = new Test2();
   
8.                 test2.jieCheng(1000);
   
9.         }
   
10.        
    
11.         public void jieCheng(int number){
    
12.                 BigInteger res = new BigInteger("1");  
    
13.                
    
14.                 for (int i = 1; i <= number; i++) {  
    
15.                 BigInteger num = new BigInteger(String.valueOf(i));  
    
16.                 res = res.multiply(num); //相当于res * = num;，但是不是基本数据类型，不能使用*运算符
    
17.             }
    
18.                 String str = res.toString();
    
19.                 int allZero = allZeroCount(str);
    
20.                 int lastZro =lastZeroCount(str);
    
21.                 System.out.println(number+"的阶乘为："+"\n"+str);
    
22.                 System.out.println(number+"的阶乘中所有的0的个数："+allZero);
    
23.                 System.out.println(number+"的阶乘中末尾的0的个数："+lastZro);
    
24.         }
    
25.        
    
26.         //求阶乘结果末尾的0的个数
    
27.         public int lastZeroCount(String str){
    
28.                 int count = 0;
    
29.                 char regex = '0';
    
30.                 int length = str.length();
    
31.                 int index = length-1;
    
32.                 while(str.charAt(index)==regex){
    
33.                         count++;
    
34.                         index--;
    
35.                 }
    
36.                 return count;
    
37.         }
    
38.        
    
39.         //求阶乘结果所有的0的个数
    
40.         public int allZeroCount(String str){
    
41.                 int count = 0;
    
42.                 String regex = "0";
    
43.                 Pattern p = Pattern.compile(regex);  
    
44.         Matcher m = p.matcher(str);  
    
45.         while (m.find())  
    
46.         {  
    
47.             count++;
    
48.         }  
    
49.                 return count;
    
50.         }
    
51. }

复制代码

---

作者: syw02014    时间: 2014-3-9 19:55
你试试：

1. import java.util.*;
   
2. public class Factorial
   
3. {
   
4.         public static void main(String[] args)
   
5.         {
   
6.                
   
7.                 System.out.print("输入要求阶乘的数：");
   
8.                 Scanner cin = new Scanner(System.in);
   
9.                 int n = cin.nextInt();
   
10.                 FactorialMethod(n);
    
11.         }
    
12.        
    
13.         public static void FactorialMethod(int n)
    
14.         {
    
15.                 int[] data=new int[100000];
    
16.                 int weishu=1; // 求出来的值的位数
    
17.                 int count=0;
    
18.                 data[1]= 1;
    
19.                
    
20.                 for(int i=1;i<=n;i++)
    
21.                 {
    
22.                         for(int j=1;j<=weishu;j++)
    
23.                                 data[j]=data[j]*i;
    
24.                        
    
25.                         for(int j=1;j<weishu;j++) // 确保除最高位外的每位不大于9
    
26.                         {
    
27.                                 if(data[j]>=10)
    
28.                                 {
    
29.                                         data[j+1]+=data[j]/10;
    
30.                                         data[j]=data[j]%10;
    
31.                                 }
    
32.                         }
    
33.                        
    
34.                         while(data[weishu]>=10)//确保最高位不大于9
    
35.                         {
    
36.                                 weishu++;
    
37.                                 data[weishu]+=data[weishu-1]/10;
    
38.                                 data[weishu-1]=data[weishu-1]%10;
    
39.                         }
    
40.                 }
    
41.                
    
42.                 System.out.println(n + "的阶乘：");
    
43.                 for(int i=weishu;i>=1;i--)
    
44.                 {
    
45.                         if(data[i]==0)
    
46.                                 count++;
    
47.                         if(i%100==0)
    
48.                                 System.out.println();
    
49.                         System.out.print(data[i]);
    
50.                 }
    
51.                 System.out.println("\n"+n+"的阶乘中0的个数："+count);
    
52.         }
    
53. }
    

复制代码

程序测试：
输入要求阶乘的数：1000
1000的阶乘：
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
1000的阶乘中0的个数：472

---

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

黑马程序员IT技术论坛 X3.2