首页 > 试题广场 >

Rational Sum (20)

[编程题]Rational Sum (20)
  • 热度指数:8870 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
Given N rational numbers in the form "numerator/denominator", you are supposed to calculate their sum.

输入描述:
Each input file contains one test case. Each case starts with a positive integer N (<=100), followed in the next line N rational numbers "a1/b1 a2/b2 ..." where all the numerators and denominators are in the range of "long int".  If there is a negative number, then the sign must appear in front of the numerator.


输出描述:
For each test case, output the sum in the simplest form "integer numerator/denominator" where "integer" is the integer part of the sum, "numerator" < "denominator", and the numerator and the denominator have no common factor.  You must output only the fractional part if the integer part is 0.
示例1

输入

5
2/5 4/15 1/30 -2/60 8/3

输出

3 1/3

python solution,使用Fraction库,真简单。看了一下大家的解法,也就这个代码量最少了:

from fractions import Fraction
a,b,res=input(),input().split(),Fraction(0)
for i in b:
    res+=Fraction(i)
if res.numerator<res.denominator:
    print(res)
else:
    aa=res.numerator//res.denominator
    bb=res.numerator%res.denominator
    print(str(aa)+" "+str(bb)+"/"+str(res.denominator))
编辑于 2017-10-09 09:45:51 回复(0)
#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <string>

using namespace std;

typedef struct {
    long numerator;
    long denominator;
}Fraction;

int getLCM(int num1, int num2) { //求最小公倍数
    int r;
    if (num1 < num2) {
        int temp = num1;
        num1 = num2;
        num2 = temp;
    }
    int m = num1;
    int n = num2;
    while ((r = m % n) != 0) {
        m = n;
        n = r;
    }
    return abs(num1 * num2 / n);
}

int getGCD(int num1, int num2) { //求最大公约数
    int m, n, r;
    if (num1 < num2) {
        int temp = num1;
        num1 = num2;
        num2 = temp;
    }
    m = num1;
    n = num2;
    while((r = m % n) != 0) {
        m = n;
        n = r;
    }
    return abs(n);
}

int main() {
    int count = 0;
    cin >> count;
    Fraction* data = (Fraction*)malloc(count * sizeof(Fraction));
    for (int i = 0; i < count; i++) {
        string input;
        long num, deno;
        cin >> input;
        int separator = input.find('/');
        string s_num = input.substr(0, separator);
        string s_deno = input.substr(separator + 1);
        num = atol(s_num.c_str());
        deno = atol(s_deno.c_str());
        data[i].numerator = num;
        data[i].denominator = deno;
    }
    /*
    for (int i = 0; i < count; i++) {
        cout << i + 1 << ": " << data[i].numerator << "/" << data[i].denominator << endl;
    }
    */
    Fraction current = data[0];
    for(int i = 1; i < count; i++) {
        int LCM = getLCM(current.denominator, data[i].denominator);
        int mulLeft = LCM / current.denominator;
        int mulRight = LCM / data[i].denominator;
        current.numerator = current.numerator * mulLeft + data[i].numerator * mulRight;
        current.denominator = LCM;
    }
    //cout << "Result: " << current.numerator << "/" << current.denominator << endl;
    if (current.numerator == 0) {
        cout << 0 << endl;
        return 0;
    }
    int GCD = getGCD(current.numerator, current.denominator);
    current.numerator /= GCD;
    current.denominator /= GCD;
    int integer = 0;
    if (current.numerator != 0) {
        integer = current.numerator / current.denominator;
    }
    current.numerator %= current.denominator;
    int flag;
    if (current.numerator < 0) {
        flag = -1;
    } else if (current.numerator == 0){
        flag = 0;
    } else if (current.numerator > 0) {
        flag = 1;
    }
    if (flag == -1) {
        if (integer != 0)
            cout << "-" << integer << " " << abs(current.numerator) << "/" << current.denominator << endl;
        else
            cout << "-" << abs(current.numerator) << "/" << current.denominator << endl;
    } else if (flag == 1) {
        if (integer != 0)
            cout << integer << " " << current.numerator << "/" << current.denominator << endl;
        else
            cout << current.numerator << "/" << current.denominator << endl;
    } else if (flag == 0) {
        cout << integer << endl;
    }

    return 0;
}

发表于 2020-09-13 10:51:07 回复(0)
#include<cstdio>
#include<iostream>
using namespace std;
int n, a, b,c,d;
int gcd(int x, int y)
{
    return y == 0 ? x : gcd(y, x%y);
}
int lcm(int x, int y)
{
    return x / gcd(x, y)*y;
}
int main()
{
    cin >> n;
    scanf("%d/%d", &a, &b);
    for (int i = 1; i < n; i++)
    {
        scanf("%d/%d", &c, &d);
        int lc = lcm(b, d);
        a = (lc / b*a + lc / d*c);
        b = lc;
    }

    //cout << a << endl; cout << b << endl;
    int tt = gcd(a, b);// cout << tt << endl;
    a /= tt, b /= tt;
    if (a!=0){
        if ((a / b) != 0){
            if ((a/b) > 0)
                printf("%d %d/%d\n", a / b, a%b, b);
            else
            {
                if ((a%b)!=0)
                    printf("%d %d/%d\n", a / b,-(a%b) , b);
                else
                    printf("%d\n", a / b);
            }
        }
        else{
            if (a*b > 0){
                printf("%d/%d\n",  a, b);
            }else
                printf("-%d/%d\n", (a<0?-a:a),(b<0?-b:b));

        }


    }
    else
        printf("%d\n", a);
    //cout << (-10 / 3) << endl; cout << (-10 % 3) << endl;
    system("pause");
    return 0;
}
发表于 2018-09-23 20:18:43 回复(0)
package go.jacob.day822;

import java.util.Scanner;

public class Demo1 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String[] strs = new String[n];
		//三个数分别为分子,分母,带分数的整数部分
		int numerator = 0, denominator = 0, first = 0;
		for (int i = 0; i < n; i++)
			strs[i] = sc.next();
		sc.close();
		for (int i = 0; i < n; i++) {
			int flag = 1, begin = 0;
			if (strs[i].charAt(0) == '-') {
				flag = -1;
				begin = 1;
			}
			int tmpNumerator = flag * Integer.parseInt(strs[i].substring(begin, strs[i].indexOf("/")));
			int tmpDenominator = Integer.parseInt(strs[i].substring(strs[i].indexOf("/") + 1));
			if (tmpDenominator == 0)
				return;
			if (i == 0) {
				numerator = tmpNumerator;
				denominator = tmpDenominator;
			} else {
				numerator = numerator * tmpDenominator + tmpNumerator * denominator;
				denominator *= tmpDenominator;
			}
			// 使用欧几里得算法求最大公约数,每次计算都要对分数进行化简,放置溢出
			int factor = gcd(numerator, denominator);
			if (factor == 0) {
				System.out.println(0);
				return;
			}
			numerator /= factor;
			denominator /= factor;
		}
		// 把假分数化成带分数
		first += numerator / denominator;
		numerator = numerator % denominator;

		// 输出结果的时候要判断:整数部分是否为0?分子书否为0?
		if (first != 0)
			if (numerator != 0)
				System.out.println(first + " " + numerator + "/" + denominator);
			else
				System.out.println(first);
		else if (numerator != 0)
			System.out.println(numerator + "/" + denominator);
		else
			System.out.println(0);
	}

	private static int gcd(int a, int b) {
		if (a == 0)
			return 0;
		if (a < 0)
			a = -a;
		if (b < 0)
			b = -b;
		if (a < b) {
			int tmp = a;
			a = b;
			b = tmp;
		}
		if (a % b == 0)
			return b;
		else
			return gcd(b, a % b);

	}
}


发表于 2017-08-22 09:56:45 回复(0)
#include<stdio.h>
long gcd(long a,long b){return !b?a:gcd(b,a%b);}
int main (){//the shorter,the better.
    int n,i,f;long a,b,c,d,t;
    for(;~scanf("%d",&n);a%b?a>b?printf("%ld %ld/%ld\n",f*a/b,a-a/b*b,b):printf("%ld/%ld\n",f*a,b):printf("%ld\n",f*a/b)){
       for (a=i=0,b=1;i<n&&~scanf("%ld/%ld",&c,&d);a=a*d+b*c,b*=d,i++);
       b>0?:(b*=-1,a*=-1),f=a>0?1:-1,a*=f,t=gcd(a,b),a/=t,b/=t;
    }
}

发表于 2018-02-01 17:17:58 回复(0)

这其实就是一道小学数学题,貌似也没有什么快速的方法,就按照分数的加减法写了下代码。

读入数据,使用两个vector分别存储了对应分数的分子和分母,方便后面计算。

首先是进行通分,将分式通分为同分母的分式
然后再按同分母的分式加减,分母不变,分子相加减;
最后进行将假分数化为代分数,并进行约分。约分时求最小公约数可以使用辗转相除法计算。注意下负数的情况。


以下是完整代码:

#include<iostream>
#include<vector>
 using namespace std;
 
 //辗转相除法求最大公约数
 int gcd(int x,int y)
 {
     int t;
     while(y)
     {
         t=x%y;
         x=y;
         y=t;
     }
     return  x;
 }
 
 int main()
 {
     int n;
     cin >> n;
     vector<long long> numerator(n);    //存储分子部分
     vector<long long> denominator(n);    //存储分母部分
     long long a, b;
     char c;
     long long product = 1;    //各个数分母相乘的积
     for (int i=0; i<n; i++)
     {
         cin >> a >> c >> b;
         numerator[i] = a;
         denominator[i] = b;
         product *= b;
     }
     long long sum = 0;
     for (int i=0; i<n; i++)    //计算通分后分子相加的和
     {
         long long tmp = product/denominator[i] * numerator[i];
         sum += tmp;
     }
     if (sum==0)    //分子和为0,说明分数正负抵消,输出0
     {
         cout << 0;
         return 0;
     }
         
     long long num = sum / product;    //计算和是否为假分数
     a = sum % product;
     
     if (a == 0)    //得到的和为整数
     {
         if (num != 0)
             cout << num;
         return 0;
     }
     
     long long g = gcd(product, a);    //约分
     a = a/g;
     b = product/g;
     
     if (b < 0)    //处理负数的情况
     {
         a *= -1;
         b *= -1;
     }
     
     if (num != 0)
         cout << num << " ";
     cout << a << "/" << b;
 } 


 
编辑于 2015-08-19 18:27:03 回复(0)
为什么不用高精度啊
万一两个分母是互质的很大的相乘超longlong的数呢
编辑于 2024-03-27 02:05:23 回复(0)
#include<iostream>
using namespace std;

//辗转相除法求最大公约数
int gcd(int x,int y){
    int z;
    while(y){
        z = x % y;
        x = y;
        y = z;
    }
    return abs(x);  //这里做了特殊处理,返回绝对值,因为公约数有可能是负数
}

int main(){
    long a[2] = {0},b[2] = {0};
    int n,gb;
    cin>>n;
    scanf("%ld/%ld",&a[1],&b[1]);
    for(int i = 1;i < n;i++){
        scanf("%ld/%ld",&a[0],&b[0]);
        a[1] = a[0] * b[1] + a[1] * b[0];
        b[1] = b[0] * b[1];
    }
    //先化为最简
    gb = gcd(a[1],b[1]); 
    a[1] /= gb; b[1] /= gb;
    
    //输出
    if(a[1] == 0) cout<<0;
    else if(a[1]/b[1] != 0 && a[1]%b[1] != 0){
        cout<<a[1]/b[1]<<' '<<a[1]%b[1]<<'/'<<b[1];
    }
    else if(a[1]/b[1] != 0) cout<< a[1]/b[1];
    else if(a[1] % b[1] != 0) cout<< a[1]%b[1]<<'/'<<b[1];
}

发表于 2020-03-05 23:02:10 回复(0)
#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

struct Fraction {
	LL up,down;
} sum,temp;

LL gcd(LL a,LL b) {
	return b==0?a:gcd(b,a%b);
}

Fraction reduction(Fraction a) {
	if(a.down==-1) {
		a.up=-a.up;
		a.down=-a.down;
	}
	if(a.up==0) {
		a.down=1;
	} else {
		LL d=gcd(abs(a.up),a.down);
		a.up/=d;
		a.down/=d;
	}
	return a;
}

Fraction Add(Fraction a,Fraction b) {
	Fraction c;
	c.up=a.up*b.down+a.down*b.up;
	c.down=a.down*b.down;
	return c;
}

void Printf(Fraction a) {
	a=reduction(a);
	if(a.down==1) {
		cout<<a.up;
	}
	else if(abs(a.up)>a.down) {
		cout<<a.up/a.down<<" "<<(a.up%a.down)<<'/'<<a.down;
	}else{
		cout<<a.up<<'/'<<a.down;
	}
}

int main() {
	int n;
	cin>>n;
	sum.up=0,sum.down=1;
	for(int i=0;i<n;i++){
		scanf("%lld/%lld",&temp.up,&temp.down);
		sum=Add(sum,temp);
	}
	Printf(sum);
	return 0;
}

发表于 2022-11-16 15:02:24 回复(1)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int lcm = 1, numerator, denominator; // 最小公倍数,分子,分母
        List<Integer[]> numbers = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String[] split = sc.next().split("/");
            numerator = Integer.parseInt(split[0]); 
            denominator = Integer.parseInt(split[1]);
            numbers.add(new Integer[]{numerator, denominator});
            lcm = (lcm * denominator) / gcd(lcm, denominator);
        }

        int sumNumerator = 0;  // 求和
        for (Integer[] number : numbers) sumNumerator += lcm / number[1] * number[0];

        if (sumNumerator == 0) System.out.println(0);
        else if(sumNumerator > 0){
            int gcd = gcd(sumNumerator, lcm);
            numerator = sumNumerator / gcd;
            denominator = lcm / gcd;
            int a = numerator / denominator;
            int b = numerator % denominator;
            if (a == 0) System.out.println(numerator + "/" + denominator);
            else if (b == 0) System.out.println(a);
            else System.out.println(a + " " + b + "/" + denominator);
        } else {
            sumNumerator=-sumNumerator;
            int gcd = gcd(sumNumerator, lcm);
            numerator = sumNumerator / gcd;
            denominator = lcm / gcd;
            int a = numerator / denominator;
            int b = numerator % denominator;
            if (a == 0)  System.out.println(-numerator + "/" + denominator);
            else if (b == 0) System.out.println(-a);
            else System.out.println(-a + " " + b + "/" + denominator);
        }
    }

    static int gcd(int a, int b) {
        int t;
        while (b != 0) {
            t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}

发表于 2022-10-31 19:42:56 回复(0)
#include<iostream>
#include<string>
#include<vector>
#include<stdlib.h>
#include<math.h>
using namespace std;
int gys(long ss,long mm){
    //int m=abs(ss)*abs(mm);
    if(ss<0){
        ss*=-1;
    }
    if(mm<0){
        mm*=-1;
    
    }
    /*long t;
      if(mm<ss)
    {
        t=mm;
        mm=ss;
        ss=t;
    }*/
    int    n=abs(mm)%abs(ss);
    while(n!=0){
        mm=ss;
        ss=n;
        n=mm%ss;
    
    
    }

    return ss;

}

int main(){
    vector<long> s;
    vector<long> m;
    
    int count=0;
    char son[100],mot[100];
    string user;
    string user_s[50];
    string user_m[50];
    int N;

    cin>>N;
    int n=N;
    while(N){
    
        //cin>>user;
        cin>>user;
        for(int i=0;i<user.size();i++){
            if(user[i]=='/'){
                int curr=0;
                while(curr<i){
                    son[curr]=user[curr];
                    
                
                    curr++;
                }
                son[curr]='\0';
                s.push_back(atoi(son));
                
                user_s[count]=(string)son;
                
                curr=0;
                i++;
                while(i<user.size()){
                    mot[curr]=user[i];
                    
                    i++;
                    curr++;
                
                }
                mot[curr]='\0';
                m.push_back(atoi(mot));
                user_m[count]=(string)mot;
                
                count++;
                break;
            }
        
        
        }
        N--;
        //s.push_back(user);
        
            
    
    }
    /*cout<<"当前输入的所有分子:";
    for(int i=0;i<count;i++)
    cout<<user_s[i]<<" ";
    cout<<endl;
    cout<<"当前输入的所有分母:";
    for(i=0;i<count;i++)
    cout<<user_m[i]<<" ";
    cout<<endl;*/
    long first,_first,flag;
    long ss=s[0];
    long mm=m[0];
    for(int i=0;i<n;i++){
        if(n-i>1){
            ss=ss*m[i+1]+mm*s[i+1];
            mm=mm*m[i+1];
        }
        
    
    
    }
//    cout<<"当前的分子和为:"<<ss<<endl;
//    cout<<"当前的分母和为:"<<mm<<endl;
    first=abs(ss)/abs(mm);
    _first=ss/mm;

        if(ss<0){
            ss+=first*mm;
            if(ss==0){
                flag=1;
            }
        }else{
            ss-=first*mm;
        
        }
    if(ss!=0){    
    long mode=gys(ss,mm);
    
    ss/=mode;
    mm/=mode;
    if(first!=0)
    printf("%ld %ld/%ld",first,ss,mm);
    else
    printf("%ld/%ld",ss,mm);
    }else{
        if(flag=1)
            cout<<_first;
        else
        cout<<0;
    
    }



    return 0;
    
}
发表于 2021-10-18 21:36:59 回复(0)
当输出是一个带有正数和分数的负数时,负号应该在哪里?测试点好像没有这个
发表于 2020-03-31 20:16:34 回复(0)
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <string>
#include <set>
#include <vector>
#include <map>
#include <iomanip>
#include <sstream>
using namespace std;


//1081 Rational Sum (20分)
//化最简分式本质上就是找最大公约数
//pat.6,全为0时需要输出0
//pat与牛客均通过

int maxc(int a, int b) {
	//获得最大公约数
	int t;
	while (b != 0) {
		t = a % b;
		a = b;
		b = t;
	}

	return a;
}

int main() {
	int n;
	cin >> n;

	long long x, y;
	long long itg = 0, nu = 0, den = 1; //寄存的整数,分子,分母
	string e;
	long long p, mc;
	for (int i = 0; i < n; ++i) {
		cin >> e;
		p = e.find('/');
		x = stoll(e.substr(0, p)); //分子
		y = stoll(e.substr(p+1)); //分母

		//并入寄存部分
		itg += x / y; //这样做一次可以避免分子溢出
		x = x % y;

		nu = nu * y + x * den;
		den = den * y;
		itg += nu / den; //相加后处理整数部分
		nu = nu % den;
		//约分
		mc = nu < 0 ? maxc(-nu, den) : maxc(nu, den);
		nu /= mc;
		den /= mc;
	}

	if (itg != 0) { 
		cout << itg; 
		if (nu != 0) cout << " ";
	}
	if (nu != 0) {
		cout << nu << "/" << den;
	}

	//pat.6,全为0时需要输出0
	if (itg == 0 && nu == 0) cout << 0;
	return 0;
}

编辑于 2020-02-29 16:16:19 回复(0)
using System;
using System.Collections.Generic;
namespace PAT_01
{
    class Program
    {
        /*
        题目描述
        Given N rational numbers in the form "numerator/denominator", you are supposed to calculate their sum.
        输入描述:
        Each input file contains one test case. Each case starts with a positive integer N (<=100), followed in the next line N rational numbers "a1/b1 a2/b2 ..." where all the numerators and denominators are in the range of "long int".  If there is a negative number, then the sign must appear in front of the numerator.

        输出描述:
        For each test case, output the sum in the simplest form "integer numerator/denominator" where "integer" is the integer part of the sum, "numerator" < "denominator", and the numerator and the denominator have no common factor.  You must output only the fractional part if the integer part is 0.
        输入例子:
        5
        2/5 4/15 1/30 -2/60 8/3
        输出例子:
        3 1/3
         */
        static void Main(string[] args)
        {
            var count = long.Parse(Console.ReadLine());
            var molecularList = new List<long>();
            var denominatorList = new List<long>();
            foreach (var item in Console.ReadLine().Split(' '))
            {
                var str = item.Split('/');
                if (str[0][0] == '-')
                {
                    molecularList.Add(long.Parse(str[0].Remove(0, 1)) * -1);
                }
                else
                {
                    molecularList.Add(long.Parse(str[0]));
                }
                denominatorList.Add(long.Parse(str[1]));
            }
            var maxMaleMultiple = denominatorList[0];
            for (int index = 1; index < count; index++)
            {
                maxMaleMultiple = GetMaxMaleMultiple(maxMaleMultiple, denominatorList[index]);
            }
            long sum = 0;
            for (int index = 0; index < count; index++)
            {
                sum += molecularList[index] * maxMaleMultiple / denominatorList[index];
            }
            var value = sum / maxMaleMultiple;
            var maxC = GetMaxConventions(maxMaleMultiple, sum - (value * maxMaleMultiple));
            Console.WriteLine("{0} {1}/{2}", value, (sum - (value * maxMaleMultiple)) / maxC, maxMaleMultiple / maxC);
        }
        private static long GetMaxConventions(long a, long b)
        {
            long max = a > b ? a : b;
            long min = a < b ? a : b;
            while (max % min != 0)
            {
                a = min;
                b = max % min;
                max = a > b ? a : b;
                min = a < b ? a : b;
            }
            return min;
        }
        private static long GetMaxMaleMultiple(long a, long b)
        {
            return a * b / GetMaxConventions(a, b);
        }
    }
}
发表于 2019-08-23 11:16:18 回复(0)
#include 
#include 
#include 
using namespace std;
int gys(int a,int b){return !b?a:gys(b,a%b);} //大的数字为负数,则返回负数
int main(){
    int n,f; scanf("%d",&n);
    int s1,s2; scanf("%d/%d",&s1,&s2);
    for(int i=1;i<n;i++){
        int t1,t2; scanf("%d/%d",&t1,&t2);
        s1=s1*t2+t1*s2; s2=s2*t2; //先算s1后算s2,避免先改变s2
        int t=gys(s2,s1);
        s2/=t; s1/=t;
        if(s2<0) s2*=-1,s1*=-1; //保证s2为正数
    }
    s1<0?f=-1,s1*=-1:f=1;
    if(s1%s2==0){ //0%6,0/6 = 0
        printf(f>0||!s1?"%d":"-%d",s1/s2);
    }else{
        if(s1/s2==0) printf(f>0?"%d/%d":"-%d/%d",s1,s2);
        else printf(f>0?"%d %d/%d":"-%d %d/%d",s1/s2,s1%s2,s2);
    }
    return 0;
}
发表于 2019-02-24 14:30:24 回复(0)
/*
 * ============================================================================================
 *
 *       Filename:  1001 Public Bike Management (30).cpp
 *
 *        Version:  1.0
 *        Created:  2018/09/25 13:06:07
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  Covfefe
 *   Organization:    Fs-studio
 *  
 *    Description: 
 *
 *             idea:  
 *
 * ============================================================================================
 */
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
#define FOR(i,n) for(i = 0; i < n; i++)
int main()
{
    int N, a[102], b[102], c = 0, d = 1;        //long int将不能过测试点,但运行正确。。long long运行也不正确
    int i, j, k, maxab;
    cin >> N;
    FOR(i, N)
        scanf("%d/%d", &a[i], &b[i]);
    if (N % 2 != 0)        //若总个数为奇数
    {
        c = a[N - 1];
        d = b[N - 1];
        N--;
    }
    while (N > 1)
    {
        for (i = 0; i < N; i += 2)
        {
            a[i / 2] = a[i] * b[i + 1] + a[i + 1] * b[i];
            b[i / 2] = b[i] * b[i + 1];
        }
        N /= 2;
    }
    a[0] = a[0] * d + c * b[0];
    b[0] = b[0] * d;
    maxab = a[0] > b[0] ? a[0] : b[0];
    for(j = maxab; j >= 1; j--)
        if (a[0] % j == 0 && b[0] % j == 0)
        {
            a[0] /= j;
            b[0] /= j;
            break;
        }
    if (!a[0])
    {
        cout << a[0];
    }
    else
    {
        if (abs(a[0]) > b[0])
        {
            cout << a[0] / b[0] << " ";
            a[0] %= b[0];
        }
        if (a[0])
            cout << a[0] << "/" << b[0];
    }
    return 0;
}
发表于 2018-10-17 23:38:57 回复(0)
所以根本没有考虑到100个质数分母的情况嘛,害我想这么久
发表于 2018-08-22 16:36:57 回复(0)
有哪一位大神能告诉我我自己写的辗转相除法哪里错了,题目老是报浮点错误(可能除0)
CommonDivisor(abs(sumA), abs(sumB));
这个是我的函数

#include <iostream>
#include <math.h>
using namespace std;
long long CommonDivisor(long long a, long long b);
long long gcd(long long x,long long y);
int main()
{
    int n;
    cin >> n;
    long long a,b;
    long long sumA=0,sumB=1;
    for(int i=0; i<n; i++)
    {
        scanf("%ld/%ld",&a,&b);
        sumA=sumA*b+a*sumB;
        sumB=b*sumB;
        //long long commonDivisor = CommonDivisor(abs(sumA), abs(sumB));
        long long commonDivisor = gcd((sumA < 0)?(-sumA):sumA, sumB);
        if(CommonDivisor == 0)
            cout << a << b <<endl;
        sumA = sumA / commonDivisor;
        sumB = sumB / commonDivisor;
    }
    long long master = sumA / sumB,y = sumA % sumB;
    if(y==0){
        cout << master << endl;
    }
    else
    {
        if(master)
        {
            cout << master << " ";
        }
        cout << y << "/" << sumB << endl;
    }
}

long long gcd(long long x,long long y) {
    return y?gcd(y, x % y):x;
}
long long CommonDivisor(long long a, long long b)
{
    long long max=a>b?a:b;
    long long min=a>b?b:a;
    long long remainder = max%min;
    if(min == 0)
        cout << "fdafdsa" ;
    long long remainder1 = 0;
    while(remainder)
    {
        remainder1 = min % remainder;
        //cout << "remainder is 0" << endl;
        if(remainder1 != 0)
        {
            min = remainder;
            remainder = remainder1;
        }
        else
        {
            break;
        }
    }
    return remainder;
}

发表于 2018-07-25 17:36:48 回复(0)
我实在无法理解,牛客全部AC,pat全部答案错误
发表于 2017-12-08 17:37:25 回复(1)
//居然没有Js的,不过的确js刷题太恶心了,光输入输出就很恶心,别提怎么调试了。。。。根本就是坑。
// 其实想复杂了,额外作了个最大公倍数/最小公约数,其实直接把分母乘起来转换就可以。

function getArr(n,string){
	var arr = []
	arr = string.split(' ')
	var a = {}
		a.fenzi = []
		a.fenmu = []
	arr.forEach(function(item,index){
		a.fenzi.push(+(item.split('/')[0]) )
		a.fenmu.push(+(item.split('/')[1]) )
		
	})
	return a;
}

//分母不可能为0
function getMin(arr){
	var min = Infinity , minindex = 0
	arr.forEach(function(item,index){
		if( item < min && item !=0 ){
			min = item
			minindex = index
		}

	})
	return {
		min: min,
		minindex: minindex
	}
}

function howMuchZero(arr){
	var zerocount = 0
	arr.forEach( function(item){
		item === 0 ? 
		zerocount++ : zerocount 
	}
		)
	if(zerocount >= arr.length -1) {
		return true
	}
	else return false
}

function maxDivi(arr){
	do {
	var min = getMin(arr).min,
	minindex = getMin(arr).minindex
	arr = arr.map(
		function(item,index){
			if (index === minindex){
				return item
			}
			else return item % min
		})
	}
	while (!howMuchZero(arr))
	return getMin(arr).min
}

function minMulti(arr){
	var totalMulti = arr.reduce(function(pre,item){
		return  pre * item
	})
	var brr = arr.map(function(item){
		return totalMulti/item
	})
	var brr_maxDivi = maxDivi(brr)
	return totalMulti/brr_maxDivi
}

function transfenzi(fenzi ,fenmu , multi ){
	return fenzi*multi/fenmu
}

function transOut(fenzi,fenmu,underzero){
	if (fenzi === 0 ){
		return '0'
	}
		if(fenzi < fenmu){
			return underzero * fenzi + '/' + fenmu
		}
		else {
		var newFenzi = fenzi % fenmu ,
		interger = underzero * (fenzi - newFenzi)/fenmu
		o = {
			interger: interger,
			fenzi: newFenzi,
			fenmu: fenmu
		}
		if(o.fenzi === 0){
			return o.interger
		}
		else return (o.interger + ' ' + o.fenzi + '/' + o.fenmu)
		}
	
}

var readline = require('readline'),
 	input = [];
const rl = readline.createInterface({
	input:process.stdin,
	output:process.stdout
})
var n, str
var fenmu_maxDivi,fenmu_minMulti

rl.on('line',function(line){
	input.push(line.trim())
	if(input.length === 2 ){
				
		n = +input[0]
		str = input[1]

		var chaiFen = getArr(n,str)

		fenmu_maxDivi  = maxDivi(chaiFen.fenmu)
		fenmu_minMulti = minMulti(chaiFen.fenmu)
		var fenzi_map = []

		//console.log(fenmu_minMulti)
		for( var i =0 ;i < chaiFen.fenmu.length ; i++){
			fenzi_map.push(transfenzi(chaiFen.fenzi[i],chaiFen.fenmu[i],fenmu_minMulti))
		}
		
		var sum_fenzi = fenzi_map.reduce(function(prev,item){
				return  prev = prev + item
			});
		var underzero = sum_fenzi < 0? -1 : 1
		sum_fenzi = sum_fenzi < 0? -sum_fenzi : sum_fenzi
		var output_maxDivi = maxDivi([sum_fenzi,fenmu_minMulti])
		var output_fenzi = sum_fenzi/output_maxDivi
		var output_fenmu = fenmu_minMulti/output_maxDivi

		var outputstr = transOut(output_fenzi,output_fenmu,underzero)
		console.log(outputstr)


	}
})


发表于 2017-08-30 11:52:34 回复(0)

问题信息

难度:
27条回答 10998浏览

热门推荐

通过挑战的用户