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.
Ordinamento "numeri"
Re: Ordinamento "numeri"
Se ce n'è più di uno, il valore abbassato è uno a piacere o il primo che s'incontra?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.
Re: Ordinamento "numeri"
E' il primo che si incontra...Marco ha scritto:Se ce n'è più di uno, il valore abbassato è uno a piacere o il primo che s'incontra?
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);
}
}
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);
}
}