Algoritmo di ordinamento: output

1

Ho affrontato questo problema su un sito web e non riesco a capire l'output, per favore aiutami a capirlo: -

Bogosort, è un algoritmo stupido che mescola casualmente la sequenza finché non viene ordinata. Ma qui lo abbiamo modificato leggermente, in modo tale che se dopo l'ultimo shuffle alcuni dei primi elementi finiscono nei posti giusti li aggiustiamo e non rimescoliamo questi elementi. Faremo lo stesso per gli ultimi elementi se sono nei posti giusti. Ad esempio, se la sequenza iniziale è (3, 5, 1, 6, 4, 2) e dopo uno shuffle otteniamo (1, 2, 5, 4, 3, 6) manterremo 1, 2 e 6 e procediamo con l'ordinamento (5, 4, 3) usando lo stesso algoritmo. Calcola la quantità prevista di shuffles per l'algoritmo migliorato per ordinare la sequenza dei primi n numeri naturali dato che nessun elemento è nel posto giusto inizialmente.

Input:

2
6
10

Output:

2
1826/189
877318/35343

Per ogni caso di test, viene prodotta la quantità prevista di shuffles necessari per l'algoritmo migliorato per ordinare la sequenza dei primi n numeri naturali sotto forma di frazioni irriducibili. Non riesco a capire l'output.

    
posta potato man 17.06.2012 - 11:58
fonte

1 risposta

1

Stai lavorando con un algoritmo stocastico, l'output richiesto è il valore atteso E [X] del numero di shuffles X necessari per ordinare il vettore (che è casuale in ogni dato tentativo).

Dato un vettore di input di dimensione N senza numeri al loro posto (non ti danno il vettore perché può essere mostrato che E [X] è lo stesso per tutti i vettori di N numeri con questa proprietà), che può essere "Bogosorted" in k modi diversi, in ogni modo con Si shuffles e con la probabilità di comparsa Pi , quindi E[X] = sum(Pi * Si)/sum(Pi) dove la somma è presa in tutti i modi possibili in cui il vettore può essere ordinato in questo modo (ovviamente, sum(Pi) = 1 quindi è in realtà E[X] = sum(Pi * Si) ).

Porta la frazione di [X] in irriducibile, e c'è il tuo risultato.

    
risposta data 17.06.2012 - 12:32
fonte

Leggi altre domande sui tag