1、问题描述java
把一个真分数表示成最少的埃及分数之和。算法
埃及分数即分子为1的分数。测试
2、问题分析spa
一、贪心算法的思想在本问题中的体现为在每一步的分解中都寻找最大的埃及分数。.net
二、具体步骤以下code
步骤一blog
假设真分数N/M的分子为N，分母为M，则有下式成立rem
M = K * N + Z，其中Z必小于Nget
两边同时除以分子N后，可知io
M/N = K + Z/N < K + 1
因此，必有下式成立
N/M > 1/K+1
因此，小于真分数N/M的最大埃及分数为1/K+1。
步骤二
下一步再寻找N/M - 1/K+1的最大埃及分数，通分后也即寻找真分数(N*(K+1) - M)/M*(K+1)的最大埃及分数。
在开始以前，须要先把(N*(K+1) - M)/M*(K+1)约分，也即寻找分子与分母的最大公约数，详见博文两正整数最大公约数。
约分以后再按步骤一的解法寻找最大埃及分数。
步骤三
步骤一和步骤二循环执行，直到分子为1。
3、算法代码
public void egyptFraction(int num1, int num2){
int trade = 0;
int maxComDiv = 0;
while(num1 > 1){
trade = num2 / num1 + 1;
System.out.println(1 + "/" + trade);
num1 = num1 * trade - num2;
num2 = num2 * trade;
maxComDiv = maxComDiv(num1, num2);
if(maxComDiv > 1){
num1 = num1 / maxComDiv;
num2 = num2 / maxComDiv;
}
}
System.out.println(1 + "/" + num2);
}
public int maxComDiv(int num1, int num2) {
int remaind = 0;
while(num2 != 0){
remaind = num1 % num2;
num1 = num2;
num2 = remaind;
}
return num1;
}
4、完整测试代码
public class Solution {
public static void main(String [] args){
int nums1 = 2;
int nums2 = 3;
egyptFraction(nums1, nums2);
}
public static void egyptFraction(int num1, int num2){
int trade = 0;
int maxComDiv = 0;
while(num1 > 1){
trade = num2 / num1 + 1;
System.out.println(1 + "/" + trade);
num1 = num1 * trade - num2;
num2 = num2 * trade;
maxComDiv = maxComDiv(num1, num2);
if(maxComDiv > 1){
num1 = num1 / maxComDiv;
num2 = num2 / maxComDiv;
}
}
System.out.println(1 + "/" + num2);
}
public static int maxComDiv(int num1, int num2) {
int remaind = 0;
while(num2 != 0){
remaind = num1 % num2;
num1 = num2;
num2 = remaind;
}
return num1;
}
}
5、运行结果
1/2
1/3
1/24
