Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Десятичная дробь в обычную

Автор: tishaishii 2.3.2007, 00:21

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

Автор: Тьма 2.3.2007, 00:49

я думаю так:
берем десятичную дробь ну допустим 1.234 преобразовываем ее в дробь вида 1234/1000, дальше находим наименьший наибольший общий делитель для этой пары чисел, и делим числитель и знаменатель на НОД

Автор: skyboy 2.3.2007, 00:59

tishaishii, только имей в виду, что такое преобразование будет не совсем корректно: исходной дробью для значения 0.33333333 могло быть как 1/3, так и 33333333/100000000.

Автор: SelenIT 2.3.2007, 02:48

Ух, помнится, в "Календаре школьника" за далекий 1988 год был шикарный алгоритм для этой задачи в стихотворном виде (для исполнения вручную на пару с обычным калькулятором). Сейчас попытаюсь его воспроизвести по памяти:

Часть 1.

Код


ЕСЛИ ты соображаешь,
Что число не так малО, // т.е. не что-то вроде 0.0000000213 из-за ошибки округления
ТО бесстрашно обращаешь
Десятичное число.     // даже на советских калькуляторах той поры была кнопа 1/x
Целой частью пополняешь
Ты "волшебных" чисел стек,
С дробной же НАЗАД шагаешь,
Как упорный человек.

Часть 2.

Код


Взяв единицу в знаменатель
И ноль оставив как числитель,
Прилежно ПОВТОРЯЙ, читатель,
Дробей <какой-то> повелитель:
Число "волшебное" из стека
На знаменатель помножаешь,
Задолго до скончанья века
В числитель это прибавляешь,
Переставляешь с неохотой
Числитель ты и знаменатель,
И ЕСЛИ в стеке есть хоть что-то,
ТО ВОЗВРАЩАЕШЬСЯ, читатель!

ПыСы:

нихрена себе однако в то время у меня память была... эх, куда что делось...
ПыПыСы: а вот фамилию автора этой прелести не вспомню... возможно, она была только мелким шрифтом на последней странице обложки ("Авторский коллектив: ... и т.д."), куда я в ту пору "по увлеченности" не смотрел. А жалко... там еще был алгоритм нахождения НОД им. Евклида, тоже в стихах...

Автор: V.A.KeRneL 2.3.2007, 09:35

SelenIT, э-э-э, что-то у меня с рифмованными алгоритмами не очень, похоже. Я не понял! :-( А можно перевести [для особо одарённых] с советского стихотворного на русский прозаический?

Добавлено @ 09:41

Цитата(skyboy @ 2.3.2007, 00:59

)

Да-да! Именно, из-за этого обычно подразделяют эти две задачи: перевод конечной десятичной дроби (рационального числа) в обыкновенную дробь и бесконечного (но периодического) ---//---.

Автор: maxim1000 2.3.2007, 14:06

1. непериодические дроби отбрасываем сразу, т.к. они не представляются дробями целых чисел
2. выделяем начальную часть (до начала периода) - это конечная десятичная дробь, её умножаем на 10 в нужной степени и его же ставим в знаменатель
3. часть с периодом представляем в виде суммы геометрической прогрессии и считаем её сумму

пример для 1.232222222...
1.23=123/100
0.0022222...=0.001*2.2222222...=2.22222/1000
x=2.222222...
x=2+x/10
9*x=2*10
x=20/9
вот и получается 1.2322222...=123/100+20/9000
ну а дальше - сокращать и приводить к одному знаменателю

Добавлено @ 14:07
правда, из-за представления чисел в компьютере могут возникнуть проблемы
если я не ошибаюсь, компьютер хранит только те дроб, которые в двоичной системе конечные (остальные - усекает)

Автор: corpsehunter 2.3.2007, 17:30

Че-то ты как-то сложно намутил или я не понял Вот как это считается:
Возмем ту же дробь. С непереодичной частью все нормально. Рассмотрим переодичную:
0.002222222 = 0.002 + 0.0002 + 0.00002 + ....
Это, как ты сказал, сумма геометрической прогрессии:
первый член а1 = 0.002, а знаменатель q = 0.1, так как каждый член получается из предыдущего умножением на него.
Формула для суммы: S = a1 / (1-q) = 0.002 / (1-0.1) = 0.002 / 0.9 = 2 / 900
И прибавляем непереодическую часть

p.s. эта формула справедлива только для бесконечно убывающей геометрической последовательности.

Автор: MBo 2.3.2007, 18:42

не обязательн отделять непериод. часть
X = 1.230909(09)
Длина периода 2, делим на 10^2 = 100
X/100 = 0.0123(09)
вычитаем
X-X/100 = X* 99/100= 1.2186 = 12186/10000
X = 12186/(99*100) и сокращаем 1354/1100 = 677/550 = 1 127/550

Автор: tishaishii 2.3.2007, 19:10

Всё ОК, ищу я самый большой делитель, но правильно ли я определил знаменатель?
Вот, например, мантисса отлично делится на 17, так может быть надо было выбирать в качестве знаменателя что-то другое?
Вот какова вероятность, что в числителе появится число с последней цифрой 2, 5 или 0? Надо бы подсчитать, плохо помню теорию вероятностей, но задача следующая:
допустим, я имеюю поток сообщений из 16-значных чисел, причём цифры в 16-значных числах выбираются по равномерному распределнию, вот какова вероятность, что следующее число будет иметь в конце цифру 2, 5 или 0?
Хотелось бы ответ и на это. Но думаю, что 1/10+1/10+1/10=30%. Но какова вероятность того, что в результате числитель и знаменатель снова сократятся? И так далее, до 16го колена.
Мне надо на выходе как можно короче.

Так что надо как-то по-гибче.

Ну что, интереснее стало? smile

)) Задачка ещё та.