Bạn đang xem trang 1 / 1 trang
2進数 % 3=?
Đã gửi: Hai T7 28, 2008 1:31 am
Viết bởi bac_honshu
Mình muốn hỏi có ai biết thuật toán,
xác định một số ở hệ cơ số 2 có chia hết cho 3 hay không?
(ただし không chuyển sang hệ cơ số khác)
よろしく！
Re:2進数 % 3=?
Đã gửi: Hai T7 28, 2008 3:04 am
Viết bởi azelahn
Trước tiên ta có 2[sup]2k[/sup]=4[sup]k[/sup] chia 3 dư 1; 2[sup]2k+1[/sup]=2*4[sup]k[/sup] chia 3 dư 2
Suy ra A=a*2[sup]2n[/sup]+b*2[sup]2m+1[/sup]=(a-b)*2[sup]2n[/sup]+b*(2[sup]2m+1[/sup]+2[sup]2n[/sup]) chia hết cho 3 khi a-b chia hết cho 3 (1)
Ngoài ra a[sub]n[/sub]a[sub]n-1[/sub]..a[sub]0[/sub] ở hệ cơ số 2 khi chuyển sang hệ cơ số 10 sẽ có dạng a[sub]n[/sub]*2[sup]n[/sup]+a[sub]n-1[/sub]*2[sup]n-1[/sup]+..+a[sub]0[/sub]*2[sup]0[/sup] (2)
Từ (1)&(2)=> 1 số ở hệ cơ số 2 sẽ chia hết cho 3 khi (a[sub]0[/sub]+a[sub]2[/sub]+..) - (a[sub]1[/sub]+a[sub]3[/sub]+..) chia hết cho 3
Re:2進数 % 3=?
Đã gửi: Hai T7 28, 2008 11:24 pm
Viết bởi AnhSaoDem
Xin loi vi minh dung mac nen khong go duoc Tieng Viet, moi nguoi chiu kho dich tam vay.
Neu nhu bieu dien nhi phan cua 1 so duoc sinh ra duoi dang cau truc (1(01*0)*10*)* thi no se chia het cho 3.
Trong do "*" bieu thi chu so hoac bieu thuc trong ngoac dung truoc no duoc lap lai lien tiep n lan, voi n la so nguyen khong am.
vi du
1(00)1 =1001,
1(0(1)0)1 = 10101,
1(0(11)0) =10110,
101010101010000
....
de kiem tra xem bieu dien nhi phan cua 1 so co dang cau truc tren hay khong, co the viet 1 chuong trinh de quy bang C, Java...
Tuy nhien co 1 cach don gian hon khi viet chuong trinh loai nay, do la su dung bo phan tich cu phap YACC. Vi dang ban thi hoc ky nen khong co thoi gian viet cu the ve cai nay, ban tu tim hieu them YACC tren cac trang web nhe!
Re:2進数 % 3=?
Đã gửi: Hai T7 28, 2008 11:26 pm
Viết bởi AnhSaoDem
Xin loi vi minh dung mac nen khong go duoc Tieng Viet, moi nguoi chiu kho dich tam vay.
Neu nhu bieu dien nhi phan cua 1 so duoc sinh ra duoi dang cau truc (1(01*0)*10*)* thi no se chia het cho 3.
Trong do "*" bieu thi chu so hoac bieu thuc trong ngoac dung truoc no duoc lap lai lien tiep n lan, voi n la so nguyen khong am.
vi du
1(00)1 =1001,
1(0(1)0)1 = 10101,
1(0(11)0)1 =101101,
101010101010000
....
de kiem tra xem bieu dien nhi phan cua 1 so co dang cau truc tren hay khong, co the viet 1 chuong trinh de quy bang C, Java...
Tuy nhien co 1 cach don gian hon khi viet chuong trinh loai nay, do la su dung bo phan tich cu phap YACC. Vi dang ban thi hoc ky nen khong co thoi gian viet cu the ve cai nay, ban tu tim hieu them YACC tren cac trang web nhe!
Re:2進数 % 3=?
Đã gửi: Hai T7 28, 2008 11:28 pm
Viết bởi AnhSaoDem
o vi du thu 3, thieu so 1 o cuio trong khai trien
1(0(11)0) =10110,
xin sua lai thanh
1(0(11)0)1 =101101
Re:2進数 % 3=?
Đã gửi: Ba T7 29, 2008 6:36 pm
Viết bởi Locke Laton
Tổng quát bài toán này : xét số dư của 1 số dưới dạng nhị phân M cho 1 số thập phân bất kì p.
Có 1 phương pháp "xấu" là tạo mảng chuẩn bị. Gọi A[n] là số dư của 2^n cho số p. Mảng A[n] này sẽ tạo ra từ 1 lệnh lặp : A[1]=2 ( chắc p>2 :P ), A[n]=A[n-1]*2 chia lấy dư cho p.
Thuật toán tính tổng M[ i]*A[ i] rồi chia lấy dư cho p.