#include <iostream>
#include <iomanip>
#include <locale>
#include <limits>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;
// Класс число
class number
{
private:
typedef unsigned char _itemType;
typedef vector<_itemType> _byteVector;
explicit number(_byteVector digits);
// Цифры числа
_byteVector _digits;
// Позиции звездочек
_byteVector _stars;
template<class _Elem,class _Traits> friend basic_istream<_Elem,_Traits>& operator>>(basic_istream<_Elem,_Traits>& stream,number& right);
template<class _Elem,class _Traits> friend basic_ostream<_Elem,_Traits>& operator<<(basic_ostream<_Elem,_Traits>& stream,const number& right);
public:
number(){};
// Следующая подстановка
bool next();
// Операторы
bool operator==(const number& right) const;
number operator*(const number& right) const;
// Кол. цифр
_byteVector::size_type length(void) const;
// Возвращает требуемую цифру числа
number operator[](_byteVector::size_type index) const;
};
// Оператор ввода
template<class _Elem,class _Traits>
basic_istream<_Elem,_Traits>& operator>>(basic_istream<_Elem,_Traits>& stream,number& right)
{
typedef basic_string<_Elem,_Traits> _strType;
_strType str;
stream>>str;
if(!stream.fail())
{
const ctype<_Elem>& facet=use_facet<ctype<_Elem> >(stream.getloc());
const _Elem zero=facet.widen('0');
_strType::size_type notZero=str.find_first_not_of(zero);
if(notZero==_strType::npos)
{
notZero=str.length()-1;
}
str.erase(0,notZero);
_strType::size_type index=str.length();
number::_byteVector digits,stars;
bool success=true;
while(index-- && success)
{
_Elem ch=str[index];
if(facet.is(facet.digit,ch))
{
digits.push_back(ch-zero);
}
else if(ch==facet.widen('*'))
{
digits.push_back(index==0);
stars.push_back(digits.size()-1);
}
else
{
success=false;
}
}
if(success)
{
right._digits=digits;
right._stars=stars;
}
else
{
stream.setstate(stream.badbit);
}
}
return stream;
}
// Оператор вывода
template<class _Elem,class _Traits>
basic_ostream<_Elem,_Traits>& operator<<(basic_ostream<_Elem,_Traits>& stream,const number& right)
{
basic_stringstream<_Elem,_Traits> sstr;
for(number::_byteVector::const_reverse_iterator it=right._digits.rbegin(),end=right._digits.rend();it!=end;++it)
{
sstr<<static_cast<unsigned int>(*it);
}
return stream<<sstr.str();
}
number input(const char* const msg);
typedef vector<number> num_vec;
int main()
{
setlocale(LC_ALL,"russian");
// Вводим данные
number num1=input("Первый множитель:"),
num2=input("Второй множитель:");
const size_t width=num1.length()+num2.length();
const string line(width,'-');
num_vec summand(num2.length());
for(num_vec::size_type i=0;i<summand.size();++i)
{
cout<<i+1;
summand[i]=input("-я сумма:");
}
number num3=input("Произведение:");
// Счетчик найденных решений
size_t count=0;
do
{
do
{
// Умножаем
number mult=num1*num2;
// Сравниваем
if(mult==num3)
{
// Проверка промежуточных сумм
bool isOk=true;
for(num_vec::size_type i=0;i<num2.length() && isOk;++i)
{
isOk=num2[i]*num1==summand[i];
}
// Решение найдено - выводим
if(isOk)
{
cout<<setw(width)<<num1<<endl
<<'*'<<endl
<<setw(width)<<num2<<endl
<<line<<endl;
for(num_vec::size_type i=0;i<num2.length();++i)
{
cout<<(i?"+\n":"")<<setw(width-i)<<num2[i]*num1<<endl;
}
cout<<line<<endl
<<setw(width)<<mult<<endl<<endl;
++count;
}
}
}while(num2.next()); // Следующий вариант
}while(num1.next()); // Следующий вариант
if(count)
{
cout<<"Найдено "<<count<<" вариантов ответов"<<endl;
}
else
{
cout<<"Решение не найдено"<<endl;
}
system("PAUSE");
return 0;
}
// Ввод числа
number input(const char* const msg)
{
while(true)
{
cout<<msg;
number result;
cin>>result;
if(cin.fail())
{
cout<<"Ошибочный ввод"<<endl;
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(),'\n');
}
else
{
cin.ignore(numeric_limits<streamsize>::max(),'\n');
return result;
}
}
}
// Генерирует следующий вариант.
// Возвращает false когда все варианты перебраны
bool number::next()
{
for(_byteVector::const_iterator it=_stars.begin(),end=_stars.end();it!=end;++it)
{
_itemType digit=_digits[*it]+1;
if(digit>9)
{
_digits[*it]=*it==(_digits.size()-1);
}
else
{
_digits[*it]=digit;
return true;
}
}
return false;
}
// Оператор равенства
bool number::operator==(const number& right) const
{
_byteVector::size_type size=min(_digits.size(),right._digits.size()),index=0;
bool result=true;
while(index<size && result)
{
// Не учитываем места расположения звездочек
if(find(_stars.begin(),_stars.end(),index)==_stars.end() &&
find(right._stars.begin(),right._stars.end(),index)==right._stars.end())
{
result=_digits[index]==right._digits[index];
}
++index;
}
size=max(_digits.size(),right._digits.size());
while(index<size && result)
{
result=find(_stars.begin(),_stars.end(),index)!=_stars.end() ||
find(right._stars.begin(),right._stars.end(),index)!=right._stars.end();
++index;
}
return result;
}
number::number(number::_byteVector digits)
:_digits(digits)
{
}
// Оператор умножения
// Использует длинную арифметику
number number::operator*(const number& right) const
{
_byteVector resultData(_digits.size()+right._digits.size(),0);
for(_byteVector::size_type i=0,end=right._digits.size();i<end;++i)
{
_itemType digit=right._digits[i];
_byteVector tmpVector(_digits.size());
unsigned int carry=0;
for(_byteVector::size_type j=0,end=_digits.size();j<end;++j)
{
unsigned int tmp=_digits[j]*digit+carry;
carry=tmp/10;
tmpVector[j]=tmp%10;
}
if(carry)
{
tmpVector.push_back(carry);
carry=0;
}
for(_byteVector::size_type j=0,end=tmpVector.size();j<end;++j)
{
unsigned int tmp=resultData[i+j]+tmpVector[j]+carry;
carry=tmp/10;
resultData[i+j]=tmp%10;
}
if(carry)
{
_byteVector::size_type index=tmpVector.size()+i;
if(index<resultData.size())
{
resultData[index]=carry;
}
else
{
resultData.push_back(carry);
}
}
}
// Удалим ведущие нули. Если есть.
while(!resultData.back() && resultData.size()>1)
{
resultData.pop_back();
}
return number(resultData);
}
// Кол. цифр
number::_byteVector::size_type number::length(void) const
{
return _digits.size();
}
// Возвращает требуемую цифру числа
number number::operator[](_byteVector::size_type index) const
{
return number(_byteVector(1,_digits[index]));
}
Первый множитель:1*
Второй множитель:1*3
1-я сумма:33
2-я сумма:**
3-я сумма:*1
Произведение:1*53
11
*
123
-----
33
+
22
+
11
-----
1353
Найдено 1 вариантов ответов
Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.