Programmazione orientata ad oggetti - Appello 20-07-12 sol

PROGRAMMAZIONE ORIENTATA AGLI OGGETTI (DM 270)

Appello del 20-07-2012 – Allievi Informatici

Cognome: Nome: Matr: Durata: 3 ore

Esercizio 1. Dato n=11 bit, (a) specificare l'intervallo di rappresentazione degli interi relativi ad n bit per Numero add( Numero x ); complementi a due (c2), (b) dire se gli interi i1=-573, Numero sub( Numero x ); i2=-675 sono rappresentabili per c2 a 11 bit e se sì Numero mul( Numero x ); 10 mostrare le loro rappresentazioni in bit c2 (c) eseguire Numero div( Numero x ); in aritmetica binaria le operazioni -i1+i2 e i1+i2, Numero rem( Numero x ); segnalando e motivando ogni eventuale problema di Numero pow( int esp ); traboccamento c2; (d) dato il numero in c2 ad 11 bit: i=11111010100 , specificare il valore relativo di i in base 10.

Le operazioni aritmetiche si basano sugli usuali algoritmi manuali "carta e penna" e restituiscono un nuovo numero contenente il risultato dell'operazione,

Esercizio 2. Per il numero reale r

=-573.47 , o sollevano un'eccezione se l'operazione non è derivare la sua rappresentazione a 32 bit floating fattibile (es. in una operazione di sub, il valore di this èpoint IEEE 754 (singola precisione), e mostrarla sia in minore di quello del parametro x). La pow() restituiscebit che in codice esadecimale. il numero this elevato al parametro intero esp(supposto non negativo). Il metodo size() ritorna ilEsercizio 3. Scrivere un programma Java che legge numero di cifre del numero. Il metodo remda input un vettori v di 10 interi >1 e genera un corrisponde a % sugli int di Java: ritorna il resto dellasecondo vettore z di 10 boolean da riempire come divisione intera tra this e x. L'iteratore ritorna le cifresegue. Per ogni indice i valido, z[i] è uguale a true (1) del numero dalla cifra più significativa a quella menose v[i] è un numero primo, false (0) altrimenti. Il significativa.programma deve scrivere in uscita il

contenutocostruito di z. Successivamente convertire La classe astratta deve concretizzare quanti piùsistematicamente il programma Java in Assembler metodi è possibile e sicuramente i metodi standardRASP. equals(), toString() e hashCode(). Il metodo toString()deve ritornare le cifre di this (da più significativa aEsercizio 4. Data la sequenza di input: 15 45 -2 13 meno significativa) sottoforma di stringa.34 -9 7 10 -1 3 5, mostrare separatamente ilcontenuto dell’albero binario di ricerca (abr) e Implementare una classe concreta NumeroListadell’heap corrispondenti. Nell’ipotesi che venga erede di Numero. NumeroLista deve memorizzarerimosso l’elemento -2 dall’abr, mostrare come cambia un numero a precisione illimitata su una listal’abr. Similmente, se viene estratto il minimo dall’heap, concatenata doppia a puntatori espliciti, in cui ognicome cambia l’heap? nodo memorizza una singola cifra intera. Della lista

<p>simantengono l’inizio e la fine.</p>
<p>Esercizio 5.</p>
<p>Si considerano applicazioni che debbano lavorare su Sviluppare inoltre, nello stesso package, una classe di numeri interi senza segno, dotati di un qualsivoglia utilità Numeri che esporta (almeno): numero di cifre (precisione illimitata). Il concetto di <em>il metodo factory Numero crea( String s ) che crea numero (oggetto immutabile) è formalizzato dalla e restituisce un oggetto Numero a partire dalla classe astratta Numero: stringa s (che deve contenere una sequenza di cifre)</em> package poo.aritmetica; le costanti ZERO e UNO di tipo Numero.</p>
<p>public abstract class Numero implements Comparable<Numero>, Iterable<Integer>{ La classe Numeri deve basarsi sulla classe NumeroLista.}//Numero che esporta i metodi: (continua dietro)1</p>
<p>Esercizio 6.</p>
<p>Realizzare un’applicazione interattiva del tipo Bozze soluzioni “calcolatrice matematica a precisione estesa”. Per terminare l’applicazione occorre digitare</p>

‘.’ su una Esercizio 1.10 10linea a sé stante. Una generica linea di input contiene a) [-2 ,2 -1]=[-1024,1023]un’assegnazione del tipo: v=espr dove v è un nome di b) i1=-573 , i2=-675 sono rappresentabili10 10variabile (secondo la sintassi Java), espr |i1|=573=01000111101 =>un’espressione aritmetica che può essere un singolo c2(i1)=c2(-573)=10111000011operando, oppure opnd1 op opnd2 (senza spazi |i2|=675=01010100011 =>intermedi). Gli operandi possono essere o nomi di c2(i2)=c2(-675)=10101011101variabili già assegnate, o costanti intere a precisione c) –i1+i2=c2(i1)+i2=arbitraria. L’operatore op può essere uno tra +,-,*,/, 01000111101+%,^. Si capisce che è possibile calcolare il risultato di 10101011101=un’espressione complessa svolgendo separatamente -----------------------sotto calcoli e conservando il loro valore in variabili. 11110011010 nessun trabocco (…) =-102Segue un esempio di

Il tuo compito è formattare il testo fornito utilizzando tag html.

ATTENZIONE: non modificare il testo in altro modo, NON aggiungere commenti, NON utilizzare tag h1;

poi) è la somma Esercizio 3.dei due numeri che immediatamente lo precedono. Si ;int []v=new int[10];vuole scrivere un metodo long fibo(int n) della classe ;int []z=new int[10]; //bit 0 o 1;for( int i=0; i<v.length; ++i ){di utilità poo.util.Mat che restituisce l’n-esimo (n>=1) ; leggi v[i]; assert v[i]>1;numero della serie di Fibonacci. ;}Esistono diversi algoritmi per calcolare fibo(n). Segue ;for( int i=0; i<v.length; ++i ){un esempio. Sia A una matrice 2x2 di interi cosi ; if( v[i]<=3 ) z[i]=1;definita: {{1,1},{1,0}}. Si può dimostrare che l’n-esimo ; else if( v[i]%2==0 ) z[i]=0;; else{numero della serie di Fibonacci coincide con ; for( int d=3; d<=v[i]/2; d=d+2 ){n-1l’elemento [0][0] della matrice potenza A . ; if( v[i]%d==0 ){ z[i]=0; break; }Concretamente, il metodo fibo(n) deve basarsi su un ; }metodo privato ricorsivo per il calcolo della potenza di ; z[i]=1;n-1A se n>1. Per velocizzare il calcolo, si suggerisce la ;

};}
k k/2 k/2
seguente tecnica logaritmica:
A = A x A se k è pari,
for (int i = 0; i < z.length; ++i) {
    scrivi z[i];
}
k k/2 k/2 k/2
A = A x A x A se k è dispari.
A si calcola poi allo stesso modo.

2V: RES 10
STORE D
Z: RES 10
LOAD @V
ILOAD # 10
DIV # 2
STORE LENGTH
STORE LIMITE
LOAD # 0
FOR I: STORE I
LOAD D
LET V: SUB LIMITE
LOAD I
JGZ EFORI
SUB LENGTH
LOAD @V
IJZ V
TEL DIV D
LOAD # V
MUL D
ADD I
SUB @V
ISTORE V
I
JNZ GIRARE
AD @V
LOAD # 0
LOAD @V
STORE @ZI
SUB # 1
JUMP CONTINUA
JLEZ FINE

GIRA:
LOAD I
LOAD D
ADD # 1
ADD # 2
STORE I
STORE D
JUMP LETV
JUMP FORI

VTEL: EFORI:
LOAD # 0
LOAD # 1
STORE I
STORE @ZI

FORE: CONTINUA:
LOAD I
LOAD I
SUB LENGTH
ADD # 1
JZ EFORE
STORE I
LOAD # V
JUMP FORE

ADD I EFORE:
STORE V
I
LOAD # 0
LOAD # Z
STORE I
ADD I
SCRZ: STORE Z
I
LOAD I
LOAD @V
SUB LENGTH
SUB # 3
JZ FINE
JGZ AVANTI
LOAD # Z
LOAD # 1
ADD I
STORE @ZI
STORE ZI
JUMP CONTINUA
WRITE @ZI

AVANTI: LOAD I
LOAD @V
ADD # 1
DIV # 2
STORE I
MUL # 2
JUMP SCRZ
SUB @V

FINE: JNZ PROSEGUI
HALT
LOAD # 0
STORE @ZI
JUMP CONTINUA

PROSEGUI: LOAD # 3
3
throw new

RuntimeException("Divisione per zero!");

Esercizio 4: Numero r=Numeri.crea( this.toString() );
Utilizzando la visita pre e indicando con . un sotto albero vuoto si Numero q=Numeri.ZERO;
ha:
do{
    if( r.compareTo(x)>=0 ){
        abr iniziale: r=r.sub(x);
        15 -2 -9 .. 13 7 -1 . 3 . 5 .. 10 … 45 34 …
        q=q.add(Numeri.UNO);
        abr dopo rimozione -2:
    }
    15 -1 -9 .. 13 7 3 . 5 .. 10 … 45 34 …
}while( r.compareTo(x)>=0 );
return r;

heap iniziale:
}//rem[-9,-1,-2,10,3,15,7,45,13,34,5]
heap dopo rimozione del minimo -9:

public Numero pow( int esp ){
    [-2,-1,5,10,3,15,7,45,13,34]
    if( esp<0 )
        throw new RuntimeException("Esponente negativo!");

    Esercizio 5: Numero pot=Numeri.UNO;
    package poo.aritmetica;

    for( int i=0; i, Iterable {
    }//pow

    public abstract Numero add( Numero x );
    public abstract Numero sub( Numero x );
    public boolean

Numeri.ZERO; return sb.toString();
if( x.equals(Numeri.ZERO) )
}//toString
throw new RuntimeException("Divisione per zero!");
Numero r = Numeri.crea(this.toString());
public int compareTo(Numero x) {
    Numero q = Numeri.ZERO;
    if (this.size() > x.size())
        return 1;
    do {
        if (this.size() < x.size())
            return -1;
        if (r.compareTo(x) >= 0) {
            if (this.equals(x))
                return 0;
            r = r.sub(x);
            Iterator<Integer> i1 = this.iterator(), i2 = x.iterator();