7-35 有理数均值栈的运用

2024-01-06 10:08

文章标签 均值运用 35 有理数

本文主要是介绍7-35 有理数均值栈的运用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述
本题要求编写程序，计算N个有理数的平均值。

输入格式：
输入第一行给出正整数N（≤100）；第二行中按照a1/b1 a2/b2 …的格式给出N个分数形式的有理数，其中分子和分母全是整形范围内的整数；如果是负数，则负号一定出现在最前面。

输出格式：
在一行中按照a/b的格式输出N个有理数的平均值。注意必须是该有理数的最简分数形式，若分母为1，则只输出分子。

输入样例1：
4
1/2 1/6 3/6 -5/10
输出样例1：
1/6
输入样例2：
2
4/3 2/3
输出样例2：
1

错误代码

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stack>
using namespace std;void divide(int& up, int& low)
{int i = 2;while (true){if (up % i == 0 && low % i == 0){up = up / i;low = low / i;continue;}i++;if (up >= low){if (i > up){break;}}else {if (i > low){break;}}}
}
void Toghter(int a,int b,int c,int d,stack<int>& up1,stack<int>& low1)
{int up,low;if(b!=d){a = a*d;c = c*b;b = b*d;d = b;
//		a = a*d;分子在前先化 
//		c = c*b;up = a+c;low = b;divide(up,low);}else{up = a+c;low = b;divide(up,low);}up1.push(up);low1.push(low);
}int main()
{int N;cin >> N;stack<int> up;stack<int> low;int preup;int prelow;int son;int mother;for (int i = 0; i < N; i++){scanf("%d/%d", &preup, &prelow);//cin貌似不能像scanf一样cin>>'/' up.push(preup);low.push(prelow);}while(up.size()!=1){preup = up.top();prelow = low.top();up.pop();low.pop();son = up.top();mother = low.top();Toghter(preup,prelow,son,mother,up,low); 	}preup = up.top();prelow = low.top()/N;divide(preup,prelow);if(prelow==1){cout<<preup;}else{cout<<preup<<"/"<<prelow;}
}

问题分析

思路一：是先将他们全部相加再化简，但是PTA提示最大N运行超时，且若不随时化简，则会溢出
思路二：用STL的栈容器储存分数，再两两相加，当容器的size()为1时则退出循环，但是这样仍然提示若不随时化简，则会溢出
思路三：看了一些大佬的代码，必须拿到分数后就立即化简，再两两相加，这样测试点就全部通过了

正确代码：

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <stack>
using namespace std;void divide(int& up, int& low)
{int i = 2;while (true){if (up % i == 0 && low % i == 0){up = up / i;low = low / i;continue;}i++;if (up >= low){if (i > up){break;}}else {if (i > low){break;}}}
}
void Toghter(int a, int b, int c, int d, stack<int>& up1, stack<int>& low1)
{int up, low;if (b != d){a = a * d;c = c * b;b = b * d;d = b;//		a = a*d;分子在前先化 //		c = c*b;up = a + c;low = b;divide(up, low);}else {up = a + c;low = b;divide(up, low);}up1.push(up);low1.push(low);
}
int main()
{int N;cin >> N;stack<int> up;stack<int> low;int preup;int prelow;int son;int mother;for (int i = 0; i < N; i++){scanf("%d/%d", &preup, &prelow);//cin貌似不能像scanf一样cin>>'/' up.push(preup);low.push(prelow);}while (up.size() != 1){preup = up.top();prelow = low.top();divide(preup, prelow);up.pop();low.pop();son = up.top();mother = low.top();divide(son, mother);up.pop();low.pop();Toghter(preup, prelow, son, mother, up, low);}preup = up.top();prelow = low.top()* N;divide(preup, prelow);if (prelow == 1){cout << preup;}else {cout << preup << "/" << prelow;}
}