Algoritmo Divide et Impera

[Zen-Zen]

salve a tutti, sto cercando di fare un esercizio sull'approccio divide et impera per risolvere i problemi, ma mi sono incasinato su questo:

Scrivere un algoritmo divide et impera che, dato in input un array A, sposta ogni suo elemento di una posizione a destra (l’elemento in posizione N sarà spostato in posizione 1)
Esempio:
Se A=[8, 3, 10, 7, 9, 6, 2] al termine dell’esecuzione si avrà A=[2, 8, 3, 10, 7, 9, 6]

è semplice, ma non ci arrivo

sto provando a farlo in java, anche prendendo spunto da come è fatto mergesort, ma niente... l'unica cosa che riesco ad ottenere è il ribaltamento degli elementi, ma non quello chiesto dalla consegna, avete qualche suggerimento? grazie in anticipo

[Zen-Zen]

ok sono riuscito a risolvere da solo il problema precedente(era una cavolata )

ma ora sono bloccato con questo che sembra più complesso per via dell'utilizzo di due array come input:

Scrivere un algoritmo divide et impera che, dati due array A e B, conta quante sono le posizioni in cui appare lo stesso elemento sia in A
che in B.

Esempio:
A=[5, 7, 2, 3, 10, 8, 4]
B=[11, 7, 3, 8, 10, 1, 5]
L’algoritmo deve ritornare 2 perché A[2]=B[2] e A[5]=B[5]


date una mano a un povero niubbo please

[Il Nero]

Mah, dovrebbe bastarti passare ricorsivamente mezzo array + mezzo array all'algoritmo.

Cioe' insomma:

int Conta(Array A, Array B)
{
if (Lunghezza(A) > 1)
return Conta(PrimaMeta'A, PrimaMeta'B) + Conta(SecondaMeta'A, SecondaMeta'B);
if (A[0] = B[0])
return 1;
return 0;
}

Quello che non capisco e' perche in tutti questi esercizi tenti di risolvere con il divide et impera un problema che gia' di suo si risolve in O(n).

Per curiosita', il precedente come l'hai risolto ?

[Zen-Zen]

beh non è che sono io che tento di farlo cosi, è la consegna dell'esercizio che me lo impone

quello precedente l'ho risolto sostituendo il primo elemento della prima metà con il primo elemento della seconda metà però ho usato lo stesso schema della mergesort...ovvero una procedura che divide in 2 l'array e alla fine una procedura che prende in input l'array e i 3 indici(inizio, centro, fine) ed effettuo la sostituzione degli elementi...e funziona...

e naturalmente stavo cercando di risolvere anche il secondo cosi, ma mi incasino di brutto...però guardando il tuo algoritmo mi rendo conto che sono io che non ho capito granchè su come impostare un algoritmo divide et impera pensavo dovessero presentare tutti una struttura simile a mergesort

[Demoxi]

in teoria dividere e imperare dovrebbe semplificare la vita non complicarla. Così non è che impari molto il suo vero utilizzo XD se un algoritmo si può scrivere in 5 righe di codice perchè complicarlo suddividendolo in parti ancora più piccole ? O_O

[Alby87]

Se è per questo, io ho dovuto usare Java Enterprise per scrivere un sistema con le "Transazioni" (Commit, Rollback)... senza poter usare i metodi già in libreria Java Enterprise!

[royp]

potevi barare usando il codice sorgente di java stesso che e' open source