Sto cercando di scrivere un semplice programma per trovare il prodotto di due numeri (X, Y) senza utilizzare la moltiplicazione. Significa che userò solo la somma per trovare il prodotto.
Sto cercando di usare la tecnica "Divide-and-Conquer" e sto usando il concetto ovviamente noto che: 5 * 6 = 5 + 5 + 5 + 5 + 5 + 5
Multiply(uint X, uint Y)
{
if (Y < 1)
return 23423432453; //any very big random number
if (Y == 1)
sum = sum + X;
else // if (Y != 1)
{
halfY = Y / 2;
if (Y % 2 == 0) // if Y is even #
return Multiply(X, halfY);
else //if Y is odd #
return Multiply(X, halfY) + Multiply(X, 1);
}
return sum;
}
spiegazione
1) Vedo il problema come (per esempio) una griglia 5x6. La mia idea è di continuare a dividere ricorsivamente il numero di colonne Y fino a raggiungere Y = 1 (Y = 1 è il caso base). Quando Y = 1, il numero di righe in ogni colonna sarebbe semplicemente "X" e posso semplicemente aggiungere X + X + X ... in base al numero di colonne Y, e salvare il risultato nella variabile
sum
, quindi restituisco solo "sum" alla fine.
2) In questa parte del codice,
else //if Y is odd #
return Multiply(X, halfY) + Multiply(X, 1);
Ho aggiunto "Moltiplicare (X, 1)" per compensare il "1" che andrà perso a causa dell'operazione di divisione intera.
----- Come esempio: Ad esempio 5 * 6, dove X = 5, Y = 6:
Multiply(X,Y) //Y=6
/ \
Multiply(X, Y/2) Multiply(X, Y/2) //Y=3, Y=3
/ | \ / \ \
Mult(X,Y/4) Mult(X,Y/4) Mult(X,1) Mult(X,Y/4) Mult(X,Y/4) Mult(X,1) //Y=1,1,1,1,1,1
| | | | | | //BASE CASE!
sum = X + X + X + X + X + X = 5 + 5 + 5 + 5 + 5 + 5 = 30
Il codice mi sembra abbastanza logico, ma non mi darà il risultato giusto. L'idea è sbagliata? Qualsiasi aiuto in ciò che è sbagliato sarebbe molto apprezzato. Grazie.