【描述】

真分数，指的是分子比分母小的分数，真分数的分数值小于1。

给出n个正整数，任取两个数分别作为分子和分母组成真分数。

求能组成多少不同值的真分数。

【输入】

第一行是一个正整数n。

第二行是n个不同的正整数ai，相邻两个整数之间用单个空格隔开。

【输出】

一个整数，即最简真分数组合的个数。

【样例输入输出】

    样例说明：共组成6个真分数：1/2，1/3，1/4，2/3，2/4，3/4。

但是这6个真分数有5个不同的值：1/2，1/3，1/4，2/3，3/4。因为1/2和2/4的值相同.

【数据范围】

100%的数据：1<=ai<=1000，n<=600。

【来源】

2019年青岛市程序设计竞赛试题（初中组）1T

【题目分析】

• 题目比较简单，模拟法求解即可 

• 题目保证输入的数据不同，也就是不存在1/1这样的数

• 可以先把数据排序，然后进行组合。

• 对于组合后的数据如果存在重复的进行筛选即可

• 筛选的过程可以用最大公约数和桶排的方法进行筛选
  
  

【参考答案】

#include<cstdio>  #include<algorithm>   using namespace std;  int fz[601],fm[601]; //分子和分母  int n;//  int flagfz[601],flagfm[601]; //标记数组  int devisor; //最大公约数   //求最大公约数   int gcd(int a,int b)  {      if(b==0)          return a;      return gcd(b,a%b);  }   int main()  {  	scanf("%d",&n);  	for(int i=0;i<n;i++){  		scanf("%d",&fz[i]);  		fm[i]=fz[i];  	}  	sort(fz,fz+n);  	sort(fm,fm+n); //分子分母排序   	//处理数据  	int k=0,q=0;   	for(int i=0;i<n;i++)  	{  		for(int j=i+1;j<n;j++)  		{  			devisor=gcd(fz[i],fm[j]);  			//printf("%d /%d\n",fz[i],fm[j]);  			flagfz[k]=fz[i]/devisor;  			flagfm[k]=fm[j]/devisor;//约分   			printf("%d/%d\n",flagfz[k],flagfm[k]);  			//约分后的数据看看以前有没有出现过  			for(int p=0;p<k;p++){  				if(flagfz[p]==flagfz[k] && flagfm[p]==flagfm[k])	  				q++; //找到重复的数据   			}  			k++; //计数器加1   		}   	}   	printf("%d",k-q);   	return 0;   }

(adsbygoogle = window.adsbygoogle || []).push({});