Trong Toán học, hệ cơ số (hay hệ đếm) là một khối hệ thống các kí hiệu toán học và quy tắc sử dụng tập kí hiệu đó để trình diễn số đếm. Các kí hiệu toán học có thể là chữ số hoặc các kí tự vần âm. Cần phân biệt giữa Hệ cơ số và Cơ số (số lượng kí hiệu sử dụng trong một hệ cơ số).

Bạn Đang Xem: Hệ cơ số (Hệ đếm)

Có rất nhiều hệ cơ số khác nhau, mỗi hệ cơ số có những quy tắc trình diễn số khác nhau. Những dãy kí hiệu giống nhau có thể sẽ ứng với những số khác nhau trong các hệ đếm khác nhau. Ví dụ trong hệ thập phân, 111111 thể hiện số “mười một”, tuy nhiên trong hệ nhị phân, nó lại thể hiện số “ba”,… Số đếm mà dãy kí hiệu thể hiện được gọi là giá trị của nó.

Có hai loại hệ cơ số là hệ cơ số phụ thuộc vào vị trí và hệ cơ số không phụ thuộc vào vị trí. Chẳng hạn, hệ đếm La Mã là một hệ cơ số không phụ thuộc vào vị trí. Hệ đếm này gồm các kí hiệu vần âm: I,V,X,L,C,D,M;I, V, X, L, C, D, M;I,V,X,L,C,D,M; mỗi kí hiệu có mức giá trị cụ thể:

I=1,V=5,X=10,L=50,C=100,D=500,M=1000I=1, V=5, X=10, L=50, C=100, D=500, M=1000 I=1,V=5,X=10,L=50,C=100,D=500,M=1000

Trong hệ đếm này, giá trị của khá nhiều kí hiệu không phụ thuộc vào vị trí của nó. Ví dụ, trong hai trình diễn IX (9)IX (9)IX (9) và XI (11)XI (11)XI (11) thì XXX đều có mức giá trị là 101010.

Các hệ đếm thường dùng là các hệ đếm phụ thuộc vị trí. Mọi số nguyên basebasebase bất kỳ có mức giá trị to ra thêm 111 đều sở hữu thể được chọn làm cơ số cho một hệ đếm. Trong các hệ đếm loại này, số lượng kí hiệu sử dụng sẽ chính bằng cơ số của hệ đếm đó, và giá trị tương ứng của khá nhiều kí hiệu là: 0,1,2,…,base−10, 1, 2,…, base – 10,1,2,…,base−1. Để thể hiện một trình diễn XXX là trình diễn của số ở hệ cơ số basebasebase, ta kí hiệu là XbaseX_{base}Xbase​.

1. Giá trị của một số trong hệ cơ số bất kỳ

Trong một hệ cơ số b,b,b, giả sử số NNN có trình diễn:

dndn−1dn−2…d0,d−1d−2…d−md_nd_{n-1}d_{n-2}…d_0,d_{-1}d_{-2}…d_{-m} dn​dn−1​dn−2​…d0​,d−1​d−2​…d−m​

Trong số đó có n+1n + 1n+1 chữ số bên trái dấu phẩy, mmm chữ số bên phải dấu phẩy thể hiện cho phần nguyên và phần phân của N,N,N, và 0≤divàlt;b0 le d_i < b0≤di​<b. Khi đó giá trị của số NNN được tính theo công thức:

N=dnbn+dn−1bn−1+…+d0b0+d−1b−1+d−2b−2+…+d−mb−mN=d_nb^n+d_{n-1}b^{n-1}+…+ d_0b^0+d_{-1}b^{-1}+d_{-2}b^{-2}+…+ d_{-m}b^{-m} N=dn​bn+dn−1​bn−1+…+d0​b0+d−1​b−1+d−2​b−2+…+d−m​b−m

Giá trị của một số trong hệ cơ số bbb cũng đây là trình diễn tương ứng của nó ở hệ cơ số 101010.

Cấu hình thiết lập

Lớp học tính giá trị một số thực NNN trong hệ cơ số bbb. Ta có thể làm cách đơn giản hơn như sau: Coi như số đó không có phần phân, tính giá trị của nó trong hệ cơ số bbb rồi chia cho 10x,10^x,10x, với xxx là số chữ số phần phân.

Xem Thêm : LẬT LÀ GÌ TRONG LGBT

Ngôn ngữ C++:

void enter(string &N, int &b) { getline(cin, N); // Nhập N ở dạng xâu. cin >> b; } // Tính giá trị của trình diễn N trong hệ cơ số b, chính là biểu diễn thập phân của nó. double get_value(string &N, int b) { int pos = N.find(‘.’); // Tìm vị trí dấu ‘.’ của N. long long mul = (long long) pow(10, N.size() – pos – 1); // Tính giá trị từng phần, lưu ý ép kiểu số thực. double value = 0, power = 1; for (int i = N.size() – 1; i >= 0; -i) { value += (double) (N[i] – ‘0’) * power; power = power * (double) b; } return value / mul; } main() { string N; int b; enter(N, b); solution(N, b); }

Ngôn ngữ Python:

def enter(N, b): N = input() b = int(input()) def get_value(N, b): pos = N.find(“.”) mul = b ** (len(s) – pos – 1) if pos >= 0 else 1 res, power = 0, 1 for d in N[::-1]: if d != “.”: res += power * int(d) power *= b return res / mul if __name__ == ‘__main__’: N = “” b = 0 enter(N, b) get_value(N, b)

2. Các hệ cơ số thông dụng trong Tin học

Trong Tin học, ngoài hệ cơ số 101010, người ta còn sử dụng hai loại hệ đếm sau:

• Hệ cơ số 222 (Hệ nhị phân): Chỉ sử dụng hai kí hiệu 000 và 111. Lấy ví dụ, 10112=1×20+1×21+0×22+1×23=11101011_2=1times 2^0 + 1times 2^1 + 0times 2^2 + 1times 2^3=11_{10}10112​=1×20+1×21+0×22+1×23=1110​.
• Hệ cơ số 161616 (Hệ thập lục phân hay hệ Hexa): Sử dụng các chữ số từ 000 tới 999 và 666 vần âm A,B,C,D,E,F;A, B, C, D, E, F;A,B,C,D,E,F; trong đó A,B,C,D,E,FA, B, C, D, E, FA,B,C,D,E,F có mức giá trị tuần tự là 10,11,12,13,14,1510, 11, 12, 13, 14, 1510,11,12,13,14,15. Lấy ví dụ, 16A=10×160+6×161+1×162=3621016A = 10times 16^0+6times 16^1+1times 16^2=362_{10}16A=10×160+6×161+1×162=36210​.

3. Trình diễn số nguyên và số thực

3.1. Trình diễn số nguyên

Trong Tin học, các số nguyên có thể được trình diễn dưới dạng có dấu hoặc không dấu. Để trình diễn số nguyên, ta có thể chọn kích thước số nguyên là 111 byte, 222 byte, 444 byte$,…,2^N$ byte, mỗi cách chọn sẽ tương ứng với một khoảng chừng giá trị có thể trình diễn.

Khi đối chiếu với số nguyên không âm, kích thước 2N2^N2N byte sẽ lưu trữ được những số trong phạm vi từ 000 tới (28×2N−1),(2^{8 times 2^N} – 1),(28×2N−1), bởi 111 byte gồm 888 bit và toàn bộ các bit đều được sử dụng để trình diễn giá trị số.

Khi đối chiếu với số nguyên có dấu, bit bên phải nhất của số nguyên sẽ tiến hành dùng để làm thể hiện dấu của số đó, quy ước 111 là dấu âm, 000 là dấu dương, các bit còn sót lại sẽ dùng để làm trình diễn giá trị số. Từ đó, số nguyên kích thước 2N2^N2N sẽ trình diễn được những giá trị trong phạm vi (−28×2N−1+1)(-2^{8 times 2^N – 1} + 1)(−28×2N−1+1) đến (28×2N−1−1)(2^{8 times 2^N – 1} – 1)(28×2N−1−1). việc này sẽ liên quan tới việc lựa chọn kiểu tài liệu và kiểm soát bộ nhớ lớp học khi lập trình.

3.2. Trình diễn số thực

Khác với cách viết trong Toán học, khi mà ta dùng dấu , để ngăn cách giữa phần nguyên và phần phân; trong Tin học ta thay dấu , bằng dấu ., và các nhóm ba chữ số cạnh nhau sẽ viết liền. Ví dụ, trong toán ta viết 123 456,789;123 456,789;123 456,789; thì trong Tin học sẽ viết là 123456.789123456.789123456.789.

Một cách trình diễn mà máy tính sử dụng để lưu trữ số thực là dạng khoa học, khi mọi số thực sẽ tiến hành trình diễn ở dạng ±M×10±Kpm M times 10^{pm K}±M×10±K. Trong số đó, 0,1≤Mvàlt;1,M0,1 le M < 1, M0,1≤Mvàlt;1,M được gọi là phần định trị, và KKK là một số nguyên không âm được gọi là phần bậc. Ví dụ, số 123 456,789123 456,789123 456,789 sẽ tiến hành trình diễn dưới dạng khoa học là 0.123456789×1060.123456789 times 10^60.123456789×106.

4. Phân tích các chữ số của một số nguyên

Việc đếm số chữ số của một số nguyên dương NNN không có gì khó khăn, bởi vì các số nguyên đều có thể coi như biểu diễn dưới dạng thập phân. Vì thế, ta sẽ chia NNN cho 101010 tới khi thương bằng 0,0,0, số lần chia sẽ tương ứng với số chữ số của NNN.

Cài đặt 1: Đếm số chữ số của số nguyên dương NNN theo cách thủ công

Xem Thêm : LẬT LÀ GÌ TRONG LGBT

Ngôn ngữ C++:

int cnt_digits(int n) { // Xét riêng trường hợp n = 0. if (n == 0) return 1; int digits = 0; while (n != 0) { ++digits; n /= 10; } return digits; }

Ngôn ngữ Python:

def cnt_digits(N): digits = 0 while N != 0: digits += 1 N /= 10 return digits

Tuy nhiên, hãy giả sử số nguyên NNN có nnn chữ số được trình diễn ở hệ thập phân dưới dạng:

N=dndn−1dn−2…d1N=d_nd_{n-1}d_{n-2}…d_1 N=dn​dn−1​dn−2​…d1​

Phân tích cấu trúc số của N,N,N, ta có:

N=dn×10n−1+dn−1×10n−2+…+d1×100N=d_n times 10^{n – 1} + d_{n-1}times10^{n-2}+…+d_1times 10^0N=dn​×10n−1+dn−1​×10n−2+…+d1​×100

⇒log⁡(dn×10n−1)≤log⁡(N)=log⁡(dn×10n−1+dn−1×10n−2+…+d1×100)≤log⁡(10n)Rightarrow log(d_ntimes 10^{n-1}) le log(N)=log(d_n times 10^{n – 1} + d_{n-1}times10^{n-2}+…+d_1times 10^0) le log(10^n)⇒log(dn​×10n−1)≤log(N)=log(dn​×10n−1+dn−1​×10n−2+…+d1​×100)≤log(10n)

⇔(n−1)≤log⁡(N)≤nLeftrightarrow (n-1)le log(N) le n⇔(n−1)≤log(N)≤n.

⇔log⁡(N)≤n≤log⁡(N)+1Leftrightarrow log(N) le n le log(N)+1⇔log(N)≤n≤log(N)+1.

Giữa hai số log⁡(N)log(N)log(N) và log⁡(N)+1log(N)+1log(N)+1 chỉ có duy nhất một số là ⌊log⁡(N)⌋+1leftlfloor{log(N)}rightrfloor + 1⌊log(N)⌋+1. Vậy n=⌊log⁡(N)⌋+1n=leftlfloor{log(N)}rightrfloor + 1n=⌊log(N)⌋+1.

Khi đó, các bạn có thể sử dụng trực tiếp hàm log10() của thư viện <cmathvàgt; trong C++, hàm log() trong thư viện math của Python để đếm số chữ số của NNN.

Cài đặt 2: Đếm số chữ số của số nguyên dương NNN bằng hàm log

Xem Thêm : LẬT LÀ GÌ TRONG LGBT

Ngôn ngữ C++:

#include <cmathvàgt; using namespace std; int cnt_digits(int N) { return (int) log10(N) + 1; }

Ngôn ngữ Python:

import math def cnt_digits(N): return int(log(N)) + 1

Dựa vào trình diễn trên của số nguyên N,N,N, ta nhận thấy, chữ số hàng đơn vị của N chính bằng N mod 10,N text{ mod } 10,N mod 10, chữ số hàng chục ngàn bằng N mod 100,…,N text{ mod }100, dots,N mod 100,…, chữ số ở hàng thứ KKK tính từ phải qua trái chính bằng N mod 10KN text{ mod } 10^KN mod 10K. Khi đối chiếu với bất kỳ hệ cơ số nào ta cũng sẽ có thể coi như đang ở hệ cơ số 101010 để tìm các chữ số từ phải qua trái Theo phong cách này.

Cài đặt 3: Xác định chữ số thứ KKK từ bên phải sang của số nguyên dương NNN

Xem Thêm : LẬT LÀ GÌ TRONG LGBT

Ngôn ngữ C++:

// Tìm chữ số thứ K từ bên phải sang của số nguyên dương N. int find_k_digits(int N, int K) { int power = (int) pow(10, K); return N % power; }

Ngôn ngữ Python:

# Tìm chữ số thứ K từ bên phải sang của số nguyên dương N. def find_k_digits(N, K): power = 10 ** K return N % power

1. Chuyển đổi từ hệ cơ số 101010 sang các hệ cơ số khác

Xét số thực NNN ở hệ cơ số 101010. Để tìm trình diễn của NNN trong hệ cơ số bbb, ta sẽ tuần tự chuyển đổi phần nguyên và phần phân, sau đó ghép chúng lại với nhau.

1.1. Chuyển đổi phần nguyên

Xét phần nguyên của NNN là KKK. Giả sử trong hệ đếm b,Kb, Kb,K có mức giá trị là:

K=dnbn+dn−1bn−1+⋯+d1b+d0K=d_nb^n + d_{n-1}b^{n-1} + cdots + d_1b + d_0 K=dn​bn+dn−1​bn−1+⋯+d1​b+d0​

Do 0≤d0vàlt;b0 le d_0 < b0≤d0​<b nên những lúc chia KKK cho bbb thì phần dư của phép chia là d0,d_0,d0​, còn thương là:

K1=dnbn+dn−1bn−1+⋯+d1K_1=d_nb^n + d_{n-1}b^{n-1} + cdots +d_1 K1​=dn​bn+dn−1​bn−1+⋯+d1​

Tương tự, d1d_1d1​ đây là phần dư của phép chia K1K_1K1​ cho b,b,b, và sẽ thu được K2K_2K2​ là thương của phép chia đó. Tái diễn quá trình chia như trên tới khi thu được thương bằng 0,0,0, khi đó trình diễn của KKK ở hệ cơ số bbb là dn…d0d_n…d_0dn​…d0​. Nói cách khác, ta lấy KKK chia cho b,b,b, thu nhận thương và số dư ở mỗi lần chia cho tới khi thương bằng 0,0,0, khi đó viết các số dư theo trật tự ngược từ dưới lên trên thì sẽ thu được trình diễn của KKK ở hệ cơ số bbb.

Ví dụ, với K=410K=4_{10}K=410​ và b=2,b=2,b=2, quá trình chuyển đổi sẽ diễn ra như sau:

• Chia 444 cho 222, thu được K1=2,d0=0K_1=2, d_0 = 0K1​=2,d0​=0.
• Chia 222 cho 222, thu được K2=1,d1=0K_2=1, d_1=0K2​=1,d1​=0.
• Chia 111 cho 222, thu được K3=0,d2=1K_3=0, d_2=1K3​=0,d2​=1.
• Tới đây quá trình tạm ngừng, thu được kết quả 410=10024_{10}=100_2410​=1002​.

Cấu hình thiết lập

Xem Thêm : LẬT LÀ GÌ TRONG LGBT

Ngôn ngữ C++:

// Chuyển phần nguyên K của số N sang hệ đếm b, lưu vào chuỗi res. string change_integer_path(int K, int b) { string res; while (K != 0) { res = (char) (K % b + 48) + res; K /= b; } return res; }

Ngôn ngữ Python:

# Chuyển phần nguyên K của số N sang hệ đếm b, lưu vào chuỗi res. def change_integer_path(K, b): res = “” while K != 0: res = str(K % b) + res K /= b return res

1.2. Chuyển đổi phần phân

Xét phần phân của số thực NNN là K′K’K′. Giả sử trong hệ đếm b,K′b, K’b,K′ có mức giá trị là:

K′=d−1b−1+d−2b−2+⋯+d−mb−m (1)K’=d_{-1}b^{-1}+d_{-2}b^{-2} + cdots + d_{-m}b^{-m} (1) K′=d−1​b−1+d−2​b−2+⋯+d−m​b−m (1)

Nhân cả 222 vế của (1)(1)(1) với b,b,b, ta có:

K1′=d−1+d−2b−1+⋯+d−mb−(m−1)K’_1=d_{-1}+d_{-2}b^{-1}+cdots+d_{-m}b^{-(m-1)} K1′​=d−1​+d−2​b−1+⋯+d−m​b−(m−1)

Ta thấy, d−1d_{-1}d−1​ đây là phần nguyên của kết quả phép nhân K′K’K′ với bbb, còn phần phân của kết quả là:

K2′=d−2b−1+⋯+d−mb−(m−1) (2)K’_2=d_{-2}b^{-1}+cdots+d_{-m}b^{-(m-1)} (2) K2′​=d−2​b−1+⋯+d−m​b−(m−1) (2)

Tiếp tục tái diễn phép nhân như trên với (2),(2),(2), ta sẽ thu được d−2d_{-2}d−2​ là phần nguyên. Làm liên tục Theo phong cách này, cuối cùng thu được dãy d−1d−2d−3…,d_{-1}d_{-2}d_{-3}…,d−1​d−2​d−3​…, trong đó 0≤divàlt;b0 le d_i < b0≤di​<b. Nói cách khác, lấy phần phân K′K’K′ nhân liên tục với b,b,b, ở từng bước một thu nhận chữ số ở phần nguyên của kết quả và tái diễn quá trình nhân với phần phân của kết quả cho tới khi thu được số lượng chữ số như ý muốn.

Ví dụ, với K′=0.12310,b=2K’=0.123_{10}, b=2K′=0.12310​,b=2 và cần lấy tới 555 chữ số phần phân ở kết quả, ta làm như sau:

• 0.123×2=0.246→d−1=00.123 times 2 = 0.246 rightarrow d_{-1}=00.123×2=0.246→d−1​=0.
• 0.246×2=0.492→d−2=00.246 times 2 = 0.492 rightarrow d_{-2}=00.246×2=0.492→d−2​=0.
• 0.492×2=0.984→d−3=00.492 times 2 = 0.984 rightarrow d_{-3}=00.492×2=0.984→d−3​=0.
• 0.984×2=1.968→d−4=10.984 times 2 = 1.968 rightarrow d_{-4}=10.984×2=1.968→d−4​=1.
• 0.968×2=1.936→d−5=10.968 times 2 = 1.936 rightarrow d_{-5}=10.968×2=1.936→d−5​=1. ⋯cdots⋯

Tới đây thu được kết quả 0.12310=0.00011…20.123_{10}=0.00011…_20.12310​=0.00011…2​

Cấu hình thiết lập

Xem Thêm : LẬT LÀ GÌ TRONG LGBT

Ngôn ngữ C++:

// Chuyển phần phân K sang hệ đếm b, lấy cnt_digits chữ số phần phân. string change_double_path(double K, int b, int cnt_digits) { string ans; while (ans.size() < cnt_digits) { double next_K = K * (double) b; int digit = (int) next_K; ans = ans + (char) (digit + 48); K = next_K – (int) next_K; } return ans; }

Ngôn ngữ Python:

# Chuyển phần phân K sang hệ đếm b, lấy cnt_digits chữ số phần phân. def change_double_path(K, b, cnt_digits): res = [] while len(res) < cnt_digits: next_K = K * float(b) digit = int(next_K) res.append(digit) K = next_K – int(next_K) return res

2. Chuyển đổi số từ hệ cơ số xxx sang hệ cơ số yyy

Để chuyển một số NNN từ hệ cơ số xxx sang hệ cơ số y,y,y, ta tuân theo các bước sau:

• Bước 111: Tính giá trị của số NNN trong hệ cơ số x,x,x, nói cách khác là chuyển NxN_xNx​ sang hệ cơ số 101010.
• Bước 222: Chuyển kết quả vừa tìm được sang hệ cơ số yyy theo phương pháp chuyển một số ở hệ 101010 sang hệ yyy ở phần 111.

Cài đặt

Tái sử dụng lại một số hàm đã xây dựng sẵn ở trên: get_value(), change_integer_path(), change_double_path, ta sẽ chuyển đổi được số thực NNN từ hệ cơ số xxx sang hệ cơ số yyy.

Xem Thêm : LẬT LÀ GÌ TRONG LGBT

Ngôn ngữ C++:

// Chuyển số thực N từ hệ đếm x sang hệ đếm y, lấy d chữ số sau dấu phẩy. string change_x_to_y(double N, int x, int y, int d) { string NN = to_string(N); double value_x = get_value(NN, x); int integer_path = (int) value_x; double double_path = value_x – integer_path; string res = change_integer_path(integer_path, y) + ‘.’ + change_double_path(double_path, y, d); return res; }

Ngôn ngữ Python:

Xem Thêm : Kiểm Thử Hộp Đen – Black box Testing

def change_x_to_y(N, x, y, d): NN = str(N) value_x = get_value(NN, x) integer_path = int(value_x) double_path = value_x – integer_path res = change_integer_path(integer_path, y) + ‘.’ + change_double_path(double_path, y, d) return res

3. Chuyển đổi giữa hệ cơ số 222 (hệ nhị phân) và hệ cơ số 161616 (hệ Hexa)

Do 161616 là lũy thừa của 222 (16=24)(16=2^4)(16=24), nên việc chuyển đổi giữa hệ nhị phân và hệ hexa có thể được thực hiện dễ dàng theo quy tắc sau:

• Bước 111: Tính từ vị trí phân cách phần nguyên và phần phân, ta gộp các chữ số thành từng nhóm 444 chữ số về hai phía trái phải, nếu thiếu chữ số sẽ thay bằng các chữ số 000.
• Bước 222: Tính giá trị của từng nhóm chữ số, sau đó thay kết quả bằng một kí hiệu tương ứng ở hệ Hexa. Ví dụ 222 tương ứng với 222, 101010 tương ứng với AAA,…
• Bước 333: Đặt các kí hiệu sau khoản thời gian đã chuyển đổi vào đúng trật tự của từng nhóm, ta thu được kết quả chuyển đổi.

Cấu hình thiết lập 1: Chuyển đổi từ hệ nhị phân sang hệ Hexa

#include <bits/stdc++.hvàgt; using namespace std; const char hexa[16] = {‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’}; string binary_to_hexa(double N) { string NN = to_string(N); int pos = NN.find(‘.’); string left_path = NN.substr(0, pos), right_path = NN.substr(pos + 1, NN.size() – pos); // Bổ sung đủ chữ số 0 để tạo thành các nhóm 4. while (left_path.size() % 4 != 0) left_path = ‘0’ + left_path; while (right_path.size() % 4 != 0) right_path = right_path + ‘0’; string ans_left, ans_right; for (int i = 0; i < left_path.size() – 3; i += 4) { // Gộp cụm 4 kí tự liên tục. string group = left_path.substr(i, 4); // Tính giá trị cụm 4 kí tự. int power = 1, value = 0; for (int j = 3; j >= 0; -j) { value += (group[j] – ‘0’) * power; power *= 2; } // Lấy kí tự hexa mang giá trị tương ứng. ans_left = ans_left + hexa[value]; } for (int i = 0; i < right_path.size() – 3; ++i) { string group = right_path.substr(i, 4); int power = 1, value = 0; for (int j = 3; j >= 0; -j) { value += (group[j] – ‘0’) * power; power *= 2; } ans_right = ans_right + hexa[value]; } return (ans_left + ‘.’ + ans_right); }

Ngôn ngữ Python:

hexa = [‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’, ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’] def binary_to_hexa(n: float) -> str: nn = str(n) pos = nn.index(‘.’) left_path, right_path = nn[:pos], nn[pos+1:] # Bổ sung đủ chữ số 0 để tạo thành các nhóm 4. while len(left_path) % 4 != 0: left_path = ‘0’ + left_path while len(right_path) % 4 != 0: right_path = right_path + ‘0’ ans_left, ans_right = ”, ” for i in range(0, len(left_path)-3, 4): # Gộp cụm 4 kí tự liên tục group = left_path[i:i+4] # Tính giá trị cụm 4 kí tự. power, value = 1, 0 for j in range(3, -1, -1): value += int(group[j]) * power power *= 2 # Lấy kí tự hexa mang giá trị tương ứng. ans_left = ans_left + hexa[value] for i in range(0, len(right_path)-3, 4): group = right_path[i:i+4] power, value = 1, 0 for j in range(3, -1, -1): value += int(group[j]) * power power *= 2 ans_right = ans_right + hexa[value] return ans_left + ‘.’ + ans_right

Ở khunh hướng trái lại, khi chuyển từ hệ nhị phân sang hệ hexa, tất cả chúng ta chỉ có đổi từng kí tự hexa sang cụm bốn kí tự nhị phân có mức giá trị tương ứng. Ta có thể đơn giản hóa bằng cách khởi tạo trước một mảng binary_codetext{binary_code}binary_code gồm 151515 phần tử, với nghĩa nghĩa binary_code[i]text{binary_code}[i]binary_code[i] là biểu diễn nhị phân tương ứng với kí tự Hexe i (0≤i≤15)i (0 le i le 15)i (0≤i≤15). Lưu ý rằng, với ivàgt;10i > 10ivàgt;10 thì sẽ tương ứng với các kí tự A, B, C, D, E, F nên ta cần xử lý tinh tế để biết được kí tự chữ cái tương ứng với iii bằng bao nhiêu.

Cài đặt 2: Chuyển đổi từ hệ Hexa sang hệ nhị phân

Xem Thêm : LẬT LÀ GÌ TRONG LGBT

Ngôn ngữ C++:

string hexa_to_binary(double N) { string binary_code[15] = {“0000”, “0001”, “0010”, “0011”, “0100”, “0101”, “0110”, “0111”, “1000”, “1001”, “1010”, “1011”, “1100”, “1101”, “1110”, “1111”} string NN = to_string(N); string res; for (int i = 0; i < NN.size(); ++i) if (‘0’ <= NN[i] && NN[i] <= ‘9’) res += binary_code[NN[i] – ‘0’]; else if (‘A’ <= NN[i] && NN[i] <= ‘F’) { int pos = NN[i] – 55; res += binary[pos]; } return res; }

Ngôn ngữ Python:

def hexa_to_binary(n: float) -> str: binary_code = [“0000”, “0001”, “0010”, “0011”, “0100”, “0101”, “0110”, “0111”, “1000”, “1001”, “1010”, “1011”, “1100”, “1101”, “1110”, “1111”] nn = str(n) res = ” for i in range(len(nn)): if ‘0’ <= nn[i] and nn[i] <= ‘9’: res += binary_code[nn[i] – ‘0’] elif ‘A’ <= nn[i] and nn[i] <= ‘F’: pos = nn[i] – 55 res += binary_code[pos] return res

1. Số nhị phân thứ K

Đề bài

Xét các số nhị phân có độ dài NNN với số nhỏ nhất là 100…0‾overline{100…0}100…0 (N−1N-1N−1 chữ số 000) và số lớn số 1 là 111…1‾overline{111…1}111…1 (NNN chữ số 111). Ví dụ với N=3,N=3,N=3, ta có những số nhị phân độ dài 3 là 100,101,110100,101,110100,101,110 và 111111111.

Yêu cầu: Cho trước hai số nguyên dương NNN và KKK. Hãy xác định số nhị phân thứ KKK trong dãy số nhị phân có độ dài N?N?N?

Input:

• Một dòng duy nhất chứa hai số nguyên dương NNN và KKK.

Ràng buộc:

• 1≤N≤301 le N le 301≤N≤30.
• 1≤K≤1091 le K le 10^91≤K≤109.

Output:

• Số nhị phân thứ KKK tìm được.

Sample Input:

3 3

Sample Output:

110

Ý tưởng

Trong dãy nhị phân có độ dài N,N,N, số nhỏ nhất là: 100…0‾overline{100…0}100…0 (N−1N – 1N−1 chữ số 000). Số này có mức giá trị tương ứng trong hệ thập phân đây là 2N−12^{N – 1}2N−1. Muốn lấy số thứ K,K,K, ta chỉ có thêm vào đó K−1K – 1K−1 đơn vị vào số nhỏ nhất đó, nhưng nếu như tiến hành cộng ở hệ nhị phân thì sẽ tương đối phức tạp. Do đó, ta có thể lấy luôn giá trị 2N−1+(K−1)2^{N – 1} + (K – 1)2N−1+(K−1) ở hệ thập phân của số nhị phân thứ K,K,K, rồi đổi trái lại hệ nhị phân, kết quả vẫn sẽ hoàn toàn xác thực.

Độ phức tạp: O(N)O(N)O(N).

Code mẫu

#include <bits/stdc++.hvàgt; #define int long long using namespace std; void solution(int n, int k) { int power = 1 << (n – 1) + (k – 1); // Tính 2^{n – 1} + (k – 1). string res; while (power > 0) { if (power % 2) res = ‘1’ + res; else res = ‘0’ + res; power /= 2; } cout << res; } main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin >> n >> k; solution(n, k); return 0; }

2. Trình diễn nhị phân

Đề bài

Mọi số nguyên dương XXX đều sở hữu thể trình diễn trong hệ nhị phân tương tự như trình diễn trong hệ thập phân. Chẳng hạn, số X=17X=17X=17 có trình diễn nhị phân là 100011000110001 vì 17=1×24+117=1×2^4+117=1×24+1.

Yêu cầu: Cho trước một số nguyên dương XXX. Hãy thực hiện các yêu cầu sau:

• Tìm trình diễn nhị phân của số XXX.
• Tìm số YYY lớn số 1 trong hệ thập phân sao cho trình diễn nhị phân của YYY thu được từ XXX bằng phương pháp hoán vị vòng quanh các chữ số trong trình diễn nhị phân của XXX.

Input:

• Gồm một số nguyên dương XXX duy nhất.

Ràng buộc:

• 1≤X≤1091≤X≤10^91≤X≤109.

Output:

• Dòng thứ nhất ghi trình diễn nhị phân của XXX.
• Dòng thứ hai ghi số YYY tìm được.

Sample Input:

17

Sample Output:

10001 24

Giảng giải:

Ta có 17=1×24+1,17=1×2^4+1,17=1×24+1, do đó trình diễn nhị phân của 171717 là 100011000110001.

Số nhị phân có mức giá trị lớn số 1 thu được từ XXX khi hoán vị vòng quanh các chữ số trong trình diễn nhị phân của XXX là 110001100011000. Số đó có mức giá trị thập phân là 242424.

Ý tưởng

Khi đối chiếu với yêu cầu thứ nhất, ta dùng thuật toán chuyển đổi từ hệ cơ số 101010 sang hệ nhị phân thông thường, không có gì đặc biệt quan trọng. Sau đó lưu kết quả thu được vào trong 1 xâu sss.

Khi đối chiếu với yêu cầu thứ hai, trước tiên các bạn cần phải làm rõ thế nào là hoán vị vòng quanh? Bởi vì có rất nhiều bạn ở bài này sẽ lầm tưởng kết quả là đảo toàn bộ số 111 lên trước, số 000 về cuối. Tuy nhiên, ta chỉ được phép xét các hoán vị vòng quanh của xâu nhị phân s,s,s, tức là cứ đảo một chữ số từ trên đầu xuống cuối thì ta được một hoán vị vòng quanh, chứ không phải hoán vị lộn xộn tất cả những chữ số. Như vậy, nếu xâu nhị phân có độ dài nnn thì ta sẽ có được nnn hoán vị vòng quanh.

Để xét các hoán vị vòng quanh, ta sử dụng một kĩ thuật nhỏ, đó là nhân đôi xâu. Chẳng hạn, xâu 110011 sẽ trở thành 110011110011. Gọi nnn là độ dài của xâu nhị phân cũ, ta xét từng vị trí i (0≤ivàlt;n),i (0 le i < n),i (0≤ivàlt;n), thì một xâu con độ dài nnn xuất phát điểm từ vị trí iii sẽ là một hoán vị vòng quanh. Sau đó, với mỗi hoán vị này ta chỉ có đổi nó sang hệ thập phân lại, rồi lấy kết quả lớn số 1 là xong.

Độ phức tạp: O(n2)O(n^2)O(n2) với nnn là độ dài xâu nhị phân sss.

Code mẫu

#include <bits/stdc++.hvàgt; #define int long long using namespace std; string dec_to_bin(int x) { string res; while (x != 0) { res = (char) (x % 2 + ‘0’) + res; x /= 2; } return res; } // Tìm giá trị thập phân của một xâu nhị phân S. int bin_to_dec(string s) { int exp = 1, res = 0; for (int i = s.size() – 1; i >= 0; -i) { res = res + (s[i] – ‘0’) * exp; exp *= 2; } return res; } /** * Hàm tính toán hai yêu cầu của đề bài. * Yêu cầu thứ nhất: Đưa ra trình diễn nhị phân của số X -> Dùng hàm dec_to_bin(). * Yêu cầu thứ hai: Ta xét mọi hoán vị vòng quanh của xâu nhị phân s (là trình diễn của x), sau đó tìm giá trị thập phân lớn số 1 trong tất cả những hoán vị vòng quanh đó. Phương pháp xây dựng hoán vị vòng quanh là gấp đôi xâu lên, rồi xét mọi xâu độ dài n (n là độ dài xâu np thuở đầu) xuất phát điểm từ vị trí i (0 <= i < n). */ void solution(int x) { string circular_per = dec_to_bin(x); // Kết thúc yêu cầu thứ nhất: In ra trình diễn nhị phân của x. cout << circular_per << endl; // Mở màn yêu cầu thứ hai, ta nhân đôi xâu nhị phân lên để tiến hành tìm các hoán vị vòng quanh. int n = circular_per.size(), max_decimal = 0; circular_per += circular_per; for (int i = 0; i < n; ++i) max_decimal = max(max_decimal, bin_to_dec(circular_per.substr(i, n))); cout << max_decimal; } main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int x; cin >> x; solution(x); return 0; }

• https://en.wikipedia.org/wiki/Numeral_system
• Sách giáo khoa Tin học 10 – Thầy Hồ Sĩ Đàm