☰

Como posso compor um algoritmo com colunas como no CLRS (Introdução aos Algoritmos)?

tag-icon • tag-icon algorithms
Como posso compor um algoritmo com colunas como no CLRS (Introdução aos Algoritmos)?

Em Introdução aos Algoritmos, de Thomas Cormen, existem alguns algoritmos como nesta imagem. Com uma coluna para o código, uma para o custo e outra para os tempos.

Procurei muito, mas não encontrei como fazer.

insira a descrição da imagem aqui

Responder1

Isso é o que eu faria, se não usasse 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 algumas coisas:

  1. Existem três larguras (em centímetros) que podem precisar de ajustes.

  2. Os custos fore whileextratos estão entre colchetes e não deve haver espaço entre eles e o colchete de fechamento. Isso é um pouco frágil. O mesmo para ife todas as outras instruções de bloco.

  3. O custo da linha 3 é exibido próximo à primeira das duas linhas, não à segunda (como no original). Foi mais fácil assim, mas acho que também prefiro.

Esta resposta segue o caminho oposto da resposta do Jubobs, que está usando o clrscodepacote. Se você preferir usar clrscode, tenho certeza que encontrará uma maneira de usar corretamente |>para tabular as colunas extras, embora não esteja bem documentado. Além disso, pode ser preferível por outros motivos, se você quiser que seus algoritmos sejam exatamente iguais aos do livro.

resultado

Responder2

(Apenas uma resposta parcial)

Cormen usou seuclrscodepacotepara a segunda edição do CLRS, mas uma versão "reforçada" dele, chamadaclrscode3e, para a terceira edição, da qual oClassificação de inserçãoalgoritmo em sua captura de tela é obtido. Para mais detalhes, consulteesse.

O código para composição do algoritmo (massemcolunas "custo" e "tempos") podem ser encontradas na página 6 doclrscode3edocumentação. Este último não menciona como compor colunas. Além disso, o código-fonte do pacote não parece fornecer nenhum mecanismo (não documentado) para isso.

Entretanto, o ambiente de Cormen codeboxé baseado em um tabbingambiente; talvez haja algo a ser feito aí, mas não estou tão familiarizado com isso tabbing...

insira a descrição da imagem aqui

\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}

Responder3

Existe o pacote CLRS, codinome "clrscode3e", a descrição do pacote bem como o .styarquivo estão disponíveis no site:http://www.cs.dartmouth.edu/~thc/clrscode/, você pode baixar facilmente o .styarquivo e também ler a descrição.

\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}

informação relacionada