Binary to Decimal Conversion using Divide-and-conq

问题:

I am currently stuck on an assignment and have looked nearly everywhere for even a hint at what I am trying to do.

The assignment is simple, we are to be given a binary number in the form of a vector (e.g. [1,1,1,1] and we are to compute the decimal form of this number and put in back into the same vector form (e.g. [1,5] for the answer to the previous example).

While at first I thought this would have an easy solution, I soon found that we are to use this method to calculate extremely large numbers such as 300 1's in binary.

Now after I realized my mistake of trying to straight up calculate it, I soon found the "divide-and-conquer" method idea but I did not find a single place that gave a precise example of how to use it in this context.

Since this is an assignment, I would rather an answer be proposed that actually explains the concept and provides examples rather than a straight up block of code.

Thank you in advance,

Matthew

回答1:

Write a base 10 math engine.

It should include addition by another base 10 number, and multiplication by int. (well doubling is enough)

Iterate over the binary digits, keeping track of a base 10 number that corresponds to the digit.

Conditionally accumulate.

The only hard part is the base 10 math system, everything else takes 3 to 8 lines of code.

Sadly, there is very limited easy ways to do thus more efficiently, as any digit of a binary number can influence any digit of the equivalent base 10 number. There may be fancy ways, but for 300 digits you should not bother.

回答2:

Following is the solution to your problem:

#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;
}

The names are self explanatory. here are the steps performed:

1. Take the string as input
2. Reverse the string using the std library function coz the processing starts from the right side i.e. unit digit in the number.
3. Initialize the power and counter to 0
4. the formula for converting 1110 to decimal: (1)*2*2*2 + (1)*2*2 + (1)*2 + (0)*1 = 14
5. iterate the characters of string one by one; if the character is 1 calculate the 2^power and add to counter. if it is 0 then ignore
6. increment the power by 1
7. convert the counter, which is the answer, to string
8. Write the Accumulate() yourself.