codewars: Some Egyptian fractions

문제 링크입니다: https://www.codewars.com/kata/54f8693ea58bce689100065f/train/cpp

이집트 분수는 일반 분수를 분자가 1인 분수들의 합으로 표현합니다.

예를 들어 4/5=1/2+1/4+1/20으로 표현됩니다.

상당히 흥미로운 주제인데도 불구하고 처음 접했기 때문에 개념이 상당히 어렵게 느껴졌는데 다행히 이에 대해 잘 설명된 포스팅이 있었기 때문에 프로그램을 쉽게 작성할 수 있었습니다.

https://en.wikipedia.org/wiki/Egyptian_fraction <- 영어로 작성되어있지만 이집트 분수에 대해 상세히 설명되어있습니다.

한글로 작성된 글은 아래 링크가 자세히 설명되어있는 것 같습니다! 

http://blog.naver.com/PostView.nhnblogId=forfriend5&logNo=220548077589&parentCategoryNo=12&categoryNo=&viewDate=&isShowPopularPosts=false&from=postView

#include <iostream>

#include <string>

using namespace std;

 

class Decomp

{

public:

        static string decompose(const string &nrStr, const string &drStr);

};

 

//numerator String, denominator String

string Decomp::decompose(const string &nrStr, const string &drStr)

{

        string result = "[";

        long long numerator = atoll(nrStr.c_str());

        long long denominator = atoll(drStr.c_str());

        while (!(numerator==0 || denominator==0))

        {

               if (denominator % numerator == 0) //분자가 분모로 나누어진다면 ex) 12/24

               {

                       result += "1/";

                       result += to_string(denominator / numerator);

                       return result += "]";

               }

               if (numerator % denominator == 0) //분수가 아니라 양의 정수라면

               {

                       result += to_string(numerator / denominator);

                       return result += "]";

               }

               if (numerator > denominator) //분자가 분모보다 큰 경우(대분수로 만듬)

               {

                       result += to_string(numerator / denominator);

                       numerator %= denominator;

                       result += ", ";

                       continue;

               }

               //(분자/분모)의 upper_bound

               long long newDenominator = (denominator / numerator) + 1;

               result += "1/";

               result += to_string(newDenominator);

               result += ", ";

               //이집트 분수 공식대로 진행

               numerator = (numerator*newDenominator) - denominator;

               denominator *= newDenominator;

        }

        if(result.length()>2) //0과 0이 입력된 경우 고려

               for(int i=0; i<2; i++)

                       result.pop_back(); //마지막 쉽표와 공백 삭제

        result += "]";

        return result;

}

 

int main(void)

{

        cout << Decomp::decompose("3", "4") << endl;

        cout << Decomp::decompose("12", "4") << endl;

        cout << Decomp::decompose("4", "5") << endl;

        cout << Decomp::decompose("66", "100") << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~