Алгоритм ТПК - TPK algorithm
Алгоритм TPK простая программа введена Дональдом Кнутом и Луис Trabb Pardo , чтобы проиллюстрировать эволюцию компьютерных языков программирования . В своей работе 1977 года «Раннее развитие языков программирования» Трабб Пардо и Кнут представили небольшую программу, которая включала массивы , индексацию, математические функции , подпрограммы , ввод-вывод , условные выражения и итерацию . Затем они написали реализации алгоритма на нескольких ранних языках программирования, чтобы показать, как были выражены такие концепции.
Для объяснения названия «ТПК» авторы ссылались на закон Гримма (который касается согласных «т», «р» и «к»), звуки в слове «типичный» и свои собственные инициалы (Трабб Пардо и Кнут). В докладе, основанном на статье, Кнут сказал:
Вы можете оценить, насколько глубок этот предмет, только увидев, как хорошие люди боролись с ним и как идеи возникали по очереди. Чтобы изучить это - я думаю, Луис был главным вдохновителем этой идеи - мы берем одну программу - один алгоритм - и пишем ее на всех языках. Таким образом, на одном примере мы можем быстро понять вкус этого конкретного языка. Мы называем это программой ТПК, и то, что в ней написаны инициалы Трабб Пардо и Кнут, - просто забавное совпадение.
Алгоритм
Кнут описывает это следующим образом:
Мы ввели простую процедуру, называемую «алгоритм TPK», и придали вкус каждому языку, выразив TPK в каждом конкретном стиле. […] Алгоритм TPK вводит одиннадцать чисел ; затем он выводит последовательность из одиннадцати пар, где
Очевидно, что эта простая задача не представляет большого труда для любого приличного компьютерного языка.
В псевдокоде:
ask for 11 numbers to be read into a sequence S
reverse sequence S
for each item in sequence S
call a function to do an operation
if result overflows
alert user
else
print result
Алгоритм считывает одиннадцать чисел с устройства ввода, сохраняет их в массиве, а затем обрабатывает их в обратном порядке, применяя определяемую пользователем функцию к каждому значению и сообщая либо значение функции, либо сообщение о том, что значение превысил некоторый порог.
Реализации
Реализации в оригинальной статье
В исходной статье, охватывающей «примерно первое десятилетие» разработки языков программирования высокого уровня (с 1945 по 1957 год), они дали следующий пример реализации «на диалекте АЛГОЛА 60 », отметив, что АЛГОЛ 60 был более поздняя разработка, чем языки, фактически обсуждаемые в статье:
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.
Поскольку многие ранние языки высокого уровня не могли точно обрабатывать алгоритм TPK, они допускают следующие модификации:
- Если язык поддерживает только целочисленные переменные, тогда предположим, что все входы и выходы имеют целочисленные значения, а это
sqrt(x)означает, что наибольшее целое число не превышает .
- Если язык не поддерживает буквенный вывод, то вместо строки
'TOO LARGE'выведите число 999.
- Если язык не допускает никакого ввода и вывода, то предполагается , что входные значения 11 были от внешнего процесса каким - то образом, и задача состоит в том, чтобы вычислить выходные значения 22 (с заменой 999 слишком больших значений ).
- Если язык не позволяет программистам определять свои собственные функции, замените
f(a[i])их выражением, эквивалентным .
С учетом этих изменений в случае необходимости, авторы реализовать этот алгоритм в Конрада Цузе «s планкалкюль , в Goldstine и фон Неймана » s схем , в Haskell Curry предлагаемой нотации «s, в Сокращенный код от Джона Мочли и других, в промежуточной программе Язык из Arthur Беркс , в обозначениях Heinz Rutishauser , на языке и компиляторе по Corrado Бем в 1951-52, в AutoCode из Alick Гленни , в а-2 системы Грейс Хоппер , в системе Laning и Zierler , в самый ранний предложил Fortran (1954) от Джона Бэкусом в AutoCode для Марка 1 по Тони Брукер , в ПП-2 Андрей Ершов , в BACAIC Мандалай Гремс и RE Портера, в Kompiler 2 А. Кентон Элсворт и другие, в ADES из Е.К. Блюм, внутренний переводчик Алана Перлиса , в Fortran Джона Бэкуса, в ARITH-MATIC и MATH-MATIC из лаборатории Грейс Хоппер , в системе Бауэра и Самельсона и (в дополнениях в 2003 и 2009 гг.) ПАКТ I и TRANSCODE. Затем они описывают, какой вид арифметики был доступен, и предоставляют субъективную оценку этих языков по параметрам «реализация», «удобочитаемость», «управляющие структуры», «структуры данных», «машинная независимость» и «влияние», помимо упоминания что каждый сделал первым.
Реализации на более поздних языках
C реализация
Это показывает реализацию C, эквивалентную вышеуказанному АЛГОЛУ 60.
#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
Это показывает реализацию 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)
if y > 400:
print(i, "TOO LARGE")
else:
print(i, y)
Реализация Rust
Это показывает реализацию Rust.
use std::io::{self, prelude::*};
fn f(t: f64) -> f64 {
t.abs().sqrt() + 5.0 * t.powi(3)
}
fn main() {
let mut a = [0f64; 11];
for (t, input) in a.iter_mut().zip(io::stdin().lock().lines()) {
*t = input.unwrap().parse().unwrap();
}
a.iter().enumerate().rev().for_each(|(i, &t)| match f(t) {
y if y > 400.0 => println!("{} TOO LARGE", i),
y => println!("{} {}", i, y),
});
}