Lezione del 12/5/2014

Classe polinomio:

File polynomial.rb

  1#!/usr/bin/env ruby
  2#-------------------------------------------------------------------------#
  3#  Esercitazioni in Laboratorio per il Corso di                           #
  4#  Fondamenti di Informatica e Calcolo Numerico, AA 2013/2014             #
  5#                                                                         #
  6#  Autori:   Enrico Bertolazzi e Carlos Maximiliano Giorgio Bort          #
  7#            Dipartimento di Ingeneria Industriale, Universita` di Trento #
  8#  Sito web: http://www.ing.unitn.it/~bertolaz/                           #
  9#                                                                         #
 10#  Contatti: enrico.bertolazzi@unitn.it, cm.giorgiobort@unitn.it          #
 11#                                                                         #
 12#  Copyright (c) 2014 E.Bertolazzi e C.M. Giorgio Bort                    #
 13#-------------------------------------------------------------------------#
 14
 15
 16# Classe polinomio
 17class Polynomial
 18  attr_reader :dd
 19  attr_reader :x
 20  attr_reader :coeffs
 21  attr_reader :omega
 22  
 23  #
 24  # inizializza il polinomio al polinomio vuoto
 25  #
 26  def initialize( cf = [] )
 27    @dd     = [] # differenze finite
 28    @x      = [] # ascisse di interpolazione
 29    @omega  = [] # coefficienti polinomio omega della interpolazione di Newton
 30    @coeffs = cf # coefficienti polinomio interpolante o polinomio passato
 31  end
 32
 33  #
 34  #  aggiunge un punto di interpolazione al polinomio
 35  #
 36  def add(x,y)
 37    update_dd(x,y)
 38    update_omega(x)
 39    update_coeffs()
 40  end
 41  
 42  #
 43  # somma di due polinomi
 44  #
 45  def +(other)
 46    # calcolo ordine polinomio in uscita
 47    a = self.coeffs.dup # per non modificare i @coeff di self
 48    b = other.coeffs
 49    n = [ a.size, b.size ].max
 50    while a.size < n do a << 0 end
 51    while b.size < n do b << 0 end
 52    for i in 0...n do a[i] += b[i] end # meglio un collect per risparmare il dup
 53    return Polynomial.new a
 54  end
 55  
 56  #
 57  # converte il polinomio in una stringa "human readable"
 58  #
 59  def to_s
 60    tmp = ""
 61    @coeffs.each_with_index do |c,idx|
 62      if idx == 0 then
 63        tmp += c.to_s
 64      elsif idx == 1 then
 65        tmp += " + " + c.to_s + " * x"
 66      else
 67        tmp += " + " + c.to_s + " * x^" + idx.to_s
 68      end
 69    end
 70    tmp = "0" if tmp.empty?
 71    return tmp
 72  end
 73
 74private  
 75
 76  #
 77  # date le differenze divise dd[] che contiene
 78  # f[x0], f[x0,x1], ...., f[x0,x1,...,xn]
 79  # aggiunge in coda la differenza divisa f[x0,x1,...,xn,x[n+1]]
 80  #
 81  def update_dd(x,y)
 82    n = @dd.size
 83    if n == 0 then
 84      @dd << y
 85    else
 86      d = y
 87      for k in 0...n do # fino a n-1
 88        d = (@dd[k]-d)/(@x[k]-x)
 89      end
 90      @dd << d # d contiene f[x0,x1,...,x[n+1]]
 91    end
 92  end
 93  #
 94  # dato omega[n](x) costruisco 
 95  # omega[n+1](x) = omega[n](x)*(x-x[n])
 96  # dove x[n] = @lastx
 97  def update_omega(x)
 98    n = @omega.size
 99    if n == 0 then
100      @omega << 1
101    else
102      # moltiplico @omega * (x-@x[n]) = @omega * x - @x[n] * @omega
103      @omega.insert(0,0) ;
104      for k in 0...n do
105        @omega[k] = @omega[k] - @omega[k+1]*@x[-1]
106      end
107    end
108    @x << x
109  end
110  #
111  # aggiunge al polinomio 
112  # p(x) = f[x0]+f[x1]*(x-x0)+ .... +f[x0,x1,...,xn]*omega[n](x)
113  # il polinomio
114  # f[x0,x1,...,xn,x[n+1]]*omega[n+1](x)
115  # p(x) interpola anche l'ultimo punto inserito
116  def update_coeffs()
117    n = @coeffs.size
118    @coeffs << 0 ;
119    for k in 0..n do
120      @coeffs[k] += @omega[k] * @dd[-1]
121    end
122  end
123end
124
125if __FILE__ == $0
126  poly = Polynomial.new
127  puts "poly = "+poly.to_s
128  poly.add(1,5)
129  puts "poly = "+poly.to_s
130  poly.add(2,15)
131  puts "poly = "+poly.to_s
132  poly.add(3,31)
133  puts "poly = "+poly.to_s
134  poly1 = Polynomial.new [1,2,3]
135  
136  poly2 = poly+poly1
137  puts "poly = "+poly.to_s
138  puts "poly1 = "+poly1.to_s
139  puts "poly+poly1 = "+poly2.to_s
140  
141end