C++ Função de multiplicação usando divisão e fatoração das colunas

Bianca Regan · 25 de setembro de 2019

Oi pessoal! Sou nova no fórum. a professora de Algoritmos e Estrutura de Dados me passou uma lista de exercícios com funções e este foi o único que não consegui resolver, me ajudem por favor!

OBS:. NÃO precisam me dar solução pronta, só me ajudem a entender como chegar nela, pois tentei de tudo e nem um parãmetro consegui elaborar

Citação

Escreva uma função em C/C++ que receba dois números inteiros, positivos, e determine o produto dos mesmos, utilizando o seguinte método de multiplicação: Dividir, sucessivamente, o primeiro número por 2, até que se obtenha 1 como quociente; Paralelamente, dobrar, sucessivamente, o segundo número; Somar os números da segunda coluna que tenham um número ímpar na primeira coluna. O total obtido é o produto procurado.

Exemplo: 9 x 6
9 6 => 6
4 12
2 24
1 48 => + 48
54

Ansi C · 26 de setembro de 2019

Olá@Bianca Regan , que parte você não entendeu?

Aplique uma estrutura de repetição, o seu controle é o multiplicando dos fatores.
A cada laço o multiplicando é atualizado por um novo valor que é o quociente dele mesmo pelo número 2.
Enquanto isso, o multiplicador é atualizado passando a ser também a cada laço o produto dele mesmo por 2.
Atente a parte dos ímpares. Sempre que o resultar do quociente (no multiplicando) é ímpar se acumula o valor na somatório de multiplicadores para ser adicionado no produto.
Quando o multiplicando for igual a 1 a copia do multiplicador agora é quase produto, se o multiplicando for par é o produto, mas se é impar resta adicionar +1 vez o multiplicador ao produto.

Atenção se o multiplicando é par.

Bianca Regan · 26 de setembro de 2019

@MB_ sim, a minha dúvida foi essa mesmo, qual estrutura eu aplicaria para fazer a divisão e multiplicação sucessivas, se somente o laço de de repetição ou se eu precisaria entrar numa matriz. Obrigada

Ansi C · 26 de setembro de 2019

Atente a parte dos ímpares que acabei esquecendo. Sempre que o resultar do quociente no multiplicando é ímpar se acumula o valor na somatório de multiplicadores para ser adicionado no produto.

arfneto · 27 de setembro de 2019

Olá!

Acho que apenas repetir o que fez no enunciado estaria bem.

Se quiser conferir pode usar algo bem igual.Você vai calcular um produto e um int tem em geral 32 bits então são poucas linhas a calcular mesmo. Pode declarar

    int        linha[32][2];

e estará bem. Como é só um exercício acho que não precisa entrar no mérito de poder estourar o valores do produto e não caber num int. Se for essencial avise.

Claro que tem muitas maneiras de escrever qualquer coisa mas essa sugestão é só uma reprodução linear do enunciado

int produto(const int x, const int y)
{
    int        linha[32][2];
    int        quociente = x;
    int        b = y;
    int        passo = 1;
    int        valor = 0;
...

Essas variáveis já fariam o serviço e facilitariam na hora de ler o texto por ter os nomes de acordo com o método.

Veja uma possível saída de um teste de quem está desconfiado e quer conferir:

Calculando produto de (9,6)
saida depois de 4 passos. Eis a tabela:
00             9 <==             6 *
01             4                12
02             2                24
03             1 <==            48 *
produto(9,6) retornou 54  (ok)

Claro que o ok à direita do produto é porque o programa multiplicou do modo convencional e conferiu

Enquanto a gente não confia, pode ser assim:

    printf("\nCalculando produto de (%d,%d)\n", x, y);
    linha[0][0] = x;
    linha[0][1] = y;
    if ((x%2) == 1) valor = valor + y;
    do
    {
        quociente = quociente / 2;
        b = b * 2;
        linha[passo][0] = quociente;
        linha[passo][1] = b;
        if ( (quociente%2) == 1) valor = valor + b;
        passo = passo + 1;
    } while (quociente > 1);

    printf("saida depois de %d passos. Eis a tabela:\n", passo);
    for (int i = 0; i < passo; ++i)
    {
        if (linha[i][0] % 2 == 1)
        {
            printf("%02d    %10d <==    %10d *\n", i, linha[i][0], linha[i][1]);
        }
        else
        {
            printf("%02d    %10d        %10d\n", i, linha[i][0], linha[i][1]);
        }
    }    // end for
    return valor;

E podemos testar com aquele "ok" ou "ERRO"

int testa_produto(int a, int b)
{
    int p = produto(a, b);
    int r = a * b;
    if (p == r)
    {
        printf("produto(%d,%d) retornou %d  (ok)\n", a, b, p);
    }
    else
    {
        printf("produto(%d,%d) retornou %d  (ERRO)\n", a, b, p);
    }
    return (p == a * b);
}    // end testa_produto()

E esse código

int main()
{
    testa_produto(9, 6);
    testa_produto(6, 9);
    testa_produto(10, 1000);
    testa_produto(90987, 656);
    return 0;
}

mostraria

Calculando produto de (9,6)
saida depois de 4 passos. Eis a tabela:
00             9 <==             6 *
01             4                12
02             2                24
03             1 <==            48 *
produto(9,6) retornou 54  (ok)

Calculando produto de (6,9)
saida depois de 3 passos. Eis a tabela:
00             6                 9
01             3 <==            18 *
02             1 <==            36 *
produto(6,9) retornou 54  (ok)

Calculando produto de (10,1000)
saida depois de 4 passos. Eis a tabela:
00            10              1000
01             5 <==          2000 *
02             2              4000
03             1 <==          8000 *
produto(10,1000) retornou 10000  (ok)

Calculando produto de (90987,656)
saida depois de 17 passos. Eis a tabela:
00         90987 <==           656 *
01         45493 <==          1312 *
02         22746              2624
03         11373 <==          5248 *
04          5686             10496
05          2843 <==         20992 *
06          1421 <==         41984 *
07           710             83968
08           355 <==        167936 *
09           177 <==        335872 *
10            88            671744
11            44           1343488
12            22           2686976
13            11 <==       5373952 *
14             5 <==      10747904 *
15             2          21495808
16             1 <==      42991616 *
produto(90987,656) retornou 59687472  (ok)

Uma versão mais compacta não precisaria dessas mensagens todas, como essa abaixo

int prod(const int x, const int y)
{
    int        linha[32][2];
    int        quociente = x;
    int        b = y;
    int        passo = 1;
    int        valor = 0;

    linha[0][0] = x;
    linha[0][1] = y;
    if ((x % 2) == 1) valor = valor + y;
    do
    {
        quociente = quociente / 2;
        b = b * 2;
        linha[passo][0] = quociente;
        linha[passo][1] = b;
        if ((quociente % 2) == 1) valor = valor + b;
        passo = passo + 1;
    } while (quociente > 1);
    return valor;
}    // end produto()

que mostraria

produto(9,6) retornou 54  (ok)
produto(6,9) retornou 54  (ok)
produto(10,1000) retornou 10000  (ok)
produto(90987,656) retornou 59687472  (ok)

para os mesmos números

Boa sorte. Essa é só uma maneira de fazer. Nada criativa. Só imitando o enunciado

Ansi C · 27 de setembro de 2019

@arfneto Legal.

A dúvida da autora no segundo momento foi essa mesmo.

20 horas atrás, Bianca Regan disse:

laço de de repetição ou se eu precisaria entrar numa matriz

Ai já foi uma outra pergunta ...

Pelo entendo do enunciado segundo @arfneto está implícito o uso de matrizes sim.

6 horas atrás, arfneto disse:

Acho que apenas repetir o que fez no enunciado estaria bem.

Só que eu não vejo isso como sendo importante é uso de memória sem sentido algo a se pensar, mas isso eu porque sou rebelde pra cara***o.

Existe enorme preocupação na melhoria de hardware porque os recursos são escassos, quando na verdade o problema está no software ruins e abusivos que por falta de planejamento roubam memória sem sentido, forçando upgrades de hardware que só atende o capitalismo do setor de peças que gera bastante descontentamento (exemplo o android).

@Bianca Regan

Enfim, acho que com tempo e capacidade de fazer as duas coisas: com e sem matriz, o faça.

Opinião: Acho incoerente o uso dos operadores de multiplicação e divisão porque descaracteriza a técnica que é justamente de produto um caso a se imaginar que não tem outra alternativa, remove-lhe esse sentido principalmente com o uso do operador para multiplicar por 2.

arfneto · 27 de setembro de 2019

@MB_ Entendo sua preocupação com a escassez de recursos mas entenda que esse é um programa de exemplo para um curso de algoritmos e estruturas de dados e a ideia era usar a linguagem de programação para replicar o algoritmo descrito, possivelmente usando ... estruturas de dados.

Nesse caso, a matriz é totalmente supérflua e existe apenas para o aluno poder testar ou mostrar as etapas na saída mantendo a analogia do que foi feito no enunciado. Apagando todas as referências a tabela o programa continua funcionando porque nenhuma operação era feita com a matriz. Esse abaixo dá na mesma:

int prod(const int x, const int y)
{
    int        quociente = x;
    int        b = y;
    int        passo = 1;
    int        valor = 0;

    if ((x % 2) == 1) valor = valor + y;
    do
    {
        quociente = quociente / 2;
        b = b * 2;
        if ((quociente % 2) == 1) valor = valor + b;
        passo = passo + 1;
    } while (quociente > 1);
    return valor;
}    // end produto()

Em relação aos recursos desperdiçados, considere que uma matriz de 256 BYTES cobre todo o espectro int

Sobre a multiplicação por constantes, entenda que os compiladores otimizam esses códigos há décadas e muitas vezes a operação é até substituída por tabelas ou códigos de interpolação. Por exemplo, coisas como trocar (a * 2) por (a + a) ou( a<<1) são até românticas mas talvez não sejam mais vantagem alguma. E dependendo da linguagem pode ter até efeitos colaterais indesejáveis ao se usar um outro operador para supostamente otimizar uma operação, porque pode estar descartando alguma otimização que o próprio autor da classe tenha feito na operação --- no caso de C++ por exemplo.

Veja o código gerado em um compilador moderno para essas linhas, sem mudar nada das configurações padrão

Note que a divisão e a multiplicação por 2 foram trocadas por shift left e shift right: shl e sar

Mas entendo sua preocupação e acho bastante válida

Abraço

adicionado 27 minutos depois

Esqueci de postar o programa de teste...

Está em https://github.com/ARFNeto-CH/ch-190927-divisao onde tem um botão de download em formato zip

Ou apenas para ler o programa neste link

Ansi C · 27 de setembro de 2019

8 horas atrás, arfneto disse:

Entendo sua preocupação com a escassez de recursos mas entenda que esse é um programa de exemplo para um curso de algoritmos e estruturas de dados e a ideia era usar a linguagem de programação para replicar o algoritmo descrito, possivelmente usando ... estruturas de dados.

Mais motivo ainda para se ensinar boas e não más práticas desdo começo.