Trova prodotto usando la somma C # Problema? [chiuso]

-2

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.

    
posta user1910524 29.11.2013 - 14:09
fonte

1 risposta

0

non sei andato giù per la strada giusta come hai chiamato Multiply (X, halfY) una sola volta; devi raddoppiare il risultato della chiamata ricorsiva: ( x*y = 2*(x*y/2) )

var prod = Multiply(X, halfY);
if (Y % 2 == 0) // if Y is even #
    return prod + prod ;
else //if Y is odd #
    return prod + prod  + X;

anche il sum globale non è necessario, basta restituire X in quel punto:

if (Y == 1)
    return X;
    
risposta data 29.11.2013 - 14:19
fonte

Leggi altre domande sui tag