• Non ci sono risultati.

È possibile risolvere il problema con due sole pesate? 2

N/A
N/A
Protected

Academic year: 2021

Condividi "È possibile risolvere il problema con due sole pesate? 2"

Copied!
1
0
0

Testo completo

(1)

Esercizi

Esercizio 1 [Selection Sort]

Qual è l’invariante di ciclo mantenuto dall’algoritmo SelectionSort?

Esercizio 2 [Ricerca sequenziale]

Considerate il seguente problema di ricerca:

Input: un array a di n interi, non ordinato e una chiave intera k

Output: un indice i tale che k = a[i], o il valore -1 se k non occorre in a.

Progettare un algoritmo di ricerca sequenziale che esamina gli elementi dell’array alla ricerca di k, e studiarne la complessità al caso ottimo, medio e pessimo, valutando il costo in tempo e il numero di confronti effettuati.

Esercizio 3 [Albero di decisione]

Siano date 9 monete d’oro tutte dello stesso peso, tranne una che è più leggera delle altre, e una bilancia a due piatti, su ciascuno dei quali è possibile mettere un numero qualunque di monete e sapere se i piatti hanno lo stesso peso, o quale dei due è più leggero.

1. È possibile risolvere il problema con due sole pesate?

2. In caso di risposta affermativa al punto 1, disegnare l’albero di decisione corrispondente all’algoritmo trovato che risolve il problema con due sole pesate.

Riferimenti

Documenti correlati

Un sistema costituito da 0, 08 moli di gas perfetto biatomico percorre in senso orario un ciclo reversibile composto da due trasformazioni adiabatiche e

DUE AUTO SONO UGUALI, QUALI?.

ClipArt – Raccolta Multimediale Microsoft?.

Per il primo sottospazio abbiamo un sistema

[r]

Una mole di qualsiasi sostanza contiene sempre un numero fisso di entità chimiche pari a 6,023x10 23 (un numero di Avogadro, N A ).. Tutto quello che serve sapere per risolvere

Scrivi la frazione rappresentata e la frazione complementare, la quale ricostruisce l’intero.. Scrivi la frazione complementare e

Considerando il teorema di Pitagora e il fatto che le misure dei lati devono essere espresse da numeri interi (di metri), si ha che l´altezza del trapezio misura m 40, mentre