PAT 解题报告 1081. Rational Sum (20)

1081. Rational Sum 题目描述:

Given N rational numbers in the form “numerator/denominator”, you are supposed to calculate their sum. 也就是给出N个分数形式的有理数, 求他们的累加和.

1081. Rational Sum 算法分析:

考察的是分数加法, 最大公约数的求法, 最大公约数利用辗转相除就可以获得, 做加法的时候通分求和, 注意通分的过程中还是要利用最大公约数求两次, 一次是求两个分数的最大公约数g1, 然后得到约简以后的分子和t, 再求一次t和g1的最大公约数g2, 计算的过程中就已经要进行约分, 做到最简化, 否则容易溢出什么的. 关键还是最大公约数的求法还有做加法的时候小心溢出问题, 尽量先约分, 不要粗鲁的先求和然后再约简. 可以AC的源代码如下:

#include <exception>
#include <iostream>
#include <cstdio>

class CRationalNumber
{
public:
	CRationalNumber()
	{
		m_llNumeratro = 0;
		m_llDenominator = 1;
	}

	CRationalNumber(long long llNumerator, long long llDenominator, bool bNeedToSimply)
	{
		if (llDenominator < 0)
		{
			m_llNumeratro = -llNumerator;
			m_llDenominator = -llDenominator;
		}
		else
		{
			m_llNumeratro = llNumerator;
			m_llDenominator = llDenominator;
		}
		if (bNeedToSimply)
			this->Simplify();
	}
public:
	CRationalNumber & operator+=(const CRationalNumber &Op2)
	{
		long long g1 = this->GetGCD(this->m_llDenominator, Op2.GetDenominatro());
		if (0 == g1)
		{
			return *this; //  do nothing
		}

		long long t = Op2.GetDenominatro() / g1 * this->GetNumerator() + this->GetDenominatro() / g1 * Op2.GetNumerator();
		long long g2 = this->GetGCD(g1, t);

		this->m_llNumeratro = t / g2;
		this->m_llDenominator = this->GetDenominatro() / g1 * (Op2.GetDenominatro() / g2);
		return *this;
	}

	long long GetNumerator() const
	{
		return m_llNumeratro;
	}

	long long GetDenominatro() const
	{
		return m_llDenominator;
	}
private:
	long long GetGCD(long long llOperandA, long long llOperandB)
	{
		if (llOperandA < 0) llOperandA = -llOperandA;
		if (llOperandB < 0) llOperandB = -llOperandB;

		if (0 == llOperandB)
			return llOperandA;

		long long llRemain = 0;
		while (llRemain = llOperandA % llOperandB)
		{
			llOperandA = llOperandB;
			llOperandB = llRemain;
		}
		return llOperandB;
	}

	void Simplify()
	{
		long long t = GetGCD(m_llNumeratro, m_llDenominator);
		if (!t)
			m_llDenominator = 1;
		else
		{
			m_llNumeratro /= t;
			m_llDenominator /= t;
		}
	}
private:
	long long m_llNumeratro;
	long long m_llDenominator;
};

int main_1081()
{
	int n;
	scanf("%d", &n);
	long long num;
	long long den;

	CRationalNumber result;
	while(n--)
	{
		scanf("%lld/%lld", &num, &den);
		CRationalNumber tmp(num, den, true);
		result += tmp;
	}

	long long integer = result.GetNumerator() / result.GetDenominatro();
	num = result.GetNumerator() % result.GetDenominatro();

	if (integer && num)
		printf("%lld %lld/%lld\n", integer, num, result.GetDenominatro());

	if (integer && !num)
		printf("%lld", integer);

	if (!integer && num)
		printf("%lld/%lld", num, result.GetDenominatro());

	if (!integer && !num)
		printf("0");
	return 0;
}

1081. Rational Sum 注意点:

注意各种特例吧, 正负数, 分子是零, 分母是零, 等等等等.

Written on July 15, 2014