☰

CLRS (アルゴリズム入門) のように列を使用してアルゴリズムをタイプセットするにはどうすればよいですか?

tag-icon • tag-icon algorithms
CLRS (アルゴリズム入門) のように列を使用してアルゴリズムをタイプセットするにはどうすればよいですか?

で アルゴリズム入門Thomas Cormen による、この画像のようなアルゴリズムがいくつかあります。コード用に 1 つの列、コスト用に 1 つ、時間用に 1 つあります。

いろいろ検索しましたが、やり方がわかりませんでした。

ここに画像の説明を入力してください

答え1

を使用しない場合は、これを実行します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}

いくつかの点に注意してください:

  1. 微調整が必​​要な幅（センチメートル単位）が 3 つあります。

  2. forおよびステートメントのコストはwhile括弧内にあります。また、それらと閉じ括弧の間にはスペースがあってはなりません。これは少し脆弱です。ifおよび他のすべてのブロック ステートメントについても同様です。

  3. 3 行目の料金は、元のように 2 行目ではなく、最初の行の横に表示されます。この方が簡単でしたが、私もその方が好みだと思います。

この回答は、パッケージを使用する Jubobs の回答とは逆のルートをたどりますclrscode。 を使用することを好む場合はclrscode、十分に文書化されていませんが、追加の列をタブで区切るために を適切に使用する方法が見つかると思います|>。また、アルゴリズムを本のアルゴリズムとまったく同じようにしたい場合は、他の理由でもそれが好ましい場合があります。

結果

答え2

（部分的な回答です）

コーメンはclrscodeパッケージCLRSの第2版のものですが、その「強化版」と呼ばれるclrscode3e、第3版では、挿入ソートスクリーンショットのアルゴリズムが取得されます。詳細については、これ。

アルゴリズムをタイプセットするためのコード（ただしそれなし「コスト」と「時間」の欄は、clrscode3eドキュメンテーション後者では、列をタイプセットする方法については何も言及されていません。また、パッケージのソース コードには、そのための (文書化されていない) メカニズムが提供されていないようです。

しかし、Cormen のcodebox環境は環境に基づいていますtabbing。おそらく、そこで何かできることがあるのでしょうが、私はあまり詳しくありませんtabbing...

ここに画像の説明を入力してください

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

答え3

CLRS パッケージ (コード名 "clrscode3e") があり、パッケージの説明と.styファイルは Web サイトで入手できます。http://www.cs.dartmouth.edu/~thc/clrscode/、.styファイルを簡単にダウンロードでき、説明も読むことができます。

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

関連情報