View Full Version : [Tutti] Contest: Esercizio per le vacanze
Ecco un bell'esercizio per le vacanze.
Semplice e veloce, quando si trova il modo...
Come al solito, lasciamo tempo per pensare agli altri, nel caso in cui la soluzione ci fulminasse in fretta.
Sia dato una array di numeri interi, di lunghezza indefinita.
Si vuole ottenere come risultato un array di pari lunghezza, con ciascuna cella valorizzata tale per cui essa sia il prodotto di tutte le celle dell'array originale, tranne la propria cella corrispondente.
Es:
Array Originale: 1 5 6 3 4
Array risultate di 5 elementi.
Nella prima cella si vorrebbe avere il prodotto dei valori 5*6*3*4
Nella seconda cella invece 1*6*3*4
(il secondo, ovvero il 5, corrispondente alla nostra posizione, non si vuole)
Nella terza cella invece 1*5*3*4
etc.
Array risultato = 360 72 60 120 90
(Sempre se non ho fatto i soliti errori manuali)
Bene.
Ma c'e' un problema.
Non siamo sul nostro processore preferito.
Siamo sull'utlimissimo e innovativo processore progettato da Z80Fan, cdimauro, cionci e tutti gli altri.
Nella foga di pensare agli indirizzamenti, ai registri, ai bus e al resto, si sono dimenticati di focalizzarsi sulla ALU.
E in questa prima versione di processore si sono dimenticati semplicemente della DIVISIONE.
La divisione non la possiamo utilizzare mai.
Ne' all'inizio, ne durante, ne alla fine ne in alcun minimo step, perche' eseguendo la divisione del nostro linguaggio preferito viene sollevata un'eccezione macchina.
Qui l'array originale
2 1 3 1 2 2 3 3 4 3 3 1 1 4 4 4 2 2 4 4 4 2 2 4 2 3 1 1 3 3 2 1 3 4 3 4 2 1 4 1 3 1 4 4 1 2 1 2 4 1 2 4
Non facciamoci ingannare dai valori bassi degli elementi. Potrebbero essere a priori anche alti.
Sono bassi perche' gia' cosi' i risultati sono valori parecchio grandi, e infatti occorre restituire un array di elementi almeno a 64bit per poter ospitare correttamente tutti i risultati.
Inoltre il nostro responsabile e' uno schiavista da piantagione.
Si richiede che il risultato sia geenrato mediante un algoritmo di complessita' O(N)
Ma per iniziare ciascuno provi a buttare giu' la soluzione come riesce...
Bene, niente divisioni (mai) e buon lavoro (e buone vacanze, io domani saro' a galleggiare sul mar Rosso)
Ecco un bell'esercizio per le vacanze.
Semplice e veloce, quando si trova il modo...
Come al solito, lasciamo tempo per pensare agli altri, nel caso in cui la soluzione ci fulminasse in fretta.
Sia dato una array di numeri interi, di lunghezza indefinita.
Si vuole ottenere come risultato un array di pari lunghezza, con ciascuna cella valorizzata tale per cui essa sia il prodotto di tutte le celle dell'array originale, tranne la propria cella corrispondente.
Es:
Array Originale: 1 5 6 3 4
Array risultate di 5 elementi.
Nella prima cella si vorrebbe avere il prodotto dei valori 5*6*3*4
Nella seconda cella invece 1*6*3*4
(il secondo, ovvero il 5, corrispondente alla nostra posizione, non si vuole)
Nella terza cella invece 1*5*3*4
etc.
Array risultato = 360 72 60 120 90
(Sempre se non ho fatto i soliti errori manuali)
Bene.
Ma c'e' un problema.
Non siamo sul nostro processore preferito.
Siamo sull'utlimissimo e innovativo processore progettato da Z80Fan, cdimauro, cionci e tutti gli altri.
Nella foga di pensare agli indirizzamenti, ai registri, ai bus e al resto, si sono dimenticati di focalizzarsi sulla ALU.
E in questa prima versione di processore si sono dimenticati semplicemente della DIVISIONE.
La divisione non la possiamo utilizzare mai.
Ne' all'inizio, ne durante, ne alla fine ne in alcun minimo step, perche' eseguendo la divisione del nostro linguaggio preferito viene sollevata un'eccezione macchina.
Qui l'array originale
2 1 3 1 2 2 3 3 4 3 3 1 1 4 4 4 2 2 4 4 4 2 2 4 2 3 1 1 3 3 2 1 3 4 3 4 2 1 4 1 3 1 4 4 1 2 1 2 4 1 2 4
Non facciamoci ingannare dai valori bassi degli elementi. Potrebbero essere a priori anche alti.
Sono bassi perche' gia' cosi' i risultati sono valori parecchio grandi, e infatti occorre restituire un array di elementi almeno a 64bit per poter ospitare correttamente tutti i risultati.
Inoltre il nostro responsabile e' uno schiavista da piantagione.
Si richiede che il risultato sia geenrato mediante un algoritmo di complessita' O(N)
Ma per iniziare ciascuno provi a buttare giu' la soluzione come riesce...
Bene, niente divisioni (mai) e buon lavoro (e buone vacanze, io domani saro' a galleggiare sul mar Rosso)
Per ora mi viene in mente solo una versione O(2N)
Ci penserò meglio quando sarò ispirato :D
Fare la divisione usando altre funzioni non è un problema. L'o(n) invece sembra più impegnativo come requisito. Per ora ho ancora due cicli. Uno per il totale e l'altro in cui divido.
Per ora mi viene in mente solo una versione O(2N)
Ci penserò meglio quando sarò ispirato :D
O(2N) è O(N) ;)
Anche a me viene in mente così...
Non posso postare per non rovinare il gioco, comunque l'idea che avevo è corretta ed è O(N): si va avanti e poi si torna indietro ;)
Oddio non capisco.. Ho un bug che mi fa sclerare. Se metto l'array da cinque elementi, uguale al tuo, ho i risultati uguali. Se metto quello lungo, ottengo tutti zeri :D Qualcuno riesce a capire cosa potrebbe essere senza guardare il codice? Contenst nel contest :D
EDIT: dimenticato di dire che l'ho scritto in java.
Non posso postare per non rovinare il gioco, comunque l'idea che avevo è corretta ed è O(N): si va avanti e poi si torna indietro ;)
La mia stessa idea :D
è O(N) sia per quanto riguarda la complessita computazionale sia per la quantità di memoria occupata
Forse ho trovato la soluzione anche io, tra un po' implemento il codice e vediamo cosa esce con l'array grande :D.
EDIT: dimenticato di dire che l'ho scritto in java.
Sei probabilmente in overflow perche' stai usando interi a 32bit.
Ne servono almeno 64bit
Non posso postare per non rovinare il gioco, comunque l'idea che avevo è corretta ed è O(N): si va avanti e poi si torna indietro ;)
Mi sa che hai beccato una soluzione corretta. :)
Mi sa che hai beccato una soluzione corretta. :)
Se ho copiato bene il vettore di partenza:
Res[0] = 779100745302540288
Res[1] = 1558201490605080576
Res[2] = 519400496868360192
Res[3] = 1558201490605080576
Res[4] = 779100745302540288
Res[5] = 779100745302540288
Res[6] = 519400496868360192
Res[7] = 519400496868360192
Res[8] = 389550372651270144
Res[9] = 519400496868360192
Res[10] = 519400496868360192
Res[11] = 1558201490605080576
Res[12] = 1558201490605080576
Res[13] = 389550372651270144
Res[14] = 389550372651270144
Res[15] = 389550372651270144
Res[16] = 779100745302540288
Res[17] = 779100745302540288
Res[18] = 389550372651270144
Res[19] = 389550372651270144
Res[20] = 389550372651270144
Res[21] = 779100745302540288
Res[22] = 779100745302540288
Res[23] = 389550372651270144
Res[24] = 779100745302540288
Res[25] = 519400496868360192
Res[26] = 1558201490605080576
Res[27] = 1558201490605080576
Res[28] = 519400496868360192
Res[29] = 519400496868360192
Res[30] = 779100745302540288
Res[31] = 1558201490605080576
Res[32] = 519400496868360192
Res[33] = 389550372651270144
Res[34] = 519400496868360192
Res[35] = 389550372651270144
Res[36] = 779100745302540288
Res[37] = 1558201490605080576
Res[38] = 389550372651270144
Res[39] = 1558201490605080576
Res[40] = 519400496868360192
Res[41] = 1558201490605080576
Res[42] = 389550372651270144
Res[43] = 389550372651270144
Res[44] = 1558201490605080576
Res[45] = 779100745302540288
Res[46] = 1558201490605080576
Res[47] = 779100745302540288
Res[48] = 389550372651270144
Res[49] = 1558201490605080576
Res[50] = 779100745302540288
Res[51] = 389550372651270144
Certo che sono proprio malato...
const int v[] = {2, 1, 3, 1, 2, 2, 3, 3, 4, 3,
3, 1, 1, 4, 4, 4, 2, 2, 4, 4,
4, 2, 2, 4, 2, 3, 1, 1, 3, 3,
2, 1, 3, 4, 3, 4, 2, 1, 4, 1,
3, 1, 4, 4, 1, 2, 1, 2, 4, 1, 2, 4};
const int size = sizeof(v) >> (ffs(sizeof(int)) - 1);
const int last = size - 1;
long long prod[size];
long long res[size];
Non è colpa mia...non si poteva usare la divisione :asd:
Certo che sono proprio malato...
const int v[] = {2, 1, 3, 1, 2, 2, 3, 3, 4, 3,
3, 1, 1, 4, 4, 4, 2, 2, 4, 4,
4, 2, 2, 4, 2, 3, 1, 1, 3, 3,
2, 1, 3, 4, 3, 4, 2, 1, 4, 1,
3, 1, 4, 4, 1, 2, 1, 2, 4, 1, 2, 4};
const int size = sizeof(v) >> (ffs(sizeof(int)) - 1);
const int last = size - 1;
long long prod[size];
long long res[size];
Non è colpa mia...non si poteva usare la divisione :asd:
:confused:
La divisione non serve :mbe:
:confused:
La divisione non serve :mbe:
:confused:
"The sizeof operator yields the size of its operand with respect to the size of type char."
Fatto, ma non mi riesce di non andare in overflow in C :D
E' che non mi basta la voglia di creare un progetto x64 per espandere gli unsigned long.
Cmq m'è venuto lungo una decina di righe, 2N come esecuzione e N come memoria (se consideriamo che il risultato lo scrivo nell'input).
Un tipo a 64 bit ce l'ha sicuramente il tuo compilatore ;)
Su gcc a 32 bit ad esempio c'è long long...
Fatto, adesso devo fare un programma che controlli i risultati con quelli di cionci :sofico:
Fatto, adesso devo fare un programma che controlli i risultati con quelli di cionci :sofico:
Su...è semplice. Il prodotto di tutti è quello che hai nelle posizioni dove c'è l'1...nelle altre basta che sia la metà, un terzo o un quarto...
Su...è semplice. Il prodotto di tutti è quello che hai nelle posizioni dove c'è l'1...nelle altre basta che sia la metà, un terzo o un quarto...
Si ma a me vengono sfalsati, sarà che uso un algoritmo tutto mio :Prrr:
Occhio che l'algoritmo deve funzionare anche con il test di prova
E anche con array tipo
4 233 1313131 233 14 4443
(Overflow a parte)
Un tipo a 64 bit ce l'ha sicuramente il tuo compilatore ;)
Su gcc a 32 bit ad esempio c'è long long...
long long? :stordita:
It's magic (cit.)
Comunque ora funziona, mi vengono i tuoi stessi risultati.
Cmq non ho fatto controllando le frazioni, io l'ho risolto in 2N con un doppio accumulatore... così dovrebbe funzionare con qualsiasi numero fornito in input.
In fondo questo problema, quando si rimuove la divisione, diventa una classica Reduction (http://en.wikipedia.org/wiki/Prefix_sum), che dà tanti grattacapi nelle architetture parallele :D
I miei risultati sono leggermente diversi da quelli di cionci. In alcuni numeri sbaglia l'ultima cifra. Spero conti lo stesso come soluzione perché la teoria di fondo è giusta. È colpa del signor intel che il core 2 duo non ha una precisione infinita :O
Fatto, ma non mi riesce di non andare in overflow in C :D
E' che non mi basta la voglia di creare un progetto x64 per espandere gli unsigned long.
Cmq m'è venuto lungo una decina di righe, 2N come esecuzione e N come memoria (se consideriamo che il risultato lo scrivo nell'input).
Una riga in haskell :eek: :D
:confused:
"The sizeof operator yields the size of its operand with respect to the size of type char."
Allora non ho capito cosa intendevi dire..
Allora non ho capito cosa intendevi dire..
Per ottenere la dimensione del vettore dovevo fare siezof(v) / sizof(int), visto che non potevo fare la divisione l'ho sostituito con quel coso (ffs trova il primo bit settato in un bitmap).
In fondo questo problema, quando si rimuove la divisione, diventa una classica Reduction (http://en.wikipedia.org/wiki/Prefix_sum), che dà tanti grattacapi nelle architetture parallele :D
L'algoritmo presentato lì comunque è O(N*log(N))...
Hai usato due accumulatori ? Non riesco a capire come tu faccia ad ottenere il risultato. Anzi, sarebbe interessante vederlo. A me serve un vettore di dimensione pari all'input per contenere i prodotti parziali.
rеpne scasb
27-06-2010, 11:04
■
Simile a come l'ho fatto io, non proprio uguale. Nel tuo mi sembra che il terzo vettore non sia eliminabile sfruttando il primo per contenere i risultati...
const int v[] = {
2, 1, 3, 1, 2, 2, 3, 3, 4, 3,
3, 1, 1, 4, 4, 4, 2, 2, 4, 4,
4, 2, 2, 4, 2, 3, 1, 1, 3, 3,
2, 1, 3, 4, 3, 4, 2, 1, 4, 1,
3, 1, 4, 4, 1, 2, 1, 2, 4, 1,
2, 4
};
const int size = sizeof(v) >> (ffs(sizeof(int)) - 1);
const int last = size - 1;
long long prod[size];
long long res[size];
prod[0] = v[0];
prod[last] = v[last];
for(int i = 1; i < last; ++i)
{
prod[i] = prod[i-1] * v[i];
}
long long tot = prod[last - 1] * v[last];
res[last] = prod[last - 1];
for(int i = last - 1; i > 0; --i)
{
prod[i] = v[i] * prod[i + 1];
res[i] = prod[i - 1] * prod[i + 1];
}
res[0] = prod[1];
for(int i = 0; i < size; ++i)
{
printf("Res[%d] = %lld %c\n", i, res[i], (tot / v[i] == res[i]) ? 'V':'F');
}
PS: la divisione in fondo serve per verificare i risultati ;)
I miei risultati sono leggermente diversi da quelli di cionci. In alcuni numeri sbaglia l'ultima cifra. Spero conti lo stesso come soluzione perché la teoria di fondo è giusta. È colpa del signor intel che il core 2 duo non ha una precisione infinita :O
In teoria dovrebbero essere precisi, ho fatto la verifica. Non ti dovrebbe nemmeno sbagliare con la precisione, sempre che tu usi interi a 64 bit.
L'algoritmo presentato lì comunque è O(N*log(N))...
Hai usato due accumulatori ? Non riesco a capire come tu faccia ad ottenere il risultato. Anzi, sarebbe interessante vederlo. A me serve un vettore di dimensione pari all'input per contenere i prodotti parziali.
Si mi sono spiegato male... uso due vettori accumulatore.
Comunque se avessi copiato il tuo codice sarebbe venuto più diverso, tra un pò sono uguali anche gli spazi :asd:
int i;
int len = 52;
int input[] = {
2, 1, 3, 1, 2, 2, 3, 3, 4, 3,
3, 1, 1, 4, 4, 4, 2, 2, 4, 4,
4, 2, 2, 4, 2, 3, 1, 1, 3, 3,
2, 1, 3, 4, 3, 4, 2, 1, 4, 1,
3, 1, 4, 4, 1, 2, 1, 2, 4, 1,
2, 4};
unsigned long long* temp = new unsigned long long[len];
unsigned long long* res = new unsigned long long[len];
temp[0] = 1;
for( i = 1; i < len; ++i )
temp[i] = temp[i-1] * input[i-1];
res[len-1] = 1;
for( i = len-1; i > 0; --i )
{
res[i-1] = res[i] * input[i];
res[i] *= temp[i];
}
for( i = 0; i< len; ++i )
std::cout << res[i] << "\n";
Oddio, poi alla fine non sono proprio identici... Prova a stampare direttamente il risultato senza metterlo in res ;)
const int v[] = {
2, 1, 3, 1, 2, 2, 3, 3, 4, 3,
3, 1, 1, 4, 4, 4, 2, 2, 4, 4,
4, 2, 2, 4, 2, 3, 1, 1, 3, 3,
2, 1, 3, 4, 3, 4, 2, 1, 4, 1,
3, 1, 4, 4, 1, 2, 1, 2, 4, 1,
2, 4
};
const int size = sizeof(v) >> (ffs(sizeof(int)) - 1);
const int last = size - 1;
long long prod[size];
prod[0] = v[0];
prod[last] = v[last];
for(int i = 1; i < last; ++i)
{
prod[i] = prod[i-1] * v[i];
}
cout << "res[" << last << "] = " << prod[last - 1] << endl;
for(int i = last - 1; i > 0; --i)
{
prod[i] = v[i] * prod[i + 1];
cout << "res[" << i << "] = " << prod[i - 1] * prod[i + 1] << endl;
}
cout << "res[0] = " << prod[1] << endl;
Certo stampa al contrario...
In teoria dovrebbero essere precisi, ho fatto la verifica. Non ti dovrebbe nemmeno sbagliare con la precisione, sempre che tu usi interi a 64 bit.
Io sono passato per una strada diversa. Ho sfruttato il fatto che log(a/b) = log(a) - log(b) per effettuare la divisione. Solo che ovviamente perdo qualcosa a giocare con i float.
include Math
vector = [1, 5, 6, 3, 4]
# calcola il totale
total = vector[0]
for i in 1...vector.size
total *= vector[i] if vector[i] != 1
end
# divide
temp = log(total)
for i in 0...vector.size
vector[i] = vector[i] != 1 ? exp(temp-log(vector[i])) : total
end
# stampa i numeri a video
vector.each do |result|
puts result.to_i
end
Oddio, poi alla fine non sono proprio identici... Prova a stampare direttamente il risultato senza metterlo in res ;)
Certo stampa al contrario...
Beh per quello basta invertire i due for, fare prima quello che va dalla fine all'inizio, e poi l'altro.
Comunque ho pensato che non fosse un problema, perchè l'algoritmo che ci si chiede non comprende i prints... quindi è meglio tenere i print fuori dai cicli che realizzano l'obiettivo della funzione.
Se volessi metterlo in una funzione doWhatever() sarei piuttosto seccato se questa stampasse qualcosa :D
non capisco molto la limitazione di non poter fare le divisioni: basta moltiplicare per il divisore elevato alla -1, e per elevare alla -1 ad esempio in C/C++ si puó usare pow che sta in math.h (o cmath).
package prova;
public class Main {
public static void main(String[] args) {
long[] input = new long[] { 2, 1, 3, 1, 2, 2, 3, 3, 4, 3, 3, 1, 1, 4, 4, 4,
2, 2, 4, 4, 4, 2, 2, 4, 2, 3, 1, 1, 3, 3, 2, 1,
3, 4, 3, 4, 2, 1, 4, 1, 3, 1, 4, 4, 1, 2, 1, 2,
4, 1, 2, 4 };
long[] output = new long[input.length];
long totalProduct = 1;
for(int i = 0; i < input.length; i++) {
totalProduct *= input[i];
output[i] = 1;
}
for(int i = 0; i < output.length; i++)
output[i] =(long) (totalProduct * Math.pow(input[i], -1));
for(Long element : output)
System.out.println(element);
}
}
Così fero?
Edit: vabbè. Rinuncio all'indentazione degli elementi dell'input :(
arr = [2,1,3,1,2,2,3,3,4,3,3,1,1,4,4,4,2,2,4,4,4,2,2,4,2,3,1,1,3,3,2,1,3,4,3,4,2,1,4,1,3,1,4,4,1,2,1,2,4,1,2,4]
dest = []
for x in range (0, len(arr)):
dest.append(1)
for x in range(len(arr)-1, 0, -1):
dest[x-1] = dest[x]*arr[x]
mult = arr[0]
for x in range(1, len(arr)):
dest[x] *= mult
mult *= arr[x]
print dest
Dopo pranzo spiego meglio che voglio fare un disegnino :D.
Anche se penso che molti hanno fatto così.
wingman87
27-06-2010, 14:02
Io l'avevo pensato praticamente come quello di cionci (uso il codice di ndakota come base)
public class Main {
public static void main(String[] args) {
long[] input = new long[] { 2, 1, 3, 1, 2, 2, 3, 3, 4, 3, 3, 1, 1, 4, 4, 4,
2, 2, 4, 4, 4, 2, 2, 4, 2, 3, 1, 1, 3, 3, 2, 1,
3, 4, 3, 4, 2, 1, 4, 1, 3, 1, 4, 4, 1, 2, 1, 2,
4, 1, 2, 4 };
long[] output = new long[input.length];
output[0]=1;
for(int i = 1; i < input.length; i++) {
output[i]= input[i-1]*output[i-1];
}
long product=1;
for(int i = input.length-1; i >= 0; i--){
output[i] =product*output[i];
product*=input[i];
}
for(Long element : output)
System.out.println(element);
}
}
Due righe in factor... l'algoritmo è quello di repne. Confermo i risultati di cionci.
: products ( seq -- seq ) 1 [ * ] accumulate nip ;
: solve ( seq -- seq ) [ products ] keep reverse products reverse v* ;
ps. language flame war in 3..2..1.. :D
^TiGeRShArK^
27-06-2010, 14:24
decimal [] input = {2, 1, 3, 1, 2, 2, 3, 3, 4, 3, 3, 1, 1, 4, 4, 4, 2, 2, 4, 4, 4, 2, 2, 4, 2, 3, 1, 1, 3, 3, 2, 1, 3, 4, 3, 4, 2, 1, 4, 1, 3, 1, 4, 4, 1, 2, 1, 2, 4, 1, 2, 4};
var product = input.Aggregate((tempProduct, n) => decimal.Multiply(tempProduct, n)).ToArray();
var result = input.Select(n => decimal.Divide(product, n));
Se proprio vogliamo fare i pignoli non ho usato l'operazione di divisione dato che ho utilizzato la funzione decimal.Divide perchè mi rompevo a mettermi a shiftare i bit del decimal per dividere. :p
Io l'avevo pensato praticamente come quello di cionci (uso il codice di ndakota come base)
Si in pratica è simile al mio, io approccio prima da destra verso sinistra :D.
Comunque è abbastanza semplice:
http://img139.imageshack.us/img139/1566/mult.png
L'immagine mostra gli elementi da moltiplicare escludendo l'elemento in posizione X (non racchiuso da rettangoli).
Si vede che appunto accumulando le moltiplicazioni in una direzione e poi nell'altra si può arrivare alla soluzione.
non capisco molto la limitazione di non poter fare le divisioni: basta moltiplicare per il divisore elevato alla -1, e per elevare alla -1 ad esempio in C/C++ si puó usare pow che sta in math.h (o cmath).
Non credo che si potesse usare la FPU...se non abbiamo avuto tempo di realizzare la divisione...figuriamoci la FPU :D
rеpne scasb
27-06-2010, 15:29
■
Due righe in factor... l'algoritmo è quello di repne. Confermo i risultati di cionci.
: products ( seq -- seq ) 1 [ * ] accumulate nip ;
: solve ( seq -- seq ) [ products ] keep reverse products reverse v* ;
ps. language flame war in 3..2..1.. :D
solve ns = [ l*r | (l,r) <- zip (scanr1 (*) (tail ns ++ [1])) (1 : scanl1 (*) ns) ]
solve ns = [ l*r | (l,r) <- zip (scanr1 (*) (tail ns ++ [1])) (1 : scanl1 (*) ns) ]
Eh lo so... devo passare anch'io al lato oscuro... :asd:
Eh lo so... devo passare anch'io al lato oscuro... :asd:
La tua pero' e' forse piu' chiara (una volta che uno si ricorda che e' un linguaggio basato su stackperlomeno :p)
Direi che si potrebbe proporre un altro contest :cool:
astorcas
28-06-2010, 11:57
solve ns = [ l*r | (l,r) <- zip (scanr1 (*) (tail ns ++ [1])) (1 : scanl1 (*) ns) ]
ma sono lo stesso linguaggio? :asd:
Per me queste righe potrebbero fare qualsiasi cosa :D
ma sono lo stesso linguaggio? :asd:
Per me queste righe potrebbero fare qualsiasi cosa :D
Questo è in haskell, il mio era in factor.
Cmq è semplice da capire... fa sostanzialmente quello che fanno le altre versioni che sono state postate in C, C++, ecc... accumula da destra (scanr), accumula da sinistra (scanl) ne fa delle tuple (zip) e ne moltiplica gli elementi all'interno di una list comprehension (ci sono anche in python, forse più facili da leggere come sintassi) per produrre la lista che risolve il problema.
astorcas
28-06-2010, 12:34
Questo è in haskell, il mio era in factor.
Cmq è semplice da capire... fa sostanzialmente quello che fanno le altre versioni che sono state postate in C, C++, ecc... accumula da destra (scanr), accumula da sinistra (scanl) ne fa delle tuple (zip) e ne moltiplica gli elementi all'interno di una list comprehension (ci sono anche in python, forse più facili da leggere come sintassi) per produrre la lista che risolve il problema.
ok ora riesco a leggerlo grazie :D
EDIT: in ogni caso questo contest era facilino, gugo facci male con uno nuovo su! :D
ratman511
28-06-2010, 13:00
scusate perchè si deve andare prima a destra e poi a sinistra?ho guardato tutti i codice e anche se da leggere non sono difficili non riesco proprio a capirli nè tantomeno a scrivere una soluzione.voi dite che è facilissimo questo contest ma me sembra il contrario, sono troppo scarso forse :D ho iniziato facendo un disegno su carta però non so come procedere consigli?almeno ne approfitto per imparare un pò qualcosa
scusate perchè si deve andare prima a destra e poi a sinistra?ho guardato tutti i codice e anche se da leggere non sono difficili non riesco proprio a capirli nè tantomeno a scrivere una soluzione.voi dite che è facilissimo questo contest ma me sembra il contrario, sono troppo scarso forse :D ho iniziato facendo un disegno su carta però non so come procedere consigli?almeno ne approfitto per imparare un pò qualcosa
Prova prima con l'approccio più banale possibile ma che funzioni, ad esempio ti potrebbe venire in mente che per ogni elemento del vettore moltiplichi tra loro i restanti.
Tuttavia sarebbe O(N^2).
Se elenchi tutte le moltiplicazioni che dovresti fare per raggiungere lo scopo, ti accorgi che ci sono alcune moltiplicazioni che si ripetono spesso e che coinvolgono gli stessi elementi.
A quel punto devi pensare ad un modo per non ripetere le moltiplicazioni.
http://img139.imageshack.us/img139/1566/mult.png
IL FLUSSO CANALIZZATORE (cit.) :D.
L'immagine mostra gli elementi da moltiplicare escludendo l'elemento in posizione X (non racchiuso da rettangoli).
Lascio a te la conclusione facendoti notare che ad ogni passo dell'algoritmo hai due insiemi: gli elementi già moltiplicati e gli elementi ancora da moltiplicare (per raggiungere lo scopo).
ratman511
28-06-2010, 13:39
ma anche voi avete prima fatto qualcosa su carta?comunque la mia conclusione è che ad esempio l'1 e il 5 vengono moltiplicati 3 volte e capisco tutto il tuo discorso, il problema è che non capisco nè il codice come funzionamento nè come scrivere una mia soluzione.e gli elementi già moltiplicati sono quelli che non hanno un rettangolo?comunque io mi faccio una specie di schema su carta ma poi non riesco a tradurre in codice. forse ho poca esperienza, non so
Se ti può consolare è il primo contest a cui riesco a partecipare e comunque le mie soluzioni sono sempre le più scontate possibili :D
ratman511
28-06-2010, 14:12
almeno tu una soluzione l'hai trovata e hai anche modificato un pò il codice quando fero ha detto quella cosa della potenza.io invece non riesco nemmeno a capire il funzionamento dei vostri codice anche se da leggere sono facili
almeno tu una soluzione l'hai trovata e hai anche modificato un pò il codice quando fero ha detto quella cosa della potenza.io invece non riesco nemmeno a capire il funzionamento dei vostri codice anche se da leggere sono facili
Prendi uno dei programmi che sono stati postati, quello che riesci a seguire meglio, e fai i passi uno ad uno su un pezzo di carta.
Provo a rigirarti la soluzione sperando di non dire stronzate.
Accumulando hai il prodotto di tutti gli elementi fino alla i-esima posizione partendo da una certa direzione. Fallo partendo da destra e partendo da sinistra. Adesso, qual'è il prodotto degli elementi alla i-esima posizione? Basta prendere l'i-esimo valore in entrambi gli accumulatori, moltiplicarli... e voilà. Hai moltiplicato il prodotto di tutti gli elementi alla sinistra di 'i' con il prodotto di tutti gli elementi a destra di 'i'.
Spero di non aver peggiorato la situazione. :asd:
ratman511
28-06-2010, 15:02
l'ho fatto, ma vado avanti per poco e poi vorrei capire come siete arrivati a questa soluzione.quello che mi interessa è imparare a risolvere gli esercizi principalmente,ho visto anche soluzioni in una riga:eek:
l'ho fatto, ma vado avanti per poco e poi vorrei capire come siete arrivati a questa soluzione.quello che mi interessa è imparare a risolvere gli esercizi principalmente,ho visto anche soluzioni in una riga:eek:
Le soluzioni in una riga fanno uso di linguaggi che lo permettono ;)
Le soluzioni in una riga fanno uso di linguaggi che lo permettono ;)
Si' e tra l'altro si tratta di una cosa poco leggibile che va bene giusto per fare lo spavaldo :D. Fosse codice di produzione avrebbe una forma un tantino diversa :p
astorcas
28-06-2010, 15:39
Le soluzioni in una riga fanno uso di linguaggi che lo permettono ;)
E poi a parte il fatto che fanno figo non hanno una reale utilità ;)'
(P.S. Intendo il fatto che siano scritti su una sola riga)
ratman511
28-06-2010, 15:57
anche se il linguaggio lo permette la soluzione l'hanno saputa scrivere io non riesco nemmeno a risolverlo :) avete fatto tutti qualche schizzo su carta prima?forse sbaglio approccio
E poi a parte il fatto che fanno figo non hanno una reale utilità ;)'
(P.S. Intendo il fatto che siano scritti su una sola riga)
Scrivere meno codice mi sembra abbastanza 'utile', no? :asd:
astorcas
28-06-2010, 16:32
Scrivere meno codice mi sembra abbastanza 'utile', no? :asd:
si sicuramente però a volte poche righe è sinonimo di "criptico". In alcuni casi è meglio una riga in più che fa chiarezza anziché una in meno che crea confusione.
Poi è chiaro che io con i linguaggi funzionali puri c'ho poco a che fare quindi parto svantaggiato ;)
anche se il linguaggio lo permette la soluzione l'hanno saputa scrivere io non riesco nemmeno a risolverlo :) avete fatto tutti qualche schizzo su carta prima?forse sbaglio approccio
Ovvio. Carta e penna sono i migliori amici del programmatore. :D
ratman511
28-06-2010, 17:18
io vorrei capire come risolverlo.allora ho questa sequenza per facilità tengo in considerazione quella breve del primo topic.avete detto di accumulare da destra e da sinistra,ma in che senso accumulare?e che utilità ha?la moltiplicazione è commutativa infine volevo capire una cosa,cioè perchè tutte le soluzioni mettono come primo elemento dell'array di appoggio o risultante 1. ad esempio repne mette y[0]=1,un altro codice temp[0]=1 e cosi via.nel codice di repne poi mette l'ultimo elemento di z=1 e parte il ciclo da n-2.perchè?
lupoxxx87
28-06-2010, 18:00
provo a spiegartelo io con un piccolo esempio, magari così lo vedi meglio.
immaginiamo il vettore
input := {a, b, c, d}
noi ci creiamo due vettori in modo che nell'i-esimo posto ci sia la moltiplicazione di tutti i numeri precedenti in un vettore, e di tutti i successivi nell'altro vettore, rispetto all'i-esimo elemento di input.
prec := {1, a, a*b, a*b*c}
succ := {b*c*d, c*d, d, 1}
a questo punto basta costruire il vettore risultato, in cui ogni elemento è la moltiplicazione tra prec[i] e succ[i]. ok ?
per generare e popolare i due vettori ci sono diversi modi, ma il più efficiente è dichiarare prec[0] = 1 e succ[n] = 1, e moltiplicare ogni elemento i-esimo di input con l'elemento (i-1)-esimo di prec (a specchio per succ.)
e così ti ritrovi la tua soluzione con complessità O(n) senza utilizzare divisioni o moduli, ma soltanto moltiplicazioni e somme
ratman511
28-06-2010, 19:22
ora è più chiaro,vorrei però sapere perchè
moltiplicare ogni elemento i-esimo di input con l'elemento (i-1)-esimo di prec (a specchio per succ.)
e cosa posso fare per imparare a ragionare sugli esercizi in questo modo
lupoxxx87
28-06-2010, 20:32
una volta che sai la teoria......esercizi, esercizi, esercizi...
ratman511
28-06-2010, 21:10
mi spieghi perchè
moltiplicare ogni elemento i-esimo di input con l'elemento (i-1)-esimo di prec (a specchio per succ.)
intendi per ogni array?cioè per gli array di precedenti fare questa procedura e per l'array successivo quella simmetrica?e quindi dovrei partire dalla posizione 1 dell'array di precedenti e lunghezza-2 da quello dei successivi?
Eccomi di ritorno.
Non credo che si potesse usare la FPU...se non abbiamo avuto tempo di realizzare la divisione...figuriamoci la FPU :D
Si', esatto. Mi ero dimenticato di scriverlo.
Anche perche' il circuito logico della divisione per la FPU sarebbe diverso da quello della ALU, e quindi non si capirebbe perche' non la si sarebbe potuta usare.
Vabbe', bacchettata sulle mani a gugoXX per aver proposto un quesito tanto elementare.... :D :D
Dai, era un esercizietto per le vacanze.
Ma non proprio per forza banale.
O(N) solo con numeri interi occorre pensarci un pochino.
Comunque ce l'abbiamo fatta. Ora studio qualcos'altro.
vBulletin® v3.6.4, Copyright ©2000-2026, Jelsoft Enterprises Ltd.