Các hệ đếm trong tin học
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ố và 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ệ đếm1. 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_-mdndn−1dn−2...d0,d−1d−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≤dib. 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=dnbn+dn−1bn−1+...+d0b0+d−1b−1+d−2b−2+...+d−mb−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=dndn−1dn−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=dnbn+dn−1bn−1+⋯+d1b+d0
Do 0≤d0b0 le d_0 0≤d0b 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=dnbn+dn−1bn−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 đặtNgô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−1b−1+d−2b−2+⋯+d−mb−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−2b−1+⋯+d−mb−(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−2b−1+⋯+d−mb−(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−1d−2d−3..., trong số đó 0≤dib0 le d_i 0≤dib. 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 đặtNgô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
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
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
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_code1. 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