Algoritmo de Trabb Pardo-Knuth
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. 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.
O programa Olá Mundo tem sido usado para o mesmo propósito.
O algoritmo
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.
Implementações
ALGOL 60
TPK: begin integer i; real y; real array a;
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);
for i := 10 step -1 until 0 do
begin y := f(a);
if y > 400 then write(i, "TOO LARGE")
else write(i, y);
end
end TPK.
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
#include <math.h>
#include <stdio.h>
double f(double t)
{
return sqrt(fabs(t)) + 5 * pow(t, 3);
}
int main(void)
{
double a = {0}, y;
for (int i = 0; i < 11; i++)
scanf("%lf", &a);
for (int i = 10; i >= 0; i--) {
y = f(a);
if (y > 400)
printf("%d TOO LARGE\n", i);
else
printf("%d %.16g\n", i, y);
}
}
Python
from math import sqrt
def f(t):
return sqrt(abs(t)) + 5 * t ** 3
a =
for i, t in reversed(list(enumerate(a))):
y = f(t)
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
use std::{io, iter::zip};
fn f(t: f64) -> f64 {
t.abs().sqrt() + 5.0 * t.powi(3)
}
fn main() {
let mut a = ;
for (t, input) in zip(&mut a, io::stdin().lines()) {
*t = input.unwrap().parse().unwrap();
}
a.iter().enumerate().rev().for_each(|(i, &t)| match f(t) {
y if y > 400.0 => println!("{i} TOO LARGE"),
y => println!("{i} {y}"),
});
}
Rust lida com transbordamento numérico retornando f64::NAN.
Ver também
Referências
- ↑ a b «The Early Development of Programming Languages» (PDF) (em inglês). Stanford University. 1977. Consultado em 11 de dezembro de 2011
- ↑ a b «Tpk Algorithm» (em inglês). Consultado em 6 de dezembro de 2011
- ↑ 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
- ↑ 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
Ligações externas