在数组 C++ 中乘以大字符串

Question

这里我有一个 SafeArray（不太安全，但我的老师说没问题）class 和一个 bigint class。我的 bigint class 可以很好地加减，但是当我尝试乘法函数时它根本不打印任何东西，我已经尝试调试并逐步执行它但我似乎无法弄清楚，一直工作了一段时间，我无可救药地陷入困境。任何帮助，将不胜感激。谢谢

        #include <iostream>
        using namespace std;
#include <algorithm>

template<typename Element>
class SafeArray
{
    int size;
    Element*Array;
    Element def;

public:
    SafeArray()                         //default constructor(with no parameter)
    {
        size = 10;
        Array = new Element[size]();
    }

    SafeArray(int value)         //constructor with one int
    {
        size = value;
        Array = new Element[value];
        for (int i = 0; i < size; ++i)
            Array[i] = 0;
    }

    ~SafeArray() {
        delete[] Array;
    }                                       //destructor

    SafeArray(const SafeArray& rhs) : size(rhs.size), Array(new Element[size]), def(rhs.def)
    {
        for (int i = 0; i < size; ++i )
            Array[i] = rhs.Array[i];
    }

    SafeArray& operator=(SafeArray rhs)
    {
        std::swap(Array, rhs.Array);
        std::swap(size, rhs.size);
        std::swap(def, rhs.def);
        return *this;
    }

    Element get(int pos)    const                 //get method
    {
        if (pos<0)
        {
            cout << "error";
        }

        return Array[pos];
    }

    void set(int pos, Element val)
    {
        if (pos<0)
        {
            cout << "error";
            return;
        }
        if (pos >= size)
        {
            resize(pos + 1);
        }
        Array[pos] = val;
    }

    void resize(int new_size)
    {
        Element*temp = new Element[new_size];
        for (int i = 0; i<size; i++)
        {
            temp[i] = Array[i];
        }
        delete[]Array;
        Array = temp;
        size = new_size;
    }

    void set_default(Element d)        //set_default
    {
        def = d;
    }

    int get_size()                       //get size
    {
        return size;
    }
};

int size = 100; //for testing

class bigint
{
    SafeArray<int> *arr;
public:
    bool sign;
bigint()                                                   //initializes to zero
    {
        arr = new SafeArray<int>;
        for(int i =0;i < size; i++)
            arr->set(i,0);
    }

void print()                                               //prints numbers without zeroes in front
    {
        bool start_num=false;
        for(int i = 0;i <arr->get_size() ;i++)
        {
            if(arr->get(i)!=0 && start_num==false )
            {start_num=true;
                cout << arr->get(i);}
         else if(start_num==true)
             cout<<arr->get(i);

        }

       cout<<endl;
    }
    void assign(const bigint &A)                             //
{
    for(int i=0;i<arr->get_size();i++)
    {                                                            //Ways to initialize stuff
        arr->set(i,A.arr->get(i));
    }

}
void assign(string num)                                  
    {
        long len = num.length();
        int j=arr->get_size()-1;
        for(long i=len-1;i>=0;i--)
        {
            arr->set(j,num[i]-48);
            j--;
        }
    }
void add_pos(const bigint &A)                                //add big ints
    {
        int carry=0;
        for(int i=size-1;i>=0;i--)
           {
               int result = arr->get(i)+A.arr->get(i)+carry;
               arr->set(i,result%10);
               carry=result/10;
           }
    }

void sub_pos(const bigint &A)
        {
           int borrow=0;
           for(int i=size-1;i>=0;i--)
           {
              int result = ((arr->get(i) - A.arr->get(i)-borrow));
              if(result<0)
              {
                 arr->set(i,result +10);
                 borrow = 1;
              }
              else
              {
                 arr->set(i,result);
                 borrow = 0;
              }
            }
        }


    void multiply(const bigint &A)
        {
            for(int i=size-1;i>=0;i--)
                {
                  int carry=0;

               for(int j=size-1;j>=0;j--)
                 {
                   int product=((arr->get(i)*A.arr->get(j))+carry);
                   arr->set(i+j,product%10);
                   carry=product/10;
                 }
            }
    }

    }

int main()
{
 bigint a,b;
a.assign("1234");
b.assign("5678");
a.multiply(b);
a.print();

return 0;
}

Answer 1

鉴于 SafeArray

的评论和以下更改

http://coliru.stacked-crooked.com/a/0f22a24e04421ae1

实现乘法的一种方法是利用您所说的已经可用的函数，即 bigint::add_pos 和 bigint::sub_pos 来进行乘法。目标是通过将 m 添加到自身 n-1 次来模拟 m * n。例如，4 * 3 与 4 + 4 + 4 相同（我们将 4 加到自身 2 次）。

注意：如果要求你必须编写完全独立于现有函数的乘法代码，and/or使用不安全版本的SafeArray，那么这个答案对你没有帮助而且您将不得不从头开始。

预赛：

首先应该做的是将 bigint class 中指向 SafeArray 的指针替换为实际实例：

SafeArray<int> arr;

第二个变化是在 bigint class 中将 arr-> 更改为 arr.。这应该是无缝更改。

现在，第三件事是在 bigint 中创建一个辅助函数，调用它 is_zero 来确定 bigint 是否代表 0。你可以很容易地做到这一点编写一个循环并确保 arr 中的所有条目都是 0。函数应该是const，即

bool is_zero() const;

最后一个变化是您的 bigint 默认构造函数中有一个错误。该错误是您没有将 arr SafeArray 初始化为具有 size 元素。您使用了默认值，它只有 10。要解决此问题，请将 arr 初始化为 size 元素

bigint() : arr(size)
{
    for (int i = 0; i < size; i++)
        arr.set(i, 0);
}

我保留了你的全局变量 size，但它确实应该从全局变量中删除，你的 bigint class 应该使用 arr.get_size() 来获取大小的阵列。

执行：

现在我们开始使用您现有的函数来实现 multiply。这是一种迂回的方式，对于非常大的值可能会很慢。

让我们来看代码：

void multiply(const bigint &A)
{
    // check for multiplication by 0
    if ( A.is_zero() )
    {
       *this = A;  // copy our paramter (which is 0) to this object
       return;  
    }

    bigint tempInt(*this);  // our original value
    bigint startVal(*this);  // our running total
    bigint startA(A);   // our counter
    bigint subtractor;
    subtractor.assign("1");  // our decrementor for looping

    // subtract one from the number of times we need to add
    startA.sub_pos(subtractor);

    // keep adding until the number of times we've added is 
    // sufficient
    while (!startA.is_zero()) 
    {
        // add to running total
        startVal.add_pos(tempInt);

        // subtract 1 from our counter
        startA.sub_pos(subtractor);
    } 

    // assign the final result to our object, and we're done
    *this = startVal;
}

那我们做了什么？

首先我们检查了 0 的乘法。如果是，那么我们将所有内容清零，然后 return。

如果不是 0 的乘法，我们设置一个临时 bigint 来保存我们的原始值 (tempInt)。然后我们设置另一个 bigint 来保存我们当前的 "running total" (startVal)。我们设置了另一个 bigint 来保存我们的乘数 startA。请注意我们如何使用复制构造函数从现有的 bigint 构造临时的。如果您的 SafeArray 不是真正安全的（即您坚持使用原来的实现），这将是不可能的。

现在，当我们需要计算添加的次数时，问题就出现了。为此，设置了第四个名为 subtractor 的 bigint，它所做的只是将自身初始化为 1。我们需要它来帮助我们从 bigint 乘数中减去 1（这就是 bigint::sub_pos 在我们的设计中发挥作用的地方）。

请注意，我们必须执行所有这些操作才能减去 1，而不是使用简单的 int。原因——如果传递给 multiply 的 bigint 是一个不适合 int 或 long 的巨大数字，那么我们就不能使用 "traditional" C++ 整数类型。我们正在处理 100 位数字，可能没有 C++ 编译器具有本机 100 位整数类型。

所以我们首先从乘数中减去 1。如果乘数现在为零，我们就不会循环（基本上这会处理乘以 1 的情况，但请参阅下面的进一步编辑以了解实现乘以 1 的优化方法）。

如果乘数大于 0，我们现在所做的就是对运行总数调用 add_pos，直到我们的乘数变为 0。我们通过测试乘数看它是否每次为 while() 条件调用 is_zero 已达到 0。每次我们调用 sub_pos 从乘数中减去 1。

从高层次的角度看这个乘法函数在做什么，在纸上解决这个问题——您应该了解正在做什么（偷偷摸摸地避免必须像您那样实际编写乘法代码在你的问题中）。

最后，我们将运行总数分配给 this。而已。全部使用您现有的功能，加上一个简单的助手，让您的 SafeArray class 更安全一些。

编辑：您可以进行的优化是检查乘以 1。您这样做的方法是设置计数器，从中减去 1，然后检查计数器是否为 0。如果为 0，则 return 没有做任何进一步的工作。

在数组 C++ 中乘以大字符串

Multiply Large Strings in Array C++

c++

arrays

string

class

bigint