avatar

I. Giới thiệu chung

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

Có thật nhiều hệ cơ số không giống nhau, từng hệ cơ số sở hữu những quy tắc màn trình diễn số không giống nhau. Những sản phẩm kí hiệu kiểu như nhau rất có thể tiếp tục ứng với những số không giống nhau trong số hệ kiểm đếm không giống nhau. Ví dụ nhập hệ thập phân, thể hiện nay số "mười một", song nhập hệ nhị phân, này lại thể hiện nay số "ba",... Số kiểm đếm nhưng mà sản phẩm kí hiệu thể hiện nay được gọi là độ quý hiếm của chính nó.

Có nhị loại hệ cơ số là hệ cơ số tùy theo địa điểm và hệ cơ số ko tùy theo địa điểm. Chẳng hạn, hệ kiểm đếm La Mã là 1 trong hệ cơ số ko tùy theo địa điểm. Hệ kiểm đếm này bao gồm những kí hiệu chữ cái: từng kí hiệu có mức giá trị cụ thể:

Trong hệ kiểm đếm này, độ quý hiếm của những kí hiệu ko tùy theo địa điểm của chính nó. Ví dụ, nhập nhị màn trình diễn và thì đều sở hữu độ quý hiếm là .

Các hệ kiểm đếm thông thường sử dụng là những hệ kiểm đếm dựa vào địa điểm. Mọi số vẹn toàn ngẫu nhiên có mức giá trị to hơn đều rất có thể được lựa chọn thực hiện cơ số cho 1 hệ kiểm đếm. Trong những hệ kiểm đếm loại này, con số kí hiệu dùng tiếp tục chủ yếu vì như thế cơ số của hệ kiểm đếm cơ, và độ quý hiếm ứng của những kí hiệu là: . Để thể hiện nay một màn trình diễn là màn trình diễn của số ở hệ cơ số tớ kí hiệu là .

II. Biểu biểu diễn số trong số hệ đếm

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

Trong một hệ cơ số fake sử số sở hữu biểu diễn:

Trong cơ sở hữu chữ số phía bên trái vết phẩy, chữ số phía bên phải vết phẩy thể hiện nay cho tới phần vẹn toàn và phần phân của và . Khi cơ độ quý hiếm của số được xem theo gót công thức:

Giá trị của một trong những nhập hệ cơ số cũng đó là màn trình diễn ứng của chính nó ở hệ cơ số .

Cài đặt

Chương trình tính độ quý hiếm một trong những thực nhập hệ cơ số . Ta có thể làm cách đơn giản hơn hẳn như sau: Coi như số đó ko có phần phân, tính giá trị của nó nhập hệ cơ số rồi phân chia cho tới với là số chữ số phần phân của số ban sơ.

Để đơn giản và giản dị rộng lớn, nhập setup này tớ tiếp tục bịa ở loại chuỗi kí tự động. Nếu như chỉ quy đổi số vẹn toàn thì tùy nằm trong nhập buộc ràng tớ tiếp tục dùng loại tài liệu tương thích.

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ý hiếm của màn trình diễn N nhập 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 địa điểm vết '.' của N.
    long long mul = (long long) pow(b, N.size() - pos - 1);

    // Tính độ quý hiếm toàn cỗ số N, coi như không tồn tại phần phân.
    double value = 0, power = 1;
    for (int i = N.size() - 1; i >= 0; --i)
        if (N[i] != '.')
        {
            value += (double) (N[i] - '0') * power;
            power = power * (double) b;
        }

    // Kết trái khoáy là lấy độ quý hiếm đang được tính phân chia cho tới b^x với x là số chữ số phần phân.
    return value / mul;
}

main()
{
    string N;
    int b;

    enter(N, b);
    solution(N, b);

    return 0;
}

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 thườn nhập Tin học

Trong Tin học tập, ngoài hệ cơ số người tớ còn dùng nhị loại hệ kiểm đếm sau:

  • Hệ cơ số (Hệ nhị phân): Chỉ dùng nhị kí hiệu và . Lấy ví dụ, .
  • Hệ cơ số (Hệ thập lục phân hoặc hệ Hexa): Sử dụng những chữ số kể từ cho tới và vần âm nhập cơ có mức giá trị thứu tự là . Lấy ví dụ, .

3. Biểu biểu diễn số vẹn toàn và số thực

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

Trong Tin học tập, những số vẹn toàn rất có thể được màn trình diễn bên dưới dạng sở hữu vết hoặc ko vết. Để màn trình diễn số vẹn toàn, tớ rất có thể lựa chọn độ cao thấp số vẹn toàn là byte, byte, byte, byte, từng cơ hội lựa chọn tiếp tục ứng với 1 khoảng chừng độ quý hiếm rất có thể màn trình diễn.

Đối với số vẹn toàn ko âm, độ cao thấp byte tiếp tục tàng trữ được những số nhập phạm vi kể từ cho tới vì như thế byte bao gồm bit và toàn cỗ những bit đều được dùng nhằm màn trình diễn độ quý hiếm số.

Đối với số vẹn toàn sở hữu vết, bit phía bên phải nhất của số vẹn toàn sẽ tiến hành dùng để làm thể hiện nay vết của số cơ, quy ước là vết âm, là vết dương, những bit còn sót lại tiếp tục dùng để làm màn trình diễn độ quý hiếm số. Theo cơ, số vẹn toàn độ cao thấp tiếp tục màn trình diễn được những độ quý hiếm nhập phạm vi cho tới . việc này tiếp tục tương quan cho tới việc lựa lựa chọn kiểu dữ liệu và trấn áp bộ nhớ lưu trữ lịch trình Khi thiết kế.

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

Khác với cơ hội viết lách nhập Toán học tập, Khi nhưng mà tớ sử dụng vết , nhằm ngăn cơ hội thân thiết phần vẹn toàn và phần phân; nhập Tin học tập tớ thay cho vết , vì như thế vết ., và những group tía chữ số cạnh nhau tiếp tục viết lách ngay tắp lự. Ví dụ, nhập toán tớ viết lách thì nhập Tin học tập tiếp tục viết lách là .

Một cơ hội màn trình diễn nhưng mà PC dùng nhằm tàng trữ số thực là dạng khoa học tập, Khi từng số thực sẽ tiến hành màn trình diễn ở dạng . Trong số đó, được gọi là phần toan trị, và là một trong những vẹn toàn ko âm được gọi là phần bậc. Ví dụ, số sẽ tiến hành màn trình diễn bên dưới dạng khoa học là .

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

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

Cài để 1: Đếm số chữ số của số vẹn toàn dương theo gót cách thủ công

Ngôn ngữ C++:

int cnt_digits(int n)
{
    // Xét riêng biệt tình huố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 digits

Tuy nhiên, hãy fake sử số vẹn toàn sở hữu chữ số được màn trình diễn ở hệ thập phân bên dưới dạng:

Phân tích kết cấu số của tớ có:

.

.

Giữa nhị số và chỉ mất độc nhất một trong những là . Vậy .

Khi đó, các quý khách hàng có thể dùng thẳng hàm log10() của tủ sách <cmath> nhập C++, hàm log() nhập thư viện math của Python để đếm số chữ số của .

Cài để 2: Đếm số chữ số của số vẹn toàn dương bằng hàm log

Ngôn ngữ C++:

#include <cmath>

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 nhập màn trình diễn bên trên của số vẹn toàn tớ nhận biết, chữ số sản phẩm đơn vị chức năng của chủ yếu vì như thế chữ số hàng trăm vì như thế chữ số ở sản phẩm loại tính kể từ cần qua loa trái khoáy chủ yếu vì như thế . Đối với ngẫu nhiên hệ cơ số này tớ cũng rất có thể coi như đang được ở hệ cơ số nhằm lần những chữ số kể từ cần qua loa trái khoáy Theo phong cách này.

Cài để 3: Xác định chữ số thứ từ mặt mày phải lịch sự của số vẹn toàn dương

Ngôn ngữ C++:

// Tìm chữ số thứ K từ mặt mày phải lịch sự của số vẹn toàn dương N.
int find_k_digits(int N, int K)
{
    int power = (int) pow(10, K - 1);

    return N / power % 10;
}

Ngôn ngữ Python:

# Tìm chữ số thứ K từ mặt mày phải lịch sự của số vẹn toàn dương N.
def find_k_digits(N, K):
    power = 10 ** (K - 1)

    return N / power % 10

III. Chuyển thay đổi trong số những hệ cơ số

1. Chuyển thay đổi kể từ hệ cơ số lịch sự những hệ cơ số khác

Xét số thực ở hệ cơ số . Để lần màn trình diễn của nhập hệ cơ số tớ tiếp tục thứu tự quy đổi phần vẹn toàn và phần phân, tiếp sau đó ghép bọn chúng lại cùng nhau.

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

Xét phần vẹn toàn của là . Giả sử nhập hệ kiểm đếm có mức giá trị là:

Do nên những khi phân chia cho tới thì phần dư của quy tắc phân chia là còn thương là:

Tương tự động, đó là phần dư của quy tắc phân chia cho tới và tiếp tục nhận được là thương của quy tắc phân chia cơ. Lặp lại quy trình phân chia như bên trên cho tới Khi nhận được thương vì như thế Khi cơ màn trình diễn của ở hệ cơ số là . Nói cách tiếp theo, tớ lấy phân chia cho tới tiếp thu thương và số dư ở từng phen phân chia cho đến Khi thương vì như thế Khi cơ viết lách những số dư theo gót trật tự ngược kể từ bên dưới lên bên trên thì tiếp tục nhận được màn trình diễn của ở hệ cơ số .

Ví dụ, với và quy trình quy đổi tiếp tục ra mắt như sau:

  • Chia cho tới nhận được .
  • Chia cho tới nhận được .
  • Chia cho tới nhận được .
  • Tới trên đây quy trình tạm dừng, nhận được thành quả .

Cài đặt

Ngôn ngữ C++:

// Chuyển phần vẹn toàn K của số N lịch sự hệ kiểm đếm b, lưu nhập 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 vẹn toàn K của số N lịch sự 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 thay đổi phần phân

Xét phần phân của số thực là . Giả sử nhập hệ kiểm đếm có mức giá trị là:

Nhân cả vế của với tớ có:

Ta thấy, đó là phần vẹn toàn của thành quả quy tắc nhân với còn phần phân của thành quả là:

Tiếp tục tái diễn quy tắc nhân như bên trên với tớ tiếp tục nhận được là phần vẹn toàn. Làm liên tiếp Theo phong cách này, sau cuối nhận được sản phẩm nhập cơ . Nói cách tiếp theo, lấy phần phân nhân liên tiếp với ở từng bước tiếp thu chữ số ở đoạn vẹn toàn của thành quả và tái diễn quy trình nhân với phần phân của thành quả cho đến Khi nhận được con số chữ số như mong muốn mong muốn.

Ví dụ, với và cần thiết lấy cho tới chữ số phần phân ở thành quả, tớ thực hiện như sau:

  • .
  • .
  • .
  • .
  • .

Tới trên đây nhận được thành quả

Cài đặt

Ngôn ngữ C++:

// Chuyển phần phân K lịch sự hệ kiểm đế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 lịch sự 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 thay đổi số kể từ hệ cơ số lịch sự hệ cơ số

Để gửi một trong những kể từ hệ cơ số lịch sự hệ cơ số tớ tuân theo công việc sau:

  • Bước : Tính độ quý hiếm của số nhập hệ cơ số trình bày cách tiếp theo là gửi lịch sự hệ cơ số .
  • Bước : Chuyển thành quả vừa phải tìm ra lịch sự hệ cơ số theo gót cách thức gửi một trong những ở hệ lịch sự hệ ở đoạn .

Cài đặt

Tái sử dụng lại một trong những hàm đang được kiến thiết sẵn ở trên: get_value(), change_integer_path(), change_double_path, tớ tiếp tục quy đổi được số thực kể từ hệ cơ số lịch sự hệ cơ số .

Ngôn ngữ C++:

// Chuyển số thực N kể từ hệ kiểm đếm x lịch sự hệ kiểm đếm hắn, lấy d chữ số sau vết 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. Chuyển thay đổi thân thiết hệ cơ số (hệ nhị phân) và hệ cơ số (hệ Hexa)

Do là lũy quá của cho nên việc quy đổi thân thiết hệ nhị phân và hệ hexa rất có thể được triển khai dễ dàng và đơn giản theo gót quy tắc sau:

  • Bước : Tính từ vựng trí phân cơ hội phần vẹn toàn và phần phân, tớ gộp những chữ số trở nên từng group chữ số về nhị phía trái khoáy cần, nếu như thiếu thốn chữ số tiếp tục chứ không những chữ số .
  • Bước :Tính độ quý hiếm của từng group chữ số, tiếp sau đó thay cho thành quả vì như thế một kí hiệu ứng ở hệ Hexa. Ví dụ ứng với ứng với ...
  • Bước : Đặt những kí hiệu sau khoản thời gian đang được quy đổi nhập trúng trật tự của từng group, tớ nhận được thành quả quy đổi.

Cài bịa 1: Chuyển đổi từ hệ nhị phân lịch sự hệ Hexa

#include <bits/stdc++.h>

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 đầy đủ chữ số 0 muốn tạo trở nên những group 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ự động tiếp tục.
        string group = left_path.substr(i, 4);

        // Tính độ quý hiếm cụm 4 kí tự động.
        int power = 1, value = 0;
        for (int j = 3; j >= 0; --j)
        {
            value += (group[j] - '0') * power;
            power *= 2;
        }

        // Lấy kí tự động hexa đem độ quý hiếm ứ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 đầy đủ chữ số 0 muốn tạo trở nên những group 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ự động liên tiếp
        group = left_path[i:i+4]
        
        # Tính độ quý hiếm cụm 4 kí tự động.
        power, value = 1, 0
        for j in range(3, -1, -1):
            value += int(group[j]) * power
            power *= 2
        
        # Lấy kí tự động hexa đem độ quý hiếm ứ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 ngược lại, Khi gửi kể từ hệ nhị phân lịch sự hệ hexa, tất cả chúng ta chỉ việc thay đổi từng kí tự động hexa lịch sự cụm tứ kí tự động nhị phân có mức giá trị ứng. Ta có thể đơn giản hóa bằng cách khởi tạo trước một mảng gồm phần tử, với nghĩa nghĩa là biểu diễn nhị phân tương ứng với kí tự Hexe . Lưu ý rằng, với thì sẽ tương ứng với các kí tự A, B, C, D, E, F nên tớ cần xử lý tinh ranh tế để biết được kí tự chữ cái tương ứng với bằng từng nào.

Cài để 2: Chuyển đổi từ hệ Hexa lịch sự 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[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

IV. Bài toán minh họa

1. Số nhị phân loại K

Đề bài

Xét những số nhị phân có tính nhiều năm với số bé xíu nhất là ( chữ số ) và số lớn số 1 là ( chữ số ). Ví dụ với tớ sở hữu những số nhị phân phỏng nhiều năm 3 là và .

Yêu cầu: Cho trước nhị số vẹn toàn dương và . Hãy xác lập số nhị phân loại nhập sản phẩm số nhị phân có tính nhiều năm

Input:

  • Một dòng sản phẩm độc nhất chứa chấp nhị số vẹn toàn dương và .

Ràng buộc:

  • .
  • .

Output:

  • Số nhị phân loại tìm ra.

Sample Input:

3 3

Sample Output:

110

Ý tưởng

Trong sản phẩm nhị phân có tính nhiều năm số bé xíu nhất là: ( chữ số ). Số này còn có độ quý hiếm ứng nhập hệ thập phân đó là . Muốn lấy số loại tớ chỉ việc thêm vào đó đơn vị chức năng nhập số bé xíu nhất cơ, tuy nhiên nếu mà tổ chức nằm trong ở hệ nhị phân thì sẽ rất phức tạp. Do cơ, tớ rất có thể lấy luôn luôn độ quý hiếm ở hệ thập phân của số nhị phân loại rồi thay đổi ngược lại hệ nhị phân, thành quả vẫn tiếp tục trọn vẹn đúng mực.

Độ phức tạp: .

Code mẫu

#include <bits/stdc++.h>
#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. Biểu biểu diễn nhị phân

Đề bài

Mọi số vẹn toàn dương đều rất có thể màn trình diễn nhập hệ nhị phân tương tự động như màn trình diễn nhập hệ thập phân. Chẳng hạn, số sở hữu màn trình diễn nhị phân là vì như thế .

Yêu cầu: Cho trước một trong những vẹn toàn dương . Hãy triển khai những đòi hỏi sau:

  • Tìm màn trình diễn nhị phân của số .
  • Tìm số lớn số 1 nhập hệ thập phân sao cho tới màn trình diễn nhị phân của nhận được kể từ bằng phương pháp thiến vòng xung quanh những chữ số nhập màn trình diễn nhị phân của .

Input:

  • Gồm một trong những vẹn toàn dương độc nhất.

Ràng buộc:

  • .

Output:

  • Dòng loại nhất ghi màn trình diễn nhị phân của .
  • Dòng loại nhị ghi số tìm ra.

Sample Input:

17

Sample Output:

10001
24

Giải thích:

Ta sở hữu bởi vậy màn trình diễn nhị phân của là .

Số nhị phân có mức giá trị lớn số 1 nhận được kể từ Khi thiến vòng xung quanh những chữ số nhập màn trình diễn nhị phân của là . Số cơ có mức giá trị thập phân là .

Ý tưởng

Đối với đòi hỏi loại nhất, tớ sử dụng thuật toán quy đổi kể từ hệ cơ số lịch sự hệ nhị phân thường thì, không tồn tại gì đặc biệt quan trọng. Sau cơ lưu thành quả nhận được vào trong 1 xâu .

Đối với đòi hỏi loại nhị, trước tiên chúng ta cần thiết làm rõ thế này là hoán vị vòng quanh? Bởi vì như thế sở hữu thật nhiều các bạn ở bài xích này tiếp tục lầm tưởng thành quả là hòn đảo toàn cỗ số lên trước, số về cuối. Tuy nhiên, tớ chỉ được quy tắc xét những hoán vị vòng quanh của xâu nhị phân tức là cứ hòn đảo một chữ số kể từ bên trên đầu xuống cuối thì tớ được một thiến vòng xung quanh, chứ không hề cần thiến lộn xộn toàn bộ những chữ số. Như vậy, nếu như xâu nhị phân có tính nhiều năm thì tớ sẽ có được thiến vòng xung quanh.

Để xét những thiến vòng xung quanh, tớ dùng một kinh nghiệm nhỏ, này là nhân song xâu. Chẳng hạn, xâu 110011 tiếp tục trở nên 110011110011. Gọi là phỏng nhiều năm của xâu nhị phân cũ, tớ xét từng địa điểm thì một xâu con cái phỏng nhiều năm chính thức từ vựng trí tiếp tục là 1 trong thiến vòng xung quanh. Sau cơ, với từng thiến này tớ chỉ việc thay đổi nó lịch sự hệ thập phân lại, rồi lấy thành quả lớn số 1 là hoàn thành.

Độ phức tạp: với là phỏng nhiều năm xâu nhị phân .

Code mẫu

#include <bits/stdc++.h>
#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 độ 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[i] - '0') * exp;
        exp *= 2;
    }

    return res;
}

/**
  * Hàm đo lường nhị đòi hỏi của đề bài xích.
  * Yêu cầu loại nhất: Đưa đi ra màn trình diễn nhị phân của số X -> Dùng hàm dec_to_bin().
  * Yêu cầu loại hai: Ta xét từng thiến vòng xung quanh của xâu nhị phân s (là màn trình diễn của x), tiếp sau đó lần giá bán trị
    thập phân lớn số 1 nhập toàn bộ những thiến vòng xung quanh cơ. Phương pháp kiến thiết thiến vòng xung quanh là gấp
    song xâu lên, rồi xét từng xâu phỏng nhiều năm n (n là phỏng nhiều năm xâu np ban đầu) chính thức từ vựng trí i (0 <= i < n).
*/
void solution(int x)
{
    string circular_per = dec_to_bin(x);

    // Kết thúc giục đòi hỏi loại nhất: In đi ra màn trình diễn nhị phân của x.
    cout << circular_per << endl; 

    // Bắt đầu đòi hỏi loại nhị, tớ nhân song xâu nhị phân lên nhằm tổ chức lần những thiến vòng xung 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