列出真分数序列-526互联

1.问题描述

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

2.问题分析

分子采用穷举法，分子分母最大公约数为1，判断分子与40是否构成真分数。

3.算法分析

num1和num2存储分母分子的值

用num1除以num2，余数存储到temp中，temp=num1%num2

num2和temp构成新的一对数，分别赋值给num1和num2，继续除法，如果num2=0，num1就是最大公约数

4.程序

#include<iostream>
using namespace std;
int main()
{
    int i, num1, num2, temp, n = 0;
    for (i = 1; i < 40; i++)//穷举40以内的分子
    {
        num1 = 40;
        num2 = i;
        while (num2 != 0)//辗转相除求出最大公约数
        {
            temp = num1 % num2;
            num1 = num2;
            num2 = temp;
        }
        if (num1 == 1)//最大公约数为1
        {
            n++;
            cout << i << "  " << endl;
        }
    }
    return 0;
}