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.^[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

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

ALGOL 60

Ver artigo principal: ALGOL

TPK: 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, "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

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

#include <math.h>
#include <stdio.h>

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

int main(void)
{
    double a[11] = {0}, y;
    for (int i = 0; i < 11; i++)
        scanf("%lf", &a[i]);

    for (int i = 10; i >= 0; i--) {
        y = f(a[i]);
        if (y > 400)
            printf("%d TOO LARGE\n", i);
        else
            printf("%d %.16g\n", i, y);
    }
}

Python

Ver artigo principal: Python

from math import sqrt


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


a = [float(input()) for _ in range(11)]
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

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

use std::{io, iter};

fn f(t: f64) -> Option<f64> {
    let y = t.abs().sqrt() + 5.0 * t.powi(3);
    (y <= 400.0).then_some(y)
}

fn main() {
    let mut a = [0f64; 11];
    for (t, input) in iter::zip(&mut a, io::stdin().lines()) {
        *t = input.unwrap().parse().unwrap();
    }

    a.iter().enumerate().rev().for_each(|(i, &t)| match f(t) {
        None => println!("{i} TOO LARGE"),
        Some(y) => println!("{i} {y}"),
    });
}

Rust lida com transbordamento numérico retornando f64::NAN.

Ver também

• Algoritmo
• Programa Olá Mundo

Referências

1. «The Early Development of Programming Languages» (PDF) (em inglês). Stanford University. 1977. Consultado em 11 de dezembro de 2011
2. «Tpk Algorithm» (em inglês). Consultado em 6 de dezembro de 2011
3. 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