本文共 1952 字，大约阅读时间需要 6 分钟。
问题描述
分子为1 的分数称为埃及分数，现输入一个真分数，请将该分数按下面的方法分解为埃及分数: 1.若真分数的分子a能整除分母b，则真分数经过化简就可以得到埃及分数; 2.若真分数的分子不能整除分母，则可以从原来的分数中分解出一个分母为b/a+1的埃及分数; 3.用这种方法将剩余部分反复分解，最后可得到结果。如：8/11=1/2 + 1/5 + 1/37 + 1/4070。
输入样例：
一个分数如A/B的形式，例如：3/88输出样例：
1/30 + 1/1320问题分析
比如，2/15 一共有 4 种不同的分解法（姑且称为埃及分解法）：
1/8 + 1/120
1/9 + 1/45 1/10 + 1/30 1/12 + 1/20由于埃及分数都是以1为分子的,因此,假设最初的分数为A/B,那么如果A能够整除B,则埃及数为1/(B/A)
如果不能够整除时,能够从其中分离出来的最大的分子为1的分数就是1/((A/B)+1) 以2/7为例,能够从中分离出来的最大的分子为1的数是1/(7/2+1) = 1/4 分离出此数之后,再计算出剩下的余数,重复进行以上的判断即可算法设计
判断a是否为1
是: 直接输出a/b, 退出循环 否: 得到小于它的最大的埃及分数的分母 C = A / B + 1得到余数的分子: A*C-B 得到余数的分母: B*C
返回2继续循环
[运行结果]
请输入一个分数的分子 2 请输入一个分数的分母 45 2/45=1/23+1/1035 可分解为埃及数的个数为: 2算法实现
/* * numerator 代表分子 * denominator 代表分母 * * * 例如: numerator = 2 ; denominator =4 * 2/4 进行约分 * 2/5 进行计算 * * */ public static void egyptFraction(int numerator, int denominator) { int total=0; //计数器 System.out.print(numerator + "/" + denominator + "="); while(true) { /* 如果分子能够整除分母,则对原分数进行约分 , 保持分子为1 */ if (denominator % numerator == 0) { denominator = denominator / numerator; numerator = 1; } /* 分子为1时,直接输出结果,中止循环 */ if (numerator == 1) { System.out.print(numerator + "/" + denominator); total++; break; } else { /* 保留原有的分子与分母的值 */ int d = denominator; int n = numerator; /* 得到比当前分数小的最大埃及分数的分母,并输出找到的最大埃及数 */ int num = denominator / numerator + 1; System.out.print(1 + "/" + num + "+"); total++; /* 得到余数的分子与分母,继续循环 */ denominator = d * num; numerator = n * num - d; } } System.out.println(); System.out.println("可分解为埃及数的个数为: " + total); } （完）
转载地址：http://egvdi.baihongyu.com/