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][3] 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][2]

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

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

peça por 11 números para serem lidos em uma sequência A
inverta a sequência A
para cada item na sequência A
   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.[3]

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

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

Ver artigo principal: ALGOL 60
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]

Ver artigo principal: C (linguagem de programação)
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

double f(double t) {
    return sqrt(fabs(t)) + 5 * pow(t, 3);
}

int main(void) {
    double a[11], y;
    int i;

    for (i = 0; i < 11; i++)
        scanf("%lf", &a[i]);

    for (i = 10; i >= 0; i--) {
        y = f(a[i]);
        y > 400 ? puts("Valor muito grande") : printf("%lf\n", y);
    }
}

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

Ver artigo principal: C♯
using System;

class Programa
{
    static double F(double t)
    {
        return Math.Sqrt(Math.Abs(t)) + 5 * Math.Pow(t, 3);
    }

    static void Main()
    {
        double[] a = new double[11];

        for (int i = 0; i < 11; i++)
            a[i] = double.Parse(Console.ReadLine());

        Array.Reverse(a);

        foreach (double t in a)
        {
            double y = F(t);
            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 t | t' > 400  = Nothing
    | otherwise = Just t'
  where t' =  sqrt (abs t) + 5 * (t ^ 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]

Ver artigo principal: Lua (linguagem de programação)

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

function f(t)
   return math.abs(t) ^ 0.5 + 5 * t ^ 3
end

a = {}

for i = 1, 11 do
   table.insert(a, io.read())
end

for i = #a, 1, -1 do
   local y = f(a[i])
   if y > 400 then
      print("Valor muito grande")
   else
      print(y)
   end
end

Perl[editar | editar código-fonte]

Ver artigo principal: Perl
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]

Ver artigo principal: Python
import math

def f(t):
    return math.sqrt(abs(t)) + 5 * t ** 3

a = [float(input()) for i in range(11)]

for t in reversed(a):
    y = f(t)
    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]

Ver artigo principal: Ruby (linguagem de programação)
def f(t)
  Math.sqrt(t.abs) + 5 * t ** 3
end

Array.new(11) { gets.to_f }.reverse.each do |t|
  y = f(t)
  puts(y > 400 ? "Valor muito grande" : y)
end

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

Rust[editar | editar código-fonte]

Ver artigo principal: Rust (linguagem de programação)
fn main() {
    let f = |t: f64| t.abs().sqrt() + 5.0 * t.powi(3);
    let mut a = [0f64; 11];

    for t in &mut a {
        let mut num = String::new();
        std::io::stdin().read_line(&mut num).ok();
        *t = num.trim().parse().unwrap();
    }

    for &t in a.iter().rev() {
        match f(t) {
            y if y > 400.0 || y.is_nan() => println!("Valor muito grande"),
            y => println!("{}", y)
        }
    }
}

Rust lida com transbordamento numérico retornando NAN.

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

Referências

  1. a b «The Early Development of Programming Languages» (PDF) (em inglês). Stanford University. 1977. Consultado em 11 de dezembro de 2011 
  2. a b «Tpk Algorithm» (em inglês). Consultado em 6 de dezembro de 2011 
  3. a b Ryan Stansifer (12 de julho de 2011). «TPK Algorithm in Different Programming Languages» (em inglês). cs.fit.edu. Consultado em 6 de dezembro de 2011 
  4. Wolfram Rösler (25 de setembro de 2010). «The Hello World Collection» (em inglês). helloworldsite.he.funpic.de. Consultado em 6 de dezembro de 2011 

Bibliografia[editar | editar código-fonte]

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