1984. Дроби
Для заданного
натурального числа n вывести в
порядке возрастания все правильные несократимые дроби, знаменатель которых не
превышает n.
Вход. Первая строка содержит количество тестов t (t
≤ 10). Каждая из следующих t
строк содержит одно натуральное число n
(1 < n ≤ 2000).
Выход. Для каждого
теста вывести в порядке возрастания все правильные несократимые дроби. Соседние
дроби должны быть разделены запятой и одним пробелом.
|
Пример
входа |
Пример
выхода |
325
3 |
1/2 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5 1/3, 1/2, 2/3 |
РЕШЕНИЕ
рекурсия
- последовательность Фарея
Анализ алгоритма
Сгенерируем
последовательность Фарея порядка 2000 (все дроби со знаменателем, не большим
2000, в возрастающем порядке) и занесем ее в массив. Для вывода дробей для каждого
теста будем проходить по сгенерированному массиву и выводить все дроби со
знаменателями, не большими n.
Пример
Реализация алгоритма
i-ой сгенерированной дробью будет nom[i] / denom[i].
#define MAX 1300000
int nom[MAX], denom[MAX];
Генерируем все
дроби со знаменателем, не большим 2000, в возрастающем порядке и заносим их
числители и знаменатели в массивы nom и denom.
void farrey(int
a1, int b1, int
a2, int b2)
{
if (2000 <
b1 + b2) return;
farrey(a1,b1,a1+a2,b1+b2);
nom[ptr] = a1 + a2; denom[ptr++] = b1 + b2;
farrey(a1+a2,b1+b2,a2,b2);
}
Основная часть
программы. Генерируем правильные несократимые дроби в порядке возрастания при
помощи функции farrey.
ptr = 0;
farrey(0,1,1,1);
Читаем количество тестов.
scanf("%d",&tests);
while(tests--)
{
Переменная flag = 1 до тех пор пока не выведется первая дробь в строке для
заданного n. Дробь выводится только
если ее знаменатель не больше n.
scanf("%d",&n);
flag = 1;
for(i = 0; i
< ptr; i++)
{
if
(denom[i] <= n)
if (flag)
{
printf("%d/%d",nom[i],
denom[i]); flag = 0;
}
else
printf(",
%d/%d",nom[i], denom[i]);
}
printf("\n");
}
Реализация при помощи класса
#include <stdio.h>
#define MAX 1300000
int i, j, ptr, n, tests;
class Fraction
{
public:
int nom,
denom;
Fraction() {nom = denom = 0;};
Fraction(int
nom, int denom) : nom(nom), denom(denom) {};
bool operator== (const
Fraction &a)
{
return
(a.nom == nom) && (a.denom == denom);
}
};
Fraction f[MAX];
void farrey(int
a1, int b1, int
a2, int b2)
{
if (2000 <
b1 + b2) return;
farrey(a1,b1,a1+a2,b1+b2);
f[ptr++] = Fraction(a1 + a2, b1 + b2);
farrey(a1+a2,b1+b2,a2,b2);
}
int main(void)
{
ptr = 0; farrey(0,1,1,1);
scanf("%d",&tests);
while(tests--)
{
scanf("%d",&n);
printf("1/%d",n);
for(i = 0;
i < ptr; i++)
{
if (f[i]
== Fraction(1,n)) continue;
if
(f[i].denom <= n)
printf(",
%d/%d",f[i].nom, f[i].denom);
}
printf("\n");
}
return 0;
}