Как умножить std :: vector <int>на int, где каждый элемент вектора должен быть равен di git? - PullRequest
Новая
       56

Как умножить std :: vector <int>на int, где каждый элемент вектора должен быть равен di git?

0 голосов
/ 22 апреля 2020

У меня есть класс, назовите его 'BigNumber', у которого есть поле вектора v.
Каждый элемент должен быть одним ди git.
Я хочу реализовать метод для умножения этого вектора на целое число , но также сохраняют элементы один di git.
Например: <7,6> * 50 = <3,8,0,0>
Вектор представляет число, сохраненное таким образом.
В моем примере <7,6> равно 76, а <3,8,0,0> - 3800.
Я пробовал следующее, но это не очень хорошо (хотя это работает), а не фактическое решение проблемы. 

   //int num, BigNumber bn
    if (num > 0)
  {
    int value = 0, curr = 1;
    for (int i = bn.getBigNumber().size() - 1; i >= 0; i--)
    {
      value += bn.getBigNumber().at(i) * num * curr;
      curr *= 10;
    }
    bn.setBigNumber(value); //this shouldn't be here
    return bn;
  }

Ожидаемый алгоритм - это умножение самого вектора, а не переменной, которую я конвертирую в этот BigNumber.

Способ, которым я устанавливаю Integer в BigNumber: 

void BigNumber::setBigNumber(int num)
{
  if (num > 0)
  {
    bigNum.clear();
    while (num != 0)
    {
      bigNum.push_back(num % 10);
      num = (num - (num % 10)) / 10;
    }
    std::reverse(bigNum.begin(), bigNum.end());
  }
  else
  {
    throw TOOSMALL;
  }
};

Метод, который я хочу реализовать: 

//class BigNumber{private: vector<int> bigNum; ... }
void BigNumber::multiplyBigNumber(BigNumber bn, int num)
{
  if (num > 0)
  {
    //bn.bigNum * num
  }
  else
  {
    throw TOOSMALL;
  }
}

Ответы [ 2 ]

1 голос
/ 22 апреля 2020

Так как это для школьного проекта, я не хочу просто писать код для вас. Итак, вот подсказка.

Допустим, вы даете мне число 1234 --- и я выбираю для хранения каждый ди git в векторе в обратном порядке . Итак, теперь у меня есть bignum = [4, 3, 2, 1].

Теперь вы просите меня умножить это на 5. Итак, я создаю новый пустой векторный результат = []. Я смотрю на первый пункт в Bignum. Это 4.

4 * 5 - это 20, или (как вы делаете в школе) это 0 для переноса 2. Таким образом, я помещаю * 026 в результат, давая результат = [0] и продолжаю = 2.

Вопросы для вас:

  1. Если бы вы делали это вручную (на бумаге), что бы вы делали дальше?
  2. Почему я решил хранить цифры в обратном порядке?
  3. Почему я решил использовать новый вектор (результат), а не модифицировать bignum?

и только после того, как вы выработали способ умножить bignum на int:

Как бы вы умножили два бигнума вместе?
0 голосов
/ 25 апреля 2020

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

BigNumber BigNumber::multiplyBigNumber(BigNumber bn, int num){
    if (num > 0)
  {
    std::vector<int> result;
    std::vector<int> rev = bn.getBigNumber();
    std::reverse(rev.begin(),rev.end());
    int carry = 0;
    for(int i = 0; i<rev.size(); i++){
        result.push_back((rev[i] * num + carry) % 10);
        carry = (rev[i] * num + carry) / 10;
        if(i == rev.size()-1 && carry / 10 == 0 && carry % 10 != 0 ) {
                result.push_back(carry);
                carry = carry / 10;
        }
    }
    while((carry / 10) != 0){
        result.push_back(carry % 10);
        carry /= 10;
        if(carry / 10 == 0) result.push_back(carry);
    }
    std::reverse(result.begin(),result.end());
    bn.setBigNumber(result);
    return bn;
  }else{
    throw TOOSMALL;
  }
}
...