Преобразование из двоичной системы в десятичную с использованием функции "разделяй и властвуй"

Question

В настоящее время я застрял на задании и почти везде искал намек на то, что я пытаюсь сделать.

Назначение простое, нам нужно дать двоичное число в виде вектора (например, [1,1,1,1], и мы должны вычислить десятичную форму этого числа и вернуть обратно в ту же векторную форму (например, [1,5] для ответа на предыдущий пример).

Хотя сначала я думал, что это будет простое решение, я вскоре обнаружил, что мы должны использовать этот метод для вычисления чрезвычайно больших чисел, таких как 300 1 в двоичном виде.

Теперь, после того, как я осознал свою ошибку, пытаясь вычислить его прямо, я вскоре нашел идею метода "разделяй и властвуй", но я не нашел ни одного места, которое дало бы точный пример того, как использовать его в этом контексте.

Поскольку это задание, я бы предпочел, чтобы был предложен ответ, который фактически объясняет концепцию и дает примеры, а не простой блок кода.

Заранее спасибо,

Мэтью

Answer 1

Напишите базовый 10 математический движок.

Он должен включать в себя добавление еще одного базового числа 10 и умножение на int, (вполне достаточно удвоения)

Перебирайте двоичные цифры, отслеживая базовое число 10, соответствующее этой цифре.

Условно накапливать.

Единственная сложная часть - базовая математическая система, все остальное занимает от 3 до 8 строк кода.

К сожалению, есть очень ограниченные простые способы сделать это более эффективно, так как любая цифра двоичного числа может влиять на любую цифру эквивалентного базового числа 10. Там могут быть причудливые способы, но за 300 цифр вам не стоит беспокоиться.

Answer 2

Ниже приведено решение вашей проблемы:

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

string Reverse(string input){
    string copy(input);
    reverse(copy.begin(), copy.end());
    return copy;
}


string Accumulate(vector<double> vNumbers){
    // Do some processign here to add these doubles
    return string("");
}

string Convert(string input){
    input = Reverse(input);
    int power =0;
    vector<double> vNumbers;

    for(string::iterator it=input.begin();it!=input.end();it++){
         if(*it=='1')
             vNumbers.push_back(pow(2, power));
         power++;
    }


    return Accumulate(vNumbers);
}


void main(){
 string s = "0110 0010 0010 1000 0000 1011 0110 1111 0010 0000 1101 1101 0101 0010 0011 0111 0001 0001 0010 0100 1110 0110 0010 0010 1000 0000 1011 0110 1111 0010 0000 1101 1101 0101 0010 0011 0111 0001 0001";

 cout << "input:" << s.c_str() << endl;
 cout << "Output:" << Convert(s).c_str() << endl;
}

Имена говорят сами за себя. Вот шаги, выполненные:

1. Возьмите строку в качестве ввода
2. Переверните строку, используя библиотечную функцию std, потому что обработка начинается с правой стороны, т. Е. Единичная цифра в числе.
3. Инициализируйте мощность и счетчик на 0
4. формула для преобразования 1110 в десятичное число: (1)*2*2*2 + (1)*2*2 + (1)*2 + (0)*1 = 14
5. повторяйте символы строки один за другим; если символ равен 1, вычислите мощность 2 ^ и добавьте к счетчику. если это 0, то игнорировать
6. увеличить мощность на 1
7. преобразовать счетчик, который является ответом, в строку
8. Напишите Accumulate() самостоятельно.