hỏi về các tìm các chử số 0 của một tích

#1

Anh/CHị nào cho em hỉu phát :
Trong C/C++ để tìm số chử số 0 của 50! thì có cách nào khác ngoài cách tính ra kết quả của phép 50! không nhỉ? Nếu tính 50! thì phải dùng kiểu dữ liệu gì? vì 50! tính ra kết quả của nó rất lớn :blush:

2 Likes
#2

bạn tham khảo cách này. ntn thì tự suy nghĩ ra nha :joy:

for (int i=1; i<=n; i++)
	{
		j=i;
		while (j%5==0)
		{
			j /= 5;
			zero_count +=1;
		}
	}
#3

Vì 10=2*5 nên khi có số 0 tận cùng thì nó phải phân tích ra thừa số nguyên tố a số 2 và b số 5. Và số 0 tận cùng = min(a,b). Nhưng vì số cách phân tích ra 2 nhiều hơn nên chỉ cần tính số 5. Thì theo bạn Huy làm như trên. Mình đưa ra cải tiến cho pp trên đó là: giả sử ta đếm được từ 0->n là a cách phân tích, ta thấy cách tính số x thì sau khi chia 5 ta lại thêm tính lại x/5 đã tính từ trước. Từ đó ta có công thức cho số n:
zero_count(n)= zero_count(n/5) + n/5. Từ đó có hàm:

int zero_count(int n){
    return n<5?0: n/5+ zero_count(n/5);
}
2 Likes
#4

Mình k hiểu lắm. ý là đếm số số 0 trong kết quả của phép 50!=123*…*50 . ví dụ kq là 10110 thì số số 0 là 2 ấy :blush:

#5

Số 0 có 2 cách xuất hiện là phần đuôi của số đó và giữa số đó. VD 102045000 . Phần 000 cuối là phần đuôi, mình sẽ cải tiến thuật toán để không bị tràn số phần này :smiley: không biết đúng ý bạn @Gio không?

1 Like
#6

sao k dùng chia lấy dư với 10 rồi chạy vòng lặp bạn?? mà phải dung 2 với 5 vậy?

#7

À. Mình hiểu nhầm tưởng đếm số 0 tận cùng. Nếu đếm tất cả số 0 thì phải dùng bigint thôi :slight_smile:

1 Like
#8

bigint là gì thế cậu? mới tập tành nên k rõ lắm :smile:

#9

Tức là bạn phải dùng 1 cấu trúc khác để cài lại± * / … cho tính toán số có giá trị lớn hơn giới hạn của máy tính.

#10

Mình định dạng một kiểu dữ liệu khác lớn hơn :smile: mình thì cài đặt dưới dạng chuỗi

#11

ọc.nghe thấy rối luôn :cry:

#12

Bạn tham khảo tài liệu này nhé :smiley: đồ án của mình https://drive.google.com/file/d/0B3-lo4OX6uIVb1ZJNi1yM0JuTVk/view?usp=sharing

2 Likes
#13

cảm ơn bạn nhiều nha. có gì thắc mắc mình lại hỏi tiếp :smiley:

#14

Em lại đang cần cái đếm số cuối, cám ơn anh, em nghĩ tới 5 x 2 là hết cỡ rồi.
@B_c_Mai_Van Anh thử google, down 2 cuốn tài liệu giáo khoa chuyên tin sẽ có phần này

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?