Algoritmo Frazioni Continue

di il
3 risposte

Algoritmo Frazioni Continue

Ciao a tutti! Sto scrivendo un algoritmo per calcolare i quozienti di una frazione continua, ma non riesco a trovare il modo di evitare l'approssimazione in quanto ad esempio quando va a fare

(1/7)^(-1)-7
non mi da zero ma tipo 0.000000000000002.
quindi come posso evitarlo? in quando il fatto che sia zero mi serve come condizione per fermare un while! grazie in anticipo!

3 Risposte

  • Re: Algoritmo Frazioni Continue

    Ho provato ad eseguire il calcolo proposto nella domanda con diverse impostazioni di "format", ma il risultato è sempre "0.0":
    
     format longg
    >> (1/7)^(-1)-7
    ans =
         0
    >> format longeng
    >> (1/7)^(-1)-7
    ans =
        0.00000000000000e+000
    
    
    Utilizzare una variabile "float" per controllare la condizione di un ciclo non è la scelta migliore, proprio per via delle approssimazioni numeriche che avvengono in certi calcoli.
    In generale (e nel caso specifico della domanda) per gestire il ciclo sarebbe più opportuno utilizzare un numero intero (ad esempio un contatore o un flag che potrebbe essere settato "0" o "1" in qualche "if") calcolato all'interno del ciclo.

    Se nel caso specifico dell'algoritmo in questione non fosse possibile individuare un flag e sia necessario usare un numero "float", si può confrontare il valore (condizione) che controlla il ciclo con un valore di soglia anzichè con "0":
    
    %
    % Definizione soglia: un numero "molto" piccolo che viene utilizzato come
    % approssimazione del valore 0.0.
    %
    soglia=1.0e-12;
    %
    % Confronto con "0.0"
    %
    while(x ~= 0.0)
       %
       %    Codice all'interno del ciclo
       %
    end
    % 
    % Esempi di utilizzo della "soglia"
    %
    while(x >= soglia)
       %
       %    Codice all'interno del ciclo
       %
    end
    %
    flg=1;
    while(flg)
       %
       %    Codice all'interno del ciclo
       %
       if(x <= soglia)
          flg=0;
       end
    end
    %
    while(abs(x) >= soglia)
       %
       %    Codice all'interno del ciclo
       %
    end
    
    Hope this helps.
  • Re: Algoritmo Frazioni Continue

    Ciao ho ancora il mio problema questo è lo script per calcolare i quozienti di una frazione continua

    %Calcolo q'_{i},r'_{i}
    format rat
    FC=input('inserire frazione continua')
    QZ=[];
    RST=[];
    QZ(1)=floor(FC);
    RST(1)=FC-QZ(1);
    i=1;
    %la vera condizione è resti(i)diverso da zero)
    while(RST(i)>1e-3)

    i=i+1
    QZ(i)=fix(1/RST(i-1));
    RST(i)=(sym(1)/sym(RST(i-1)))-sym(QZ(i));
    RST(i)
    end

    QZ

    la frazione che inserisco in input è 127099/891581
    il vettore QZ giusto che dovrebbe calcolare è:[0,7,67,3,7,1,1,1,2,1,1,1,2]
    e il vettore dei resti RST giusto è [202/1417 , 72/4847 ,603/1888, 79/603 , 50/79 ,29/50 , 21/29, 8/21 ,5/8,3/5, 2/3,1/2,0]
    pero il realta il programma calcola
    QZ=[0,7,67,3,7,1,1,1,2,1,1,1,1,1]
    e
    RST=[202/1417 , 72/4847 ,603/1888, 79/603 , 50/79 ,29/50 , 21/29, 8/21 ,5/8,3/5, 232953/349430 ,116477/232953, 116476/116477 ,5/582379]

    quindi il problema sta nella 11-esima iterazione del while in cui mi calcola RST(11)=(5/3)-1 che invece di essere 2/3 esce fuori il numero 232953/349430 !!!!!!! come posso risolvere???


    gRAzie in anticipo
  • Re: Algoritmo Frazioni Continue

    Come spesso accade quando si cerca un baco, il problema non è dove si pensa che sia.
    In questo caso il problema non è nella definizione della soglia per il controllo dell'uscita dal ciclo "while" nè nell'11° iterazione.

    Sostituendo l'istruzione

    "format rat"

    con l'istruzione

    "format longg"

    ed eliminando le chiamate alla funzione "sym", si scopre che Il problema sorge nella 10 iterazione.

    A causa delle approssimazioni numeriche, nel corso della 10° iterazione, il corrispondente elemento del vettore "RST" assume il valore

    0.600000288716453

    anzichè il valore

    0.6

    questo comporta che nell'11° iterazione "RST" assuma il valore

    0.66666571273035

    che, con "format rat" corrisponde a

    232953/349430

    Si può verificare che, settando in fase di debug

    RST(10)=0.6

    si ottiene, come ultimo valore di "QZ" 2.

    L'algoritmo utilizzato nello script risulta molto sensibile agli effetti delle approssimazioni numeriche soprattutto nel caso delle inversioni di valori frazionari; una possibile alternativa, potrebbe essere utilizzare l'algoritmo di Euclide", come nell'esempio in calce.
    
    % 
    % Definizione frazione
    % 
    numeratore=127099;
    denominatore=891581;
    % 
    % Algoritmo di Euclide: Primo passaggio
    % 
    i=1;
    q(i)=floor(numeratore/denominatore);
    r=numeratore-q(i)*denominatore;
    % 
    % Algoritmo di Euclide: il loop termina quando il resto è minore o uguala 1
    % 1
    % 
    while(r > 1)
    %    
    %    Inversione dei "ruoli": il denominatore prende il posto del numeratore
    %    ed i resto quello del denominatore
    %    
       numeratore=denominatore;
       denominatore=r;
    % 
    %    Incremento contatore
    %    
       i=i+1;
    % 
    %    Calcolo del quoziente e del resto
    %    
       q(i)=floor(numeratore/denominatore);
       r=numeratore - q(i)*denominatore;
    end
    % 
    % Se, al termine del loop, il resto è diverso da 0 (=1), l'ultimo valore
    % assunto dal "denominatore" (nella particolare accezione dell'algoritmo)
    % rappresenbta l'ultimo quoziente
    % 
    if(r ~= 0)
       q(i+1)=denominatore;
    end
    
    
    Hope this helps.
Devi accedere o registrarti per scrivere nel forum
3 risposte