[Algoritmi] Tecnica Divide et Impera

[Skeggia1]

Ciao a tutti.
Vengo subito al dunque ho il seguente esercizio da risolvere con la tecnica divide et impera:

"Dato un vettore di interi A[0...n-1] progettare un algoritmo basato sulla tecniica divide et impera per calcolare la quantità
$S=A[0]*2^0+A[1]*2^1+A[2]*2^2+...+A[n-1]*2^(n-1)$."

Io l'ho fatto così:

int quantita(int a[],int l, int r)
{
  int x,y,n;
  if (l==r)
    return a[l]*2^l;
  else
  {
    n=(l+r)/2;
    x=quantita(a,l,n);
    y=quantita(a,n+1,r);
    return (x+y);
  }
}   

L'ho provato anche a computer e purtroppo non mi trovo con il valore della quantità. Secondo voi dove sbaglio?
Grazie.

[apatriarca]

a[l]*2^l non fa quello che immagini.. Calcola infatti l'or esclusivo (lo xor) bit a bit tra a[l]*2 ed l...

Secondo me comunque il metodo divide et impera doveva essere usato nel modo seguente:
\[ q = \sum_{i=0}^{n-1} a_i\,2^i = \sum_{i=0}^{n/2-1} a_i\,2^i + 2^{n/2}\,\sum_{i=0}^{n/2-1} a_{n/2+i}\,2^i. \]

[Skeggia1]

Caro apatriarca sto morendo dalla vergogna Mi sono completamentamente dimenticato degli operatori di bitwise. Come vorrei cancellare quella castroneria che ho scritto...comunque ovviamente devo scrivere in pseucodice l'algoritmo che si basa sul tuo suggerimento ma al momento non riesco a definire il caso base... non lo so, ma come posso fare per capire bene queste cose. Cioè capisco gli esempi sul libro e sulle slide del corso, ma gli esercizi sono sempre più difficili, che rabbia.

[vict85]

Tanto per riprendere un po' la mano con la programmazione mi sono messo a risolvertelo. L'implementazione è un po' naive. Si può fare di meglio. Prova ad estrapolare gli aspetti importanti. Il main controlla con un metodo iterativo se la funzione ha il risultato giusto.

Ho usato interi a dimensione ben determinata, tu puoi leggerli come int64_t = long long e uint16_t = unsigned short. Ho anche usato lo shift ( 1<

#include <iostream>
#include <cstdint>

int64_t quant(int64_t const * const a, uint16_t const l);

int64_t check(int64_t const a[], uint16_t const l);

int main() {

	int64_t a[60] = { 72, 3, 19, -23, 69, 100, 0, 1, -1, 1, -1, -235, 1, -23456, +8, 1};
	a[59] = 1;
	int64_t const b = check(a, 60);
	int64_t c = quant(a, 60);
	
	std::cout<<c<<" "<<b<<std::endl;
}

int64_t quant(int64_t const * const a, uint16_t const l)
{
	if(l > 1)
	{
		uint16_t m = l/2;
		return quant(a,m) + (1<<m)*quant(a+m,l-m);
	}
	else if (l == 1)
	{	
		return (*a);
	}
	else
	{
		return 0;
	}
}

int64_t check(int64_t const a[], uint16_t const l)
{
	int64_t r = 0, m = 1;
	for(uint16_t i = 0; i<l; ++i, m*=2)
	{
		r += a[i]*m;
	}
	return r;
}

Domande?