☰

¿Cómo puedo componer un algoritmo con columnas como en CLRS (Introducción a los algoritmos)?

tag-icon • tag-icon algorithms
¿Cómo puedo componer un algoritmo con columnas como en CLRS (Introducción a los algoritmos)?

En Introducción a los algoritmos, de Thomas Cormen, hay algunos algoritmos como en esta imagen. Con una columna para el código, otra para el costo y otra para los tiempos.

Busqué mucho, pero no encontré cómo hacerlo.

ingrese la descripción de la imagen aquí

Respuesta1

Esto es lo que haría si no usara clrscode.

\documentclass[11pt]{article}

\usepackage[noend]{algorithmic}

\newcommand{\TITLE}[1]{\item[#1]}
\renewcommand{\algorithmiccomment}[1]{$/\!/$ \parbox[t]{4.5cm}{\raggedright #1}}
% ugly hack for for/while
\newbox\fixbox
\renewcommand{\algorithmicdo}{\setbox\fixbox\hbox{\ {} }\hskip-\wd\fixbox}
% end of hack
\newcommand{\algcost}[2]{\strut\hfill\makebox[1.5cm][l]{#1}\makebox[4cm][l]{#2}}

\begin{document}
\begin{algorithmic}[1]
  \TITLE{\textsc{Insertion-Sort}$(A)$}
    \algcost{\textit{cost}}{\textit{times}}
  \FOR{$j=2$ \TO $A.\mathit{length}$
    \algcost{$c_1$}{$n$}}
  \STATE $\mathit{key} = A[j]$
    \algcost{$c_2$}{$n-1$}
  \STATE \COMMENT{Insert $A[j]$ to the sorted sequence $A[1..j-1]$}
    \algcost{$0$}{$n-1$}
  \STATE $i = j-1$
    \algcost{$c_4$}{$n-1$}
  \WHILE{$i>0$ \AND $A[i]>key$
    \algcost{$c_5$}{$\sum_{j=2}^{n} t_j$}}
  \STATE $A[i+1]= A[i]$
    \algcost{$c_6$}{$\sum_{j=2}^{n} (t_j-1)$}
  \STATE $i = i-1$
    \algcost{$c_7$}{$\sum_{j=2}^{n} (t_j-1)$}
  \ENDWHILE
  \STATE $A[i+1] = \mathit{key}$
    \algcost{$c_8$}{$n-1$}
  \ENDFOR
\end{algorithmic}
\end{document}

Por favor, observe algunas cosas:

  1. Hay tres anchos (en centímetros) que pueden necesitar ajustes.

  2. Los costos fory whiledeclaraciones se encuentran entre paréntesis y no debe haber ningún espacio entre ellos y el paréntesis de cierre. Esto es un poco frágil. Lo mismo para ify todas las demás declaraciones de bloque.

  3. El costo de la línea 3 se muestra al lado de la primera de las dos líneas, no de la segunda (como en el original). Era más fácil así, pero creo que también lo prefiero.

Esta respuesta toma el camino opuesto a la respuesta de Jubobs, que utiliza el clrscodepaquete. Si prefiere utilizar clrscode, estoy seguro de que encontrará la manera de utilizarlo correctamente |>para tabular las columnas adicionales, aunque no está bien documentado. Además, puede ser preferible por otras razones, si desea que sus algoritmos se vean exactamente como los del libro.

resultado

Respuesta2

(Solo una respuesta parcial)

Cormen usó suclrscodepaquetepara la segunda edición de CLRS, pero una versión "reforzada", llamadaclrscode3e, para la tercera edición, de la queTipo de inserciónSe toma el algoritmo en su captura de pantalla. Para más detalles, vereste.

El código para componer el algoritmo (perosinlas columnas "costo" y "tiempos") se pueden encontrar en la página 6 delclrscode3edocumentación. Este último no menciona cómo componer las columnas. Además, el código fuente del paquete no parece proporcionar ningún mecanismo (no documentado) para ello.

Sin embargo, el entorno de Cormen codeboxse basa en un tabbingentorno; tal vez haya algo que hacer allí, pero no estoy tan familiarizado con tabbing...

ingrese la descripción de la imagen aquí

\documentclass{article}

\usepackage{clrscode3e}

\begin{document}

\begin{codebox}
\Procname{$\proc{Insertion-Sort}(A)$}
\li \For $j \gets 2$ \To $\attrib{A}{length}$
\li     \Do
            $\id{key} \gets A[j]$
\li         \Comment Insert $A[j]$ into the sorted sequence
                $A[1 \twodots j-1]$.
\li         $i \gets j-1$
\li         \While $i > 0$ and $A[i] > \id{key}$
\li             \Do
                    $A[i + 1] = A[i]$
\li                 $i \gets i-1$
                \End
\li         $A[i+1] \gets \id{key}$
        \End
\end{codebox}

\end{document}

Respuesta3

Existe el paquete CLRS, nombre en clave "clrscode3e", la descripción del paquete y el .styarchivo están disponibles en el sitio web:http://www.cs.dartmouth.edu/~thc/clrscode/, puede descargar fácilmente el .styarchivo y también leer la descripción.

\documentclass{article}

\usepackage{clrscode3e}

\begin{document}

\begin{codebox}
\Procname{$\proc{Insertion-Sort}(A)$}
\li \For $j \gets 2$ \To $\attrib{A}{length}$
\li     \Do
            $\id{key} \gets A[j]$
\li         \Comment Insert $A[j]$ into the sorted sequence
                $A[1 \twodots j-1]$.
\li         $i \gets j-1$
\li         \While $i > 0$ and $A[i] > \id{key}$
\li             \Do
                    $A[i + 1] = A[i]$
\li                 $i \gets i-1$
                \End
\li         $A[i+1] \gets \id{key}$
        \End
\end{codebox}
\end{document}

información relacionada