Строки char: умножение двух чисел

@annussaa · Регистрация: 01.11.2014

Author24 — интернет-сервис помощи студентам

нужно было создать функцию, умножающую два числа (до 30 цифр включительно). эти числа - два char массива.
есть один момент, с которым мне сложновато разобраться - при переходе на следующее число, на которое будут умножаться первое число по цифрам, идет путаница с цифрой "в уме" и той, что записывается как остаток. (15 строка)
если как тестовые данные взять 567 умножить на 89, то результат будет 50863 (3 цифра в процессе переписалась почему то с положенной 1 на 5, вследствии чего и в результате 3 цифра не положенная 4, а 8)... а если в 15 строке "j + bcount - parbide - 1" изменить на "j + bcount - parbide - 2", тогда результат будет правильным. но уже перестанет быть правильным для других вводимых данных.
подскажите идеи, помогите, с общем.

фрагмент кода:

C++

    int acount = strlen(a), bcount = strlen(b);
    int gar = acount + bcount; 
 
    char c[61];
    for (int i = 0; i < gar; i++) c[i] = '0';
    c[gar] = '\0';
    int sk = 0; 
    int mind = 0; // цифра "в уме"
    int parbide = 0; // сдвиг
    for (int i = bcount - 1; i >= 0; i--){
        for (int j = acount - 1; j >= 0; j--){
            sk = (b[i] - '0') * (a[j] - '0') + (c[j + bcount - parbide] - '0') + mind;
            mind = sk/10;
            c[j + bcount - parbide] = sk%10 + '0';
            if (i == 0) c[j + bcount - parbide - 1] = mind + '0'; // то самое место, в котором что то идет не так
            sk = 0;
        }
        mind = 0;
        parbide++;
    }

PS. нет, длинная арифметика мне не подходит.

Байт · 22.01.2015, 23:10

Сообщение от annussaa

нет, длинная арифметика мне не подходит.

Если я правильно понял, вы хотите ее реализовать сами? Похвально! Я не знаю ни одного уважающего себя программиста, который не попробовал бы себя на этом поприще. Это чрезвычайно полезное упражнение, и Бог вам в помощь!
ИМХО, вы на правильном пути. Но кода вашего я смотреть не стал - время позднее. Могу дать несколько ни к чему не обязывающих советов.
1. Возьмите лист бумаги, напишите 2 числа и попробуйте их перемножить столбиком, тщательно следя за своими действиями и алгоритмизируя их. (И как только первоклашки это проделывают, ни о чем не задумываясь?!)
2. разряды я бы расположил наоборот. От младших к старшим. Так логика будет прозрачней. Ведь на бумажке вы именно так и делаете - от младших к старшим.
3. Используйте не символьные представления, '0', '1' ... а числовые 0, 1,.. Так вам не придется возиться с - '0', '0'+... сможете сосредоточиться на самом алгоритме. По ходу может появиться мысль использовать не 10-ичную с/с, а 256-ричную, что значительно эффективнее
4. В проблемных местах не стесняйтесь выводить промежуточную информацию (printf, cout). Если ее слишком много и она не помещается на экран, запустите вашу программу из командной строки "proga >file.txt" В файле окажется вся ваша выдача и вы ее спокойно сможете проанализировать
Удачи!

@annussaa · 22.01.2015, 23:15 **[ТС]**

Байт, дело в том, что я не могу отклоняться от условий данного мне задания..) программа должна быть написана именно с использованием char.
что насчет ваших советов - да, именно так я и делала. с бумаги именно все перенеслось в код. и cout'ы тоже были, убрала их лишь здесь

спасибо за советы!

@DU · 22.01.2015, 23:31

я вот когда-то писал то ли лабу, толи тестовое. специально откопал в архивах. врятли TC разберется в коде, это я так, похвастаться

C++

#include <algorithm>
#include <cassert>
#include <functional>
#include <iostream>
#include <vector>
#include <string>
#include <stdexcept>
 
using namespace std;
 
class BigInt
{
  std::string m_value;
 
public:
  class Exception : public std::exception
  {
  public:
    enum ErrorCode { bad_format, division_by_zero, unknown_error };
 
  private:
    ErrorCode m_code;
 
  public:
    Exception(ErrorCode code) : m_code(code)
    {
    }
 
    virtual const char* what() const
    {
      switch (m_code)
      {
        case bad_format       : return "BigInt exception: bad format";
        case division_by_zero   : return "BigInt exception: division by zero";
      }
      return "BigInt exception: unknown error";
    }
  };
 
  BigInt(int value = 0);
  BigInt(const std::string& value);
  BigInt(const char* pValue);
 
  std::string   ToString() const;
 
  BigInt& operator += (const BigInt& lhs);
  BigInt& operator -= (const BigInt& lhs);
  BigInt& operator *= (const BigInt& lhs);
  BigInt& operator /= (const BigInt& lhs);
 
  BigInt& operator ++ ();
  const BigInt operator ++ (int);
 
  BigInt& operator -- ();
  const BigInt operator -- (int);
 
  const BigInt operator - () const;
 
  friend bool operator == (const BigInt& lhs, const BigInt& rhs);
  friend bool operator != (const BigInt& lhs, const BigInt& rhs);
  friend bool operator < (const BigInt& lhs, const BigInt& rhs);
  friend bool operator > (const BigInt& lhs, const BigInt& rhs);
  friend bool operator <= (const BigInt& lhs, const BigInt& rhs);
  friend bool operator >= (const BigInt& lhs, const BigInt& rhs);
 
  friend BigInt abs(const BigInt& value);
 
  friend std::ostream& operator << (std::ostream& o, const BigInt& bi);
  friend std::istream& operator >> (std::istream& i, BigInt& bi);
};
 
bool operator == (const BigInt& lhs, const BigInt& rhs);
bool operator != (const BigInt& lhs, const BigInt& rhs);
bool operator < (const BigInt& lhs, const BigInt& rhs);
bool operator > (const BigInt& lhs, const BigInt& rhs);
bool operator <= (const BigInt& lhs, const BigInt& rhs);
bool operator >= (const BigInt& lhs, const BigInt& rhs);
 
BigInt operator + (const BigInt& lhs, const BigInt& rhs);
BigInt operator - (const BigInt& lhs, const BigInt& rhs);
BigInt operator * (const BigInt& lhs, const BigInt& rhs);
BigInt operator / (const BigInt& lhs, const BigInt& rhs);
 
BigInt abs(const BigInt& value);
 
std::ostream& operator << (std::ostream& o, const BigInt& bi);
std::istream& operator >> (std::istream& i, BigInt& bi);
 
 
void ReportError(BigInt::Exception::ErrorCode code)
{
  throw BigInt::Exception(code);
}
 
BigInt::BigInt(int value)
  : m_value(std::to_string(value))
{
}
 
BigInt::BigInt(const string& value)
  : m_value(value)
{
  if (m_value.empty())
  {
    ReportError(Exception::bad_format);
  }
 
  if (m_value[0] == '+')
  {
    m_value.erase(m_value.begin());
  }
 
  if (m_value.empty())
  {
    ReportError(Exception::bad_format);
  }
 
  string::iterator it = m_value.begin();
  if (*it == '-')
  {
    if (m_value.size() == 1)
    {
      ReportError(Exception::bad_format);
    }
    else
    {
      ++it;
    }
  }
 
    m_value.erase(it, find_if(it, m_value.end() - 1, bind2nd(not_equal_to<int>(), int('0'))));
 
  if (m_value[0] == '-' && m_value[1] == '0')
  {
    m_value.erase(m_value.begin());
  }
 
  string::iterator from = m_value.begin();
  if (*from == '-')
  {
    ++from;
  }
 
  if (m_value.end() != find_if(from, m_value.end(), not1(ptr_fun(isdigit))))
  {
    ReportError(Exception::bad_format);
  }
}
 
BigInt::BigInt(const char* pValue)
{
  BigInt tmp((string(pValue))); // warning C4930!
  m_value.swap(tmp.m_value);
}
 
string BigInt::ToString() const
{
  return m_value;
}
 
BigInt& BigInt::operator += (const BigInt& rhs)
{
  const bool f1 = *this < 0;
  const bool f2 = rhs < 0;
 
  if (true == f1 && true == f2)
  {
    return *this = -((-*this) + (-rhs)); 
  }
 
  if (true == f1)
  {
    return *this = rhs - (-(*this));
  }
 
  if (true == f2)
  {
    return *this -= (-rhs);
  }
 
  const size_t maxLength = max(m_value.size(), rhs.m_value.size());
 
  vector<int> tmpThis(maxLength, 0);
  vector<int> tmpOther(maxLength, 0);
 
  {
    vector<int>::reverse_iterator itVec = tmpThis.rbegin();
    string::const_reverse_iterator end = m_value.rend();
    for (string::const_reverse_iterator it = m_value.rbegin(); it != end; ++it, ++itVec)
    {
      *itVec = static_cast<int>(*it - '0');
    }
  }
 
  {
    vector<int>::reverse_iterator itVec = tmpOther.rbegin();
    string::const_reverse_iterator end = rhs.m_value.rend();
    for (string::const_reverse_iterator it = rhs.m_value.rbegin(); it != end; ++it, ++itVec)
    {
      *itVec = static_cast<int>(*it - '0');
    }
  }
 
  int inMind = 0;
  vector<int>::reverse_iterator itThis = tmpThis.rbegin();
  vector<int>::reverse_iterator itOther = tmpOther.rbegin();
  for (vector<int>::reverse_iterator end = tmpThis.rend(); itThis != end; ++itThis, ++itOther)
  {
    const int tmp = *itThis + *itOther + inMind;
    *itThis = tmp % 10;
    inMind = tmp / 10;
  }
 
    transform(tmpThis.begin(), tmpThis.end(),
    tmpThis.begin(),
    bind2nd(plus<int>(), int('0')));
 
  string tmpValue;
  if (inMind > 0)
  {
    tmpValue += std::to_string(inMind);
  }
  tmpValue.insert(tmpValue.end(), tmpThis.begin(), tmpThis.end());
 
  m_value.swap(tmpValue);
 
  return *this;
}
 
BigInt& BigInt::operator -= (const BigInt& rhs)
{
  const bool f1 = *this < 0;
  const bool f2 = rhs < 0;
 
  if (true == f1 && true == f2)
  {
    return *this = (-rhs) - (-*this); 
  }
 
  if (true == f1)
  {
    return *this = -((-*this) + rhs);
  }
 
  if (true == f2)
  {
    return *this += (-rhs);
  }
 
  const size_t maxLength = max(m_value.size(), rhs.m_value.size());
  vector<int> first(maxLength, 0);
  vector<int> second(maxLength, 0);
 
  {
    vector<int>::reverse_iterator itVec = first.rbegin();
    string::const_reverse_iterator end = m_value.rend();
    for (string::const_reverse_iterator it = m_value.rbegin(); it != end; ++it, ++itVec)
    {
      *itVec = static_cast<int>(*it - '0');
    }
    }
 
  {
    vector<int>::reverse_iterator itVec = second.rbegin();
    string::const_reverse_iterator end = rhs.m_value.rend();
    for (string::const_reverse_iterator it = rhs.m_value.rbegin(); it != end; ++it, ++itVec)
    {
      *itVec = static_cast<int>(*it - '0');
    }
  }
 
  if (*this < rhs)
  {
    first.swap(second);
  }
 
  vector<int>::reverse_iterator itFirst = first.rbegin();
  vector<int>::reverse_iterator itSecond = second.rbegin();
  for (vector<int>::reverse_iterator end = first.rend(); itFirst != end; ++itFirst, ++itSecond)
  {
    int diff = *itFirst - *itSecond;
    while (diff < 0)
    {
      if (diff < 0)
      {
        diff += 10;
        --*(itFirst + 1);
      }
    }
    *itFirst = diff;
  }
 
    transform(first.begin(), first.end(),
    first.begin(),
    bind2nd(plus<int>(), int('0')));
 
  string tmpValue;
  if (*this < rhs)
  {
    tmpValue.push_back('-');
  }
 
  tmpValue.insert(tmpValue.end(),
    find_if(first.begin(), first.end() - 1, bind2nd(not_equal_to<int>(), int('0'))),
    first.end());
 
  m_value.swap(tmpValue);
 
  return *this;
}
 
BigInt& BigInt::operator *= (const BigInt& rhs)
{
  const bool f1 = *this < 0;
  const bool f2 = rhs < 0;
 
  if (true == f1 && true == f2)
  {
    return *this = (-*this) * (-rhs);
  }
 
  if (true == f1)
  {
    return *this = -((-*this) * rhs);
  }
 
  if (true == f2)
  {
    return *this = -(*this * (-rhs));
  }
 
  const size_t maxLength = max(m_value.size(), rhs.m_value.size());
  typedef vector<int> Cont;
  Cont tmpThis(maxLength, 0);
  Cont tmpOther(maxLength, 0);
 
  {
    Cont::reverse_iterator itVec = tmpThis.rbegin();
    string::const_reverse_iterator end = m_value.rend();
    for (string::const_reverse_iterator it = m_value.rbegin(); it != end; ++it, ++itVec)
    {
       *itVec = static_cast<int>(*it - '0');
    }
  }
 
  {
    Cont::reverse_iterator itVec = tmpOther.rbegin();
    string::const_reverse_iterator end = rhs.m_value.rend();
    for (string::const_reverse_iterator it = rhs.m_value.rbegin(); it != end; ++it, ++itVec)
    {
      *itVec = static_cast<int>(*it - '0');
    }
  }
 
  typedef vector<Cont> Conts;
  Conts conts;
  Cont::reverse_iterator itThis = tmpThis.rbegin();
  Cont::reverse_iterator itOther = tmpOther.rbegin();
  unsigned int n = 0;
  for (Cont::reverse_iterator end = tmpThis.rend(); itThis != end; ++itThis, ++itOther, ++n)
  {
    int inMind = 0;
    Cont tmpCont;
 
    for (unsigned i = 0; i < n; ++i)
    {
      tmpCont.push_back(0);
    }
 
    Cont::reverse_iterator itOther = tmpOther.rbegin();
    for (Cont::reverse_iterator endOther = tmpOther.rend(); itOther != endOther; ++itOther)
    {
      const int tmp = (*itThis) * (*itOther) + inMind;
      tmpCont.push_back(tmp % 10);
      inMind = tmp / 10;
    }
 
    if (inMind != 0)
    {
      bool exit = false;
      while (!exit)
      {
        tmpCont.push_back(inMind % 10);
        exit = ( (inMind /= 10) == 0 );
      }
      tmpCont.push_back(inMind);
    }
 
    conts.push_back(tmpCont);
  }
 
  BigInt res;
  for (Conts::iterator it = conts.begin(), end = conts.end(); it != end; ++it)
  {
        transform(it->begin(), it->end(),
      it->begin(),
      bind2nd(plus<int>(), int('0')));
 
    res += string(it->rbegin(), it->rend());
  }
 
  m_value.swap(res.m_value);
 
  return *this;
}
 
BigInt& BigInt::operator /= (const BigInt& rhs)
{
  const bool f1 = *this < 0;
  const bool f2 = rhs < 0;
 
  if (true == f1 && true == f2)
  {
    return *this = (-*this) / (-rhs);
  }
 
  if (true == f1)
  {
    return *this = -((-*this) / rhs);
  }
 
  if (true == f2)
  {
    return *this = -(*this / (-rhs));
  }
 
 
  if (*this < rhs)
  {
    return *this = 0;
  }
 
  if (rhs == 0)
  {
    ReportError(Exception::division_by_zero);
  }
 
  typedef vector<int> Cont;
  Cont cont;
 
  BigInt tmpBI(*this);
  const string& strLhs = tmpBI.m_value;
  const string& strRhs = rhs.m_value;
 
  for (;;)
    {
    if (strLhs.size() < strRhs.size())
    {
      break;
    }
 
    string::const_iterator begin = strLhs.begin();
    string::const_iterator end = begin + strRhs.size();
 
    bool do_break = false;
    while (BigInt(string(begin, end)) < rhs)
    {
      if (static_cast<size_t>(distance(begin, end++)) >= strLhs.size())
      {
        do_break = true;
        break;
      }
    }
 
    if (true == do_break)
    {
      break;
    }
 
    BigInt bi(string(begin, end));
    int c = 0;
    while (bi >= rhs)
    {
      ++c;
      bi -= rhs;
    }
    cont.push_back(c);
 
    int cZero = 0;
    for (bool first = true; bi <= rhs && end != strLhs.end(); first = false, ++end)
    {
      if (bi == 0)
      {
        bi.m_value[0] = *end;
      }
      else
      {
        bi.m_value.push_back(*end);
      }
 
      if (bi < rhs)
      {
        ++cZero;
      }
    }
 
    cont.insert(cont.end(), cZero, 0);
 
    if (bi < rhs)
    {
      break;
    }
 
    bi.m_value.insert(bi.m_value.end(), end, strLhs.end());
    tmpBI.m_value.swap(bi.m_value);
  }
 
    transform(cont.begin(), cont.end(),
    cont.begin(),
    bind2nd(plus<int>(), int('0')));
 
  string(cont.begin(), cont.end()).swap(m_value);
 
  return *this;
}
 
BigInt& BigInt::operator ++ ()
{
  return *this += 1;
}
 
const BigInt BigInt::operator ++ (int)
{
  const BigInt tmp(*this);
  ++*this;
  return tmp;
}
 
BigInt& BigInt::operator -- ()
{
  return *this -= 1;
}
 
const BigInt BigInt::operator -- (int)
{
  const BigInt tmp(*this);
  --*this;
  return tmp;
}
 
const BigInt BigInt::operator - () const
{
  if (m_value[0] == '-')
  {
    return BigInt(string(m_value.begin() + 1, m_value.end()));
  }
 
  return BigInt(string("-") + m_value);
}
 
bool operator == (const BigInt& lhs, const BigInt& rhs)
{
  return lhs.m_value == rhs.m_value;
}
 
bool operator != (const BigInt& lhs, const BigInt& rhs)
{
  return !(lhs == rhs);
}
 
bool operator < (const BigInt& lhs, const BigInt& rhs)
{
  if (lhs == rhs)
  {
    return false;
  }
 
  if (lhs.m_value[0] == '-' && rhs.m_value[0] == '-')
  {
    return !(abs(lhs) < abs(rhs));
  }
 
  if (lhs.m_value[0] == '-')
  {
    return true;
  }
 
  if (rhs.m_value[0] == '-')
  {
    return false;
  }
 
  if (lhs.m_value.size() < rhs.m_value.size())
  {
    return true;
  }
 
  if (lhs.m_value.size() > rhs.m_value.size())
  {
    return false;
  }
 
  return lhs.m_value < rhs.m_value;
}
 
bool operator > (const BigInt& lhs, const BigInt& rhs)
{
  return !(lhs < rhs) && !(lhs == rhs);
}
 
bool operator <= (const BigInt& lhs, const BigInt& rhs)
{
  return !(lhs > rhs);
}
 
bool operator >= (const BigInt& lhs, const BigInt& rhs)
{
  return !(lhs < rhs);
}
 
BigInt operator + (const BigInt& lhs, const BigInt& rhs)
{
  BigInt tmp(lhs);
  return tmp += rhs;
}
 
BigInt operator - (const BigInt& lhs, const BigInt& rhs)
{
  BigInt tmp(lhs);
  return tmp -= rhs;
}
 
BigInt operator * (const BigInt& lhs, const BigInt& rhs)
{
  BigInt tmp(lhs);
  return tmp *= rhs;
}
 
BigInt operator / (const BigInt& lhs, const BigInt& rhs)
{
  BigInt tmp(lhs);
  return tmp /= rhs;
}
 
BigInt abs(const BigInt& value)
{
  return value.m_value[0] == '-' ? (-value) : value;
}
 
std::ostream& operator << (std::ostream& o, const BigInt& bi)
{
  return o << bi.m_value;
}
 
std::istream& operator >> (std::istream& i, BigInt& bi)
{
  string str;
  i >> str;
  if (false == str.empty())
  {
    bi = BigInt(str);
  }
  return i;
}
 
//////////
int main()
{
 
  BigInt b1 = "9999999999999999999999";
  BigInt b2 = "666";
 
  std::cout << b1 << " * " << b2 << " = " << b1 * b2 << std::endl;
 
 
  return 0;
}

@annussaa · 24.01.2015, 21:34 **[ТС]**

update: все же довела ту самую строку до ума и теперь программа на ввод любых положительных целых чисел длиной до 30 знаков включительно выдаёт правильный результат.

C++

1	if (j == 0) c[i] = mind + '0';

может, кому пригодится.

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	22.01.2015, 23:10	2
	Сообщение от annussaa нет, длинная арифметика мне не подходит. Если я правильно понял, вы хотите ее реализовать сами? Похвально! Я не знаю ни одного уважающего себя программиста, который не попробовал бы себя на этом поприще. Это чрезвычайно полезное упражнение, и Бог вам в помощь! ИМХО, вы на правильном пути. Но кода вашего я смотреть не стал - время позднее. Могу дать несколько ни к чему не обязывающих советов. 1. Возьмите лист бумаги, напишите 2 числа и попробуйте их перемножить столбиком, тщательно следя за своими действиями и алгоритмизируя их. (И как только первоклашки это проделывают, ни о чем не задумываясь?!) 2. разряды я бы расположил наоборот. От младших к старшим. Так логика будет прозрачней. Ведь на бумажке вы именно так и делаете - от младших к старшим. 3. Используйте не символьные представления, '0', '1' ... а числовые 0, 1,.. Так вам не придется возиться с - '0', '0'+... сможете сосредоточиться на самом алгоритме. По ходу может появиться мысль использовать не 10-ичную с/с, а 256-ричную, что значительно эффективнее 4. В проблемных местах не стесняйтесь выводить промежуточную информацию (printf, cout). Если ее слишком много и она не помещается на экран, запустите вашу программу из командной строки "proga >file.txt" В файле окажется вся ваша выдача и вы ее спокойно сможете проанализировать Удачи! 0

@annussaa 2 / 2 / 1 Регистрация: 01.11.2014 Сообщений: 39
	22.01.2015, 23:15 [ТС]	3
	Байт, дело в том, что я не могу отклоняться от условий данного мне задания..) программа должна быть написана именно с использованием char. что насчет ваших советов - да, именно так я и делала. с бумаги именно все перенеслось в код. и cout'ы тоже были, убрала их лишь здесь спасибо за советы! 0

	24.01.2015, 21:34