蓝桥杯 2014本科C++ B组 奇怪的分式 暴力枚举
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了蓝桥杯 2014本科C++ B组 奇怪的分式 暴力枚举，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1612字，纯文字阅读大概需要3分钟。
内容图文
蓝桥杯 枚举 奇怪的分式
标题：奇怪的分式
上小学的时候，小明经常自己发明新算法。一次，老师出的题目是：
1/4 乘以 8/5
小明居然把分子拼接在一起，分母拼接在一起，答案是：18/45 （参见图1.png）
老师刚想批评他，转念一想，这个答案凑巧也对啊，真是见鬼！
对于分子、分母都是 1~9 中的一位数的情况，还有哪些算式可以这样计算呢？
请写出所有不同算式的个数（包括题中举例的）。
显然，交换分子分母后，例如：4/1 乘以 5/8 是满足要求的，这算做不同的算式。
但对于分子分母相同的情况，2/2 乘以 3/3 这样的类型太多了，不在计数之列!
注意：答案是个整数（考虑对称性，肯定是偶数）。请通过浏览器提交。不要书写多余的内容。
挺简单的，要是暴力枚举也没问题，用一个DFS的深搜代码看上去简单点，另外熟悉GCD,将两个分数的最大公约数求出，相除公约数，再去判断这两个分数是否相同。
答案：14
代码如下
1 #include<iostream>
2 #include<cstdio>
3#define MAXN 5
4usingnamespace std;
5int num[MAXN],s1,s2,r1,r2;
6int count=0;
7int gcd(int a,int b)
8{
9int s;
10while(b)
11 {
12 s=a%b;
13 a=b;
14 b=s;
15 }
16return a;
17 }
18void dfs(int m)
19{
20int i,j,a,b,t,ss1,ss2,rr1,rr2;
21if(m==5)
22 {
23if(num[1]!=num[2]&&num[3]!=num[4])
24 {
25 s1=num[1]*10+num[3];
26 s2=num[2]*10+num[4];
27 r1=num[1]*num[3];
28 r2=num[2]*num[4];
29if(r1<r2)
30 {
31 a=r2;
32 b=r1;
33 t=gcd(a,b);
34 }
35else36 {
37 a=r1;
38 b=r2;
39 t=gcd(a,b);
40 }
41 rr1=r1/t;
42 rr2=r2/t;
43if(s1<s2)
44 {
45 a=s2;
46 b=s1;
47 t=gcd(a,b);
48 }
49else50 {
51 a=s1;
52 b=s2;
53 t=gcd(a,b);
54 }
55 ss1=s1/t;
56 ss2=s2/t;
57if(rr1==ss1&&rr2==ss2)
58 {
59 cout<<num[1]<<"/"<<num[2]<<" * "<<num[3]<<"/"<<num[4]<<" = "<<num[1]<<num[3]<<"/"<<num[2]<<num[4]<<endl;
60 count++;
61 }
62 }
63 }
64else65 {
66for(i=1;i<=9;i++)
67 {
68 num[m]=i;
69 dfs(m+1);
70 }
71 }
72 }
73int main()
74 {
75 dfs(1);
76 cout<<count<<endl;
77return0;
78 }
原文：http://www.cnblogs.com/fancy-itlife/p/4379613.html
内容总结
以上是互联网集市为您收集整理的蓝桥杯 2014本科C++ B组 奇怪的分式 暴力枚举全部内容，希望文章能够帮你解决蓝桥杯 2014本科C++ B组 奇怪的分式 暴力枚举所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。