乘大型字符串数组中的C ++ [英] Multiply Large Strings in Array C++
问题描述
在这里，我有一个SAFEARRAY（不是安全的，但我的老师说，这是罚款）类和BIGINT类。我BIGINT类可以加减就好了，但是当我尝试乘功能它都没有，我已经试过调试打印任何东西，单步运行它，但我似乎无法弄清楚，一直致力于它一段时间，我绝望地卡住。任何帮助将是AP preciated。谢谢
的#include＆LT;＆iostream的GT;
使用命名空间std;
＃包括LT＆;＆算法GT;模板＆LT; typename的组件＆gt;
一流的SafeArray
{
INT大小;
元素*数组;
元素DEF;上市：
安全数组（）//默认构造函数（不带参数）
{
大小= 10;
阵列=新的元素[大小]（）;
} 安全数组（int值）//构造一个INT
{
大小=价值;
阵列=新元素[值];
的for（int i = 0; I＆LT;大小; ++ I）
阵列[I] = 0;
} 〜的SafeArray（）{
删除[]数组;
} //析构函数 安全数组（常量的SafeArray＆安培;右）：尺寸（rhs.size），阵列（新元素[尺寸]），高清（rhs.def）
{
的for（int i = 0; I＆LT;大小; ++ I）
阵列[我] = rhs.Array [I]
} safearray之所以和放大器;运算符=（RHS的SafeArray）
{
的std ::互换（阵列，rhs.Array）;
的std ::交换（大小，rhs.size）;
的std ::互换（DEF，rhs.def）;
返回*这一点;
} 元素得到（INT POS）常量//获取方法
{
如果（POS℃，）
{
COUT＆LT;＆LT; 错误;
} 返回数组[POS]
} 空集（INT POS，元素VAL）
{
如果（POS℃，）
{
COUT＆LT;＆LT; 错误;
返回;
}
如果（POS＆GT; =大小）
{
调整（POS + 1）;
}
数组[POS] = VAL;
} 无效调整大小（INT new_size）
{
元* TEMP =新元素[new_size]
的for（int i = 0; I＆LT;大小;我++）
{
临时[I] =阵列[我]
}
删除[]数组;
阵列=温度;
大小= new_size;
} 无效set_default（元件D）// set_default
{
DEF = D;
} INT get_size（）//获取大小
{
返回的大小;
}
};INT大小= 100; //测试类BIGINT
{
safearray之所以＆LT; INT＆GT; * ARR;
上市：
布尔标志;
BIGINT（）//初始化为零
{
ARR =新的SafeArray＆LT; INT取代;
的for（int i = 0; I＆LT;大小;我++）
arr-＆GT;集合（I，0）;
}无效的print（）//输出数字没有在前面零
{
布尔START_NUM = FALSE;
的for（int i = 0; I＆LT; arr-＆GT; get_size（）;我++）
{
如果（arr-＆GT;！得到（I）= 0＆放大器;＆安培; START_NUM ==假）
{START_NUM = TRUE;
COUT＆LT;＆LT; arr-＆GT;让（我）;}
否则，如果（START_NUM ==真）
COUT＆LT;＆LT; arr-＆GT;得到（I） } COUT＆LT;＆LT; ENDL;
}
无效分配（常量BIGINT＆安培; A）//
{
的for（int i = 0; I＆LT; arr-＆GT; get_size（）;我++）
{//方法来初始化的东西
arr-＆GT;集（I，A.arr-＆GT;获得（一））;
}}
无效分配（字符串NUM）
{
长LEN = num.length（）;
INT J = arr-＆GT; get_size（） - 1;
为（长I = LEN-1; I＆GT; = 0;我 - ）
{
arr-＆GT;集（J，NUM [I] -48）;
j--;
}
}
无效add_pos（常量BIGINT＆安培; A）//添加大整数
{
INT携带= 0;
的for（int i =大小-1; I＆GT; = 0;我 - ）
{
INT结果= arr-＆GT;让（我）+ A.arr-＆GT;让（我）+随身携带;
arr-＆GT;集（I，导致10％）;
携带=结果/ 10;
}
}无效sub_pos（常量BIGINT＆安培; A）
{
INT借= 0;
的for（int i =大小-1; I＆GT; = 0;我 - ）
{
INT结果=（（arr-＆GT;得到（一） - A.arr-＆GT;获得（ⅰ）-borrow））;
如果（结果℃，）
{
arr-＆GT;集（I，导致+10）;
借用= 1;
}
其他
{
arr-＆GT;集（I，结果）;
借用= 0;
}
}
}
无效乘法（常量BIGINT＆安培; A）
{
的for（int i =大小-1; I＆GT; = 0;我 - ）
{
INT携带= 0; 对于（INT J =大小-1，J＆GT; = 0; j--）
{
INT产品=（（arr-＆GT;让（我）* A.arr-＆GT;得到（J））+利差）;
arr-＆GT;集（I + J，产品10％）;
携带=产品/ 10;
}
}
} }诠释的main（）
{
BIGINT A，B;
a.assign（1234）;
b.assign（5678）;
a.multiply（二）;
打印（）;返回0;
}
由于意见和以下修改的SafeArray
http://coliru.stacked-crooked.com/a/0f22a24e04421ae1
实现倍增的一种方式是利用你说的已经工作，即 BIGINT :: add_pos功能和 BIGINT :: sub_pos 做乘法。我们的目标是模拟 M *ñ加入 M 本身 N-1 倍。例如， 4 * 3 是相同的 4 + 4 + 4 （我们加入4-自身2倍）
请注意：如果要求是，你必须写乘法code完全独立的现有功能，和/或使用的SafeArray 的不安全版本，那么这个答案不会帮助你，你将不得不做从头开始的事情。
preliminaries：
这是应该做的第一件事情就是在你的 BIGINT 类指针替换到的SafeArray 来的实际的实例：
的SafeArray＆LT; INT＆GT;改编;
第二个变化将是改变 arr-＆GT; 到改编你的<$ C $内。 C> BIGINT 类。这应该是无缝的变化。
现在，第三个要做的是创建 BIGINT 一个辅助函数，调用它 is_zero 确定如果 BIGINT 重新$ p $ 0 psents您可以轻松地编写循环，并确保做到这一点，在所有条目改编是 0 。该功能应该是常量，即
布尔is_zero（）const的;
最后一个变化是，你有你的 BIGINT 默认的构造函数中的错误。这错误是，你没有初始化改编 safearray之所以有尺寸元素。您使用的默认，这是只有10。为了解决这个问题，初始化改编到尺寸元素
BIGINT（）：ARR（尺寸）
{
的for（int i = 0; I＆LT;大小;我++）
arr.set（I，0）;
}
我一直在你的全局变量尺寸，但它确实应该从一个全球性删除，你的 BIGINT 类应使用 arr.get_size（）来获取数组的大小。
实施
所以，现在我们到乘的使用现有的功能的实现。这是一种迂回的方式，它可能是非常大的数值缓慢。
让我们到code：
无效乘法（常量BIGINT＆安培; A）
{
//由0检查倍增
如果（A.is_zero（））
{
*此= A; //我们放慢参数（即0）复制到该对象
返回;
} BIGINT tempInt（*此）; //我们的原始值
BIGINT startVal（*此）; //我们的总运行
BIGINT启动市场（A）; //我们的专柜
BIGINT减法;
subtractor.assign（1）; //我们的循环decrementor //减一，我们需要添加的次数
startA.sub_pos（减法）; //不断增加，直到我们已经添加的次数
//充足
而（！startA.is_zero（））
{
//添加到总运行
startVal.add_pos（tempInt）; //从我们的计数器减1
startA.sub_pos（减法）;
} //最后的结果分配给我们的对象，我们就大功告成了
*此= startVal;
}
所以，我们做了什么？
首先，我们检查的0乘法。如果是这样，那么我们归零一切，只是返回。
如果不是0乘法，我们设置了保存我们的原值（tempInt）临时BIGINT。然后，我们设置另一个 BIGINT 持有我们现在的运行总计（ startVal ）。我们建立了另一个 BIGINT ，将持有我们的乘数启动市场。请注意我们如何使用拷贝构造函数从现有的修建临时 BIGINT 的。如果你的的SafeArray 并没有取得真正安全（即你坚持你最初的实现，而不是），这将是不可能的。
现在，麻烦的时候，我们需要保持我们添加次数的计数发生。要做到这一点，第四 BIGINT 名为减法成立，所有它本身初始化为 1 。我们需要这种帮助我们减去1从我们的 BIGINT 乘数（这是 BIGINT :: sub_pos 进场的我们的设计）。
请注意，我们不得不做这一切减去1，而不是用简单的 INT 的。究其原因 - 如果 BIGINT 传递给乘的是，不适合成为一个巨大的数量 INT 或长，那么我们就不能使用传统的C ++整型。我们正在处理的100位数字，有可能是一个具有本地100位的整数类型没有C ++编译器。
所以，我们从我们的乘数减1开始了。如果乘数现在是零，我们只是不循环（基本上这1情况下负责乘法，但看到下面的进一步修改一个优化的方式通过1完成乘法）。
如果乘数大于0，所有我们现在要做的是呼吁 add_pos 我们的总的运行，直到我们的乘数变为0。我们通过测试我们倍频看它是否已通过调用达到0 is_zero 每次在而（）状态。每一个我们称之为 sub_pos 时间从乘数减1。
工作就在纸上的一个高层次的看一下这个乘法函数是干什么的方面 - 你应该得到的正在做什么（鬼祟地避免了必须实际编写乘法code，你的想法在你的问题做了）。
最后，我们我们企业的经营总分配到的这个的。而已。所有使用您现有的功能，再加上另外一个简单的辅助，并且让你的的SafeArray 类一点点安全。
编辑：
你可以让一个优化比为1。检查乘法的方式你这样做是为了建立专柜，从中减去1，并检查计数器为0如果是0，则返回而不做任何进一步的工作
Here I've got a SafeArray(not that safe but my teacher said it's fine) class and a bigint class. My bigint class can add and subtract just fine but when I try the multiply function it doesn't print anything at all, i've tried debugging and stepping through it but I can't seem to figure it out, been working on it for a while and am hopelessly stuck. Any help would be appreciated. Thanks
#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;
}
Given the comments and the following changes to SafeArray
http://coliru.stacked-crooked.com/a/0f22a24e04421ae1
one way to achieve multiplication is to leverage the functions you say already work, namely bigint::add_pos and bigint::sub_pos to do the multiplication. The goal is to simulate m * n by adding m to itself n-1 times. For example, 4 * 3 is the same as 4 + 4 + 4 (we added 4 to itself 2 times).
Note: If the requirements are that you have to write the multiply code totally independent of the existing functions, and/or use the unsafe version of SafeArray, then this answer won't help you and you will have to do things from scratch.
Preliminaries:
The first thing that should be done is to replace the pointer to the SafeArray in your bigint class to an actual instance:
SafeArray<int> arr;
The second changes will be the changing of arr-> to arr. within your bigint class. This should be seamless change.
Now, the third thing to do is to create a helper function in bigint, call it is_zero to determine if the bigint represents 0. You can easily do this by writing a loop and making sure that all entries in arr are 0. The function should be const, i.e.
bool is_zero() const;
The last change is that you have a bug in your bigint default constructor. That bug is that you didn't initialize the arr SafeArray to have size elements. You used the default, which is only 10. To fix this, initialize the arr to size elements
bigint() : arr(size)
{
for (int i = 0; i < size; i++)
arr.set(i, 0);
}
I kept your global variable size, but it really should be removed from being a global, and your bigint class should use arr.get_size() to get the size of the array.
Implementation:
So now we get to the implementation of multiply using your existing functions. It is kind of a roundabout way, and it may be slow for very large values.
Let's get to the code:
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;
}
So what did we do?
First we checked for multiplication of 0. If so, then we zero out everything and just return.
If not a multiplication of 0, we set up a temporary bigint that holds our original value (tempInt). Then we setup another bigint that holds our current "running total" (startVal). We set up another bigint that will hold our multiplier startA. Note how we use the copy constructor to construct temporary bigint's from existing ones. This would not be possible if your SafeArray wasn't made truly safe (i.e. you stuck with your original implementation instead).
Now, the trouble happens when we need to keep a count of the number of times we add. To do that, a fourth bigint called subtractor was set up, and all it does is initialize itself to 1. We need this to help us subtract 1 from our bigint multiplier (this is where bigint::sub_pos comes into play in our design).
Note that we had to do all of this to subtract 1, and not use simple int's. The reason -- if the bigint that is passed to multiply is a huge number that won't fit into an int or long, then we can't use the "traditional" C++ integer types. We are dealing with 100 digit numbers and there is probably no C++ compiler that has native 100 digit integer types.
So we start out by subtracting 1 from our multiplier. If the multiplier is now zero, we just don't loop (essentially this takes care of the multiplication by 1 case, but see the further edit below for an optimized way to accomplish multiplication by 1).
If the multiplier is greater than 0, all we do now is call add_pos on our running total until our multiplier goes to 0. We do that by testing our multiplier to see if it has reached 0 by calling is_zero each time for the while() condition. Each time we call sub_pos to subtract 1 from the multiplier.
Work it out on paper in terms of a high-level look at what this multiply function is doing -- you should get the idea of what is being done (sneakily avoiding having to actually write the multiplication code as you did in your question).
At the end, we assign our running total to this. That's it. All using your existing functions, plus an addition of a simple helper, and making your SafeArray class a little safer.
Edit: An optimization you can make is to check for multiplication by 1. The way you do that is to set up the counter, subtract 1 from it, and check if the counter is 0. If it is 0, then return without doing any further work.
这篇关于乘大型字符串数组中的C ++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
