[Ajuda] subtrações sucessivas

Programação Java
#1

Pessoal,

Vejam se conseguem me ajudar, estou estudando linguagem e estrutura de dados e preciso criar uma funcão recursiva que realize a divisão entre dois numeros inteiros, sem utilizar o ‘/’ ou ‘Mod’. Para fazer esse tipo de coisa, preciso realizar essa divisao atraves de subtrações sucessivas.

implementei da seguinte forma:

decimal divisao(int dividendo, int divisor) {
if (dividendo< divisor)
return 0;
else {
return (divisao(dividendo - divisor, divisor) + 1);
}
}

Para uma divisao do tipo 12 / 4 funciona perfeitamente; Porem essa rotina é ineficiente quando considero os seguintes casos:

46 / 108
-2 / -5

Alguem poderia me ajudar nessa questão?

Sds,

Charles

#2

Esse nunca ouvi falar. Como funciona?

#3

Não entendi. O que não funciona?

O primeiro caso retorna 0, que é mesmo a resposta certa.

No segundo, você tem problema pq a comparação deveria ser invertida, caso o divisor seja < 0.
Ao invés de inverter a comparação, multiplique por -1 o divisor e o dividendo nesse caso.

A resposta novamente será 0.

float divisao(int dividendo, int divisor) { if (divisor < 0) return divisao(-dividendo, -divisor); if (dividendo < divisor) return 0; return divisao(dividendo - divisor, divisor)+1; }

#4

Quase esqueço.

Charles, quando você for postar código, pode usar a tag code? Aí seu código fica colorido e formatado como o meu. Muita gente nem lê o código se você não usar esse recurso.

Se ainda não sabe como, dá uma lida nesse tópico:
http://www.guj.com.br/posts/list/50115.java

Ele explica esse e outros recursos do fórum. :wink:

#5

Bruno

A ideia é fazer uma divisão sem utilizar o operador ‘/’, estão é feito com varias subtrações ate chegar ao quociente da divisão…

#6

ViniGodoy

Esses casos que coloquei a rotina não poderia retornar ‘zero’, por exemplo:

No primeiro caso 46 / 108 = 0,42 { A rotina deveria retornar 0,42 }

Aconcontece isso pq está caindo nessa condição:

  if (dividendo < divisor)
    return 0;

at,

Charles

[quote=ViniGodoy]Não entendi. O que não funciona?

O primeiro caso retorna 0, que é mesmo a resposta certa.

No segundo, você tem problema pq a comparação deveria ser invertida, caso o divisor seja < 0.
Ao invés de inverter a comparação, multiplique por -1 o divisor e o dividendo nesse caso.

A resposta novamente será 0.

float divisao(int dividendo, int divisor) { if (divisor < 0) return divisao(-dividendo, -divisor); if (dividendo < divisor) return 0; return divisao(dividendo - divisor, divisor)+1; }[/quote]

#7

Você quer usar subtrações sucessivas e imprimir um número decimal? Digamos que você queira um resultado com 3 casas depois da vírgula. Então multiplique o primeiro número por 1000, chame sua rotina de subtrações sucessivas, e então divida o resultado por mil. (Para multiplicar um número por 1000, sem usar multiplicação - acho que é isso que o professor vai lhe cobrar), simplesmente crie uma rotina que multiplica um número por 10, sem usar multiplicação, e chame a rotina 3 vezes sucessivamente.
Para dividir o resultado por mil, você pode pegar o resultado da tal divisão - que vai dar o número 420, e então pôr a quantidade de zeros e pontos à esquerda, conforme necessário.

#8

E mais, o resultado da divisão de 46 por 108 não é 0,42 como você informou. Está errado mesmo.

#9

Eu reduzi o resultado só para exemplificar, o resultado da divisão de 46 / 108 é 0.4259259259259259259259259259.

Sds,

Charles

#10

Você tem certeza que tem que dar o resultado com casas decimais?
Geralmente esse método é usado para divisões inteiras.

Senão o algoritmo vai realmente ficar bem mais complicado. Até porque, você terá que cobrir casos como 5 / 3…

Se o número de casas for fixa, faça o que o colega falou. Multiplique por 10 elevado ao número de casas que você quer, e divida ao final.

#11

ViniGodoy

Sim, esse é o problema… é obrigatorio o resultado com casas decimais, por isso que tentei implementar essa rotina com o retorno sendo decimal.!

tá complicado essa parada… :shock:

#12

Olá, pensei um pouco e acho que consegui uma função que faz o que você quer:

/**
 * @param num Número a ser dividido.
 * @param div Divisor do Número.
 * @param casdec Número de casas decimais a ser exibidas
 */
public static double division( double num, double div, int casdec )
{
  return Double.parseDouble( division( num, div, casdec, 0 ) );
}
private static String division( double num, double div, int casdec, int recc )
{
  boolean inverted;
  if ( ( num < 0 ) == ( div < 0 ) )
    inverted = false;
  else
    inverted = true;
  if ( casdec < 0 )
    casdec = 0;
  // Opcional. Suporta divisão por zero e NaNs
  if ( div == 0 )
    return "+Infinity";
  else if ( div == -0 )
    return "-Infinity";
  else if ( !( div > 0 ) && !( div < 0 ) && !( div == 0 ) )
    return "NaN";
  else if ( !( num > 0 ) && !( num < 0 ) && !( num == 0 ) )
    return "NaN";
  // Fim do Opcional
  int c = 0;
  while ( num >= div )
  {
    num -= div;
    c++;
  }
  String string = ( inverted ? "-" : "" );
  if ( casdec - recc <= 0 )
    string += String.format( "%d", c );
  else if ( recc == 0 )
    string += String.format( "%d.%s", c, division( num * 10, div, casdec, recc + 1 ));
  else
    string += String.format( "%d%s", c, division( num * 10, div, casdec, recc + 1 ));
  return string;
}

A Performance fica horrível, mais fazer o quê. Acho que isso deve resolver, ainda não testei. Se der qualquer coisa errada avisa =D. Não tente usar números grandes.
Você pode usar o casdec como o número máximo de casas decimais em um double. =D
Tire a parte opcional se não tiver que suportar divisoes por 0 e NaN’s.

#13