Newsgroup: it.comp.lang.c++
Titolo: Decimali in frazioni

Qualcuno potrebbe darmi qualche dritta su come trasformare numeri decimali
in frazioni? Pere esempio fin'ora ci sono riuscito con i decimali finiti,
come 0.5 trasformarlo in 1/2, ma se sono periodici? oppure misti?
Grazie e ciao.
Luca Carlon

come 0.5 trasformarlo in 1/2, ma se sono periodici? oppure misti?
Innanzitutto bisogna dire che, a livello teorico, non e'
detto che tu ci riesca.  Un numero come 'radice quadrata di
2', per esempio, non e' riconducibile ad una frazione. 
Nella pratica, i numeri reali vengono 'rappresentati' in un
PC sotto forma di numeri in virgola mobile e, in quanto
rappresentazione, possono essere comunque ricondotti ad una
frazione.
Il codice seguente, rozzo e per niente ottimizzato, ti
espone un metodo semplicissimo e poco preciso:
<CODE>
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
// estrae numeratore e denominatore
void numden(const char *s, int& num, int& den)
{
     char s_num[64] = {0};
     int ptidx = -1;
     for (int i = 0, j = 0; s[i] ; i++)
     {
         if (s[i] != '.')
           s_num[j++] = s[i];
         else
           ptidx = i;
     }
     num = atoi(s_num);
     if (ptidx == -1)
       den = 1;
     else
       den = pow(10, strlen(s)-ptidx-1);
}
// funzione per ottenere il GCD
int fn_gcd(int a, int b)
{
    int gcd, min = (a <= b) ? a : b;
    for (int i = 1; i <= min; i++)
    {
        if ((a % i) == 0 && (b % i) == 0)
          gcd = i;
    }
    return gcd;
}
int main()
{
    char s[64];
    int num, den, gcd;
    cout << "inserisci un numero : " ;
    cin.getline(s, sizeof s);
    numden(s, num, den);
    gcd = fn_gcd(num, den);
    num /= gcd;
    den /= gcd;
    cout << "frazione : " << num << "/" << den << endl;
}
</CODE>
-- 
Andrea Laforgia (
walkie...@libero.it
)
"Usenet is a strange place" [Dennis Ritchie]

 come 0.5 trasformarlo in 1/2, ma se sono periodici? oppure misti?
Fra i migliori algoritmi di approssimazione vi e` quello dovuto a Farey (la 
cui correttezza fu poi dimostrata solo da Cauchy), in pseudocodice:
def farey(x, max_denominator):
    # precondizione: reale x>0, intero max_denominator>0
    # postcondizione: ritorna frazione ai minimi termini (a,b) che e` la
    #     piu` vicina ad x fra tutte le frazioni ai minimi termini (n,d)
    #     tali che d<=max_denominator (v. la dimostrazione di Cauchy)
    #     NB: (1,0) rappresenta la frazione "infinito"
    lower = (0,1)
    upper = (1,0)
    while 'true':
        # invariante di ciclo: lower <= x <=upper
        mediant = (lower[0] + upper[0]), (lower[1]+upper[1])
        if x * mediant[1] > mediant[0]:
            if max_denominator < mediant[1]: return upper
            lower = mediant
        elif x * mediant[1] == mediant[0]:
            if max_denominator >= mediant[1]: return mediant
            if lower[1] < upper[1]: return lower
            return upper
        else:
            if max_denominator < mediant[1]: return lower
            upper = mediant
Naturalmente non e` difficile tradurre questo algoritmo in C++,
ad esempio data una struct fract { unsigned int n, d; }:
fract
farey(double x, int max_denominator) {
    fract lower = {0, 1};
    fract upper = {1, 0};
    for(;;} {
        fract mediant;
        mediant.n = lower.n + upper.n;
        mediant.d = lower.d + upper.d;
        if(x*mediant.d > mediant.n) {
            if(max_denominator<mediant.d) return upper;
            lower = mediant;
        } else if(x*mediant.d==mediant.n) {
            if(max_denominator >= mediant.d) return mediant;
            if(lower.d < upper.d) return lower;
            return upper;
        } else {
            if(max_denominator<mediant.d) return lower;
            upper = mediant;
        }
    }
}
Usando solo addizioni, moltiplicazioni e confronti, l'algoritmo di
approssimazione di Farey offre la potenzialita` di prestazioni assai
elevate (per quei rari casi in cui l'approssimazione di numeri reali
con frazioni dovesse costituire il collo di bottiglia di un programma,
ove mai dovessero presentarsene).
Per studiare le serie di Farey e la loro connessione con altri temi
elementari di teoria dei numeri, si puo` iniziare da
http://www.cut-the-knot.com/blue/Farey.html
Alex

 [...cut..]
Pseudocodice? A me quello sembra + che altro codice Python ;-)
-- 
Lawrence "Rhymes" Oluyede (
rhy...@myself.com
)
"Per cambiare, per diventare un'altra
cosa dobbiamo prima sapere cosa siamo"
(Bruce Lee)

 Pseudocodice? A me quello sembra + che altro codice Python ;-)
Perche`, c'e` differenza?-)
Alex

 wrote in message
news:ldZ48.31186$hi.7...@news1.tin.it...

ROTFL
--
Andrea Ferro
IHHC - Member of HT-Group  DVD Authoring operator  Fan of I.Asimov
C++ Master: 
http://www.brainbench.com/transcript.jsp?pid=2522556
This post expresses personal opinions which may or may not be the
opinions of the company(s) I work for. I speak for myself only.

 frazione.
Grazie per l'esempio. Ho preso spunto da quello e ne ho fatto uino mio. Cmq
ho anche aggirato il problema per i numeri irrazionali, in quanto se
esistono radici evito di svolgerle, piuttosto fattorizzo il numero
all'interno e se possibile porto fuori il quadrato, poi vedo se è posssibile
raccogliere qualcosa con gli altri monomi e semplifico la frazione. In cosa
contrario lascio la scritta radice del numero. Nel codice che sto scrivendo
però ho evitato di utilizzare puntatori visto che ancora non li conosco bene
e mi sono arrangiato con soli cicli.
Grazie ancora a tutti.
Luca Carlon