Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1

Danh tiếng các thành viên

HạngThành viênĐiểm
1mr_invincible+213
2conankudo+149
3khuc_tuan+137
4tuananhnb93+129
5khanhptnk+108
6hphong+103
7flash_mt+99
8paulmcvn+71
9technolt+70
10hoangle+63

Topcoder Vietnam

HạngThành viênĐiểm
Diễn đàn
Forum
Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) (1 đang xem) ,(1) Khách
Bài viết dưới cùng Gửi trả lời Được ưa thích: 1
  • Trang:
  • << < 1 2 > >>
CHỦ ĐỀ - Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp)
#64031
pe_nhok_su (Thành viên)
pe_nhok_su-
Biết code binary-indexed tree
Bài viết: 22
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước   (+0)
Cho N bất kì (ví dụ N=20). Hãy tính số chữ số 0 tận cùng của số N!

Giai thừa là phép toán rất lớn mà em lại chưa có thuật toán nào tối ưu cả, chỉ cần cho N>25 là bài của em sẽ sai ngay vì vượt quá giới hạn của kiểu dữ liệu. Các anh chị có thể cho em tham khảo một số thuật toán tối ưu để giải quyết được bài này không ạ?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64043
mikelhpdatke (Thành viên)
mikelhpdatke
Đã biết code đệ quy
Bài viết: 7
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước   (+0)
Viết các chữ số tận cùng của 5!,25!,50!,... la` bạn sẽ tìm ra quy luật

Code:
Var n:Longint;
 
Procedure Init;
Var  m,KQ,t,dem:Longint;
Begin
 Readln(n);
 m:=n;
If m>=25 then
 Begin
   If m mod 25=0 then
     Begin
       t:=m div 25;
       KQ:=6*t;
       writeln(KQ);
      End
    Else
      Begin
        dem:=0;
        Repeat
          dec(m);
          if m mod 5=0 then inc(dem);
        Until m mod 25=0;
        t:=m div 25;
        KQ:=6*t+dem;
        writeln(KQ);
     End;
   End
Else
   Begin
      If m mod 5 =0 then
        Begin
          KQ:=m div 5;
          writeln(KQ);
        End
      Else
        Begin
          Repeat
           dec(m);
          Until m mod 5=0;
          KQ:=m div 5;
          writeln(KQ);
        End;
     End;
End;
BEGIN
iNit;
readln
end.
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64061
royalsilver16 (Thành viên)
royalsilver16+1
Super fast coder
Bài viết: 78
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước   (+0)
pe_nhok_su viết:
QUOTE:
Cho N bất kì (ví dụ N=20). Hãy tính số chữ số 0 tận cùng của số N!

Giai thừa là phép toán rất lớn mà em lại chưa có thuật toán nào tối ưu cả, chỉ cần cho N>25 là bài của em sẽ sai ngay vì vượt quá giới hạn của kiểu dữ liệu. Các anh chị có thể cho em tham khảo một số thuật toán tối ưu để giải quyết được bài này không ạ?



Công thức Lagrange Số mũ của p trong n! là
[n / (p ^ 1)] + [n / (p ^ 2)] + [n / (p ^ 3)] + .. + [n / (p ^ oo)]
 
Đã lưu IP Đã lưu IP  
 
I do what I like
I like what I do
  Đã khóa chức năng gửi bài.
#64062
joker1569 (Thành viên)
Đã biết code đệ quy
Bài viết: 18
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước   (+0)
Ban co the de dang nhan ra so chu so 0 tan cung cua n! phu thuoc vao so thua so 2 va 5 sau khi phan tich tat ca cac so tu 1 toi n ra thua so ng to, vay van de cua ban chi la tim mot cach nao do de xac dinh so thua so 2 va 5 thoi (qhd, for trau, tinh tay...) ban muon lam kieu j cung dc. Neu ban co cach tim tot thi voi n lon (vd n= 10^6) van co cach xac dinh dc so cs 0 tan cung cua n!
Than ai!
p/s: vietkey hong?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64064
pe_nhok_su (Thành viên)
pe_nhok_su-
Biết code binary-indexed tree
Bài viết: 22
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước   (+0)
joker1569 viết:
QUOTE:
Ban co the de dang nhan ra so chu so 0 tan cung cua n! phu thuoc vao so thua so 2 va 5 sau khi phan tich tat ca cac so tu 1 toi n ra thua so ng to, vay van de cua ban chi la tim mot cach nao do de xac dinh so thua so 2 va 5 thoi (qhd, for trau, tinh tay...) ban muon lam kieu j cung dc. Neu ban co cach tim tot thi voi n lon (vd n= 10^6) van co cach xac dinh dc so cs 0 tan cung cua n! :D
Than ai!
p/s: vietkey hong? =((


Em đã nhận ra điều đó rồi nhưng thuật toán lại dở nên chỉ chạy được số nhỏ thôi. Em phải làm sao đây?
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64065
studytolive (Thành viên)
studytolive+5
Super fast coder
Bài viết: 59
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước   (+1)
pe_nhok_su viết:
QUOTE:
joker1569 viết:
QUOTE:
Ban co the de dang nhan ra so chu so 0 tan cung cua n! phu thuoc vao so thua so 2 va 5 sau khi phan tich tat ca cac so tu 1 toi n ra thua so ng to, vay van de cua ban chi la tim mot cach nao do de xac dinh so thua so 2 va 5 thoi (qhd, for trau, tinh tay...) ban muon lam kieu j cung dc. Neu ban co cach tim tot thi voi n lon (vd n= 10^6) van co cach xac dinh dc so cs 0 tan cung cua n! :D
Than ai!
p/s: vietkey hong? =((


Em đã nhận ra điều đó rồi nhưng thuật toán lại dở nên chỉ chạy được số nhỏ thôi. Em phải làm sao đây?


Ơ kìa . thuật toán đã hiểu và công thức cũng có ở dưới kia thì bạn còn băn khoăn gì nữa
Thanks for reading
 
Đã lưu IP Đã lưu IP  
 
So Try
  Đã khóa chức năng gửi bài.
#64088
joker1569 (Thành viên)
Đã biết code đệ quy
Bài viết: 18
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 6 tháng trước   (+0)
Ban da nhan ra roi` thi don gian? nhat ban cung phai? viet duoc vong lap de xac dinh tu 1 toi n co bao nhieu thua so 2 va 5 chu. Ke ca? may cui` (nhu may' cua? minh) van co the dam bao? hai vong lap chay den 1000000 (chu dung noi la 20) ko qua thoi gian. Chi la ban qua cau ne viec tinh trau thoi. Ban viet code chay thu di, co gi sai dem len day cho moi nguoi mo? xe giup cho
Than ai!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64350
baolaptrinh (Thành viên)
baolaptrinh+3
Đã code là AC
Bài viết: 101
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 5 tháng trước   (+0)
Bạn 'joker1569' gõ tiếng Việt có dấu nhé!!!Viết thế mình đọc hay nhầm lắm!!!
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64889
thanhtoanth (Thành viên)
Đang tập code
Bài viết: 2
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 5 tháng trước   (+0)
pe_nhok_su viết:
QUOTE:
joker1569 viết:
QUOTE:
Ban co the de dang nhan ra so chu so 0 tan cung cua n! phu thuoc vao so thua so 2 va 5 sau khi phan tich tat ca cac so tu 1 toi n ra thua so ng to, vay van de cua ban chi la tim mot cach nao do de xac dinh so thua so 2 va 5 thoi (qhd, for trau, tinh tay...) ban muon lam kieu j cung dc. Neu ban co cach tim tot thi voi n lon (vd n= 10^6) van co cach xac dinh dc so cs 0 tan cung cua n! :D
Than ai!
p/s: vietkey hong? =((


Em đã nhận ra điều đó rồi nhưng thuật toán lại dở nên chỉ chạy được số nhỏ thôi. Em phải làm sao đây?

zay niu yêu cầu mình tinh tới giai thừa của 20000 thi sẽ ntn.
bài này nên sử dụng một mảng một chiều mà mỗi phần tử là một chữ số của giai thừa cần tìm rồi duyệt lại để đếm số chữ số 0
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
#64890
thanhtoanth (Thành viên)
Đang tập code
Bài viết: 2
graphgraph
Thành viên gián tuyến Click vào đây để xem thông tin về thành viên này
Trả lời: Bài toán tính số chữ số 0 tận cùng của N! (phần vòng lặp) 8 năm, 5 tháng trước   (+0)
nếu 20000! thì mình phải làm sao
 
Đã lưu IP Đã lưu IP  
  Đã khóa chức năng gửi bài.
Bài viết trên cùng Gửi trả lời
  • Trang:
  • << < 1 2 > >>
Powered by FireBoardBài viết mới nhất từ diễn đàn cho các chương trình nhận tin RSS