Блог пользователя HiCode2009

Автор HiCode2009, история, 2 года назад, По-английски

As we know,each fraction can be expressed as the sum of multiple unit fractions.

$$$\frac{p}{q}=\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_n}$$$

When we want to express a fraction as the sum of multiple unit fractions,we can use a greedy algorithm invented by Fibonacci,subtract the maximum unit fraction which is smaller than this fraction from this fraction.For example,$$$\frac{13}{14}=\frac{1}{2}+\frac{1}{3}+\frac{1}{11}+\frac{1}{231}$$$.

But when we want to find out the minimum value of $$$n$$$,things may be different.Can Fibonacci's greedy algorithm still work?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
2 года назад, # |
Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

Before asking, you should probably check small cases yourself to determine if there is an obvious counterexample.

Trying $$$\frac{1}{4} + \frac{1}{7} = \frac{11}{28}$$$ yields a greedy answer of $$$\frac{11}{28} = \frac{1}{3} + \frac{1}{17} + \frac{1}{1428}$$$, which is not optimal. So the greedy algorithm clearly doesn't work.