Решение задачи "Упорядоченные дроби " с Acmp

С пояснением   Просмотров: 65

Требуется вывести в порядке возрастания все несократимые дроби, заключённые между 0 и 1, знаменатели которых не превышают N.


Код 

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string.h>
#include <algorithm>
#include <stack>
#include <queue>
 
using namespace std;
 
int n;
struct drob
{
    int ch,zn;
    drob(){}
    drob(int Ch, int Zn)
    {
        ch = Ch;
        zn = Zn;
    }
    void output()
    {
        printf("%d/%d\n", ch, zn);
    }
};
bool operator < (const drob &a, const drob &b)
{
    return (double)a.ch / a.zn  < (double)b.ch / b.zn;
}
void input()
{
    cin>>n;
}
vector<drob> mas;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    return gcd(b,a%b);
}
void solve()
{
    for (int zn = 2; zn<=n; zn++)
        for (int ch = 1; ch<zn; ch++)
            if (gcd(ch,zn) == 1)
                mas.push_back(drob(ch,zn));
    sort(mas.begin(),mas.end());
}
void output()
{
    for (int i=0;i<mas.size();i++)
        mas[i].output();
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
   
    input();
    solve();
    output();
    return 0;
}

         

Администратор Photo Автор: Администратор


Код 

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> c; vector<int> z;
    c.push_back(0); c.push_back(1);
    z.push_back(1); z.push_back(1);
    for(int i = 0; i < n - 1; ++i){
        for(int j = 0; j < c.size() - 1; ++j){
            if(z[j] + z[j + 1] <= n){
                c.insert(c.begin() + j + 1, c[j] + c[j + 1]);
                z.insert(z.begin() + j + 1, z[j] + z[j + 1]);
                ++j;
            }
        }
    }
    for(int i = 1; i < c.size() - 1; ++i)
            cout << c[i] << "/" << z[i] << endl;
    return 0;
}

         

Pro Sasha Photo Автор: Pro Sasha


Код 

n = int(input())
c = [0, 1]
z = [1, 1]
for i in range(n - 1):
    for j in range(len(c) - 1):
        if z[j] + z[j + 1] <= n:
            c.insert(j + 1, c[j] + c[j + 1])
            z.insert(j + 1, z[j] + z[j + 1])
            j += 1

for i in range(1, len(c) - 1):
    print(c[i], z[i], sep="/")

         

Pro Sasha Photo Автор: Pro Sasha


Пояснение к задаче

В этой задаче достаточно воспользоваться последовательностью Фарея. Формула для вычисления каждой последующей дроби:
$$ F_1 = \frac{a}{b}; \, \frac{c}{d} => F_2 = \frac{a}{b}; \, \frac{a + c}{b + d}; \, \frac{c}{d} $$
Последовательность Фарея при \( n\ =\ 5 \) выглядит следующим образом:

\( F_1 = \frac{0}{1}; \frac{1}{1} \\
F_2 = \frac{0}{1}; \, \frac{1}{2}; \, \frac{1}{1} \\
F_3 = \frac{0}{1}; \, \frac{1}{3}; \, \frac{1}{2}; \, \frac{2}{3}; \, \frac{1}{1} \\
F_4 = \frac{0}{1}; \, \frac{1}{4}; \, \frac{1}{3}; \, \frac{2}{5}; \, \frac{1}{2}; \, \frac{3}{5}; \, \frac{2}{3}; \, \frac{3}{4}; \, \frac{1}{1} \, \\
F_5 = \frac{0}{1}; \, \frac{1}{5}; \, \frac{1}{4}; \, \frac{2}{7}; \, \frac{1}{3}; \, \frac{3}{8}; \, \frac{2}{5}; \, \frac{3}{7}; \\ \frac{1}{2}; \, \frac{4}{7}; \, \frac{3}{5}; \frac{5}{8}; \frac{2}{3}; \, \frac{5}{7}; \, \frac{3}{4}; \, \frac{4}{5}; \, \frac{1}{1} \)


Сразу же удалеям дроби, у которых знаменатель больше n. Выводим данные cо 2 дроби до предпоследней дроби . И всё.
$$ F_5 = \frac{1}{5}; \, \frac{1}{4}; \, \frac{1}{3}; \, \frac{2}{5}; \, \frac{1}{2}; \, \frac{3}{5}; \, \frac{2}{3}; \, \frac{3}{4}; \, \frac{4}{5}; \, $$

Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться