问题描述

按递增顺序依次列出所有分母为60,分子小于60的最简分数。

问题分析

分子、分母只有公因数1的分数叫做最简分数或者说分子和分母是互质数的分数,叫做最简分数,又称既约分数,如2/3,8/9,3/8等。

方法一:

求分子小于60的最简分数,对分子采用穷举的方法。根据最简分数定义知:分子分母的最大公约数为1,利用最大公约数的方法,判定分子与60是否构成真分数。

方法二:

分子、分母的公因数只有1的分数为最简分数,若分子、分母在1〜分子(num2)(题目要求分子小于60,分子、分母的公约数小于两者中的任意一个)之间除了1之外还有其他的公因数,则此分数肯定不是最简分数。

算法分析

变量num1、num2分别存储分母、分子的值。

方法一:

求最大公约数一般采用辗转相除的思想,具体步骤如下。 1. 用较大的数num1除以较小的数num2,得到的余数存储到变量temp中,temp=num1%num2。

2. 上一步中较小的除数num2和得出的余数temp构成新的一对数,并分别赋值给num1和num2,继续做上面的除法。

3. 当num2为0时,num1就是最大公约数,否则重复步骤 1、2。

方法二 :

分数的分子仍然采用穷举法。对于每一个可能的分子,都要判断在1〜num2范围内,分数num1/num2除了1之外是否有其他的公因数,循环初值为2。

在2〜num2内若有一个数j能同时整除分子、分母,说明此分数不是最简分数,j〜num2之间的数也无须再判断,利用break语句结束循环。循环结束时j<num2。循环过程中若没有一个数可以同时整除分子、分母即条件if(num1%j==0 && num2%j==0)不成立,则break语句不执行,循环正常结朿,即条件j<=num2不成立,循环结束时j>num2。利用j与num2的大小关系可判断分数是否为最简分数。

下面是方法一的完整程序:

#include<stdio.h>
int main()
{
int i, num1, num2, temp, n=; /*n记录最简分数的个数*/
printf("分母是60的真分数有:\n");
for(i=; i<; i++) /*穷举60以内的全部分子*/
{
num1 = ;
num2 = i;
/*采用辗转相除法求出最大公约数*/
while(num2 != )
{
temp = num1 % num2;
num1 = num2;
num2 = temp;
}
if(num1 == ) /*若最大公约数为1,则为最简真分数*/
{
n++;
printf("%2d/60 ", i);
if(n% == ) /*每行输出8个数*/
printf("\n");
}
}
return ;
}

下面是方法二的完整代码:

#include<stdio.h>
int main()
{
int i, num1, num2, j, n=; /*记录最简分数的个数*/
printf("The fraction serials with demominator 60 is:\n");
for(i=; i<;i++) /*穷举60以内的全部分子*/
{
num1 = ;
num2 = i;
for(j=;j<=num2; j++)
/*判断2~num2之间分子、分母是否有公约数,如果有j满足条件,则结束循环,说明此时的分数不是最简分数*/
if(num1%j== && num2%j==)
break;
if(j>num2)
/*若j>num2说明2~num2之间没有分子、分母的公约数,分数为最简分数*/
{
printf("%2d/60", i);
n++;
if(n% == )
printf("\n");
}
}
return ;
}

输出结果:

分母是60的真分数有:
/ / / / / / / /
/ / / / / / / /

最新文章

  1. asp.net mvc 多级目录结构
  2. 攻城狮在路上(贰) Spring(一)--- 软件环境、参考书目等一览表
  3. [zsh]zsh常用小技巧
  4. C# Hadoop学习笔记
  5. CSS Sprite 雪碧图制作
  6. ActiveMQ之JMSReplyTo
  7. 微信支付-b
  8. FastJSON应用前测试--转载
  9. commons-lang阅读(一)
  10. UIView和CALayer有什么关系
  11. 栈的顺序存储方式的C语言实现
  12. 20151203--filter
  13. 微软C#版SQLHelper.cs类
  14. 严重:IOException while loading persisted sessions:java.io.EOFException.
  15. [LeetCode] Sliding Window Median 滑动窗口中位数
  16. leetcode-数组-子集
  17. Ubuntu16.04 安装Tensorflow1.7过程记录二:安装CUDA及Tensorflow
  18. python之路--第一类对象,函数名,变量名
  19. 遇到一个git branch很奇怪的问题
  20. 解决linux下“XX不在 sudoers 文件中。此事将被报告&quot;的问题

热门文章

  1. loadrunner---Android、iOS压力测试
  2. python 编写登陆接口
  3. 2018.5.8 python操纵sqlite数据库
  4. sklearn pipeline
  5. Python练习十一
  6. Python练习六
  7. 学习笔记CB001:NLTK库、语料库、词概率、双连词、词典
  8. 学习笔记TF064:TensorFlow Kubernetes
  9. Django(其二)
  10. 经典问题----拓扑排序(HDU2647)