Ajuda para escrever algorímo recursivo complexo

15/08/2004

0

Tenho uma função como a abaixo:

[b:ce5f5e08a9]function RetornaS (P: Byte): DWord;[/b:ce5f5e08a9]

Onde P significa graduação e é um numero entre 1 e 50. Quanto maior o valor de P maior será o valor retornado pela função. O fato é que dado um numero N eu preciso saber a qual graduação (P) N estará mais próximo. Exemplo:

Suponhamos que N (valor definido pelo usuário) seja 440. Então eu faço:
RetornaS (1) a função me retorna 20 << Menor valor da graduação é 1
RetornaS (50) a função me retorna 1200 << Maior valor da graduação é 50
RetornaS ((50+1 div 2) a função me retorna 650 << Média é 25

Feito isso eu sei que a graduação (P) de N está entre 1 e 25 (50 + 1 div 2) pois N = 440 e 440 está entre 20 (P1) e 650 (P25). O problema é que eu tenho que repetir esse processo várias vezes por tempo indeterminado até eu achar a graduação mais próxima do numero dado pelo usuário (N). Se eu continuasse na mão eu faria:

RetornaS (1) retorna 20
RetornaS (25) retorna 650
RetornaS (25+1 div 2) retorna 390

Agora eu sei que a graduação (o mesmo que P) de N está entre 13 e 25 pois P13 = 390 e P25 = 650 e N vale 440. Assim eu devo seguir até achar a graduação (P) mais próxima. Se eu descreve-se toda o trajeto da função encontraria P = 15 pois RetornaS (15) = 430 e RetornaS (16) = 460. Como o numero procurado é 440, P15 é o que está mais perto. O que eu quero é um algorítimo para fazer isso.

Alguém pode questionar porque não fazer o cálculo de todas as graduações ao invés de ir calculando por média como to fazendo. O fato é que o cálculo da função RetornaS é lento e demora em média 4 segs. Se eu calculasse isso 50 vezes meu programa demoraria em média 3 minutos para concluir a operação. Então quanto menos eu usar a função retornaS mais rápido o programa. Além disso. o valor retornado pela função é variável de acordo com o dia. Isso signifca que RetornaS (1) pode retornar 20 quanto pode retornar 500. Isso depende do dia. Qualquer ajuda será bem vinda.


Tatuweb

Tatuweb

Responder

Posts

16/08/2004

Skywalker

Ola Tatuweb tudo bem?
Tenho uma sugestao que funciona da seguinte forma:
voce declara duas variaveis:
min, max, temp: integer; //onde min e o valor minimo e max e o valor maximo
comparativo
min:= 1; //o valor minimo de graduacao
max:= 50; //o valor maximo de graduacao
while sair <> true do
begin
temp:= max + 1 div 2
if retornas(temp) > s then //a variavel s e enviada pelo usuario
begin
max:= temp;
end
else
begin
min:= temp;
end;
if (min + 1) = max then //chegou ao intervalo minimo
begin
sair:= true;
if (retornas(min) - s) < (retornas(max) - s) then
temp:= min
else
temp:= max;
end;
ao final o valor de temp sera o mais proximo do valor digitado pelo usuario.

Espero ter ajudado.
Retorne falando se funcionou.


Responder

16/08/2004

Skywalker

Correcoes da versao 1.0 do algoritmo:

troque a linha a seguir:
temp:= max + 1 div 2
pela seguinte:
temp:= min + ((min-max) + 1 div 2)

com isso voce ira pegar o meio termo entre o minimo e o maximo mesmo que o minimo seja diferente de 1 e o maximo diferente de 50.

Agradecimentos e aguardo resposta.


Responder

16/08/2004

Tatuweb

Obrigado pela ajuda. Eu tive que fazer duas modificações para que o código funcionasse 100¬ mas sua ajuda foi muito útil.

Ao inicio do código eu adicionei a linha:
[color=blue:e34dd04174]if (S < RetornaS (Min) ) or (S > RetornaS (Max)) then Exit;[/color:e34dd04174]
para garantir que não fosse inserido um número que a função não suportasse.

A linha
[color=blue:e34dd04174]Temp := Min + ((Min - Max) + 1 div 2)[/color:e34dd04174]
eu troquei por
[color=blue:e34dd04174]Temp := (Max + Min) div 2;[/color:e34dd04174]

e no final eu também troquei
[color=blue:e34dd04174]if (Retornas (Min) - S) < (Retornas (Max) - S) then[/color:e34dd04174]
por
[color=blue:e34dd04174]if (S - RetornaS (Min)) < (retornaS (Max) - S) then[/color:e34dd04174]

Mais uma vez agradeço pela ajuda. Está tudo certo agora.


Responder

Que tal ter acesso a um e-book gratuito que vai te ajudar muito nesse momento decisivo?

Ver ebook

Recomendado pra quem ainda não iniciou o estudos.

Eu quero
Ver ebook

Recomendado para quem está passando por dificuldades nessa etapa inicial

Eu quero

Utilizamos cookies para fornecer uma melhor experiência para nossos usuários, consulte nossa política de privacidade.

Aceitar