HBC50246小宝的计算机内存,动态规划,过关题目埃及分数题解

云中君 算法基础篇 37 0
想要成为编程高手?那就来试试全网最全C++题库,让您在练习中快速成长。
,表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好,如:。由于方法一与方法二中,最小的分数相同,因此二者均是最优解。

在古埃及,人们使用单位分数的和(形如 dfrac{1}{a} a 1 ​ 的,a是自然数)表示一切有理数。如: dfrac{2}{3}= dfrac{1}{2}+ dfrac{1}{6} 3 2 ​ = 2 1 ​ + 6 1 ​ ,但不允许 dfrac{2}{3}= dfrac{1}{3}+ dfrac{1}{3} 3 2 ​ = 3 1 ​ + 3 1 ​ ,因为加数中有相同的。对于一个分数 dfrac{a}{b} b a ​ ,表示方法有很多种,但是哪种最好呢?首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。如: frac{19}{45}= frac{1}{3}+ frac{1}{12}+ frac{1}{180} 45 19 ​ = 3 1 ​ + 12 1 ​ + 180 1 ​ frac{19}{45}= frac{1}{3}+ frac{1}{15}+ frac{1}{45} 45 19 ​ = 3 1 ​ + 15 1 ​ + 45 1 ​ frac{19}{45}= frac{1}{3}+ frac{1}{18}+ frac{1}{30} 45 19 ​ = 3 1 ​ + 18 1 ​ + 30 1 ​ frac{19}{45}= frac{1}{4}+ frac{1}{6}+ frac{1}{180} 45 19 ​ = 4 1 ​ + 6 1 ​ + 180 1 ​ frac{19}{45}= frac{1}{5}+ frac{1}{6}+ frac{1}{18} 45 19 ​ = 5 1 ​ + 6 1 ​ + 18 1 ​ 最好的是最后一种,因为 dfrac{1}{18} 18 1 ​ 比 dfrac{1}{180}, dfrac{1}{45}, dfrac{1}{30}, dfrac{1}{18} 180 1 ​ , 45 1 ​ , 30 1 ​ , 18 1 ​ 都大。注意,可能有多个最优解。如: frac{59}{211}= frac{1}{4}+ frac{1}{36}+ frac{1}{633}+ frac{1}{3798} 211 59 ​ = 4 1 ​ + 36 1 ​ + 633 1 ​ + 3798 1 ​ frac{59}{211}= frac{1}{6}+ frac{1}{9}+ frac{1}{633}+ frac{1}{3798} 211 59 ​ = 6 1 ​ + 9 1 ​ + 633 1 ​ + 3798 1 ​ 由于方法一与方法二中,最小的分数相同,因此二者均是最优解。 给出a,b,编程计算最好的表达方式。保证最优解满足:最小的分数 ge cfrac{1}{10^7} ≥ 10 7 1 ​ 。

HBC50246小宝的计算机内存,动态规划,过关题目埃及分数题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)
全网最全C++题库,助您挑战自我,突破极限,成为编程领域的佼佼者!

标签: HBC50246小宝的计算机内存 动态规划 过关题目埃及分数题解