Esame di programmazione...sapete farlo?

[Piojolopez2406]

Il mio professore mi ha assegnato questi 2 programmi da scrivre entro il 15 di ottobre....ma sto avendo grossissimi problemi, se qualcuno di voi sa farli o magari sa darmi qualke dritta gliene sarei immensamente grato....


TRACCIA :

1. algoritmo per “mischiare” un mazzo di carte francesi. L’algoritmo si basa sull’idea di scambiare effettivamente a coppie le carte del mazzo; una variabile in input permette di indicare quante volte si devono effettuare gli scambi (nei test usare i valori: 10,20,50,100,200). Usare la function rand(), il cui prototipo è in <stdlib.h>, per generare a ogni passo gli indici delle due carte da scambiare. Nei test, partire sempre dal mazzo “ordinato” e poi visualizzare il mazzo “mischiato”.
Si ricorda che, se numero_casuale è dichiarata di tipo int, allora la chiamata numero_casuale=rand()%(n+1); genera un numero casuale intero (distribuzione uniforme) nell’insieme (0,1,2,..n).

2. variante dell’algoritmo di ricerca binaria che fa uso di numeri casuali. L’algoritmo, da implementare con tecnica ricorsiva, è una variante della versione standard, in cui l’indice dell’elemento da confrontare non è l’elemento di indice mediano della porzione sotto esame, ma è un indice generato a caso tra quelli che definiscono la porzione in esame; per esempio se la porzione è individuata dal primo indice =10 e dall’ultimo indice = 20, piuttosto che l’elemento di indice mediano (=15), si genera a caso un indice in (10,11,12,..,19,20) e si considera l’elemento di quell’indice nel confronto con la chiave e come elemento di partizione della porzione nelle due successive porzioni. Usare la function rand(), il cui prototipo è in <stdlib.h>, per generare a ogni passo l’indice dell’elemento da considerare a quel passo.
Si ricorda che, se numero_casuale è dichiarata di tipo int, allora la chiamata numero_casuale=rand()%(n+1); genera un numero casuale intero (distribuzione uniforme) nell’insieme (0,1,2,..n).
Oltre ai test normali, si deve effettuare il seguente test: il main definisce un array di size 1024 di int (da generare a caso in [-1000,1000]) e poi per 100 volte chiama la function di ricerca binaria su tale array, sempre con la stessa chiave che non deve appartenere all’array. Contare, per ogni chiamata, il numero di suddivisioni dell’array fatte dalla function (deve essere un dato di output della function) e alla fine visualizzare il valore medio del numero delle suddivisioni (sommare i 100 valori del numero delle suddivisioni e dividere tale somma per 100). Si ricorda che, nel caso di algoritmo standard di ricerca binaria, il numero di suddivisioni nel caso peggiore (chiave che non appartiene) è log2(1024)=10.

[Piojolopez2406]

Originariamente inviato da Piojolopez2406

Il mio professore mi ha assegnato questi 2 programmi da scrivre entro il 15 di ottobre....ma sto avendo grossissimi problemi, se qualcuno di voi sa farli o magari sa darmi qualke dritta gliene sarei immensamente grato....


TRACCIA :

1. algoritmo per “mischiare” un mazzo di carte francesi. L’algoritmo si basa sull’idea di scambiare effettivamente a coppie le carte del mazzo; una variabile in input permette di indicare quante volte si devono effettuare gli scambi (nei test usare i valori: 10,20,50,100,200). Usare la function rand(), il cui prototipo è in <stdlib.h>, per generare a ogni passo gli indici delle due carte da scambiare. Nei test, partire sempre dal mazzo “ordinato” e poi visualizzare il mazzo “mischiato”.
Si ricorda che, se numero_casuale è dichiarata di tipo int, allora la chiamata numero_casuale=rand()%(n+1); genera un numero casuale intero (distribuzione uniforme) nell’insieme (0,1,2,..n).

2. variante dell’algoritmo di ricerca binaria che fa uso di numeri casuali. L’algoritmo, da implementare con tecnica ricorsiva, è una variante della versione standard, in cui l’indice dell’elemento da confrontare non è l’elemento di indice mediano della porzione sotto esame, ma è un indice generato a caso tra quelli che definiscono la porzione in esame; per esempio se la porzione è individuata dal primo indice =10 e dall’ultimo indice = 20, piuttosto che l’elemento di indice mediano (=15), si genera a caso un indice in (10,11,12,..,19,20) e si considera l’elemento di quell’indice nel confronto con la chiave e come elemento di partizione della porzione nelle due successive porzioni. Usare la function rand(), il cui prototipo è in <stdlib.h>, per generare a ogni passo l’indice dell’elemento da considerare a quel passo.
Si ricorda che, se numero_casuale è dichiarata di tipo int, allora la chiamata numero_casuale=rand()%(n+1); genera un numero casuale intero (distribuzione uniforme) nell’insieme (0,1,2,..n).
Oltre ai test normali, si deve effettuare il seguente test: il main definisce un array di size 1024 di int (da generare a caso in [-1000,1000]) e poi per 100 volte chiama la function di ricerca binaria su tale array, sempre con la stessa chiave che non deve appartenere all’array. Contare, per ogni chiamata, il numero di suddivisioni dell’array fatte dalla function (deve essere un dato di output della function) e alla fine visualizzare il valore medio del numero delle suddivisioni (sommare i 100 valori del numero delle suddivisioni e dividere tale somma per 100). Si ricorda che, nel caso di algoritmo standard di ricerca binaria, il numero di suddivisioni nel caso peggiore (chiave che non appartiene) è log2(1024)=10.

quoto

[Marco Giunio Silano]

Originariamente inviato da Piojolopez2406

quoto

quoto? al massimo autoquoto

[ianaz]

Originariamente inviato da Marco Giunio Silano

quoto? al massimo autoquoto

o uppo


dai, up

[cionci]

Nessuno risponderà mai ad un quesito posto in questi termini, non possiamo fare l'intero esercizio per te, possiamo però darti una mano a partire dal codice che hai già fatto o un punto particolare del problema...

[Ziosilvio]

Originariamente inviato da Piojolopez2406

Il mio professore mi ha assegnato questi 2 programmi da scrivre entro il 15 di ottobre

Buon lavoro.

ma sto avendo grossissimi problemi

Quali?
Se ce li spieghi, forse possiamo aiutarti.

se qualcuno di voi sa farli

Qui non si fanno i compiti altrui.

o magari sa darmi qualke dritta

Questa, invece, è una richiesta ragionevolissima.

algoritmo per “mischiare” un mazzo di carte francesi. L’algoritmo si basa sull’idea di scambiare effettivamente a coppie le carte del mazzo; una variabile in input permette di indicare quante volte si devono effettuare gli scambi (nei test usare i valori: 10,20,50,100,200). Usare la function rand(), il cui prototipo è in <stdlib.h>, per generare a ogni passo gli indici delle due carte da scambiare. Nei test, partire sempre dal mazzo “ordinato” e poi visualizzare il mazzo “mischiato”.

Sulla generazione di sequenze pseudorandom in C, c'è un tutorial nella sezione apposita.
L'idea sembra abbastanza semplice: anzitutto, identifichi ogni carta con un numero tra 0 e 51, ad esempio parti da 0 = "due di picche", poi 1 = "tre di picche", e così via, fino a 51 = "asso di cuori".
Poi, inizializzi un vettore carte, di 52 elementi, ponendo carte[n]=n per ogni n da 0 a 51.
Poi, fai un certo numero di passi, in ciascuno dei quali chiami due volte rand per generare due interi pseudorandom n1 e n2 tra 0 e 51 inclusi, e scambiando di posto le carte corrispondenti, ossia scambiando i valori presenti in carte[n1] e carte[n2].

Si ricorda che, se numero_casuale è dichiarata di tipo int, allora la chiamata numero_casuale=rand()%(n+1); genera un numero casuale intero (distribuzione uniforme) nell’insieme (0,1,2,..n).

A priori, numero_casuale=rand()%(n+1) è uniforme se e solo se n+1 è un divisore di RAND_MAX+1.
Questo lo sa chiunque abbia letto il K&R e conosca un minimo di teoria dei generatori pseudorandom, ad esempio avendola letta sul secondo volume di "The Art of Computer Programming".

variante dell’algoritmo di ricerca binaria che fa uso di numeri casuali. L’algoritmo, da implementare con tecnica ricorsiva, è una variante della versione standard, in cui l’indice dell’elemento da confrontare non è l’elemento di indice mediano della porzione sotto esame, ma è un indice generato a caso tra quelli che definiscono la porzione in esame; per esempio se la porzione è individuata dal primo indice =10 e dall’ultimo indice = 20, piuttosto che l’elemento di indice mediano (=15), si genera a caso un indice in (10,11,12,..,19,20) e si considera l’elemento di quell’indice nel confronto con la chiave e come elemento di partizione della porzione nelle due successive porzioni. Usare la function rand(), il cui prototipo è in <stdlib.h>, per generare a ogni passo l’indice dell’elemento da considerare a quel passo.
Si ricorda che, se numero_casuale è dichiarata di tipo int, allora la chiamata numero_casuale=rand()%(n+1); genera un numero casuale intero (distribuzione uniforme) nell’insieme (0,1,2,..n).

Le considerazioni sono simili a quelle fatte prima.
Stavolta, a ogni passo hai un indice jmin e un indice jmax, e devi generare un intero pseudorandom tra jmin e jmax inclusi.
Se conosci l'algoritmo di ricerca binaria --- e dovresti conoscerlo, a questo punto del tuo corso di studi --- il resto viene da sé.

Oltre ai test normali, si deve effettuare il seguente test: il main definisce un array di size 1024 di int (da generare a caso in [-1000,1000]) e poi per 100 volte chiama la function di ricerca binaria su tale array, sempre con la stessa chiave che non deve appartenere all’array. Contare, per ogni chiamata, il numero di suddivisioni dell’array fatte dalla function (deve essere un dato di output della function) e alla fine visualizzare il valore medio del numero delle suddivisioni (sommare i 100 valori del numero delle suddivisioni e dividere tale somma per 100). Si ricorda che, nel caso di algoritmo standard di ricerca binaria, il numero di suddivisioni nel caso peggiore (chiave che non appartiene) è log2(1024)=10.

Effettuare una ricerca binaria su un array potenzialmente non ordinato, è una delle cose più sbagliate che si possano fare in Informatica.
E' una fortuna che lo scopo dell'esercizio non sia trovare un elemento di un array, ma contare il numero medio di passi ricorsivi: cosa per la quale, in realtà, si fa presto a vedere che non è necessario che l'array sia ordinato.
A proposito: il conteggio si può fare con una variabile globale, che viene passata alla funzione di ricerca binaria (ovviamente tramite puntatori) e incrementata a ogni chiamata ricorsiva.