Array
(
)

Ajuda para escrever algorímo recursivo complexo

Tatuweb
   - 15 ago 2004

Tenho uma função como a abaixo:

function RetornaS (P: Byte): DWord;

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.


Skywalker
   - 16 ago 2004

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.


Skywalker
   - 16 ago 2004

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.


Tatuweb
   - 16 ago 2004

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:
if (S < RetornaS (Min) ) or (S > RetornaS (Max)) then Exit;
para garantir que não fosse inserido um número que a função não suportasse.

A linha
Temp := Min + ((Min - Max) + 1 div 2)
eu troquei por
Temp := (Max + Min) div 2;

e no final eu também troquei
if (Retornas (Min) - S) < (Retornas (Max) - S) then
por
if (S - RetornaS (Min)) < (retornaS (Max) - S) then

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