Разложение дроби. Факториальная система

[Darts501]

Любую правильную дробь $\frac{p}{q}$, где $0<p<q$ можно представить в виде:

$$\frac{p}{q}=\frac{a_2}{2!}+\frac{a_3}{3!}+\dots+\frac{a_n}{n!}$$

где $0\le a_i<i, 2\le i\le n$ и $n$ - некоторое натуральное число. Помогите придумать алгоритм, который по заданным $p,q$ находил бы искомое разложение. Такое разложение существует всегда, возможно и не одно. Я вообще не понимаю как искать $n$ и коэффициенты $a_i$ кроме как простого перебора. Если писать прогу, то при ограничениях $0<q<p\le 1000$ простой перебор уже не покатит. Что делать?

[ИСН]

Тут надо начинать с простых аналогий. Говорят, любое натуральное число $p$ можно представить в виде $p=a_0\cdot10^0+a_1\cdot10^1+\dots+a_n\cdot10^n$, где $0\le a_i<10,\;0\le i\le n$ и $n$ - некоторое натуральное число. Только как же их найти? Перебор определённо не покатит.

[Darts501]

И разве это особо помогает? Вы хотите последовательно определять коэффициенты $a_i$, как для десятичной записи числа (если там коэффициенты не были бы такими очевидными). А если взять число $\frac{1}{607}$, где 607 - простое число, тогда n должно быть $n\ge 607$, и тут начинаются очень страшные вычисления!

[ИСН]

Ну это хорошо, но делать-то что?

[Otta]

Darts501
Говорят также, что любое натуральное число можно представить в виде $p=a_0\cdot3^0+a_1\cdot3^1+\dots+a_n\cdot3^n$, где $0\le a_i<3,\;0\le i\le n$ и $n$ - некоторое натуральное число. Только как же их найти? ))

Делать-то что?

[Darts501]

Не увидел последнего сообщения! Пока не знаю. К этой задаче можно написать прогу с ограничениями $0<p<q\le 1000$. А значит эти коэффициенты как то легче должны определяться, без диких вычислений.

[Otta]

Ну ведь правда, да? и в двоичном виде можно любое записать, и в троичном, и в восьмеричном... да? а как?

[Darts501]

Простите за тупость)) Я понял как делать. Рассмотрим как находить десятичное разложения для $\frac{1}{8}$. Получаем: $\frac{1}{8}-\frac{1}{10}=\frac{1}{40}$, $\frac{1}{40}-\frac{2}{100}=\frac{1}{200}$,$\frac{1}{200}-\frac{5}{1000}=0$ и нашли соответствующие коэффициенты. Также и в поставленной задаче, только вместо степени $10^n$ беруться $n!$. Вообще то это я понял сразу, после первого ответа (смотрите выше, про последовательное нахождение коэффициентов). Но я подумал, что если взять q очень большим простым числом (конечно не превышающем 1000) , например $q=607$, тогда в разложении дроби коэффициент $a_{607}$ перед $\frac{1}{607!}$ должен быть ненулевым, и тогда эти факториалы надо вычислять и что факториалы от чисел 4-го десятка уже не влазят даже в long long int, значит как надо подругому делать. Но это не так. На самом деле конкретные значения факториалов надо знать для $n\le 8$, то есть для первого n, такого что $n!\ge 1000$, для остальных вычислений не требуется знать точное значение $n!$ при больших n.

[Утундрий]

Darts501 в сообщении #1041849 писал(а):

что делать!

Делить и вычитать в основном.

[ИСН]

Говорят, есть такая факториальная система счисления. Ну да это неважно. Короче, можно просто идти жадным алгоритмом с самого верха и отжирать самое большое, что влезает.
Существенная подсказка:

Darts501 в сообщении #1041825 писал(а):

Такое разложение существует всегда, возможно и не одно.

Когда, например, оно будет не одно?

-- менее минуты назад --

"С самого верха" можно понимать неоднозначно. Я имел в виду - начиная с малых знаменателей (и, значит, больших дробей).

[Otta]

Где-то делить и вычитать, да. А где-то наоборот, умножать и вычитать.

Darts501 в сообщении #1041849 писал(а):

Лучше подсказал что делать!

Тут уже целая страница подсказок. Тоже ж понять надо, что не с потолка вопросы задают, а зачем-то.

Кстати, полезнее было бы научиться записывать правильные дроби, например, в том же десятичном виде.

Это у нас $\frac pq = a_1\cdot 10^{-1}+a_2\cdot 10^{-2}+\ldots$. Если разик так записать даже хотя бы $\frac{17}{125}$ вручную, чтобы был именно алгоритм, годящийся для любых оснований системы счисления, то после этого факториальная просто на ура пойдет.

[INGELRII]

Darts501
Вам на самом деле дали достаточно подсказок. Ну хорошо. Возьмем для начала задачу попроще: есть у нас дробь $\frac{1}{8}$, и нам понадобилось записать ее в виде десятичной дроби. Как вы будете это делать? Распишите подробно алгоритм. Потом обратите внимание на то, что этот алгоритм имеет прямое отношение к вашей задаче.

Просто распишите, как одну восьмую представить десятичной дробью. Прямо здесь, прямо сейчас.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- отсутствуют самостоятельные попытки решения задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Otta]

Darts501 в сообщении #1041849 писал(а):

Рассмотрим как находить десятичное разложения для $\frac{1}{8}$. Получаем: $\frac{1}{8}-\frac{1}{10}=\frac{1}{40}$, $\frac{1}{40}-\frac{2}{100}=\frac{1}{200}$,$\frac{1}{200}-\frac{5}{1000}=0$ и нашли соответствующие коэффициенты. Также и в поставленной задаче, только вместо степени $10^n$ беруться $n!$.

На самом деле, это далеко не оптимальный алгоритм. Во-первых, Вам придется каждый раз считать эти самые разные степени (или факториалы) - это в худшем случае, в лучшем - беречь их для знаменателей да еще впридачу устраивать немалое (вообще говоря) количество сравнений, чтобы понять, достаточную ли Вы дробь выбрали или нет еще.

А можно проще. Я не буду заморачиваться обозначениями, примерно, думаю, суть будет ясна. Для десятичного разложения. Факториальное делается так же.
$\frac 18 = a_1\cdot 10^{-1}+a_2\cdot 10^{-2}+a_3\cdot 10^{-3}+a_4\cdot 10^{-4}+\ldots$.
Все коэффициенты от 0 до 9.
Умножаем на 10. Получаем
$\frac {10}8 = 1+\frac{2}{8}=a_1+a_2\cdot 10^{-1}+\ldots$. Отсюда $a_1=1$.
Вычитаем.
$\frac 28=a_2\cdot 10^{-1}+a_3\cdot 10^{-2}+\ldots$. Умножаем на 10. $\frac{20}8=2+\frac{4}{8}=a_2+a_3\cdot 10^{-1}+\ldots$. Отсюда $a_2=2$. И так далее, до зануления разности.

Единственное возможное уязвимое место - это малые дроби, очень малые, такие, которые компьютер не сможет отличить от нуля. Но это место всегда уязвимо, в первом алгоритме тоже.