☰

Wie kann ich einen Algorithmus mit Spalten wie in CLRS setzen (Einführung in Algorithmen)?

tag-icon • tag-icon algorithms
Wie kann ich einen Algorithmus mit Spalten wie in CLRS setzen (Einführung in Algorithmen)?

In Einführung in Algorithmen, von Thomas Cormen, es gibt einige Algorithmen wie in diesem Bild. Mit einer Spalte für den Code, einer für die Kosten und einer für die Zeiten.

Ich habe viel gesucht, aber nicht herausgefunden, wie das geht.

Bildbeschreibung hier eingeben

Antwort1

Dies ist, was ich tun würde, wenn ich nicht verwenden würde 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}

Bitte beachten Sie ein paar Dinge:

  1. Es gibt drei Breiten (in Zentimetern), die möglicherweise angepasst werden müssen.

  2. Die Kosten von forund whileAnweisungen stehen innerhalb der Klammern und es darf kein Leerzeichen zwischen ihnen und der schließenden Klammer sein. Dies ist etwas fragil. Dasselbe gilt für ifund alle anderen Blockanweisungen.

  3. Die Kosten für Zeile 3 werden neben der ersten der beiden Zeilen angezeigt, nicht neben der zweiten (wie im Original). So war es einfacher, aber ich glaube, ich bevorzuge es auch.

Diese Antwort geht den umgekehrten Weg zu Jubobs Antwort, die das clrscodePaket verwendet. Wenn Sie lieber verwenden clrscode, werden Sie sicher den richtigen Weg finden, |>um die zusätzlichen Spalten mit Tabulatoren zu versehen, obwohl dies nicht gut dokumentiert ist. Es kann auch aus anderen Gründen vorzuziehen sein, wenn Sie möchten, dass Ihre Algorithmen genau wie die im Buch aussehen.

Ergebnis

Antwort2

(Nur eine Teilantwort)

Cormen nutzte seineclrscodePaketfür die zweite Ausgabe von CLRS, aber eine "aufgepeppte" Version davon, genanntclrscode3e, für die dritte Auflage, aus der dieSortieren durch EinfügenAlgorithmus in Ihrem Screenshot wird genommen. Weitere Einzelheiten finden Sie unterDas.

Der Code zum Setzen des Algorithmus (aberohnedie Spalten "Kosten" und "Zeiten") finden Sie auf Seite 6 desclrscode3eDokumentation. Letzteres erwähnt nicht, wie Spalten gesetzt werden. Außerdem scheint der Quellcode des Pakets keinen (undokumentierten) Mechanismus dafür bereitzustellen.

codeboxAllerdings basiert Cormens Umgebung auf einer tabbingUmgebung; vielleicht kann man da etwas machen, aber ich kenne mich damit nicht so aus tabbing…

Bildbeschreibung hier eingeben

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

Antwort3

Es gibt das CLRS-Paket mit dem Codenamen „clrscode3e“. Die Beschreibung des Pakets sowie die .styDatei sind auf der Website verfügbar:http://www.cs.dartmouth.edu/~thc/clrscode/, können Sie die .styDatei einfach herunterladen und auch die Beschreibung lesen.

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

verwandte Informationen