Algoritmo de Trabb Pardo-Knuth

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O algoritmo de Trabb Pardo-Knuth, também conhecido como algoritmo de TPK, é um programa introduzido por Donald Knuth e Luis Trabb Pardo para ilustrar a evolução da linguagens de programação.[1] [2] Em seu trabalho de 1977 "The Early Development of Programming Languages", Trabb Pardo e Knuth introduziram um programa simples que envolvia arrays, índices, funções matemáticas, sub-rotinas, Entrada/saída, condicionais e iteração. Eles então escreveram implementações do algoritmo em algumas linguagens da época para demonstrar como tais conceitos eram expressados.[1]

O programa Olá Mundo tem sido usado para o mesmo propósito.[3]

O algoritmo[editar | editar código-fonte]

peça por 11 números para serem lidos em uma sequência S
inverta a sequência S
para cada item na sequência S
   faça uma operação
   se o resultado ultrapassar o limite
      alertar usuário
   senão
      imprimir resultado

O algoritmo lê onze números de um dispositivo de entrada, armazena eles em um array, e então os processa em ordem reversa, aplicando uma dada função para cada valor e reportando o valor da função ou uma mensagem para caso o valor exceder algum limite pré-definido.[2]

Implementações[editar | editar código-fonte]

ALGOL 60[editar | editar código-fonte]

begin integer i; real y; real array a[0:10];
 
real procedure f(t); real t; value t;
   f := sqrt(abs(t)) + 5 * t ^ 3;
 
for i := 0 step 1 until 10 do read(a[i]);
 
for i := 10 step -1 until 0 do
   begin y := f(a[i]);
      if y > 400 then write(i, "Valor muito grande.")
      else write(i, y);
   end
end

O problema com a função especificada é que o termo 5 * t ^ 3 dá transbordamento praticamente em todas as linguagens para números negativos muito grandes.

C[editar | editar código-fonte]

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
 
double f(double x) {
    return sqrt(abs(x)) + 5 * pow(x, 3);
}
 
int main(void) {
    double array[11], y;
    int i = 0, j = 10;
 
    for (; i < 11; i++)
        scanf("%lf", &array[i]);
 
    for (i = 0; i < 5; i++, j--) {
        y = array[i];
        array[i] = array[j];
        array[j] = y;
    }
 
    for (i = 0; i < 11; i++) {
        y = f(array[i]);
        y > 400 ? puts("Valor muito grande.") : printf("%lf\n", y);
    }
}

C♯[editar | editar código-fonte]

using System;
 
class Programa
{
    static double F(double x)
    {
        return Math.Sqrt(Math.Abs(x)) + 5 * Math.Pow(x, 3);
    }
 
    static void Main()
    {
        double[] array = new double[11];
 
        for (int i = 0; i < 11; i++)
            array[i] = double.Parse(Console.ReadLine());
 
        Array.Reverse(array);
 
        foreach (double x in array)
        {
            double y = F(x);
            Console.WriteLine(y > 400 ? "Valor muito grande." : y.ToString());
        }
    }
}

Haskell[editar | editar código-fonte]

import Control.Monad (replicateM)
 
main :: IO ()
main = mapM_ print.reverse.map (f.read.chomp) =<< replicateM 11 getLine
 
f :: Double -> Maybe Double
f x | x' > 400  = Nothing
    | otherwise = Just x'
  where x' =  sqrt (abs x) + 5 * (x ^ 3)
 
chomp :: String -> String
chomp = takeWhile (/= '\n')

Haskell usa monads para entrada/saída e o tipo Maybe para transbordamentos de sinal.

Lua[editar | editar código-fonte]

Lua é compilada com números de precisão dobrada por padrão, mas qualquer outro formato é possível.

function f(x)
   return math.abs(x) ^ 0.5 + 5 * x ^ 3
end
 
t = {}
 
for i = 1, 11 do
   table.insert(t, io.read())
end
 
for i = #t, 1, -1 do
   local r = f(t[i])
   if r > 400
      then print("Valor muito grande.")
   else print(r)
   end
end

OCaml[editar | editar código-fonte]

Versão imperativa em OCaml:

let tpk () =
  let f x = sqrt x +. 5.0 *. (x ** 3.0) in
  let pr f = print_endline (if f > 400.0 then "overflow" else string_of_float f) in
  let a = Array.init 11 (fun _ -> read_float ()) in
  for i = 10 downto 0 do
    pr (f a.(i))
  done

Uma versão funcional pode também ser escrita em OCaml:

let tpk l =
 let f x = sqrt x +. 5.0 *. (x ** 3.0) in
 let p x = x < 400.0 in
   List.filter p (List.map f (List.rev l))

Perl[editar | editar código-fonte]

sub f($) {
  return sqrt(abs($_[0])) + 5 * $_[0] ** 3;
}
 
foreach (1..11) {
  push @inputs, scalar <>;
}
 
foreach (reverse @inputs) {
  eval {
    print f($_)."\n";
  };
  $@ && print "Valor muito grande.\n";
}

Python[editar | editar código-fonte]

import math
 
def f(x):
    return math.sqrt(abs(x)) + 5 * x ** 3
 
array = [float(input()) for i in range(11)]
 
for x in reversed(array):
    y = f(x)
    print("Valor muito grande." if y > 400 else y)

Ponto flutuante em Python na maioria das plataformas é IEEE-754, que pode retornar valores "nan" e "inf", ou lançar uma exceção.

Ruby[editar | editar código-fonte]

def f(x)
  Math.sqrt(x.abs) + 5 * x ** 3
end
 
Array.new(11) { gets.to_f }.reverse.each do |x|
  y = f(x)
  puts(y > 400 ? "Valor muito grande." : y)
end

Ruby lida com transbordamento numérico retornando Infinity, que é maior do que 400.

Ver também[editar | editar código-fonte]

Referências

  1. a b Tpk Algorithm (em inglês). Página visitada em 6 de dezembro de 2011.
  2. a b Ryan Stansifer (12 de julho de 2011). TPK Algorithm in Different Programming Languages (em inglês) cs.fit.edu. Página visitada em 6 de dezembro de 2011.
  3. Wolfram Rösler (25 de setembro de 2010). The Hello World Collection (em inglês) helloworldsite.he.funpic.de. Página visitada em 6 de dezembro de 2011.

Bibliografia[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]