Консультации Портала - Консультация #179756

Задать вопрос Консультации Пользователи Форум

Задать вопрос экспертам

Консультация № 179756

21.08.2010, 22:46

0.00 руб.

0 1 1

Компьютеры Программирование

Здравствуйте!
ЗАДАНИЕ: Числовой ребус. Написать программу решения числового ребуса, заданного в виде умножения столбиком, где часть цифр заменена звездочками.

пример

1*
*
1*3
--------
33
+
**
+
*1
-------
1*53
программа должна решить его:

11
*
123
--------
33
+
22
+
11
-------
1353

НАДО ИСПРАВИТЬ: программа должна подставлять последовательно цифры только вместо звездочек, которые есть в множителях (в данном примере в числа 1* и 1*3) и сравнивать с числами в сумме и произведении (33,**,*1,1*53 - здесь вместо звездочек цифры подставлять не надо). количество цифр в множителях может быть любым.

Приложение : Здесь цифры подставляются вместо всех звездочек

Приложение:
#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <malloc.h>

using namespace std;

typedef struct _STAR //структура для хранения информации о "звездочке"
{
int iNum; //0,1,2,... - номер числа, в котором звездочка
int iMulNum; //"вес" цифры (1, 10, 100, 1000, 10000)
int iFirst; //0 или 1 - с какой цифры начинаем цикл (первая не может быть = 0)
int i; //текущее значение цифры в позиции звездочки
}STAR, *PSTAR;

//разбираем строку шаблона числа
//параметры:

//pStars - адрес указателя на массив структур STAR
//piMuls - адрес массива известных значений чисел
//piCount - адрес переменной, в которой количество звездочек
//pStr - адрес строки шаблона числа
//idx - индекс разбираемой строки
//На выходе: 1 - все в порядке, 0 - неправильный формат (разрешены только цифры и *)
int FormData(STAR **pStars, int * piMuls, int * piCount, char *pStr, int idx)
{
int i, k;
int iLen = strlen(pStr); //длина строки
int iStart = *piCount; //начальная позиция в массиве STAR для расчета "веса"
//для текущей строки
char pBuf[16]; //буфер для числовой строки (звездочки менянм на 0)
//для получения известного значения числа
for (i=0; i<iLen; i++) //по всем символам строки
{
for (k=iStart; k<(*piCount); k++) //увеличим "вес" предыдущих звездочек
(*pStars)[k].iMulNum *= 10; //числа в 10 раз

if (pStr[i] == '*') //"звкздочка"?
{
pBuf[i] = '0'; //меняем на 0
//добавляем память под очередной элемент массива структур STAR
(*pStars) = (STAR*)realloc((*pStars),((*piCount)+1)*sizeof(STAR));
//если * - первый символ, то 1, если * - непервый символ, то 0
(*pStars)[*piCount].iFirst = (i==0);
//номер числа
(*pStars)[*piCount].iNum = idx;
//"вес" звездочки
(*pStars)[(*piCount)++].iMulNum = 1;
}
else if (isdigit(pStr[i])) //цифра?
pBuf[i] = pStr[i]; //в буфер
else
return 0; //иначе - ошибка
}
pBuf[i] = 0; //закрываем строку нулем
*(piMuls+idx) = atoi(pBuf); //преобразуем в число и сохраним в массиве
//известных значений чисел
return 1; //все ок
}

int main(int argc, char* argv[])
{
long *num = (long *)malloc(3 * sizeof (long)); //массив для расчета чисел
int i,j,k;
int iSumCount; //число цифр второго множителя (число слагаемых в столбик)
int iSolutions; //количество найденных наборов
int iCount; //количество звездочек
int *iMuls = (int *)malloc(3 * sizeof (int)); //массив известных значений чисел
int iRet; //для контроля прохода всех вариантов
STAR *stars=NULL; //указатель на массив структур STAR
//с информацией о звездочках

locale::global(locale("Russian_Russia.866")); //чтобы писалось по-русски

char sStr[80]; //буфер для ввода строки

while (1) //бесконечный цикл ввода и расчета
{
iCount = 0; //счетчик звездочек
while (1) //бесконечный цикл ввода первого множителя
{
wcout << L"Введите первый множитель (пустая строка - выход): ";
cin.getline((char*)sStr,80);
if (strlen((char*)sStr) == 0) //проверка на выход
return 0;
//преобразуем, если все ок, то идем дальше
if (FormData(&stars, iMuls, &iCount, (char*)sStr, 0))
break;
wcout << L"Ошибка ввода"<<endl;
}

while (1) //аналогично для второго множителя
{
wcout << L"Введите второй множитель (пустая строка - выход): ";
cin.getline((char*)sStr,80);
if (strlen((char*)sStr) == 0)
return 0;
if (FormData(&stars, iMuls, &iCount, (char*)sStr, 1))
break;
wcout << L"Ошибка ввода"<<endl;
}

iSumCount = strlen(sStr);
num = (long *)realloc(num, (3 + iSumCount) * sizeof(long));
iMuls = (int *)realloc(iMuls, (3 + iSumCount) * sizeof(int));

for (i=0; i<iSumCount; i++)
{
while (1) //аналогично для слагаемых
{
wcout << L"Введите " << i+1 << L"-е слагаемое (пустая строка - выход): ";
cin.getline((char*)sStr,80);
if (strlen((char*)sStr) == 0)
return 0;
if (FormData(&stars, iMuls, &iCount, (char*)sStr, 3+i))
break;
wcout << L"Ошибка ввода"<<endl;
}
}

while (1) //и произведения
{
wcout << L"Введите произведение (пустая строка - выход): ";
cin.getline((char*)sStr,80);
if (strlen((char*)sStr) == 0)
return 0;
if (FormData(&stars, iMuls, &iCount, (char*)sStr, 2))
break;
wcout << L"Ошибка ввода"<<endl;
}

//начинаем расчет
iSolutions = 0; //число наборов

wcout << L"Найденные числа:" << endl;

for(i=0; i<iCount; i++) //инициализируем начальное значение цифр
stars[i].i = stars[i].iFirst;

do //цикл по всем вариантам
{
iRet = 0; //переменная проверки прохода всех вариантов
for(i=0; i<3+iSumCount; i++)//начинаем с известных значений
num[i] = iMuls[i];

for(i=0; i<iCount; i++) //добавляем для всех звездочек
{ //произведение цифры на "вес"
iRet += stars[i].i; //складываем все "звездочные" цифры
num[stars[i].iNum] += stars[i].iMulNum * stars[i].i;
}

if (num[0] * num[1] == num[2]) //проверяем условие
{ //проверим совпадение слагаемых
//умножаем на цифры второго множителя и сравниваем с соотв слагаемым
for (j=k=0,i=num[1]; k<iSumCount; k++,i/=10)
j+=((num[0] * (i%10)) == num[3+k]); //j - число совпадений
if (j == iSumCount) //равно числу цифр - нашли набор!!! - выведем
{
cout << num[0] << " * " << num[1] << " = ";
for (i=0; i<iSumCount-1; i++)
cout << num[3+i] << " + ";
cout << num[3+i] << " = " << num[2] << endl;
iSolutions++; //сосчитаем
}
}

for(i=0; i<iCount; i++) //перейдем на следующий набор
{
if (++(stars[i].i) < 10)
break;
stars[i].i = stars[i].iFirst;
}

} while(iRet!=9*iCount); //выйдем. когда дойдем до всех девяток

if (iSolutions == 0) //если ничего не нашли
wcout << L"Решение не найдено" << endl;
cout << endl;
}

if (stars)
free(stars); //освободим память
if (num)
free(num);
return 0;
}

Обсуждение

Неизвестный

22.08.2010, 08:13

общий

это ответ

Здравствуйте, Миронычев Виталий.
Слегка модифицированная программа из ответа 173775. Тестировал MS VS 2010.

Код:

#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 вариантов ответов

Форма ответа

Отправка постов/ответов доступна только зарегистрированным и подтвержденным пользователям.

Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.