题解 | #将真分数分解为埃及分数#

using System;
using System.Collections.Generic;
using System.Text;

namespace HJ82
{

    public class TrueFraction
    {
        //分子
        public int M { get; set; }

        //分母
        public int N { get; set; }


        public TrueFraction(int m, int n)
        {
            int gcd = GetGCD(m, n);
            if (gcd != 1)
            {
                M = m / gcd;
                N = n / gcd;
            }
            else
            {
                M = m;
                N = n;
            }
        }

        /// <summary>获取两个数的最大公约数</summary>
        private int GetGCD(int a, int b)
        {
            if (a <= 1 || b <= 1)
            {
                return 1;
            }

            int max;
            int min;

            while (true)
            {
                if (a >= b)
                {
                    max = a;
                    min = b;
                }
                else
                {
                    max = b;
                    min = a;
                }
                if (max % min == 0)
                {
                    return min;
                }
                a = max % min;
                b = min;
            }
        }


        /// <summary>
        /// 此方法可以输出埃及真分数个数最小，因为每次分配都是优先将大的分子去分配的
        /// </summary>
        public string GetEgyptString()
        {
            if (M == 1)
            {
                return $"{M}/{N}";
            }

            StringBuilder sb = new StringBuilder();

            //为什么分子分母都放大N-1倍：
            //因为对于一个真分数，他的分子最大只能是N-1，
            //M/N最小的可操作真分数为1/ N * (N - 1),我们在这个最小可操作真分数上进行组合；
            int newN = N * (N - 1);

            int sum = M * (N - 1);

            //一定有解，对于任意sum, sum/newN 最差的解决方案就是 sum个1/newN 相加
            while (true)
            {
                //当sum==0时，所有分子已经分配完毕
                if (sum == 0)
                {
                    break;
                }
                if (sum == 1)
                {
                    sb.Append($"{1}/{newN}");
                    break;
                }
                // 从最大的开始分配，分配完需要减去
                for (int i = sum; i > 0; i--)
                {
                    if (newN % i == 0)
                    {
                        //分子i/i=1;
                        int m = 1;
                        //分母
                        int n = newN / i;
                        sb.Append($"{m}/{n}+");
                        sum -= i;
                        break;
                    }
                }
            }
            return sb.ToString().TrimEnd('+');

        }

    }


    internal class Program
    {
        static void Main(string[] args)
        {
            List<TrueFraction> fractions = new List<TrueFraction>();

            while (true)
            {
                string str = Console.ReadLine();
                if (string.IsNullOrEmpty(str))
                {
                    break;
                }
                string[] strings = str.Split('/');
                int m = int.Parse(strings[0]);
                int n = int.Parse(strings[1]);
                fractions.Add(new TrueFraction(m, n));
            }

            foreach (var f in fractions)
            {
                Console.WriteLine(f.GetEgyptString());
            }
        }
    }
}