5kyu Some Egyptian fractions

題目背景：

Given a rational number n

as a string (example: “2/3” in Ruby, Python, Clojure, JS, CS, Go) or as two strings (example: “2” “3” in Haskell, Java, CSharp, C++, Swift) decompose this number as a sum of rationals with numerators equal to one and without repetitions (2/3 = 1/2 + 1/6 is correct but not 2/3 = 1/3 + 1/3, 1/3 is repeated).

The algorithm must be “greedy”, so at each stage the new rational obtained in the decomposition must have a denominator as small as possible. In this manner the sum of a few fractions in the decomposition gives a rather good approximation of the rational to decompose.

2/3 = 1/3 + 1/3 doesn’t fit because of the repetition but also because the first 1/3 has a denominator bigger than the one in 1/2 in the decomposition 2/3 = 1/2 + 1/6.

題目分析：

埃及分?jǐn)?shù)是很有趣的一個(gè)數(shù)字的性質(zhì)，本道題本質(zhì)上是數(shù)學(xué)上的問(wèn)題分析，對(duì)于大于1的部分，直接分子除以分母獲取大于1的那部分整數(shù)即可；對(duì)于拆解出的小于1的部分，如果分母可以整除了分子，那么說(shuō)明埃及分?jǐn)?shù)的迭代結(jié)束，而倘若不能夠整除，需要用到貪心思想，去找到最小的分母，譬如 6 / 14， 那么它可以生成的數(shù)里面，最小的分母是 14 / 6 (c++中int 除以 int會(huì)下取整得到int型結(jié)果 ) + 1 = 3 ，于是6 / 14 = 1 / 3 + ((3 * 6) - 14) / (3 * 14) = 1 / 3 + 4 / 42 ，按照這個(gè)思路就可以寫出整個(gè)程序。

AC代碼：

using namespace std;class Decomp{ public:static string decompose(const string &nrStr, const string &drStr); };string Decomp::decompose(const string &nrStr, const string &drStr){long nr = std::stol(nrStr);long dr = std::stol(drStr);if ( nr == 0 || dr == 0 ) return "[]";string res = "[";while ( nr != 0 && dr != 0 ) {if ( nr >= dr ) {res += std::to_string(nr / dr);nr -= (nr / dr) * dr;}else {res += "1/";long tmp;if ( dr % nr == 0 ) tmp = dr / nr;else tmp = dr / nr + 1;res += std::to_string(tmp);nr = nr * tmp - dr;dr = dr * tmp;}res += ", ";}res = res.substr(0, res.size() - 2) + "]";return res; }

總結(jié)

以上是生活随笔為你收集整理的5kyu Some Egyptian fractions的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。