Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
dicas3d

divisores

Recommended Posts

dicas3d

Quem me sabe dizer porque a quantidade de divisores no meu código nunca é igual a d.

Cá vai o código:

program divisores;
var numeros, quantidades : array[0..90] of integer;
i, contador, n, maior, min, max, d, quantidade : integer;
begin
        readln(d);
        max := trunc(sqrt(d));
        readln(n);
        for i := 1 to n do begin
        maior := trunc(sqrt(4));
        quantidade := 1;
                for contador := 1 to maior do begin
                        if i mod contador = 0 then quantidade := quantidade + 1;
                end;
                writeln(quantidade, ' ', d);
                if quantidade = d then numeros[i] := numeros[i-1]+1 else numeros[i] := numeros[i-1];
                quantidade := 1;
        end;
        for i := 1 to n do begin
                readln(min, max);
                quantidades[i] := numeros[max] - numeros[max-1];
        end;
        for i := 1 to n do writeln(quantidades[i]);
        readln;
end.

Para mais detalhe eis o problema que estou a tentar resolver, que está no link.


Abraços

dicas3d

Share this post


Link to post
Share on other sites
softklin

Acho que o teu problema está nas raízes quadradas. Por exemplo, o número 10 tens os divisores 1, 2, 5, 10 (4 divisores). O próprio número estás a contar logo no inicio, mas neste caso não vais contar o 5 porque:

sqrt(10) ~ 3.16 ~ 3. No teu ciclo 2º ciclo, não vais contar o 5, e vais considerar apenas o 1, 2, 10 (3 divisores).

Não vi o resto do código, mas pareceu-me que houvesse um problema com isso. O que podes fazer é contar até metade do número, por exemplo, 10/2 = 5, então o teu "maior" vai ser 5, e até já é contabilizado.


Nick antigo: softclean | Tens um projeto? | Wiki P@P

Ajuda a comunidade! Se encontrares algo de errado, usa a opção "Denunciar" por baixo de cada post.

Share this post


Link to post
Share on other sites
pedrosorio

A razão pela qual isso está a acontecer é que não percebes para que serve verificar até à raíz quadrada.

A razão pela qual deves ir até à raíz quadrada é que se 'a' é divisor de 'b', isto é, b/a é um inteiro, então b/a também é divisor de b, já que b/(b/a) = a. Por este motivo, deves contar cada divisor 2 vezes até chegar à raíz quadrada do número. Exemplo:

n=24, qtd = 0, vamos de i=1 até raíz(24) aprox.=4.90 (portanto vamos de 1 até 4)

1 -> é divisor, contamos 2 (1 e 24/1=24)

2-> é divisor, contamos 2 ( 2 e 24/2=12)

3-> é divisor, contamos 2 ( 3 e 24/3=8)

4-> é divisor, contamos 2 ( 4 e 24/4=6)

Achámos 8 divisores: 1,2,3,4,6,8,12,24

Outro exemplo, com n=25, temos raíz(25) = 5

1-> é divisor, contamos 2 (1 e 25/1=25)

2-> não é divisor

3-> não é divisor

4-> não é divisor

5-> é divisor, contamos 2 (5 e 25/5=5)

Contamos 4 divisores, mas está errado, porque 5 é raíz de 25 e contamo-lo duas vezes. O que eu faria no código seria diminuir 1 valor ao número de divisores se o número fosse um quadrado perfeito (i.e. se trunc(sqrt(n)) = sqrt(n)).


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
dicas3d

Já tinha resolvido o problema embora de forma não tão eficiente. Mas obrigado pelas dicas.


Abraços

dicas3d

Share this post


Link to post
Share on other sites
pedrosorio

Já tinha resolvido o problema embora de forma não tão eficiente. Mas obrigado pelas dicas.

Neste tipo de concursos só há duas coisas importantes, por esta ordem:

1) Algoritmo correcto

2) Algoritmo eficiente

Tenta ver se consegues implementar algoritmos para achar divisores sem hesitar porque são fundamentais.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.