2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Перевод из десятичной дроби в обыкновенную - варианты
Сообщение26.03.2015, 17:49 
Какой алгоритм перевода конечной десятичной дроби, меньше единицы, заданной конечным набором цифр, в простую несократимую дробь является наиболее эффективным? Первое что приходит в голову - найти НОД данного числа и $10^k$ и сократить на него. Существуют ли другие подходы? Кроме того, дана оценка знаменателя $M<\sqrt{10^k/2}$, не знаю как с ее помощью можно что то сделать.

 
 
 
 Re: Перевод из десятичной дроби в обыкновенную - варианты
Сообщение26.03.2015, 18:24 
Можно не искать НОД по общему алгоритму, т.к. знаменатель делится только на 2 и 5 из простых делителей. Проще делить только на них, причём деление на 2 отлично оптимизируется, да и на константу 5 компилятор может делить быстрее, чем на произвольное число.

 
 
 
 Re: Перевод из десятичной дроби в обыкновенную - варианты
Сообщение27.03.2015, 13:28 
Аватара пользователя
Deffe в сообщении #996019 писал(а):
Первое что приходит в голову - найти НОД данного числа и $10^k$ и сократить на него.

Если для нахождения НОД используется алгоритм Евклида, то записывайте заодно в строку неполные частные. Получите конечную последовательность знаков $a_1, a_2, ..., a_n$. Стройте теперь новую последовательность $u_n$:

$u_1=a_n$
$u_2=u_1a_{n-1}+1$
$u_3=u_2a_{n-2}+u_1$
$u_4=u_3a_{n-3}+u_2$ и т.д. Последние два члена образуют знаменатель и числитель нужной Вам дроби.

upd
Для конечных легче разделить на НОД, а для периодических может пригодиться.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group