Факториал в библиотеке bignum
Я попытался создать свою собственную реализацию библиотеки bignum Я не могу заставить факториал работать. Если я попрошу его решить 4!, он выдает 96. Он умножается на 4 раза. аналогично, 5! это 600, а не 120. Я не реализовал деление, поэтому я не могу/не хочу делить ответ на число
//bignum project
#include <iostream>
using namespace std;
class bignum
{
public:
int number[100];
int dpos;
int operator/ (bignum);
bignum operator- (bignum);
bignum operator* (bignum);
bignum operator+ (bignum);
bignum operator= (string);
void output()
{
int begin=0;
for(int i=0; i<=99; i++)
{
if(number[i]!=0 || begin==1)
{
cout<<number[i];
begin=1;
}
}
}
};
bool num_is_zero(bignum k)
{
for(int a=0; a<=99; a++)
{
if(k.number[a]!=0)
{
return false;
}
}
return true;
}
bignum factorial(bignum a)
{
bignum j;
bignum fact;
fact="1";
while(!num_is_zero(a))
{
j="1";
fact=fact*a;
a=a-j;
}
return fact;
}
bignum bignum::operator= (string k)
{
int l;
l=k.length()-1;
for(int h=0; h<=99; h++)
{
number[h]=0;
}
for(int a=99; a>=0 && l>=0; a--)
{
number[a]=k[l]-'0';
l--;
}
}
bignum bignum::operator+ (bignum b)
{
bignum a;
int carry=0;
for(int k=0; k<=99; k++)
{
a.number[k]=0;
}
for(int i=99; i>=0; i--)
{
a.number[i]= number[i]+b.number[i]+a.number[i];
if(a.number[i]>9)
{
carry=(a.number[i]/10);
a.number[i-1]+=carry;
a.number[i]=(a.number[i]%10);
}
}
return (a);
}
bignum bignum::operator- (bignum c)
{
bignum a;
int sign=0;
for(int k=0; k<=99; k++)
{
a.number[k]=0;
}
for(int i=99; i>=0; i--)
{
if(number[i]<c.number[i])
{
number[i]+=10;
if(i!=0)
number[i-1]--;
}
a.number[i]=number[i]-c.number[i];
}
return (a);
}
bignum bignum::operator* (bignum b)
{
bignum ans;
int ans_grid[100][100],x,lines=0,carry,sum[100];
for(int a=0; a<=99; a++)
{
for(int b=0; b<=99; b++)
{
ans_grid[a][b]=0;
}
}
for(int i=99; i>=0; i--)
{
for(int j=i,x=99; j>=0; j--,x--)
{
ans_grid[lines][j]=(number[i]*b.number[x]);
}
lines++;
}
//------------------------------------------------Carry Forward and assign to ans------------------------------------------------//
for(int j=99; j>=0; j--)
{
for(int i=99; i>=0; i--)
{
if(ans_grid[j][i]>9 && i!=0)
{
carry=(ans_grid[j][i]/10);
ans_grid[j][i-1]+=carry;
ans_grid[j][i]%=10;
}
}
}
for(int col=99; col>=0; col--)
{
for(int row=99; row>=0; row--)
{
sum[col]+=ans_grid[row][col];
}
}
for(int i=99; i>=0; i--)
{
if(sum[i]>9 && i!=0)
{
carry=(sum[i]/10);
sum[i-1]+=carry;
sum[i]%=10;
}
}
for(int l=0; l<=99; l++)
ans.number[l]=sum[l];
//-------------------------------------------------------------------------------------------------------------------------------//
return (ans);
}
1 ответ:
Я думаю, что ваша проблема в том, что
sumнеинициализирован в вашемoperator*. Я не хочу давать частичный ответ, так как я взял код и немного повозился с ним, поэтому вот моя версия, которая, похоже, работает (и также правильно печатает "0"):Обновление: я не смог удержаться от нескольких структурных улучшений. Я не трогал вашу процедуру умножения, так что вы все равно сможете извлечь исправление, даже если вас не волнует остальное.
#include <iostream> #include <string> #include <algorithm> using namespace std; class bignum { public: int number[100]; bignum() { std::fill(number, number + 100, 0); } bignum(const bignum & other) { std::copy(other.number, other.number + 100, number); } bignum(const std::string &); bignum & operator-=(const bignum &); inline bignum operator-(const bignum & c) const { return bignum(*this) -= c; } bignum operator*(const bignum &) const; inline bignum & operator= (const std::string & k) { return *this = bignum(k); } inline operator bool() const { for (size_t a = 0; a < 100; ++a) if (number[a] != 0) return true; return false; } }; std::ostream & operator<<(std::ostream & o, const bignum & b) { bool begun = false; for (size_t i = 0; i < 100; ++i) { if (begun || b.number[i] != 0) { cout << b.number[i]; begun = true; } } if (!begun) o << "0"; return o; } bignum::bignum(const std::string & k) { std::fill(number, number + 100, 0); for(size_t h = 0; h < std::min(k.length(), 100U); ++h) number[99 - h] = k[k.length() - 1 - h] - '0'; } bignum & bignum::operator-=(const bignum & c) { for (int i = 99; i >= 0; --i) { if (number[i] < c.number[i]) { number[i] += 10; if (i != 0) --number[i-1]; } number[i] -= c.number[i]; } return *this; } bignum bignum::operator*(const bignum & b) const { bignum ans; int ans_grid[100][100], lines = 0, carry, sum[100]; std::fill(sum, sum + 100, 0); for (size_t i = 0; i < 100; ++i) std::fill(ans_grid[i], ans_grid[i] + 100, 0); for(int i=99; i>=0; i--) { for(int j=i,x=99; j>=0; j--,x--) { ans_grid[lines][j]=(number[i]*b.number[x]); } lines++; } //------------------------------------------------Carry Forward and assign to ans------------------------------------------------// for(int j=99; j>=0; j--) { for(int i=99; i>=0; i--) { if(ans_grid[j][i]>9 && i!=0) { carry=(ans_grid[j][i]/10); ans_grid[j][i-1]+=carry; ans_grid[j][i]%=10; } } } for(int col=99; col>=0; col--) { for(int row=99; row>=0; row--) { sum[col]+=ans_grid[row][col]; } } for(int i=99; i>=0; i--) { if(sum[i]>9 && i!=0) { carry=(sum[i]/10); sum[i-1]+=carry; sum[i]%=10; } } for(int l=0; l<=99; l++) ans.number[l]=sum[l]; //-------------------------------------------------------------------------------------------------------------------------------// return (ans); } bignum factorial(bignum a) { bignum j; j = "1"; bignum fact; fact="1"; while(a) { fact = fact * a; a = a-j; } return fact; } int main(int argc, char * argv[]) { if (argc < 2) return 0; bignum a; a = std::string(argv[1]); bignum b = factorial(a); cout << a << std::endl << b << std::endl; }Назначение строки по-прежнему ломается для строк с более чем одной цифрой, но это был не ваш вопрос, я полагаю...