Chris Maunder Ответов: 8

Задача кодирования: преобразование поплавка в дробь с установленным ограничением на количество цифр

Твой босс-старая школа. Действительно старая школа. Ему не нравится эта новомодная десятичная система счисления, и вместо этого он хочет, чтобы все было в дробях. 1/2. 2/3. 5647/35829. Старая школа.

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

Сигнатура функции должна быть 
string FloatToFraction(float inputValue, int denominatorDigits)

Так FloatToFraction(0.3333, 1) => "1/3", FloatToFraction(100.333333, 1) => "100 1/3"

Пример ввода:

(0.333, 1) = & gt; 1/3
(0,125, 2) => 10/80 или 1/8
(0.00205501, 6) => 719/349875

PIEBALDconsult

Ах, пора смахнуть пыль с моего класса дроби...
https://www.codeproject.com/Articles/12805/NET-Rational-fraction-value-type-using-Decimals-w

Chris Maunder

Сукин сын! .. Я должен был проверить :)

PIEBALDconsult

(0.00205501, 6) => 411/200000

PIEBALDconsult

Gaaahhh! Поэтому сегодня мне нужно найти приблизительную дробь для 0,0102 !!!
Это довольно близко к 1/96, которая имеет только 2 и 3 в качестве простых множителей, так что теперь я задаюсь вопросом о создании преобразователя с плавающей точкой в рациональный, который ограничивает знаменатель набором простых множителей...

8 Ответов

Рейтинг:
52

Patrice T

Эта программа предназначена для калькулятора HP Prime
Второй параметр-это максимальное значение как числителя, так и знаменателя.
Это полезно, когда обе части дроби должны соответствовать значениям 8 или 16 бит.
Как следует из названия, он использует серию Farey.

#pragma mode( separator(.,;) integer(h64) )
// rev 6030 update

EXPORT FareyMax(Vl, DMax)
// Round a Vl to the best fraction with denominator < DMax
BEGIN
    LOCAL VlE, Tmp;
    LOCAL DbN,DbD, FnN,FnD, RsN,RsD,RsE;
    VlE:= ABS(Vl);
    DbN:= IP(VlE); DbD:=1; FnN:=DbN+1; FnD:=1;
    RsN:= ROUND(VlE,0); RsD:= 1; RsE:= ABS(VlE-(RsN/RsD));
    WHILE DbD+FnD <= DMax AND DbN+FnN <= DMax DO
      Tmp:= (DbN+FnN)/(DbD+FnD);
      IF RsE > ABS(VlE-Tmp) THEN
        RsN:= (DbN+FnN); RsD:= (DbD+FnD); RsE:= ABS(VlE-(RsN/RsD));
      END;
      IF Tmp < VlE THEN
        DbN:= (DbN+FnN); DbD:= (DbD+FnD);
      ELSE
        FnN:= (DbN+FnN); FnD:= (DbD+FnD);
      END;
    END;
    // RETURN "'"+STRING(SIGN(Vl)*RsN,2,0)+"/"+STRING(RsD,2,0)+"'";
    RETURN EXPR("QUOTE("+STRING(SIGN(Vl)*RsN,2,0)+"/"+STRING(RsD,2,0)+")");
END;

FareyMax(0.3333, 9) => 1/3
FareyMax(100.333333, 9) => 301/3
FareyMax(0.125, 99) => 1/8
FareyMax(0.00205501, 999999) => 1829/890020 // Chris I fear your example is wrong.
FareyMax(PI, 500) => 355/113

Мне нравится эта дробь пи, очень легко запоминающаяся:
113355, cut in middle 113/355, and swap 355/113

Chris Maunder

Только для этого я добавил базовый синтаксис проверить фокусировку, благодаря окрашиванию

Patrice T

Спасибо Крис

PIEBALDconsult

Для Пи мой код производит...
3 14/99
3 14159/100000

Patrice T

С чем ? НР-премьер ?
Какие параметры ?

PIEBALDconsult

Ой, ой, прости... Я имел в виду с моим кодом, а не с вашим.

Patrice T

:)

Patrice T

Мой код дает разные результаты
FareyMax(PI, 99) => 311/99
FareyMax(PI, 100000) => 312689/99532

Jörgen Andersson

Я знал это как двоичное дерево поиска Штерна-Броко.

Patrice T

Спасибо за ссылку Stern-Brocot tree - Википедия[^]
Раньше я называл это серией Фарея, потому что именно так я научился вычислять последовательности Фарея.

Jörgen Andersson

Штерн-Брокот и фэйри, очевидно, родственники, теперь, когда я знаю о Фэйри.
Я бы связался с Википедией, если бы был рядом с компьютером, но, увы, мне лень делать это по телефону.

Рейтинг:
2

Graeme_Grant

На этой неделе у меня нет времени на это, поэтому я решу его с помощью поиска Google: c# - алгоритм упрощения десятичной дроби до дробей-переполнение стека[^]

Рейтинг:
1

Rob Philpott

Независимо от того, как я стараюсь и продаю это, мой ум решительно отказывается участвовать в этом. Выиграю ли я приз?

PIEBALDconsult

Это звучит как рациональный ответ, так что да.

Рейтинг:
1

losvce

Я собирался написать что-то, что приближенно использовало Последовательности фарея или цепная дробь, но я уже отправил эту публикацию решения.

В .Чистая, интернет float тип уже имеет точность всего в семь цифр (ссылка) таким образом, уже существует верхний предел точности преобразования. Но если вы действительно хотите продать свой поплавок коротко, вы можете дать ему еще более строгое значение знаменателя. Он использует старого доброго Евклида, чтобы сгенерировать дробь в наименьших терминах. Кроме того, как float ограничен в диапазоне 10^38, выход может быть правильно обоснован, чтобы быть "симпатичным"."

using System;

namespace CodingChallenge
{
    public class Program
    {
        public static void Main(string[] args)
        {
            float[] values = { 0.12345F, 1 / 3F, 0.12345678F, 6 };
            foreach (var f in values)
            {
                FloatToFraction fc = new FloatToFraction(f);
                Console.WriteLine(fc);
            }

            // End point
            Console.WriteLine("All done!");
            Console.ReadLine();
        }
    }

    public class FloatToFraction
    {        
        // Is a private property a priverty?
        private readonly float inputValue;
        private readonly int _floatPrecisionLimit;        
        private readonly Func<float,Fraction> _convertToFraction; 

        // ctors and overrides
        public FloatToFraction(float inputValue) : this(inputValue,7){}

        public FloatToFraction(float inputValue, int denominatorDigits)
        {
            this.inputValue = inputValue;
            this._convertToFraction = PrecisionLimitMethod;
            _floatPrecisionLimit = (int) Math.Pow(10,denominatorDigits);
        }

        public override string ToString()
        {
            int leadingDigit = (int)Math.Truncate(inputValue);
            float normalizedValue = inputValue - leadingDigit;

            Fraction f = this._convertToFraction(normalizedValue);

            string A = string.Format("{0,40}", leadingDigit.ToString());
            string B = f.ToString();

            return string.Format(string.Concat(A,B));
        }


        // Lookin' at privates
        private Fraction PrecisionLimitMethod(float normalizedValue)
        {
            int numerator = (int)(normalizedValue * _floatPrecisionLimit);
            int denominator = _floatPrecisionLimit;

            int gcd = FloatToFraction.gcd(numerator, denominator);
            numerator /= gcd;
            denominator /= gcd;

            return new Fraction(numerator, denominator);
        }
        
        private static int gcd(int a, int b)
        {
            if (b == 0)
            {
                return a;
            }
            else
            {
                return gcd(b, a % b);
            }
        }

        private struct Fraction
        {
            public int numerator;
            public int denominator;

            public Fraction(int numerator,int denominator)
            {
                this.numerator = numerator;
                this.denominator = denominator;
            }

            public override string ToString()
            {
                if (numerator == 0)
                    return string.Empty;
                else
                    return string.Format("{0,8} / {1,8}", numerator, denominator);
            }
        }
    }
}

Рейтинг:
0

PIEBALDconsult

При этом используется рациональная часть моего класса -- .Чистая рациональные (дроби) введите значение с помощью десятичных чисел, написанных на C#[^]
-- затем пытается скорректировать величину знаменателя.
В принципе, если знаменатель требует десять цифр, но вы хотите только четыре, он делит дробь на 10^6 / 10^6 .

Мой рациональный класс имеет два метода преобразования числа с плавающей запятой в дробь:
Десятичная дробь в основном выбирает соответствующую степень десяти в качестве знаменателя - для 0.333 это сделает 333/1000.
BestGuess "пытается (с некоторым успехом) определить, какие числа можно разделить, чтобы получить значение".

Оба метода хорошо работают для 0.125 , 2.
BestGuess хорошо работает для 0.333 , 1 , но Decimal хочет производить 3/10.

Для 0.00205501f , 6, Десятичная производит 411/200000 -- что сделает босса счастливым.
Что производит BestGuess для этой ценности?
Ну, это производит 277584040019137491/135076734429096447706, что равно 0.00205501 -- это хорошо, но слишком много цифр.
Когда я делю на 10^15 / 10^15, в результате получается 277/135076, что равно 0.002050697 -- что не очень хорошо.
Если я округлюсь, то получу 278/135077, что равно 0.002058085 -- что тоже не очень хорошо.

Edit: я решаю попробовать выбрать метод, основанный на желаемых цифрах знаменателя числа.

Возможно, мне придется реализовать метод DecimalConversionMethod специально для того, чтобы с самого начала учитывать количество цифр знаменателя.

private static string
FloatToFraction
(
  float inputValue
,
  int   denominatorDigits
)
{
  System.Text.StringBuilder result = new System.Text.StringBuilder() ;

  PIEBALD.Types.Rational.ConversionMethod =
    denominatorDigits > 4
    ? PIEBALD.Types.Rational.DecimalConversionMethod.Decimal
    : PIEBALD.Types.Rational.DecimalConversionMethod.BestGuess ;

  PIEBALD.Types.Rational r = (decimal) inputValue ;

  if ( r.IsNegative )
  {
    result.Append ( '-' ) ;

    r = -r ;
  }

  if ( !r.IsProper )
  {
    decimal i = System.Decimal.Floor ( r ) ;

    result.Append ( i ) ;

    r -= i ;
  }

  decimal f = System.Decimal.Ceiling ( (decimal) System.Math.Log10 ( (double) r.Denominator ) ) ;

  if ( f > denominatorDigits )
  {
    f = (decimal) System.Math.Pow ( 10 , (double) f - (double) denominatorDigits ) ;

    decimal n = System.Decimal.Round ( r.Numerator   / f , 0 ) ;
    decimal d = System.Decimal.Round ( r.Denominator / f , 0 ) ;

    r = n ;
    r /= d ;
  }

  result.Append ( r.ToString() ) ;

  return ( result.ToString() ) ;
}

Patrice T

Боюсь, вам придется усовершенствовать свой метод, я получаю совершенно другие результаты.
FareyMax(0.00205501, 136000) => 268/130413
FareyMax(0.00205501, 140000) => 281/136739
FareyMax(0.00205501, 999999) => 1829/890020

Рейтинг:
0

Andy Allinger

Попробуйте все возможные знаменатели DENDIG цифры или меньше.
Вычислите числитель как NUMER = NINT(X DENOM)
Держите самое близкое приближение.
Босс старой школы должен одобрить решение без мозгов в ФОРТРАН.

!-----------------------------------------------------------------------
! Convert a float to a fraction, by exhaustive search!
!-----------------------------------------------------------------------
      FUNCTION F2F (INPVAL, DENDIG)
       IMPLICIT NONE
       REAL INPVAL         ! float number
       INTEGER DENDIG      ! max digits in denominator
       CHARACTER*32 F2F
       INTEGER KTRIM, LTRIM       ! external functions
       
       INTEGER NUMER, DENOM, BESTN, BESTD, MAXDEN, K, L, WHOLE
       REAL AERR, BESTER, FRACT
       CHARACTER*32 NUMSTR
       
!          begin
       MAXDEN = 10 **DENDIG - 1
       WHOLE = INT(INPVAL)
       FRACT = INPVAL - FLOAT(WHOLE)
       BESTER = 1.0
       BESTD = 1                               ! needless initializations
       BESTN = 0                               !       "    "
       DO 10 DENOM = MAXDEN, 2, -1             ! backwards step for extra confusion
         NUMER = NINT(FRACT * FLOAT(DENOM))
         AERR = ABS(FRACT - FLOAT(NUMER) / FLOAT(DENOM))
         IF (AERR .LE. BESTER) THEN
           BESTER = AERR
           BESTN = NUMER
           BESTD = DENOM
         END IF
  10   CONTINUE
       
!         format output
       F2F = ''
  20   FORMAT (I16)
       IF (WHOLE > 0) THEN
         WRITE (UNIT=NUMSTR, FMT=20) WHOLE
         K = KTRIM(NUMSTR)
         L = LTRIM(NUMSTR)
         F2F = NUMSTR(K:L)
       END IF
       
       WRITE (UNIT=NUMSTR, FMT=20) BESTN
       K = KTRIM(NUMSTR)
       L = LTRIM(NUMSTR)
       F2F = F2F(1:LTRIM(F2F)) // ' ' // NUMSTR(K:L)
       
       WRITE (UNIT=NUMSTR, FMT=20) BESTD
       K = KTRIM(NUMSTR)
       L = LTRIM(NUMSTR)
       F2F = F2F(1:LTRIM(F2F)) // '/' // NUMSTR(K:L)
       RETURN
      END  ! of F2F
      
      
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!       substitute for LEN_TRIM for old compilers
      FUNCTION LTRIM (STRING)
       IMPLICIT NONE
       CHARACTER*(*) STRING
       INTEGER LTRIM
       INTEGER J, L
       
       L = LEN(STRING)
       DO 50 J = L, 1, -1
         IF (STRING(J:J) .EQ. ' ') GO TO 50
         LTRIM = J
         RETURN
  50   CONTINUE
       LTRIM = 0
       RETURN
      END ! of LTRIM


!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!        first non-blank position in character variable
      FUNCTION KTRIM (STRING)
       IMPLICIT NONE
       CHARACTER*(*) STRING
       INTEGER KTRIM
       INTEGER J, L
       L = LEN(STRING)
       DO 50 J = 1, L, +1
         IF (STRING(J:J) .EQ. ' ') GO TO 50
         KTRIM = J
         RETURN
  50   CONTINUE
       KTRIM = 0
       RETURN
      END ! of KTRIM


      PROGRAM FPI  ! test pi fractions
       IMPLICIT NONE
       INTEGER J
       REAL PI
       CHARACTER*32 F2F, STRING
       
       PI = ACOS(-1.)
       DO J = 1, 7
         STRING = F2F(PI, J)
         PRINT *, 'with ', J, ' digits, the best representation ',
     $         'of pi is ', STRING
       END DO
       
       STRING = F2F(.00205501, 6)
       PRINT *, 'F2F(.00205501, 6): ', STRING
      END  ! of test program


пример вывода:
 with  1  digits, the best representation of pi is 3 1/7
with  2  digits, the best representation of pi is 3 14/99
with  3  digits, the best representation of pi is 3 16/113
with  4  digits, the best representation of pi is 3 16/113
with  5  digits, the best representation of pi is 3 13966/98635
with  6  digits, the best representation of pi is 3 132749/937541
with  7  digits, the best representation of pi is 3 593883/4194304
F2F(.00205501, 6):  1293/629194                    ! closer approximation !

Patrice T

Скорее грубая сила !

Andy Allinger

Дерево Фарея дает ответ на несколько иной вопрос: найти наименьшую дробь для аппроксимации в пределах заданного допуска. Грубая сила найдет лучшее приближение, вплоть до точности машины

Patrice T

Я думаю, что вы должны начать с лучшего пи, как 3.141592653589 вместо 3.141592741013 тогда мы сможем увидеть, какой метод лучше.

Andy Allinger

3.1415927 максимально приближен к 32-битной математике.

Patrice T

Фортран не может быть лучше, чем 32-битная плавающая точка ?

Andy Allinger

Мое извинение. Изменена программа на двойную точность для 64-битной математики. Оказывается, ваш ответ для .00205501 был лучше, и что приближения Пи тоже были неправильными.

с 1 цифрой приблизительное число Пи равно 3 1/7
с 2 цифрами, приблизительно Пи составляет 3 14/99
с 3 цифрами приблизительное число Пи равно 3 16/113
с 4 цифрами приблизительное число Пи равно 3 16/113
с 5 цифрами приблизительное число pi равно 3 14093/99532
с 6 цифрами приблизительное число pi равно 3 140914/995207
с 7 цифрами приблизительное число Пи равно 3 244252/1725033
DF2F (. 00205501D0, 6): 1829/890020

Почему я вообще сомневался в математиках?

Patrice T

Действительно, результаты лучше. Я не согласен с 6 и 7 цифрами, но там мы имеем дело с точностью.
Воспользуйся Улучшить вопрос чтобы обновить ваш вопрос.

Рейтинг:
0

David O'Neil

В подражание лучшим традициям старой школы:

#include <iostream>
#include <sstream>
using namespace std; string aaa(float a, int aa) { int aaa = (int)a; float aaaa = a - aaa; int aaaaa = abs((int)(aaaa * 60)); stringstream str; str << aaa << " " << aaaaa << "/60"; return str.str(); } int main() { float a; int aa; cout << "Enter number: "; cin >> a; cout << "Enter digits: "; cin >> aa; string str(aaa(a, aa)); cout << "True Old School Curmudgeons only work in sexagesimal system: "; cout << str << endl; system ("PAUSE"); return 0; }

Patrice T

Вы уверены ,что этот код связан с проблемой?

David O'Neil

:)

David O'Neil

Может быть, вам больше нравится номер 8? :)

Рейтинг:
0

David O'Neil

Может быть, придирчивому боссу это понравится больше?

#include <iostream>
#include <sstream>
using namespace std; size_t a(int a) { int aa = 1; int aaa = 10;  while (a/aaa > 0) { ++aa; aaa *= 10; } return aa; } string aa(double aa, size_t aaa) { double aaaa = (double)(1/(aa - (int)aa)); int aaaaa = aaa - a((int)(aaaa)); int aaaaaa = 1; while (aaaaa > 0) { aaaaaa *= 10; --aaaaa; } int aaaaaaa = aaaaaa; int aaaaaaaa = (int)(aaaa * aaaaaa + 0.5); stringstream aaaaaaaaa; aaaaaaaaa << (int)aa << " " << aaaaaaa << "/" << aaaaaaaa; return aaaaaaaaa.str(); } int main() { string a = aa(0.333, 1); cout << a << endl; a = aa(0.125, 2); cout << a << endl; a = aa(0.00205501, 6); cout << a << endl; system ("PAUSE"); return 0; }

Patrice T

Попробуйте еще раз, не запутывая свой код.
Нота: показать свои результаты тоже было бы интересно.

David O'Neil

А пока-пункт Б:
Результаты:
.333, 1: 0 1/3
.125, 2: 0 10/80
.00205501, 6: 0 1000/486616
пи, 2: 3 10/71
Пи, 3: 3 100/706
Пи, 4: 3 1000/7063

Это дает ключ к разгадке метода.

Patrice T

Результаты странные, вероятно, есть проблема в вашем коде.

David O'Neil

Более точно определите слово "странный". Все дроби являются близкими приближениями к искомым числам. На самом деле значение 0,00205501 ближе, чем приближение Криса.

Patrice T

и 1829/890020 ближе, чем ваш. :)
странно: странно иметь все числители в степени 10 отдельно от первого.

David O'Neil

&ГТ;&ГТ; и 1829/890020 ближе, чем ваша. :)

К счастью, это не входит в требования! :)

странно: странно иметь все числители в степени 10, кроме первого.

Это и есть ключ, о котором я говорил. Этот метод может быть самым быстрым доступным методом для получения достойного дробного приближения. Я мог бы сделать знаменатель 9, 99, 999, 9999 и т. д., Не слишком много работы, для немного большей точности. Код полагается только на функции std для печати. Никакие другие внешние библиотеки не используются.