UsefullCode.net

分数の約分をしたいときは最初に分母と分子から共通因子を取り出す。ここでは共通因子を取り出す方法として素因数分解を利用した。分母、分子を素因数分解し、共通して含まれる素因数を消去することで約分した。

約分の過程で用いた素因数分解処理用のクラスと関数は「数値を素因数分解する」と同じものを利用している。

#include "math.h"
#include "atlcoll.h"
#include "atlstr.h"



class	CElementInfo
{
public:
	long	_nElement;
	ULONG	_nCount;

	CElementInfo()
	{
		_nElement = 0;
		_nCount = 0;
	}

	CElementInfo(long nElement,ULONG nCount)
	{
		_nElement = nElement;
		_nCount = nCount;
	}

	CElementInfo&	operator++()
	{
		_nCount++;
		return	*this;
	}
	CElementInfo&	operator++(int)
	{
		_nCount++;
		return	*this;
	}

	CElementInfo&	operator--()
	{
		if(_nCount)
			_nCount--;
		return	*this;
	}
	CElementInfo&	operator--(int)
	{
		if(_nCount)
			_nCount--;
		return	*this;
	}
};



//
//	素因数分解
//
bool	Digest(long nData,CAtlArray<CElementInfo>* pacElements)
{
	long	nElement;
	ULONG	nCount;
	long	nLoopMax;

	if(pacElements == NULL)
		return	false;
	pacElements->RemoveAll();

	//負の数なら素因数として-1を与える
	if(nData < 0)
	{
		pacElements->Add(CElementInfo(-1,1));
		nData *= -1;
	}
	if(nData == 0 || nData == 1)
		return	true;

	nLoopMax = (long)sqrt((double)nData) + 1;
	for(nElement = 2; nElement <= nLoopMax; nElement += 2)
	{
		if(nElement == 4)	//2で素因数分解を１回行った後は3,5,7...2n+1で処理を
			nElement--;	//行なうように4のときに1を減算

		nCount = 0;
		while(1)
		{
			if(nData % nElement)
				break;

			nCount++;
			nData /= nElement;
		}
		if(nCount > 0)
			pacElements->Add(CElementInfo(nElement,nCount));
		if(nData == 1)
			break;
	}
	if(nData > 1)
		pacElements->Add(CElementInfo(nData,1));

	return	true;
}


//
//	約分
//
//nDenominator	：分母
//nNumerator	：分子
//
bool	Reduction(long nDenominator,long nNumerator,CAtlArray<CElementInfo>* pacDenominatorElements,CAtlArray<CElementInfo>* pacNumeratorElements)
{
	CAtlArray<CElementInfo>*	pA;
	CAtlArray<CElementInfo>*	pB;

	if(pacDenominatorElements)
		pacDenominatorElements->RemoveAll();
	if(pacNumeratorElements)
		pacNumeratorElements->RemoveAll();
	if(pacNumeratorElements == NULL || pacDenominatorElements == NULL)
		return	false;

	if(nDenominator == 0 || nNumerator == 0)
		return	true;
	if(nDenominator == -1)
	{
		//分母が-1だったら、分子に-1をかけて終わり
		nDenominator = 1;
		nNumerator *= -1;
		return	true;
	}
	if(nDenominator == 1 || nNumerator == 1)
		return	true;


	///////////////////////////////
	//約分前処理
	//

	if(nDenominator < 0)
	{
		//分母がマイナスだったら分子にマイナス記号を移す
		nDenominator *= -1;
		nNumerator *= -1;
	}

	//分母・分子ともに素因数分解
	Digest(nDenominator,pacDenominatorElements);
	Digest(nNumerator,pacNumeratorElements);

	//素因数の数が少ない方をpA、多い方をpBにする
	if(pacDenominatorElements->GetCount() < pacNumeratorElements->GetCount())
	{
		pA = pacDenominatorElements;
		pB = pacNumeratorElements;
	}
	else
	{
		pA = pacNumeratorElements;
		pB = pacDenominatorElements;
	}


	///////////////////////////////
	//約分処理
	//
	size_t	i;
	size_t	j;
	size_t	nSizeA;
	size_t	nSizeB;

	i = 0;
	nSizeA = pA->GetCount();
	nSizeB = pB->GetCount();
	for(j = 0; j < nSizeB; j++)
	{
		for(; i < nSizeA; i++)
		{
			if((*pA)[i]._nElement < (*pB)[j]._nElement)
				continue;
			if((*pA)[i]._nElement > (*pB)[j]._nElement)
				break;

			//共通する素因数の数だけnCountを減らす
			if((*pA)[i]._nCount < (*pB)[j]._nCount)
			{
				(*pB)[j]._nCount -= (*pA)[i]._nCount;
				(*pA)[i]._nCount = 0;
			}
			else if((*pA)[i]._nCount > (*pB)[j]._nCount)
			{
				(*pA)[i]._nCount -= (*pB)[j]._nCount;
				(*pB)[j]._nCount = 0;
			}
			else
			{
				(*pA)[i]._nCount = 0;
				(*pB)[j]._nCount = 0;
			}
			break;
		}
	}

	return	true;
}


//
//	約分
//
//nDenominator	：分母
//nNumerator	：分子
//
bool	Reduction(long& nDenominator,long& nNumerator)
{
	bool	ret;
	CAtlArray<CElementInfo>		acElementsA;
	CAtlArray<CElementInfo>		acElementsB;

	///////////////////////////////
	//約分
	//
	ret = Reduction(nDenominator,nNumerator,&acElementsA,&acElementsB);
	if(ret == false)
		return	false;


	///////////////////////////////
	//約分結果の数値計算
	//
	size_t	i;
	size_t	j;
	size_t	nSizeI;
	size_t	nSizeJ;

	nDenominator = 1;
	nSizeI = acElementsA.GetCount();
	for(i = 0; i < nSizeI; i++)
	{
		nSizeJ = acElementsA[i]._nCount;
		for(j = 0; j < nSizeJ; j++)
			nDenominator *= acElementsA[i]._nElement;
	}

	nNumerator = 1;
	nSizeI = acElementsB.GetCount();
	for(i = 0; i < nSizeI; i++)
	{
		nSizeJ = acElementsB[i]._nCount;
		for(j = 0; j < nSizeJ; j++)
			nNumerator *= acElementsB[i]._nElement;
	}

	return	true;
}




bool	Test()
{
	long	nA;
	long	nB;

	CAtlString	strBuff;
	CAtlString	strMessage;

	nA = 384;
	nB = 96;

	strBuff.Format(_T("%d／%d ＝ "),nB,nA);
	strMessage += strBuff;

	//約分
	Reduction(nA,nB);

	strBuff.Format(_T("%d／%d"),nB,nA);
	strMessage += strBuff;

	::MessageBox(NULL,strMessage,_T("結果"),MB_OK);

	return	true;
}

プロジェクトファイルをダウンロード