Добавление значений двух отдельных векторов с разными размерами?

Question

Мне интересно, как я мог бы добавить значения двух векторов, например, так:

vector<int> v1 = {3, 1, 7};
vector<int> v2 = {6, 5};
vector<int> v3 = {3, 8, 2}; // The sum of v1 and v2

Результат здесь должен быть 382, ​​а 317 + 65 дает 382.

Есть ли способ сделать это? Размеры векторов довольно хитры. Например, 2-й элемент в v1 равен 1, а 2-й элемент в v2 равен 5. Однако к 7 нужно добавить 5, а не 1.

edit: Forgot to Отметим, что векторы могут быть бесконечно длинными. Приведение к int, а затем обратно к вектору может привести к потере чисел.

Answer 1

Вот простой подход, который я разработал для требуемых условий: (с учетом векторов v1 и v2, типа данных DT)

• Разница в размере: В случаях, когда векторы имеют неравные размеры, вы можете просто добавить 0 в конце, используя std::vector<>::insert(iterator, 0) с итератором в начале, так как для правильного сложения элемента к элементу вам понадобятся нули в начале. Перед этим проверьте, какой из двух векторов больше по размеру, соберите разницу и вставьте для того же количества раз в al oop:

   int diff;
   if(v1.size() > v2.size())
   {  diff = v1.size() - v2.size();
      for(int i = 0; i < diff; ++i)
          v2.insert(v2.begin(),0);
   }          
   else
   {  diff = v2.size() - v1.size();
      for(int i = 0; i < diff; ++i)
          v1.insert(v1.begin(),0);
   }

• Добавление : Теперь, когда векторы имеют одинаковые размеры, вы можете использовать std::plus из заголовка functional для добавления элементов одного вектора (скажем, v1) к другому вектору (v2) поэлементно, мириться с правильными позициями итератора в std::transform:

std::transform(v1.begin( ), v1.end( ), v2.begin( ), v1.begin( ),std::plus<DT>( ));

Это соберет поэлементную сумму v1 и v2 в v1 (взаимозаменяемо). Единственная оставшаяся проблема или условие для решения - переполнение, для случаев, когда сумма добавлений по элементам должна быть больше или равна 10.

• Переполнение: Для всех элементов в векторе, отличном от первого (с индексом 0 ^th ), нам потребуется перенести / добавить 1 к следующему элементу в случае переполнения (>=10) и назначить текущий элемент вектора к остатку при делении на 10. Однако для переполнения первого элемента нам нужно назначить другой элемент в начале вектора (например: {3,1} + {9,2} = {1,2,3 }), который снова будет 1 (учитывая отдельные элементы вектора di git), для которого мы можем наложить отдельные if операторы:

   for(int i = v1.size(); i > 0; --i) 
   { 
       if(i==1 && v1[1]>=10)
       {   v1[1]=v1[1]%10;
           v1.insert(v1.begin(),1);
       }     
       else if(i!=1 && v1[i-1]>=10)
       {  v1[i-1]=v1[i-1]%10;
          v1[i-2]=v1[i-2]+1;
       }
   }

---

Примеры:

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#define DT long long int
int main() 
{   
    std::vector<DT> v1 = {5, 2, 5, 7, 8}; 
    std::vector<DT> v2 = {4, 5, 6};  

                         // 52578
                         // 00456
                         // -----
        Expected output: // 53034   

   // Size management:
   int diff;
   if(v1.size() > v2.size())
   {  diff = v1.size() - v2.size();
      for(int i = 0; i < diff; ++i)
          v2.insert(v2.begin(),0);
   }          
   else
   {  diff = v2.size() - v1.size();
      for(int i = 0; i < diff; ++i)
          v1.insert(v1.begin(),0);
   }

   // Element-wise addition:
   std::transform(v1.begin( ), v1.end( ), v2.begin( ), v1.begin( ),std::plus<DT>( ));

   // Overflow management:
   for(int i = v1.size(); i > 0; --i) 
   { 
       if(i==1 && v1[1]>=10)
       {   v1[1]=v1[1]%10;
           v1.insert(v1.begin(),1);
       }     
       else if(i!=1 && v1[i-1]>=10)
       {  v1[i-1]=v1[i-1]%10;
          v1[i-2]=v1[i-2]+1;
       }
   }   

   // Display sum
   for(auto v:v1)
      std::cout<<v;
}

Выход: 53034.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#define DT long long int
int main() 
{   
    std::vector<DT> v1 = {5, 2, 5, 7}; 
    std::vector<DT> v2 = {9, 3, 7, 2};  

                         //  5257
                         //  9372
                         // -----
        Expected output: // 14629   

   // Size management:
   int diff;
   if(v1.size() > v2.size())
   {  diff = v1.size() - v2.size();
      for(int i = 0; i < diff; ++i)
          v2.insert(v2.begin(),0);
   }          
   else
   {  diff = v2.size() - v1.size();
      for(int i = 0; i < diff; ++i)
          v1.insert(v1.begin(),0);
   }

   // Element-wise addition:
   std::transform(v1.begin( ), v1.end( ), v2.begin( ), v1.begin( ),std::plus<DT>( ));

   // Overflow management:
   for(int i = v1.size(); i > 0; --i) 
   { 
       if(i==1 && v1[1]>=10)
       {   v1[1]=v1[1]%10;
           v1.insert(v1.begin(),1);
       }     
       else if(i!=1 && v1[i-1]>=10)
       {  v1[i-1]=v1[i-1]%10;
          v1[i-2]=v1[i-2]+1;
       }
   }   

   // Display sum
   for(auto v:v1)
      std::cout<<v;
} 

Выход: 14629

Answer 2

Вы хотели что-то подобное?:

Этот код сначала делает векторы v1, v2 целыми числами n1, n2

И суммирует целую сумму до n3.

И после этого снова превратить целое число n3 в вектор.

vector<int> v1 = {3, 1, 7};
vector<int> v2 = {6, 5};
vector<int> v3;// = {3, 8, 2}; // The sum of v1 and v2
int n1=0; for(int a:v1) n1=10*n1+a;
int n2=0; for(int a:v2) n2=10*n2+a;
int n3 = n1 + n2;
while(n3) v3.insert(v3.begin(), n3%10),n3/=10;
//now v3 = {3, 8, 2}

Answer 3

Самый простой способ - перебирать векторы в обратном порядке.

std::vector<int>::const_reverse_iterator first = v1.rbegin(), endfirst = v1.rend();
std::vector<int>::const_reverse_iterator second = v2.rbegin(), endsecond = v2.rend();

//   if adding two digits gives a value of 10 or more, need to carry

int carry = 0;
std::vector<int> v3(0);
//  first do summations of digits in reverse until one vector has no more

//   the following loops will collect digits in v3 (the notional "sum" of v1 and v2)
//      in reverse order

while (first != endfirst && second != endsecond)
{

     int sum = *first + *second + carry;
     carry = (sum >= 10) ? 1 : 0;
     v3.push_back(sum % 10);
     ++first; ++second;
}

//    if we have reached the end of v1, there may be additional elements in v2, so     

if (first == firstend)
{
     first = second;
     firstend = secondend;
}

//   first and firstend specify the range in whichever vector (v1 or v2) has 
//       more elements
//    The next loop does nothing if v1 and v2 have the same length

while (first != firstend)
{
     int sum = *first + carry;
     carry = (sum >= 10) ? 1 : 0;
     v3.push_back(sum % 10);
     ++first;
}

//   if we are carrying a digit after doing all the sums, then push a 1

if (carry) v3.push_back(1);

//   we have pushed the digits into v3 in reverse order, so ....

std::reverse(v3.begin(), v3.end());

Это будет обрабатывать векторы любой допустимой длины. (Я оставлю проблему поиска аппаратного обеспечения, которое может представлять векторы бесконечной длины, как нерешенную проблему).

В приведенном выше коде предполагается, что все элементы v1 и v2 находятся в диапазоне 0 до 9. Его можно тривиально изменить для обработки элементов со значением 10 или более. Я оставлю это в качестве упражнения.

Возможно уменьшить выделение / перераспределение памяти при вставке элементов в v3 путем вызова v3.reserve(). Я оставлю это как упражнение.