Các hệ đếm trong tin học

     
I. Giới thiệu chung

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 đó để màn trình diễn số đếm. Những kí hiệu toán học hoàn toàn có thể là chữ số hoặc những kí từ chữ cái. Bắt buộc phân biệt thân Hệ cơ sốCơ số (số lượng kí hiệu thực hiện trong một hệ cơ số).

Bạn đang xem: Các hệ đếm trong tin học

Có tương đối 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. đầy đủ dãy kí hiệu giống nhau có thể sẽ ứng với số đông số khác nhau trong các hệ đếm không giống nhau. Lấy một ví dụ trong hệ thập phân, 111111 bộc lộ số "mười một", tuy vậy trong hệ nhị phân, này lại thể hiện tại số "ba",... Số đếm mà dãy kí hiệu biểu lộ được hotline là quý giá của nó.

Có hai nhiều loại hệ cơ số là hệ cơ số phụ thuộc vào 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à 1 hệ cơ số không dựa vào vào vị trí. Hệ đếm này gồm những kí hiệu chữ cái: I,V,X,L,C,D,M;I, V, X, L, C, D, M;I,V,X,L,C,D,M; từng kí hiệu có giá trị rứa 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=1000I=1,V=5,X=10,L=50,C=100,D=500,M=1000

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

Các hệ đếm hay được sử dụng là các hệ đếm phụ thuộc vào vị trí. Số đông số nguyên basebasebase bất kỳ có giá chỉ trị lớn hơn 111 đều hoàn toàn có thể được chọn làm cơ số cho 1 hệ đếm. Trong số hệ đếm các loại này, số lượng kí hiệu thực hiện sẽ chính bởi cơ số của hệ đếm đó, và giá trị tương ứng của các kí hiệu là: 0,1,2,...,base−10, 1, 2,..., base - 10,1,2,...,base−1. Để biểu lộ một màn biểu diễn XXX là trình diễn của số ngơi nghỉ hệ cơ số basebasebase, ta kí hiệu là XbaseX_baseXbase​.

II. Trình diễn số trong những hệ đếm

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

Trong một hệ cơ số b,b,b, mang sử số NNN tất cả biểu diễn:

dndn−1dn−2...d0,d−1d−2...d−md_nd_n-1d_n-2...d_0,d_-1d_-2...d_-mdn​dn−1​dn−2​...d0​,d−1​d−2​...d−m​

Trong đó bao gồm n+1n + 1n+1 chữ số bên trái dấu phẩy, mmm chữ số bên đề xuất dấu phẩy miêu tả cho phần nguyên với phần phân của N,N,N, cùng 0≤dib0 le d_i 0≤di​b. Khi ấy giá trị của số NNN được xem 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-1b^n-1+...+ d_0b^0+d_-1b^-1+d_-2b^-2+...+ d_-mb^-mN=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 chính là biểu diễn tương ứng của nó ở hệ cơ số 101010.

Cài đặt

Chương trình tính giá chỉ trị một vài thực NNN trong hệ cơ số bbb. Ta có thể làm cách solo giản hơn hoàn toàn như sau: Coi như số đó ko 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.

Ngôn ngữ C++:

void enter(string &N, int &b) getline(cin, N); // Nhập N ở dạng xâu. Cin >> b;// Tính quý giá của biểu 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í vết "." của N. Long long mul = (long long) pow(10, N.size() - pos - 1); // Tính quý giá từng phần, chú ý ép loại số thực. Double value = 0, power = 1; for (int i = N.size() - 1; i >= 0; --i) value += (double) (N - "0") * power; power nguồn = power nguồn * (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 nguồn = 0, 1 for d in N<::-1>: if d != ".": res += power * int(d) nguồn *= b return res / mulif __name__ == "__main__": N = "" b = 0 enter(N, b) get_value(N, b)

2. Những hệ cơ số thịnh hành trong Tin học

Trong Tin học, ngoài hệ cơ số 101010, người ta còn thực hiện hai nhiều loại hệ đếm sau:

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

3. Màn biểu diễn số nguyên với số thực

3.1. Biểu diễn số nguyên

Trong Tin học, những số nguyên có thể được màn biểu diễn dưới dạng gồm dấu hoặc ko dấu. Để biểu diễn số nguyên, ta rất có thể chọn size số nguyên là 111 byte, 222 byte, 444 byte$,...,2^N$ byte, mỗi biện pháp chọn sẽ khớp ứng với một khoảng tầm giá trị rất có thể biểu diễn.

Đối với số nguyên không âm, kích thước 2N2^N2N byte sẽ lưu trữ được các số vào phạm vi trường đoản cú 000 cho tới (28×2N−1),(2^8 imes 2^N - 1),(28×2N−1), vì chưng 111 byte tất cả 888 bit và toàn thể các bit số đông được áp dụng để biểu diễn giá trị số.

Đối cùng với số nguyên gồm dấu, bit bên buộc phải nhất của số nguyên đang được dùng để làm thể hiện vết của số đó, quy ước 111 là vệt âm, 000 là dấu dương, các bit còn sót lại sẽ dùng để làm biểu diễn quý hiếm số. Theo đó, số nguyên kích thước 2N2^N2N sẽ biểu diễn được các giá trị trong phạm vi (−28×2N−1+1)(-2^8 imes 2^N - 1 + 1)(−28×2N−1+1) cho (28×2N−1−1)(2^8 imes 2^N - 1 - 1)(28×2N−1−1). Vấn đề này sẽ liên quan tới bài toán lựa chọn kiểu dữ liệu cùng kiểm soát bộ nhớ chương trình lúc lập trình.

*

3.2. Biểu diễn số thực

Khác với biện pháp viết trong Toán học, khi nhưng mà ta dùng dấu , để chia cách giữa phần nguyên và phần phân; vào Tin học tập ta nạm dấu , bởi dấu ., và những nhóm cha chữ số cạnh nhau vẫn 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 vẫn viết là 123456.789123456.789123456.789.

Một cách biểu diễn mà máy tính xách tay sử dụng để tàng trữ số thực là dạng khoa học, khi đông đảo số thực sẽ tiến hành biểu diễn sinh hoạt dạng ±M×10±Kpm M imes 10^pm K±M×10±K. Vào đó, 0,1≤M1,M0,1 le M 0,1≤M1,M được điện thoại tư vấn là phần định trị, và KKK là một vài nguyên không âm được call là phần bậc. Ví dụ, số 123 456,789123 456,789123 456,789 sẽ tiến hành biểu diễn bên dưới dạng khoa học là 0.123456789×1060.123456789 imes 10^60.123456789×106.

4. Phân bóc tách các chữ số của một vài 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ẽ phân chia NNN cho 101010 tới lúc thương bằng 0,0,0, số lần phân tách 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

Ngôn ngữ C++:

int cnt_digits(int n) // Xét riêng trường vừa lòng 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 digitsTuy nhiên, hãy đưa sử số nguyên NNN có nnn chữ số được trình diễn ở hệ thập phân bên dưới dạng:

N=dndn−1dn−2...d1N=d_nd_n-1d_n-2...d_1N=dn​dn−1​dn−2​...d1​

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

N=dn×10n−1+dn−1×10n−2+...+d1×100N=d_n imes 10^n - 1 + d_n-1 imes10^n-2+...+d_1 imes 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_n imes 10^n-1) le log(N)=log(d_n imes 10^n - 1 + d_n-1 imes10^n-2+...+d_1 imes 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 nhì số log⁡(N)log(N)log(N) với log⁡(N)+1log(N)+1log(N)+1 chỉ gồm duy nhất một vài là ⌊log⁡(N)⌋+1leftlfloorlog(N) ight floor + 1⌊log(N)⌋+1. Vậy n=⌊log⁡(N)⌋+1n=leftlfloorlog(N) ight floor + 1n=⌊log(N)⌋+1.

Khi đó, các bạn có thể thực hiện trực tiếp hàm log10() của thư viện vào C++, hàm log() vào 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

Ngôn ngữ C++:

#include using namespace std;int cnt_digits(int N) return (int) log10(N) + 1;Ngôn ngữ Python:

import mathdef cnt_digits(N): return int(log(N)) + 1Dựa vào biểu diễn trên của số nguyên N,N,N, ta thừa nhận thấy, chữ số hàng đơn vị của N chính bởi N mod 10,N ext hack 10,N mod 10, chữ số hàng trăm bằng N mod 100,…,N ext thủ thuật 100, dots,N mod 100,…, chữ số sinh hoạt hàng lắp thêm KKK tính từ buộc phải qua trái chính bằng N mod 10KN ext gian lận 10^KN mod 10K. Đối với bất kỳ hệ cơ số nào ta cũng hoàn toàn có thể coi như vẫn ở hệ cơ số 101010 để tìm các chữ số từ bắt buộc qua trái theo phong cách này.

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

Ngôn ngữ C++:

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

# Tìm chữ số thứ K từ mặt phải sang trọng của số nguyên dương N.def find_k_digits(N, K): nguồn = 10 ** K return N % powerIII. Biến hóa giữa những hệ cơ số

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

Xét số thực NNN nghỉ ngơi hệ cơ số 101010. Để tìm màn trình diễn của NNN trong hệ cơ số bbb, ta đã lần lượt biến đổi phần nguyên cùng phần phân, kế tiếp ghép chúng lại với nhau.

1.1. Biế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-1b^n-1 + cdots + d_1b + d_0K=dn​bn+dn−1​bn−1+⋯+d1​b+d0​

Do 0≤d0b0 le d_0 0≤d0​b nên lúc chia KKK mang đến bbb thì phần dư của phép chia là d0,d_0,d0​, còn yêu quý là:

K1=dnbn+dn−1bn−1+⋯+d1K_1=d_nb^n + d_n-1b^n-1 + cdots +d_1K1​=dn​bn+dn−1​bn−1+⋯+d1​

Tương tự, d1d_1d1​ chính là phần dư của phép chia K1K_1K1​ mang lại b,b,b, và sẽ chiếm được K2K_2K2​ là thương của phép phân tách đó. Lặp lại quá trình chia như bên trên tới khi thu được thương bằng 0,0,0, lúc đó biểu diễn của KKK sống hệ cơ số bbb là dn...d0d_n...d_0dn​...d0​. Nói giải pháp khác, ta mang KKK phân chia cho b,b,b, thu nhấn thương và số dư ở các lần chia tính đến khi thương bằng 0,0,0, khi ấy viết các số dư theo sản phẩm công nghệ tự ngược từ bên dưới lên trên thì vẫn thu được màn trình diễn của KKK sinh sống hệ cơ số bbb.

Ví dụ, với K=410K=4_10K=410​ cùng b=2,b=2,b=2, quá trình thay đổi sẽ ra mắt như sau:

Chia 444 đến 222, chiếm được K1=2,d0=0K_1=2, d_0 = 0K1​=2,d0​=0.Chia 222 đến 222, chiếm được K2=1,d1=0K_2=1, d_1=0K2​=1,d1​=0.Chia 111 đến 222, nhận được K3=0,d2=1K_3=0, d_2=1K3​=0,d2​=1.Tới đây quá trình dừng lại, thu được hiệu quả 410=10024_10=100_2410​=1002​.Cài đặt

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 quý phái hệ đếm b, lưu giữ 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. Biến hóa phần phân

Xét phần phân của số thực NNN là K′K"K′. Mang sử vào 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_-1b^-1+d_-2b^-2 + cdots + d_-mb^-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) cùng với b,b,b, ta có:

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

Ta thấy, d−1d_-1d−1​ đó là phần nguyên của tác dụng phép nhân K′K"K′ cùng 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_-2b^-1+cdots+d_-mb^-(m-1) (2)K2′​=d−2​b−1+⋯+d−m​b−(m−1) (2)

Tiếp tục lặp lại phép nhân như trên với (2),(2),(2), ta đang thu được d−2d_-2d−2​ là phần nguyên. Làm tiếp tục theo phương pháp này, sau cùng thu được hàng d−1d−2d−3...,d_-1d_-2d_-3...,d−1​d−2​d−3​..., trong số đó 0≤dib0 le d_i 0≤di​b. Nói phương pháp khác, rước phần phân K′K"K′ nhân liên tục với b,b,b, ở từng bước thu dìm chữ số tại phần nguyên của hiệu quả và lặp lại quá trình nhân với phần phân của kết quả tính đến khi thu được con số chữ số như ý muốn.

Xem thêm: Soạn Bài Cách Làm Bài Văn Biểu Cảm, Văn Biểu Cảm Là Gì

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

0.123×2=0.246→d−1=00.123 imes 2 = 0.246 ightarrow d_-1=00.123×2=0.246→d−1​=0.0.246×2=0.492→d−2=00.246 imes 2 = 0.492 ightarrow d_-2=00.246×2=0.492→d−2​=0.0.492×2=0.984→d−3=00.492 imes 2 = 0.984 ightarrow d_-3=00.492×2=0.984→d−3​=0.0.984×2=1.968→d−4=10.984 imes 2 = 1.968 ightarrow d_-4=10.984×2=1.968→d−4​=1.0.968×2=1.936→d−5=10.968 imes 2 = 1.936 ightarrow d_-5=10.968×2=1.936→d−5​=1.⋯cdots⋯

Tới phía trên thu được công dụng 0.12310=0.00011...20.123_10=0.00011..._20.12310​=0.00011...2​

Cài đặt

Ngôn ngữ C++:

// chuyển phần phân K lịch sự 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 quý phái 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. Biến đổi số từ bỏ hệ cơ số xxx lịch sự hệ cơ số yyy

Để chuyển một vài NNN trường đoản cú hệ cơ số xxx sang hệ cơ số y,y,y, ta có tác dụng theo quá trình sau:

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

Cài đặt

Tái sử dụng lại một số trong những hàm đã kiến thiết sẵn ở trên: get_value(), change_integer_path(), change_double_path, ta sẽ thay đổi được số thực NNN từ hệ cơ số xxx thanh lịch hệ cơ số yyy.

Ngôn ngữ C++:

// chuyển số thực N tự hệ đếm x thanh lịch hệ đếm y, rước 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:

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. Biến hóa giữa hệ cơ số 222 (hệ nhị phân) với hệ cơ số 161616 (hệ Hexa)

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

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

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

#include 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 để chế tạo thành những 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 tiếp. String group = left_path.substr(i, 4); // Tính giá bán trị các 4 kí tự. Int power nguồn = 1, value = 0; for (int j = 3; j >= 0; --j) value += (group - "0") * power; nguồn *= 2; // lấy kí trường đoản cú hexa sở hữu giá trị tương ứng. Ans_left = ans_left + hexa; for (int i = 0; i right_path.size() - 3; ++i) string group = right_path.substr(i, 4); int nguồn = 1, value = 0; for (int j = 3; j >= 0; --j) value += (group - "0") * power; power *= 2; ans_right = ans_right + hexa; 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 # bổ sung đủ chữ số 0 để tạo ra thành những 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 nhiều 4 kí tự liên tiếp group = left_path # Tính giá bán trị nhiều 4 kí tự. Power, value = 1, 0 for j in range(3, -1, -1): value += int(group) * power nguồn power *= 2 # rước kí từ bỏ hexa mang giá trị tương ứng. Ans_left = ans_left + hexa for i in range(0, len(right_path)-3, 4): group = right_path power, value = 1, 0 for j in range(3, -1, -1): value += int(group) * power power *= 2 ans_right = ans_right + hexa return ans_left + "." + ans_rightỞ chiều hướng ngược lại, khi chuyển từ hệ nhị phân quý phái hệ hexa, họ chỉ đề nghị đổi từng kí trường đoản cú hexa quý phái cụm tứ kí từ nhị phân có giá trị tương ứng. Ta có thể đối kháng giản hóa bằng cách khởi tạo trước một mảng binary_code extbinary\_codebinary_code gồm 151515 phần tử, với nghĩa nghĩa binary_code extbinary\_codebinary_code 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 giữ ý rằng, với i>10i > 10i>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 quý phái hệ nhị phân

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 && NN "9") res += binary_code - "0">; else if ("A" NN && NN "F") int pos = NN - 55; res += binary; 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 and nn "9": res += binary_code - "0"> elif "A" nn và nn "F": pos = nn - 55 res += binary_code return resIV. Việc minh họa

1. Số nhị phân sản phẩm K

Đề bài

Xét những số nhị phân bao gồm độ dài NNN cùng với số nhỏ bé nhất là 100…0‾overline100…0100…0 (N−1N-1N−1 chữ số 000) cùng số lớn nhất là 111…1‾overline111…1111…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ới 111111111.

Yêu cầu: mang lại trước nhì số nguyên dương NNN cùng KKK. Hãy khẳng định số nhị phân vật dụng KKK trong dãy số nhị phân tất cả độ nhiều năm N?N?N?

Input:

Một dòng duy nhất cất 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 vật dụng KKK tìm kiếm được.

Sample Input:

3 3Sample Output:

110

Ý tưởng

Trong hàng nhị phân có độ lâu năm N,N,N, số nhỏ nhắn nhất là: 100…0‾overline100…0100…0 (N−1N - 1N−1 chữ số 000). Số này có giá trị tương xứng trong hệ thập phân đó là 2N−12^N - 12N−1. Mong mỏi lấy số sản phẩm công nghệ K,K,K, ta chỉ cần cộng thêm K−1K - 1K−1 đơn vị chức năng vào số bé nhỏ nhất đó, cơ mà nếu như triển khai cộng nghỉ ngơi hệ nhị phân thì sẽ khá phức tạp. Vị đó, ta rất có thể lấy luôn giá trị 2N−1+(K−1)2^N - 1 + (K - 1)2N−1+(K−1) nghỉ ngơi hệ thập phân của số nhị phân lắp thêm K,K,K, rồi đổi ngược lại hệ nhị phân, công dụng vẫn sẽ hoàn toàn chính xác.

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

Code mẫu

#include #define int long longusing 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; nguồn /= 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. Màn trình diễn nhị phân

Đề bài

Mọi số nguyên dương XXX đều có thể biểu diễn trong hệ nhị phân tương tự như như biểu 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 bởi vì 17=1×24+117=1×2^4+117=1×24+1.

Yêu cầu: đến 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 biểu diễn nhị phân của số XXX.Tìm số YYY lớn nhất trong hệ thập phân làm thế nào để cho biểu diễn nhị phân của YYY nhận được từ XXX bằng phương pháp hoán vị vòng quanh những chữ số trong biểu diễn nhị phân của XXX.

Input:

Gồm một trong những nguyên dương XXX duy nhất.

Ràng buộc:

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

Output:

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

Sample Input:

17Sample Output:

1000124Giải thích:

Ta gồm 17=1×24+1,17=1×2^4+1,17=1×24+1, cho nên vì vậy biểu diễn nhị phân của 171717 là 100011000110001.

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

Ý tưởng

Đối cùng với yêu ước thứ nhất, ta cần sử dụng thuật toán biến đổi từ hệ cơ số 101010 sang hệ nhị phân thông thường, không có gì đặc biệt. Tiếp nối lưu công dụng thu được vào một xâu sss.

Đối cùng với yêu cầu thứ hai, trước tiên chúng ta cần nắm rõ thế làm sao là hoán vị vòng quanh? cũng chính vì có rất đa số chúng ta ở bài bác này đã lầm tưởng công dụng là đảo tổng thể số 111 lên trước, số 000 về cuối. Mặc dù nhiên, ta chỉ được phép xét những hoán vị vòng quanh của xâu nhị phân s,s,s, có nghĩa là cứ hòn đả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ứ chưa hẳn hoán vị lộn xộn toàn bộ các chữ số. Như vậy, giả dụ xâu nhị phân bao gồm độ lâu năm nnn thì ta sẽ có nnn thiến vòng quanh.

Để xét các hoán vị vòng quanh, ta thực hiện một kinh nghiệm nhỏ, sẽ là nhân song xâu. Chẳng hạn, xâu 110011 sẽ vươn lên là 110011110011. Gọi nnn là độ lâu năm của xâu nhị phân cũ, ta xét từng địa điểm i (0≤in),i (0 le i i (0≤in), thì một xâu bé độ nhiều năm nnn ban đầu từ địa điểm iii sẽ là một trong hoán vị vòng quanh. Sau đó, với mỗi thiến này ta chỉ việc đổi nó sang hệ thập phân lại, rồi lấy tác dụng lớn tốt nhất là xong.

Xem thêm: Thuyết Minh Về Chợ Nổi Cái Răng Cần Thơ, Thuyết Minh Về Chợ Nổi Cái Răng

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

Code mẫu

#include #define int long longusing 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 quý hiếm 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 - "0") * exp; exp *= 2; return res;/** * Hàm đo lường hai yêu ước của đề bài. * Yêu mong thứ nhất: Đưa ra màn biểu diễn nhị phân của số X -> dùng hàm dec_to_bin(). * Yêu mong thứ hai: Ta xét đầy đủ hoán vị vòng xung quanh của xâu nhị phân s (là màn biểu diễn của x), kế tiếp tìm quý giá thập phân lớn nhất trong tất cả các thiến vòng quanh đó. Phương pháp xây dựng thiến vòng quanh là gấp hai xâu lên, rồi xét phần nhiều xâu độ lâu năm n (n là độ dài xâu np ban đầu) bắt đầu từ địa điểm i (0 void solution(int x) string circular_per = dec_to_bin(x); // xong yêu ước thứ nhất: In ra màn trình diễn nhị phân của x. Cout circular_per endl; // bắt đầu yêu ước thứ hai, ta nhân song xâu nhị phân lên để triển khai tìm những 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;V. Tài liệu tham khảo