欧几里得算法命令

欧几里得算法命令

我目前正在努力提高我的 LaTeX 技能,因此我找到了 Jason Gross 的练习列表这里

我正在尝试完成的练习是 1.5 欧几里得算法。

我已经成功创建了一个新的命令,可以按照要求打印出所有步骤,但现在我不知道如何保持对齐。正如您在网站上看到的,所有“=”都从一行到下一行完美对齐,但我不知道如何做到这一点。

这是我写的命令,(我试图改变显示但无法对齐相等的符号......)

\newif\ifgeq \newcount\a \newcount\b \newcount\r \newcount\q \newcount\step
\newcommand{\euclidean}[3][1]{\step=#1 \a=#2 \b=#3 \[\]\vspace{-1cm}
    \loop\ifnum\b>0 \q=0 \r=\a \find \printIntDiv \a=\b \b=\r \repeat \begin{center}The gcd of #2 and #3 is equal to \number\a\end{center}}
\def\isgeq{\ifnum\r<\b \global\geqfalse\fi}
\def\find{{\global\geqtrue \isgeq
    \loop\ifgeq \global\advance\q by1 \global\advance\r by-\b \isgeq \repeat}}
\def\printIntDiv{\ifnum\step=1 \[ \number\a = \number\q \cdot \number\b + \number\r \] \vspace{-0.6cm}\fi}

\euclidean{377}{610}

主要问题似乎在于我一拿到步骤就排版,这让对齐变得困难。但是我不知道如何在不排版的情况下继续进行,因为我不知道如何以其他方式“存储”它们。

如果有人能帮助我我将非常感激。

答案1

您可以使用对齐方式,在进行过程中积累材料并在最后交付它。

\documentclass{article}
\usepackage{amsmath}

\newif\ifgeq
\newcount\a
\newcount\b
\newcount\r
\newcount\q
\newcount\step

\newcommand{\euclidean}[3][1]{%
  \[\begin{gathered}
  \step=#1 \a=#2 \b=#3
  \gdef\sofar{}%
  \gdef\result{\number\b}%
  \loop\ifnum\b>0
    \q=0
    \r=\a
    \find
    \printIntDiv
    \a=\b
    \b=\r
  \repeat
  \begin{aligned}\sofar\end{aligned} \\[0.5ex]
  \text{The gcd of $#2$ and $#3$ is equal to $\result$}
  \end{gathered}\]
}
\def\isgeq{\ifnum\r<\b \global\geqfalse\fi}
\def\find{{% <-- group
  \global\geqtrue
  \isgeq
  \loop\ifgeq
    \global\advance\q by1
    \global\advance\r by-\b
    \isgeq
  \repeat
}}
\def\printIntDiv{%
  \ifnum\step=1
    \xdef\sofar{%
      \unexpanded\expandafter{\sofar}%
      \number\a &= \number\q \cdot \number\b + \number\r\noexpand\\
    }%
  \xdef\result{\number\b}%
  \fi
}

\begin{document}

\euclidean{377}{610}

\euclidean{24}{18}

\euclidean{4}{2}

\end{document}

在此处输入图片描述

更简单的实现方式是expl3

\documentclass{article}
\usepackage{amsmath}

\ExplSyntaxOn

\tl_new:N \l_needle_euclid_steps_tl
\tl_new:N \l_needle_euclid_gcd_tl

\cs_new_protected:Nn \needle_euclid_steps:nn
 {
  \tl_put_right:Nx \l_needle_euclid_steps_tl
   {
    #1 &= \int_div_truncate:nn { #1 } { #2 } \cdot #2 + \int_mod:nn { #1 } { #2 } \exp_not:N \\
   }
  \int_compare:nTF { \int_mod:nn { #1 } { #2 } > 0 }
   {
    \needle_euclid_steps:ne { #2 } { \int_mod:nn { #1 } { #2 } }
   }
   {
    \tl_set:Nn \l_needle_euclid_gcd_tl { #2 }
   }
 }
\cs_generate_variant:Nn \needle_euclid_steps:nn { ne }

\NewDocumentCommand{\euclidean}{mm}
 {
  \[
    \needle_euclid_steps:nn { #1 } { #2 }
    \begin{gathered}
      \begin{aligned}
      \l_needle_euclid_steps_tl
      \end{aligned} \\[0.5ex]
      \text{The~gcd~of~$#1$~and~$#2$~is~$\l_needle_euclid_gcd_tl$}
    \end{gathered}\]
 }

\ExplSyntaxOff

\begin{document}

\euclidean{377}{610}

\euclidean{24}{18}

\euclidean{4}{2}

\end{document}

主函数\needle_euclid_steps:nn负责计算商和余数;它附加步骤并递归调用自身,除非最后一个余数为零。此时,它记录最后一个余数并退出递归。

计算 gcd 要简单得多,但想法是一样的

\ExplSyntaxOn
\NewExpandableDocumentCommand{\computegcd}{mm}
 {
  \int_compare:nTF { #2 = 0 }
   { #1 } % #2 = 0, do nothing and return #1
   { \needle_gcd:nn { #1 } { #2 } }
 }
\cs_new:Nn \needle_gcd:nn
 {
  \int_compare:nTF { \int_mod:nn { #1 } { #2 } = 0 }
   { #2 }
   { \needle_gcd:ne { #2 } { \int_mod:nn { #1 } { #2 } } }
 }
\cs_generate_variant:Nn \needle_gcd:nn { ne }
\ExplSyntaxOff

答案2

为了玩得开心并介绍这个问题,我们使用一个简短的尾递归程序来执行\numexprε-TeX 扩展中的减法。

(可以\number\numexpr...\relax用自己的\romannumeral扩展驱动的可扩展减法程序来替代。但为什么呢?如今,如果没有 ε-TeX 扩展,LaTeX 就无法工作。)

它仅适用于计算自然的数字。

它不会打印单个步骤。它只是提供结果。

没有检查参数是否形成自然的数字/如果满足参数的要求。

不再使用临时宏作为变量,也不再一直进行临时赋值来存储变量的值,而是将宏参数用作“变量”。在尾递归循环中,通过更改下一次迭代的相应宏参数来更改“变量”的值。

\documentclass{article}

%% Pseudocode:
%% 
%% Euclid(#1,#2)  //  Calculates gcd(#1,#2). 
%%                //  #1 and #2 are to be _natural_ numbers !!
%% 
%%     WHILE #2 =/= 0
%%       IF #1 > #2 THEN
%%         #1 :=  #1 - #2
%%       ELSE
%%         #2 :=  #2 - #1
%%       ENDIF
%%     ENDWHILE
%%     RESULT := #1
%%
\newcommand\UDPassFirstToSecond[2]{#2{#1}}%
\newcommand\UDfirstoftwo[2]{#1}%
\newcommand\UDsecondoftwo[2]{#2}%

\newcommand\Euclid[2]{%
  \ifnum#2=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
  {#1}{%
    \ifnum#1>#2 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
    {%
      \expandafter\Euclid\expandafter{\number\numexpr#1-#2\relax}{#2}%
    }{%
      \expandafter\UDPassFirstToSecond\expandafter{\number\numexpr#2-#1\relax}{\Euclid{#1}}%
    }%
  }%
}%

\begin{document}

gcd(377; 610) is: \Euclid{377}{610}

\noindent\hrulefill

gcd(144; 960) is: \Euclid{144}{960}

\noindent\hrulefill

gcd(960; 144) is:  \Euclid{960}{144}

\end{document}

在此处输入图片描述



为了获得更多乐趣,我们使用一个可扩展的尾递归例程,利用\numexprε-TeX 扩展进行减法。

它适用于计算整数

它确实打印了单个步骤。

没有检查参数是否形成整数/如果满足参数的要求。

由于\romannumeral-expansion,结果是在“命中”\expandafter两次后得出的。

您可以考虑通过包的可扩展例程进行算术和数字比较bigintcalc

顺便一提:

该例程“表示” gcd(0,0) 未定义。
之所以“表示”如此,是因为它是欧几里得算法的实现,而欧几里得未定义 gcd(0,0)。

如果“最大公约数”中的“最大”确实指的是自然数的整除性偏序,则 gcd(0,0)=0。

此外,如果“最大公约数”中的“最大”确实指的是自然数的整除偏序,那么通常不会只有一个 gcd。例如,如果自然数x是指整数的顺序的最大公约数,那么指自然数的整除偏序,gcd 是x-x

相应地改变例程应该很简单,因此留给感兴趣的人作为练习。;->

\documentclass{article}
\usepackage{amsmath}

\newcommand\UDPassFirstToSecond[2]{#2{#1}}%
\newcommand\UDExchange[2]{#2#1}%
\newcommand\UDfirstoftwo[2]{#1}%
\newcommand\UDsecondoftwo[2]{#2}%
\csname @ifdefinable\endcsname\UDstopromannumeral{\chardef\UDstopromannumeral=`\^^00}%

\newcommand\Euclidean[2]{%
  \romannumeral
  % Wrapping between braces as argument of \UDExchange might help ensuring that
  % things won't get disturbed if carried out insige a tabular-environment or
  % the like.
  \expandafter\UDExchange\expandafter{%
    \romannumeral
    \expandafter\UDPassFirstToSecond
    \expandafter{\number#2}%
                {\expandafter\EuclideanSignCheck\expandafter{\number#1}}%
  }{\UDstopromannumeral}%
}%

\newcommand\EuclideanSignCheck[2]{%
  \ifnum#1=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi{%
    \ifnum#2=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi{%
       \UDstopromannumeral
       \[\begin{gathered}\text{The gcd of #1 and #2 is not defined.}\end{gathered}\]%
    }{%
       \expandafter\UDPassFirstToSecond\expandafter{%
          \romannumeral
          \expandafter\UDExchange
          \expandafter{\number\ifnum#2<0 -\fi\number#2.}%
                      {\UDstopromannumeral The gcd of #1 and #2 is }%
       }{\UDstopromannumeral\[\begin{gathered}\text}%
       \end{gathered}\]%
    }%
  }{%
    \ifnum#2=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi{%
       \expandafter\UDPassFirstToSecond\expandafter{%
          \romannumeral
          \expandafter\UDExchange
          \expandafter{\number\ifnum#1<0 -\fi\number#1.}%
                      {\UDstopromannumeral The gcd of #1 and #2 is }%
       }{\UDstopromannumeral\[\begin{gathered}\text}%
       \end{gathered}\]%
    }{%
      \ifnum#1<0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
      {%
         \ifnum#2<0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
         {%
           \expandafter\UDPassFirstToSecond
           \expandafter{\number-#2}%
                       {\expandafter\EuclideanLoopStart\expandafter{\number-#1}}%
                       {\UDfirstoftwo}%
         }%
         {\expandafter\EuclideanLoopStart\expandafter{\number-#1}{#2}{\UDfirstoftwo}}%
      }%
      {%
         \ifnum#2<0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
         {%
           \expandafter\UDPassFirstToSecond
           \expandafter{\number-#2}%
                       {\EuclideanLoopStart{#1}}%
                       {\UDfirstoftwo}%
         }%
         {\EuclideanLoopStart{#1}{#2}{\UDsecondoftwo}}%
      }%
      {The gcd of #1 and #2 is equal to }%
    }%
  }%
}%

\newcommand\EuclideanLoopStart[4]{%
  %#1 = absolute value of 1st number
  %#2 = absolute value of 2nd number
  %#3 = \UDfirstoftwo/\UDsecondoftwo - flag indicating if switching sign occurred
  %#4 = begin of result-phrase, holding initial numbers
  #3{%
    \EuclideanLoop{#1}{0}{#2}{#1}{}{#4}{the gcd of #1 and #2:}%
  }{%
    \EuclideanLoop{#1}{0}{#2}{#1}{}{#4}{}%
  }%
}%

\newcommand\EuclideanLoop[7]{%
  %#1 = minuend
  %#2 = amount of subtractions since last switching subtrahend to minuend
  %#3 = subtrahend
  %#4 = value of minuend at last switching subtrahend to minuend
  %#5 = \\-separated list of steps
  %#6 = begin of result-phrase, holding initial numbers
  %#7 = phrase to insert at the begin
  \ifnum#3=0 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
  {%
    \expandafter\UDExchange\expandafter{%
      \romannumeral
      \ifx\relax#5\relax\expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
      {\UDstopromannumeral}{%
        \ifx\relax#7\relax\expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
        {\UDstopromannumeral}{%
          \UDstopromannumeral\text{\textit{[#6#7]}}\\[0.5ex]%
        }%
        \begin{aligned}#5\end{aligned}\\[0.5ex]%
      }%
    }{\UDstopromannumeral\[\begin{gathered}}%
    \text{#6#4.}\end{gathered}\]%
  }{%
    \ifnum#1<#3 \expandafter\UDfirstoftwo\else\expandafter\UDsecondoftwo\fi
    {%
      \EuclideanLoop{#3}{0}{#1}{#3}{#5\mathbf{#4}&=#2\cdot\mathbf{#3}+\mathbf{#1}\\}%
    }{%
      \expandafter\UDPassFirstToSecond
      \expandafter{\number\numexpr#2+1\relax}{%
        \expandafter\EuclideanLoop\expandafter{\number\numexpr#1-#3\relax}%
      }{#3}{#4}{#5}%
    }%
    {#6}{#7}%
  }%
}%



\begin{document}

\Euclidean{377}{610}

\noindent\hrulefill

\Euclidean{144}{960}

\noindent\hrulefill

\Euclidean{960}{144}

\noindent\hrulefill

\Euclidean{-1380451}{24361}

\noindent\hrulefill

\Euclidean{0}{-12}

\noindent\hrulefill

\Euclidean{-12}{0}

\noindent\hrulefill

\Euclidean{0}{0}

\noindent\hrulefill

\begin{verbatim*}
\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{%
  \Euclidean{-1380451}{24361}%
}%
\end{verbatim*}

\expandafter\expandafter\expandafter\def
\expandafter\expandafter\expandafter\test
\expandafter\expandafter\expandafter{%
  \Euclidean{-1380451}{24361}%
}%
\begingroup\ttfamily\frenchspacing\string\test: \meaning\test\endgroup

\end{document}

在此处输入图片描述 在此处输入图片描述

相关内容