将真分数分解为埃及分数

[编程题]将真分数分解为埃及分数

热度指数：77919 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

分子为1的分数称为埃及分数。现输入一个真分数(分子比分母小的分数，叫做真分数)，请将该分数分解为不同的埃及分数。如：8/11 = 1/2+1/5+1/55+1/110。

注：真分数指分子小于分母的分数，分子和分母有可能gcd不为1！

如有多个解，请输出任意一个。

输入描述:

输入一个真分数，String型

输出描述:

输出分解后的string

示例1

输入

8/11
2/4

输出

1/2+1/5+1/55+1/110
1/3+1/6

说明

第二个样例直接输出1/2也是可以的

算法知识视频讲解

Javascript

dalejace

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

function gcd(a,b){
  if(a % b === 0){
     return b;
  }
  return gcd(b, a%b);
}

rl.on('line', function(line){
    let [num1, num2] = line.split('/').map(e=>Number(e));
    let trade = 0;
    let maxGcd  = 0;
    const ans = [];
    while(num1 > 1){
      trade = Math.floor(num2/num1) +1;
      ans.push('1/' + trade);
        
      num1 = num1 * trade - num2;
      num2 = num2 * trade;
      
      maxGcd = gcd(num1, num2);
      if(maxGcd > 1){
         num1 = num1 / maxGcd;
         num2 = num2 / maxGcd;
      }
    }
    ans.push('1/' + num2);
    console.log(ans.join('+'));
});

发表于 2022-06-27 11:32:14 回复(0)

Javascript

Z＆S

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
rl.on('line', function (line) {
    let z = parseInt(line.split('/')[0]);
    let m = parseInt(line.split('/')[1]);
    
    let arr =[];
    fn(z,m,arr);

    console.log(arr.join('+'))
});

function fn (z,m,arr){
   if(m % z === 0){
       arr.push('1/'+(m/z));
       return ;
   }else {
        let f = parseInt(m/z)+1;
        arr.push('1/'+f);
        z = z*f - m;
        m = m*f;
       fn(z,m,arr)
   }
}

发表于 2022-04-29 15:16:34 回复(0)

JavaScript

小太阳照亮明天

/**
 * Created by dcp on 2018/7/2.
 */


// 准确的算法表述应该是这样的：
// 设某个真分数的分子为a，分母为b;
// 把c=(b/a+1)作为分解式中第一个***分数的分母；
// 将a-b%a作为新的a；
// 将b*c作为新的b；
// 如果a等于1，则最后一个***分数为1/b,算法结束；
// 如果a大于1但是a能整除b，则最后一个***分数为1/(b/a),算法结束；
// 否则重复上面的步骤。
var readline = require('readline');

rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

var inputs = [];
rl.on('line', function(data) {
    inputs=data.split('/');
    if(inputs.length===2){
        var a=inputs[0];
        var b=inputs[1];
        console.log(toEgpty(a,b));
        inputs.length=0;

    }



});

function toEgpty(a,b) {
    var arr1=[];
    while (a!==1){
        if(b%(a-1)==0){
            var t=parseInt(b/(a-1))
            arr1.push(1);
            arr1.push('/');
            arr1.push(t);
            arr1.push('+');
            a=1;
        }else {
            var c=parseInt(b/a+1);
            arr1.push(1);
            arr1.push('/');
            arr1.push(c);
            arr1.push('+');
            a=a-b%a;
            b=b*c;
            if(b%a==0){
                b=b/a;
                a=1;
            }
        }


    }
    arr1.push(a);
    arr1.push('/');
    arr1.push(b);
    return arr1.join('');

}

编辑于 2018-07-02 20:24:15 回复(4)