Duvida - iniciante

ronaldoboll
(usa Outra)

Enviado em 28/01/2016 - 16:40h

Bom dia, sou iniciante e estou estudando programação em um site que sugere problemas para serem resolvidos, o problema proposto foi o seguinte:
Leia um valor de ponto flutuante com duas casas decimais. Este valor representa um valor monetário. A seguir, calcule o menor número de notas e moedas possíveis no qual o valor pode ser decomposto. As notas consideradas são de 100, 50, 20, 10, 5, 2. As moedas possíveis são de 1, 0.50, 0.25, 0.10, 0.05 e 0.01. A seguir mostre a relação de notas necessárias.

Imprima a quantidade mínima de notas e moedas necessárias para trocar o valor inicial.

fiz esse código:

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

main(){


int a=0,b=0,c=0,d=0,e=0,f=0,g=0,h=0,i=0,j=0,k=0,l=0;
float n;

scanf("%f",&n);

while(n>=100){

a++;
n=n-100;

}
while(n>=50){

b++;
n=n-50;

}
while(n>=20){

c++;
n=n-20;

}
while(n>=10){

d++;
n=n-10;

}
while(n>=5){

e++;
n=n-5;

}
while(n>=2){

f++;
n=n-2;

}
while(n>=1){

g++;
n=n-1;

}

while(n>=0.5){
h++;
n=n-0.5;

}
while(n>=0.25){
i++;
n=n-0.25;

}

while(n>=0.10){
j++;
n=n-0.10;

}

while(n>=0.05){
k++;
n=n-0.05;

}

while(n>0.00){
l++;
n=n-0.01;

}


printf("NOTAS:\n");
printf("%d nota(s) de R$ 100.00\n",a);
printf("%d nota(s) de R$ 50.00\n",b);
printf("%d nota(s) de R$ 20.00\n",c);
printf("%d nota(s) de R$ 10.00\n",d);
printf("%d nota(s) de R$ 5.00\n",e);
printf("%d nota(s) de R$ 2.00\n",f);

printf("MOEDAS:\n");
printf("%d moeda(s) de R$ 1.00\n",g);
printf("%d moeda(s) de R$ 0.50\n",h);
printf("%d moeda(s) de R$ 0.25\n",i);
printf("%d moeda(s) de R$ 0.10\n",j);
printf("%d moeda(s) de R$ 0.05\n",k);
printf("%d moeda(s) de R$ 0.01\n",l);



return 0;
}

Mas o problema é que se eu entrar com o valor de 91.01 da erro na precisão do calculo e ele volta que eu tenho que dar 2 moedas de 0.001 centavo.

o certo seria sair assim :

NOTAS:
0 nota(s) de R$ 100.00
1 nota(s) de R$ 50.00
2 nota(s) de R$ 20.00
0 nota(s) de R$ 10.00
0 nota(s) de R$ 5.00
0 nota(s) de R$ 2.00
MOEDAS:
1 moeda(s) de R$ 1.00
0 moeda(s) de R$ 0.50
0 moeda(s) de R$ 0.25
0 moeda(s) de R$ 0.10
0 moeda(s) de R$ 0.05
1 moeda(s) de R$ 0.01

mas esta saindo assim

NOTAS:
0 nota(s) de R$ 100.00
1 nota(s) de R$ 50.00
2 nota(s) de R$ 20.00
0 nota(s) de R$ 10.00
0 nota(s) de R$ 5.00
0 nota(s) de R$ 2.00
MOEDAS:
1 moeda(s) de R$ 1.00
0 moeda(s) de R$ 0.50
0 moeda(s) de R$ 0.25
0 moeda(s) de R$ 0.10
0 moeda(s) de R$ 0.05
2 moeda(s) de R$ 0.01

continuando...
eu fui tentar descobrir porque tava dando esse erro e fiz o seguinte:

#include <stdio.h>
#include <stdlib.h>

int main()
{
float n=0;
scanf("%f", &n);

printf("%f", n);
return 0;
}

se eu entrar com o valor de 91.01
no printf sai o valor de 91.010002

eu presumo que o erro esta ai... esse 0002 que é acrescentado pela variavel ser float acaba mudando o valor no calculo e a precisão sai errada, como eu faço pra arrumar isso?

vlw pela atenção.
o site que eu pego os problemas é o www.urionlinejudge.com.br e esse problema em questão é o problema de numero 1021.

paulo1205
(usa Ubuntu)

Enviado em 31/01/2016 - 04:00h

Nos nossos PCs, números de ponto flutuante são armazenados internamente em modo binário. Além disso, esses números não são realmente números reais, mas sim um subconjunto dos números racionais em que o numerador pode ser entendido como um número com uma quantidade finita de bits (24 para float, 53 para double e 80 para long double) e o denominador é uma potência de dois (i.e. 2 elevado a n, sendo n um número inteiro).

Sendo o denominador necessariamente uma potência de dois, frações que tenham outros denominadores (como 0,01, que é o mesmo que 1/100) não vão ter uma representação exata com a quantidade finita de bits disponíveis, mas podem gerar dízimas periódicas em base binária (do mesmo modo como 1/3 ou 1/7 geram dízimas periódicas no sistema decimal). 0,01, por exemplo, tem uma dízima binária com período de 20 bits (10100011110101110000). Como float só tem 24 bits, seu numerador fica sendo 101000111101011100001010(2) (ou 10.737.418) e o denominador é 2^30 (que é 1.073.741.824, e não 1.073.741.800 que seria necessário para a fração ser exatamente igual a 0,01), resultando no valor exato 0,00999999977648258209228515625.

Raciocínio semelhante se aplica para os valores de 0,10 e 0.05, cuja dízima binária tem período de 4 bits (1100), com numerador 110011001100110011001101(2) (arredondando para cima, pois o próximo dígito seria 1, o que resulta em 13.421.773) e denominadores, respectivamente, 2^27 (134.217.728) e 2^28 (268.435.456), para os valores exatos 0,100000001490116119384765625 e 0,0500000007450580596923828125. As moedas de 1, 0,5 e 0,25 não geram dízimas binárias, pois suas frações são 1/1, 1/2 e 1/4 (os denominadores 1, 2 e 4 são todos potências de dois).

Quando você faz contas com esses valores inexatos, obviamente pode ter resultados inexatos -- e com erro acumulativo, ainda por cima. Por isso, você não deve esperar um saldo final igual a zero, como supõe seu último laço com while. Também não convém testar se ele é estritamente maior que 0,01, já que essa comparação também seria inexata.

Para valores suficientemente pequenos (mais sobre isso abaixo), existe um limite para o erro. Se você não tiver suas opções de moedas limitadas, nunca vai usar mais do que duas moedas de 0,10, nem mais do que uma moeda de 0,05, nem mais do que quatro moedas de 0,01. Assim sendo, o erro acumulado máximo provavelmente vai ficar lá pela quarta ou quinta casa depois da vírgula (não fiz as contas, estou estimando -- se você puder, faça as contas, pois é um bom exercício). Como você só precisa de duas casas decimais para lidar com centavos, comparar com 0,005 deve funcionar (não testei -- por favor confirme essa hipótese).

Para valores grandes, porém, você vai ter outros tipos de problemas. No caso de float, que foi o tipo que você usou, o numerador só dispõe de 24 bits para ser representado. Se você calcular, verá que 24 bits são suficientes para representar apenas 16.777.216 números diferentes. Se você começar a contar de zero e for somando 1 a uma variável do tipo float, quando chegar a 16.777.216, a contagem para de subir (o programa abaixo mostra isso).

#include <stdio.h>



int main(void){

  float a, b;

  a=0.0f;

  do {

    b=a;

    a+=1.0f;

  } while(b!=a);

  printf("a=b=%f\n", a);

  return 0;

} 

Isso acontece porque a quantidade finita de bits do numerador é usada para representar os dígitos mais significativos do número. Na medida em que o número se afasta de zero, cada vez menos bits são usados para representar a parte fracionária. A partir de um certo valor (no nosso caso, 16.777.216), já não dá nem mais para contar de um em um. Se você pensar bem, faz sentido: uma vez que o bit menos significativo vale 2²³ vezes menos do que o bit mais significativo, se eu quiser representar um número muito grande, não dá para representar, com precisão e ao mesmo tempo, um número muito pequeno. No mundo real, sobretudo para grandezas físicas, isso reflete também a forma comum de trabalhar: ninguém em sã consciência mede a distância entre Rio de Janeiro e São Paulo em Ångstroms (e, imagino, nem mesmo em milímetros), nem está preocupado com a temperatura solar com precisão de milionésimo de grau Celsius.

Só para você ter uma ideia, lembra daquele 0,01 lá de cima, que nós vimos que é arredondado para baixo e que tem uma dízima com período de vinte bits? Pois é... Se o período é de 20 bits e a representação tem 24 bits, então só sobram quatro bits de precisão para repetir o período (razão pela qual ocorre o arredondamento). Mas veja: o número é dividido por 2^30 (ou multiplicado por 2^(-30), o que dá no mesmo), o que significa que seu dígito mais significativo é 128 vezes (ou 2^7) menos significativo do que o valor unitário 1. Isso implica que se nós somarmos 1 ao valor que representa 0,01, vamos perder os sete bits menos significativos do valor (quatro da repetição da dízima, e três da própria primeira ocorrência do período). Veja como o computador opera essa soma.

Primeira parcela: 100000000000000000000000 × 2^(-23) (ou 1,00000000000000000000000 × 2^0)

 Segunda parcela: 101000111101011100001010 × 2^(-30) (ou 1,01000111101011100001010 × 2^(-7))



Alinhando as duas parcelas pelos dígitos mais significativos:



                       dígitos de guarda (usados para arredondamento durante a soma, mas desprezados depois)

                           |||

  24 bits da representação ||| dígitos desprezados (já na soma) da parcela que teve de ser deslocada

  |||||||||||||||||||||||| ||| ||||

  VVVVVVVVVVVVVVVVVVVVVVVV VVV VVVV

  100000000000000000000000|000|---- (× 2^(-23))

+ 000000010100011110101110|000|1010 (× 2^(-23))

--------------------------

  100000010100011110101110 × 2^(-23) (ou 1,00000010100011110101110 × 2^0) 

Como você viu, 1,0+0,00999999977648258209228515625 acabou resultando em 1.0099999904632568359375.

Agora volte àquele 90,01 que você mencionou. Se 1,0 já era 128 vezes maior do que o bit mais significativo de 0,01, o bit mais significativo de 90 é 8192 vezes maior do que ele: nada menos do que 13 bits da parte fracionária são deslocados, sendo os 10 inferiores sumariamente descartados, e os três imediatamente superiores usados para arredondamento do último bit do resultado (que neste caso acaba sendo para cima -- i.e. o valor final é maior do que 90,01 (exatamente 90,01000213623046875)) e depois desprezados.

Primeira parcela: 101101000000000000000000 × 2^(-17) (ou 1,01101000000000000000000 × 2^6)

 Segunda parcela: 101000111101011100001010 × 2^(-30) (ou 1,01000111101011100001010 × 2^(-7))



Alinhando as duas parcelas pelos dígitos mais significativos:



                       dígitos de guarda (usados para arredondamento durante a soma, mas desprezados depois)

                           |||

  24 bits da representação ||| dígitos desprezados (já na soma) da parcela que teve de ser deslocada

  |||||||||||||||||||||||| ||| ||||||||||

  VVVVVVVVVVVVVVVVVVVVVVVV VVV VVVVVVVVVV

  101101000000000000000000|000|---------- (× 2^(-17))

+ 000000000000010100011110|101|1100001010 (× 2^(-17))

--------------------------

  101101000000010100011111 × 2^(-17) (ou 1,01101000000010100011111 × 2^6)

                         ^                                       ^

                         |                                       |

             (por causa do arredondamento dos dígitos de guarda (101>=100)) 

Um efeito da perda de precisão que afeta particularmente o seu programa é que se o usuário digitar na entrada um número muito grande, não vai adiantar subtrair 100 para contar a quantidade de notas de cem, e você pode acabar ficando com um loop infinito (digite, por exemplo, algo na faixa de 3 bilhões como valor de entrada). Mais interessante ainda é quando você manda subtrair 100 mas, por causa de arredondamento, o que se subtrai é 128 (valores na faixa entre 550 milhões e 2 bilhões, por exemplo).

Melhor seria substituir o primeiro while por uma divisão com arredondamento do quociente para o inteiro imediatamente abaixo (a=floor(n/100.f)), e usar o resto para prosseguir com a busca de notas e moedas (n-=a*100.f). Aliás, você pode usar substituições como essa em todos os outros whiles. Não vai resolver todos os seus problemas com arredondamento -- pode até criar outros --, mas pelo menos elimina a chance do programa que nunca acaba.

---

Recomendo leitura a respeito do padrão IEEE-754 de representação e operação com números de ponto flutuante (por exemplo, o artigo na Wikipedia em Inglês é (ou era) muito bom).