Algoritmo de Trabb Pardo-Knuth

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

O algoritmo de Trabb Pardo-Knuth, também conhecido como algoritmo TPK, é um programa introduzido por Donald Knuth e Luis Trabb Pardo para ilustrar a evolução das 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
para cada item na sequência A, do último ao primeiro
   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-os 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 de 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
 1 begin integer i; real y; real array a[0:10];
 2    real procedure f(t); real t; value t;
 3       f := sqrt(abs(t)) + 5 * t ^ 3;
 4    for i := 0 step 1 until 10 do read(a[i]);
 5    for i := 10 step -1 until 0 do
 6    begin y := f(a[i]);
 7       if y > 400 then write(i, "TOO LARGE")
 8                  else write(i, y);
 9    end
10 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)
 1 #include <math.h>
 2 #include <stdio.h>
 3 
 4 double f(double t)
 5 {
 6     return sqrt(fabs(t)) + 5 * pow(t, 3);
 7 }
 8 
 9 int main(void)
10 {
11     double a[11], y;
12     for (int i = 0; i < 11; i++)
13         scanf("%lf", &a[i]);
14 
15     for (int i = 10; i >= 0; i--) {
16         y = f(a[i]);
17         if (y > 400)
18             printf("%d TOO LARGE\n", i);
19         else
20             printf("%d %.16g\n", i, y);
21     }
22 }

Python[editar | editar código-fonte]

Ver artigo principal: Python
1 from math import sqrt
2 
3 def f(t):
4     return sqrt(abs(t)) + 5 * t ** 3
5 
6 a = [float(input()) for _ in range(11)]
7 for i, t in reversed(list(enumerate(a))):
8     y = f(t)
9     print(i, 'TOO LARGE' 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.

Rust[editar | editar código-fonte]

Ver artigo principal: Rust (linguagem de programação)
 1 use std::io::{stdin, BufRead};
 2 
 3 fn f(t: f64) -> f64 {
 4     t.abs().sqrt() + 5.0 * t.powi(3)
 5 }
 6 
 7 fn main() {
 8     let mut a = [0f64; 11];
 9     for (t, input) in a.iter_mut().zip(stdin().lock().lines()) {
10         *t = input.unwrap().parse().unwrap();
11     }
12 
13     for (i, &t) in a.iter().enumerate().rev() {
14         match f(t) {
15             y if y > 400.0 => println!("{} TOO LARGE", i),
16             y => println!("{} {}", i, y),
17         }
18     }
19 }

Rust lida com transbordamento numérico retornando f64::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]