L1-009 N個數求和 (20point(s))
本題的要求很簡單，就是求N個數字的和。麻煩的是，這些數字是以有理數分子/分母的形式給出的，你輸出的和也必須是有理數的形式。
輸入格式：
輸入第一行給出一個正整數N（≤100）。隨后一行按格式a1/b1 a2/b2 ...給出N個有理數。題目保證所有分子和分母都在長整型范圍內。另外，負數的符號一定出現在分子前面。
輸出格式：
輸出上述數字和的最簡形式 —— 即將結果寫成整數部分 分數部分，其中分數部分寫成分子/分母，要求分子小于分母，且它們沒有公因子。如果結果的整數部分為0，則只輸出分數部分。
輸入樣例1：
5
2/5 4/15 1/30 -2/60 8/3
輸出樣例1：
3 1/3
輸入樣例2：
2
4/3 2/3
輸出樣例2：
2
輸入樣例3：
3
1/3 -1/6 1/8
輸出樣例3：
7/24
sizeof(long long)=8
#include <stdio.h>
typedef struct fraction
{
long long molecule;
long long dinominator;
} Fraction;
Fraction add_fraction(Fraction, Fraction);
Fraction simplify_fraction(Fraction);
static long find_biggest_factor(long, long);
void print_fraction(Fraction);
int main(void)
{
Fraction input;
Fraction sum = {0, 1};
int i;
int input_num;
scanf("%d", &input_num);
for (i = 0; i < input_num; i++)
{
scanf("%lld/%lld", &input.molecule, &input.dinominator);
sum = add_fraction(sum, input);
}
sum = simplify_fraction(sum);
print_fraction(sum);
return 0;
}
//input a/b c/d
//output (ad+bc)/bd
Fraction add_fraction(Fraction a, Fraction b)
{
Fraction result;
result.molecule = a.molecule * b.dinominator + a.dinominator * b.molecule;
result.dinominator = a.dinominator * b.dinominator;
return result;
}
//input a/b
//output (a/c)/(b/c) c is the biggest_factor
Fraction simplify_fraction(Fraction input)
{
Fraction result;
long biggest_factor = find_biggest_factor(input.molecule, input.dinominator);
result.molecule = input.molecule / biggest_factor;
result.dinominator = input.dinominator / biggest_factor;
return result;
}
//input a , b
//output c c is the biggest_factor of a and b
static long find_biggest_factor(long a, long b)
{
int result = 1;
int i;
int smaller = (a < b) ? a : b;
for (i = 1; i <= smaller; i++)
{
if (((a / i) * i == a) && ((b / i) * i == b))
result = i;
}
return result;
}
//input | 3/2 | 2/1 | 3/7 |
//output | 1 1/2 | 2 | 3/7 |
void print_fraction(Fraction input)
{
long flag = input.molecule / input.dinominator;
if (input.molecule == 0)
//molecule is 0
{
printf("0");
}
else if (flag == 0)
//molecule < dimononator
{
printf("%lld/%lld", input.molecule, input.dinominator);
}
else if (flag * input.dinominator == input.molecule)
//molecule / dimonontor is integer
{
printf("%lld", input.molecule / input.dinominator);
}
else
//molecule / dimonontor isn't initeger
{
printf("%ld %lld/%lld", flag, input.molecule %input.dinominator, input.dinominator);
}
}
uj5u.com熱心網友回復：
先通分啊，這是小學知識吧。依次求出分母的最小公倍數。通分后，分子相加。
uj5u.com熱心網友回復：
有個疑問，因為題目沒明確，就是分母保證在long long范圍內，但分母的最小公倍數是否也在long long范圍內？如果也在范圍內，那么問題還是挺簡單的。如果不在范圍內，問題還是有點復雜化的（要用陣列來做大數乘除）。分母最小公倍數在long long范圍內的情況，首先求分母的最小公倍數，就是找到最大的分母，然后大分母一次乘1，乘2，乘3，。。。，知道乘的結果可以整出每個分母，即可得出最小公倍數。最后算出結果后，約分（分子%分母），然后求約分后的分子和分母的最大公倍數，分子分母都除以最大公倍數，再輸出結果即可。
分母最小公倍數不在long long范圍內的情況，思路同上，只是分子分母都用陣列，通過陣列做大數乘除。
uj5u.com熱心網友回復：
longlong也不一定能存下uj5u.com熱心網友回復：
這個得看你求最小公倍數的方法了uj5u.com熱心網友回復：
https://www.baidu.com/s?wd=%E5%A4%A7%E6%95%B0%E8%BF%90%E7%AE%97&rsv_spt=1&rsv_iqid=0x91ed6a540001baa8&issp=1&f=8&rsv_bp=1&rsv_idx=2&ie=utf-8&rqlang=cn&tn=baiduhome_pg&rsv_enter=1&rsv_dl=tb&oq=%25E5%25B0%2586%25E5%25A4%259C&inputT=13727&rsv_t=0c4615xL9mwD%2F68RF0WtSd9rru%2B5lhYzLC3o9vzALpb0O5g4MxNgp0iVT8iGUzRTSc7Y&rsv_pq=ab7df0e80001ce7c&rsv_sug3=25&rsv_sug1=29&rsv_sug7=101&rsv_sug2=0&rsv_sug4=13727uj5u.com熱心網友回復：
先把所有分母放一起，并找到其中最大的數，從它開始找所有分母的最小公倍數，能快一些如果這個最小公倍數不超過long long的范圍還是可以做的
當然了，如果輸入資料不是最簡的形式， 比如最大的分母和它的分子之間是可約分的，那就有另外的問題了
比如其中有。 maxint / maxint 這種明明是1， 非要弄成最大的， 要是先通分必然超范圍無疑了
uj5u.com熱心網友回復：
還有就是，如果數量比較大， 寧愿先以分母為引數做一個排序， 先把分母相同的合并掉，減少后面的通分壓力甚至在做分母的最小公倍數的程序當中，邊做邊合并
比如，找到最大的分母后， 它可能就是其中一部分的最小公倍數，那么就把這一部分先合并， 然后再把這個數*2后，繼續合并直到所有的都合并完成
uj5u.com熱心網友回復：
我寫了一個simplify_fraction的函式在里面，找分子分母的最大公因數uj5u.com熱心網友回復：
這個跟我說沒關系啊。
比如
1/6+1/9===》你要計算的是6和9的最小公倍數，則是18
====》
3/18+2/18=5/18
uj5u.com熱心網友回復：
抱歉，看錯了轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/143495.html
標籤：其它技術問題
上一篇：力扣中國100題相同的樹