Nas aulas de AED é referido o algoritmo de pesquisa binária. Para procurar um elemento num vetor ordenado podemos começar pelo elemento do meio e comparar com o que procuramos para ver se devemos continuar na metade direita ou esquerda. Desta forma, cada iteração reduz o espaço de procura a metade, acelerando imenso a pesquisa. De uma pesquisa linear O(n) passamos para uma pesquisa logarítmica O(log n).
Este algoritmo está disponível nas bibliotecas Java em Arrays.binarySearch():
int[] v = new int[] {1, 5, 8, 11, 32, 123, 543, 1200};
System.out.println(Arrays.binarySearch(v, 11));
este exemplo devolve 3 dado o elemento 11 procurado está nesse índice.
Existe igualmente o método Collections.binarySearch() onde podemos fornecer um comparador feito por nós. Iremos falar de comparadores em AED.
Este tutorial parte desta ideia de partir o espaço de pesquisa em metade, para tentar encontrar soluções para problemas onde é difícil encontrar uma expressão que resolva o problema diretamente, mas onde as diferentes hipóteses têm um comportamento monótono.
Vejamos um primeiro exemplo. Um cliente chega a um Banco e quer realizar um empréstimo de 1000 euros, para ser pago a 20 prestações mensais iguais com 1% de juros sobre a dívida por pagar a cada prestação. Qual deve ser a prestação mensal?
Ora, se procurarem na net encontram que a fórmula a aplicar é esta:
$$T \frac{r (1+r)^n}{(1+r)^n - 1}$$onde T é o total, n o número de prestações, e r o juro/prestação.
Assim, a resposta para a instância acima referida é de 55.42 euros/prestação.
***
Mas se tivéssemos num concurso de programação, sem acesso à net para descobrir a fórmula, como calcular esta resposta?
Podemos usar o método da pesquisa binária. Porquê? Porque os diferentes valores para as prestações têm um comportamento monótono. Se pagássemos 100 euros/prestação, o Banco iria dever-nos dinheiro no fim do prazo. Se fosse 200 euros, essa divida seria ainda maior. Por outro lado, se pagássemos apenas 20 euros, haveria um resto por pagar. E assim sucessivamente...
Ou seja, podemos usar o processo da pesquisa binária sobre os valores possíveis da prestação.
Para tal, definimos um intervalo onde sabemos seguramente que a resposta final irá estar. No nosso exemplo, esse intervalo pode ser [0,1000]. De certeza que temos de pagar mais que zero euros/prestação, e de certeza que não temos de pagar o total/prestação (os Bancos certamente gostariam desta possibilidade).
A partir deste intervalo podemos escolher o valor do meio, 500 euros, e verificar quanto sobraria no fim das 20 prestações: -9789,31 euros (!) Ou seja, estamos a pagar demais. Então o valor tem de estar entre [0,500]. Se experimentarmos 250 euros resulta em -4284,56 euros. Então o resultado tem de estar entre [0,250]...
O seguinte método executa este algoritmo:
private static double findMonthlyPaymentExact(int months, double total, double monthlyInterest) { double r = monthlyInterest-1; double n = months; return total * (r*Math.pow(1+r,n) / (Math.pow(1+r,n)-1)); } private static double findMonthlyPayment(int months, double total, double monthlyInterest) { double Epsilon = 1e-6; double lo = 0.0, hi = total, mid = 0.0, ans = 0.0; while (lo < hi + Epsilon) { // when the answer is not found yet mid = (lo + hi) / 2.0; // try the middle value double debt = leftDebt(mid, months, total, monthlyInterest); if (Math.abs(debt) < Epsilon) { ans = mid; break; } if (debt > 0) lo = mid; else hi = mid; } return ans; }
Reparem nos seguintes detalhes:
private static double leftDebt(double monthlyPayment, int months, double total, double monthlyInterest) { double debt = total; for(int i=0; i<months; i++) debt = debt*monthlyInterest - monthlyPayment; return debt; }
Esta técnica costuma chamar-se por método da bissecção.
Antes de continuar, uma curiosidade histórica: nesta página apresenta-se um método usado na Pérsia para calcular os juros, muito similar à fórmula atual, e que se pode justificar a sua precisão através da aproximação com polinómios de Maclaurin.
***
Vejam agora o problema UVa 11881 e tentem resolver o problema usando o método da bisecção. Uma nota, o enunciado fala de haver a hipótese de múltiplas soluções, mas isso não é relevante para os inputs dados. Não considerem essa possibilidade.
Outros problemas que podem ser abordados com esta técnica: