PDA

Visualizza la versione completa : [ALGORITMO] Scambio elementi di un array


superciccio14
12-02-2007, 23:27
Ciao a tutti ho un problema enorme devo cercare un algoritmo per fare determinati scambi sugli elementi di un array, qualcuno sa scrivermi uno pseudocodice implementabile in qualsiasi linguaggio?

vi spiego meglio

devo fare k scambi ogni passo

esempio

supponiamo di avere un array t={1,0,1,1,0} i possibili scambi con k=1 sono m*n dove m sono gli 1 e n gli 0.

per cui avrei un insieme di soluzioni di questo genere

01110
00111
11010
10011
11100
10101

con k=2 le soluzioni prese in analisi saranno (m*n)^2 poich ad ogni array precedente corrispondernno m*n array

Il problema : come faccio al generico passo k ad ottenere tutte le (m*n)^k soluzioni? Sto provando ad annidare dei cilci for ma sto impazzendo...

Grazie in anticipo!

superciccio14
13-02-2007, 10:47
Allora il mio problema che un algoritmo l'ho + o - trovato

forall (i in INSi|v(i)=1)do
forall (a in INSi|v(a)=0)do
v(i):=0
v(a):=1
!a

forall (b in INSi|v(b)=1) do
forall (d in INSi|v(d)=0 )do
v(b):=0
v(d):=1

writeln(" ")
forall(j in 1..5) do
write(v(j))
end-do
writeln(" ")

v(b):=1
v(d):=0

end-do
end-do

v(i):=1
v(a):=0

end-do
end-do


come vedete si tratta di cilci for (in un linguaggio per la programmazione lineare) anidati ma che si annidano all'interno per non riesco a generalizzare la cosa dato che in questo caso la situazione vale solo per k=2

Nessuno sa nulla? urgente!

roxxy86
13-02-2007, 11:48
http://www.math.unipd.it/~colussi/Algoritmi1_2006-07/EsercSvoltiA1.pdf

guarda l'esercizio 2!! Calcola in tempo MAX O(nlogn) il numero di inversioni di un'array!! se ti puo' essere d'aiuto...

superciccio14
13-02-2007, 12:09
Ho visto ma non il mio caso... :(

Loading