算法题每日一练---第32天：奇怪的分式

一、问题描述

上小学的时候，小明经常自己发明新算法。一次，老师出的题目是：1/4乘以8/5

小明居然把分子拼接在一起，分母拼接在一起，答案是：（参见下图）

老师刚想批评他，转念一想，这个答案凑巧也对啊，真是见鬼！

对于分子、分母都是 1 ~ 9 中的一位数的情况，还有哪些算式可以这样计算呢？

请写出所有不同算式的个数（包括题中举例的）。

显然，交换分子分母后，例如：4/1乘以5/8 是满足要求的，这算做不同的算式。

但对于分子分母相同的情况， 这样的类型太多了，不在计数之列!

二、题目要求

考察

• 逻辑思维，数学思想
• 建议用时10~15min

三、问题分析

一开始我拿到这题的时候，想到了深度搜索，一个个判断条件。写到一半时，发现不对，这不是四重for循环暴力破解就能解决的问题吗。

首先，四重for循环范围分别从1到9，分别代表第一个、第二个分数的分子、分母，让普通的两个分数相乘之后的结果等于两个分数分子分母彼此相连接的结果相等就行。

四重循环只需判断6000多次，0.1s出结果，暴力法yyds。

注意

分子、分母相同的条件不算在内

四、编码实现

#include<iostream>usingnamespacestd;
intmain()
{
longlonginti,j,k,p,ans=0;//初始化条件doublea,b;//定义两个分数的值for(i=1;i<=9;i++)//第一层循环    {
for(j=1;j<=9;j++)//第二层循环        {
for(k=1;k<=9;k++)//第三层循环            {
for(p=1;p<=9;p++)//第四层循环                {
a=1.0*(i*k)/(j*p);//第一个分数的结果，小数表示b=1.0*(10*i+k)/(10*j+p);//第二个分数的结果，小数表示if(a==b&&j!=i&&k!=p)//满足条件                    {
ans++;//计数++                    }
                }
            }
        }
    }
cout<<ans;//输出结果return0;
}

五、输出结果

输出结果为：14