Ordinamento "numeri"

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
bh3u4m
Messaggi: 547
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Ordinamento "numeri"

Messaggio da bh3u4m »

Data un sequenza di numeri, essi vengono disposti su una griglia bidimensionale secondo questo ordine:
Il primo viene messo nella posizione (0, 0), in seguito, l'elemento i-esimo viene posto sulla stessa riga in questo modo: se scorrendo tra i valori già presenti non ce n'è uno maggiore di lui, viene messo in fondo alla riga, se invece ne incontra uno maggiore di lui, esso si sostituisce a questo e questo sostituito viene passato alla riga sottostante ed inserito con gli stessi criteri sopra esposti.
Data una certa configurazione, trovare tutte le combinazioni della sequenza iniziale che la genera.
Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Re: Ordinamento "numeri"

Messaggio da Marco »

bh3u4m ha scritto:se invece ne incontra uno maggiore di lui, esso si sostituisce a questo e questo sostituito viene passato alla riga sottostante ed inserito con gli stessi criteri sopra esposti.
Se ce n'è più di uno, il valore abbassato è uno a piacere o il primo che s'incontra?
Avatar utente
bh3u4m
Messaggi: 547
Iscritto il: 01 gen 1970, 01:00
Località: Milano

Re: Ordinamento "numeri"

Messaggio da bh3u4m »

Marco ha scritto:Se ce n'è più di uno, il valore abbassato è uno a piacere o il primo che s'incontra?
E' il primo che si incontra...
Pyv
Messaggi: 11
Iscritto il: 01 gen 1970, 01:00
Località: Latina

Messaggio da Pyv »

Beh, le IOI2001 hanno cambiato la storia anche per i problemi tosti che hanno proposto... TwoFive rimane forse il migliore pero' :)
CUCU
Messaggi: 40
Iscritto il: 01 nov 2005, 14:55

Messaggio da CUCU »

Avevo scritto la soluzione, poi clicco su "anteprima" e per chissà quale errore mi trovo il campo testo tutto vuoto. E non riesco a recuperarlo.
Ora mi scoccia riscriverlo.
A domani :wink:
CUCU
Messaggi: 40
Iscritto il: 01 nov 2005, 14:55

Messaggio da CUCU »

Supponiamo che a sia un array bidimensionale n*n e che non siano stati inseriti più di n-1 elementi e che le posizioni vuote contengano il simbolo 'empty'.
E supponiamo che le righe e le colonne siano numerate a partire da 1 (e non da 0 come dice il testo dell'esercizio).
La prima chiamata all'algoritmo dev'essere f(a,1,1).

f(a,i,j)
{

if (a[j]==empy) return;

if (a[j+1] is not empty)
{
print a[j]
f(a,i,j+1);

}

else
{
Sia k il prossimo indice di riga tale che la prima e la seconda posizione nella riga k non contengono empty;
Se tale k non esiste allora
{
sia k il prossimo indice di riga tale che la prima posizione non contiene empty;
Se ANCHE QUEST'ULTIMO k non esiste
{
print a[j];
return;
}

}
Scambia a[j] con a[k][1];
print a[j];
f(a,i+1,1);
}


}
Rispondi