Jan 12

multirow——多行表格

Tips on Computer 0 Comments

multirow 宏包提供了\multirow 命令可以在表格中排版横跨两行以上的文本。命令的格式如下：

\multirow{nrows}[bigstructs]{width}[fixup]{text}
  • nrows：设定行数。
  • bigstructs：可选项，在使用了bigstruct 宏包时使用。
  • width：设定宽度，可以使用“*”来达到自行调整的效果。
  • fixup：可选项，用来调整文本的垂直位置。
  • text：文本。

这里有一个例子： 

\begin{tabular}{|l|l|l|l|}
\hline \multirow{4}{2cm}{This is a demo table} & C2a &
\multirow{4}[30]{2cm}[-30pt]{This is another one} & C4a\\
& C2b & & C4b\\
& C2c & & C4c\\
& C2d & & C4d\\
\hline 
\end{tabular}

可以参考说明文档来进一步了解这个宏包。

Jan 12

阶乘的最后一位非零位

Art of Science 4 Comments

阶乘的最后一位非零位就是n!的数值中从右到左第一个非零的数字。比如，7!=5040，那么7!的最后一位非零位就是4。一个粗略的想法是每10个数字的末尾数相乘是一个定植，那么n个连续的自然数也可以类似地转化，接着就可以求出。这个想法无疑是错误的，因为注意到2*5=10，而12*15=180，两个结果的末位非零数并不相等，所以末尾数相乘不是10个数字为一个循环。

如果要求n!末尾0的个数，就是一个非常简单的问题。因为10=2*5，我们只要求出2和5在n!的标准分解式中出现了多少次，就可以求出末尾0的个数。而又由于2出现的次数一定比5多，所以，只需要求出5出现的次数。例如，n=2005，那么5出现的次数就是401+80+16+3=500个，也就是2005!的末尾有500个0。

现在我们对n!的情况有了一个大概的认识。简单点来说，n!=2a5bc，这里c是所有不包含2和5的因数的乘积。显然，最后一位非零位取决于2a-bc的最后一位。我们只要想办法求出c，n!的非零位就很容易了。注意到如果一个数字的末位如果是3,5,7,9，那么一定是c的组成部分。但是这些数字还不够，因为当2和5被提取之后，又产生了新的末位为3,5,7,9的数字，所以我们要逐次的提取2和5这两个因数，然后算出每种情况下末位为3,5,7,9的数字的数量。

回忆求2这个因数的办法，就是逐次的除以2来缩小规模。例如，当n=2005时，只含有一个因数2的数一共有1002个，含有两个因数2的数字一共有501个，……。也就是一种递归的思想，不过这里是尾递归，可以消除。下面关于如何求出末位为3,5,7,9的数字的方法就不再赘述了，直接给出代码，相信还是能够理解的。

//co2,co3,co5,co7,co9分别表示了2,3,5,7,9的个数。
static int co2,co3,co5,co7,co9;

void calc(int n) {
  if (n<=1) return;
  for (int i = n; i>0; i /= 5) {
    int p = i/10,q = i%10;
    co3 = p+(int)(q>=3);
    co5 = p+(int)(q>=5);
    co7 = p+(int)(q>=7);
    co9 = p+(int)(q>=9);
  }
  co2 += n/2;
  calc(n/2);
}

至此，问题转化为了2,3,5,7,9之间幂的关系，注意到32n=9n，而$3^n\equiv 7^{3n}\pmod{10}$，所以又可以转化为3的幂，下面的过程就简单多了。

其实求n!的最后一位非零位还有其它的方法，但其实也不外乎利用递归的思想提取因数，来达到化大为小的目的。有兴趣的可以去Google一下，可以找到很多资料。

Jan 11

解一元三次方程

Art of Science 0 Comments

三次方程就是形如ax3+bx2+cx+d=0的一类方程。如果a,b,c,d都是实数，那么我们确定至少有一个实数根。要确定根的实数或者复数的具体情况，要计算下列的判别式：

$\Delta = 18abcd -4b^3d + b^2c^2 - 4ac^3 - 27a^2d^2$

考虑$\Delta$的正负情况：

  • $\Delta<0$，那么只有一个实数解，另外两个解是复数解。
  • $\Delta=0$，存在重根，但是所有解都是实数。
  • $\Delta>0$，存在三个实数解。

另外，判别重根的问题可以参见我的另外一篇文章。

下面只是对三次方程的求解做一些简单的介绍。由于直接的求根公式可以从各种途径找到，在此不再重复。对于可以找到一个解的情况，我们可以因式分解来得到一个二次方程，而后解出其余两个解。

三次方程最早的解法是由波斯的数学家欧玛尔·海亚姆提出的，他采用了一种圆锥截面与圆相交的方法，至于具体情况我不是很清楚。南宋的秦九韶也对这个问题提出了自己的看法，提出了“正负开方术”，原则是“商常为正，实常为负，从常为正，益常为负”，并且可以扩充到任何高次方程中去。其实我们可以发现，秦九韶对高次方程非常有兴趣，他为了展示自己解方程的技巧，曾经构造出一个十次方程来，并命名为“开连枝某乘方”（“开玲珑某乘方”）。

后来到了16世纪，费罗找到了形如x2+mx=n方程的解法。其实如果允许复数存在，任何三次方程都是可以被化归为这个形式的。塔塔利亚很快也找到了一个方法，并且告诉了卡尔丹诺。卡尔丹诺以自己的名义发表了这个做法，据说塔塔利亚非常生气，并与之绝交。但是由于塔塔利亚的方法里面有时候需要对负数进行开方，所以也推动了复数理论的诞生。拉斐罗·邦别利很快就注意到了这些，并因此被人们认为是复数的发现者。

三次方程的求根公式一般而言有两种：一种是纯代数解，一种使用三角函数来表示。

我们先来看看卡尔丹诺的方法。首先我们可以很快将方程化为x3+bx2+cx+d=0的形式，只需要令$x=z-\frac{b}{3}$，就可以消去二次项，从而得到z3+pz+q=0。我们令z=u+v，得到(u+v)3+p(u+v)+q=0，因式分解得到(u3+v3+q)+(u+v)(3uv+p)=0，由于u,v的值是不确定的，所以我们可以再加上一个条件3uv+p=0，这样我们得到u3+v3+q=0。至此，我们可以解出u和v，可以接下来得到三次方程的解。需要注意的是，在复数域中，求解u,v的时候要考虑三种情况。

我们也可以通过归纳法来求解方程。我们观察得到三次方程解得形式一定是$x=\sqrt[3]{A}+\sqrt[3]{B}$。那么我们得到$x^3=(A+B)+3\sqrt[3]{AB}x$。移项化简得到x3+px+q=0的形式，这里$A+B=-q,AB=-\frac{p^3}{27}$ 。所以可以化归为二次方程两个根的韦达定理。从而进一步就可以求出用p,q表示的x的解。这里A,B只是起到了一个中间变量的作用。

三次方程解的形式还是有很多的。对于x3+px+q=0形式的方程，我们还有$x=2\sqrt{-\frac{p}{3}}\sin\theta$形式的解，其中$\theta$满足$\sqrt{\frac{p^3}{27}} \left( e^{3i\theta}-e^{-3i\theta} \right)+q=0$。但其实这也只是将变量x用$\theta$代换的结果。

还有一些结论性的结果可以在Wikipedia上面找到，我想要说的大概就到这里了。

Jan 11

xeCJK的字体配置

Tips on Computer 0 Comments

使用Adobe和TeX Gyre字体。 

% Default OpenType Font Configuration for xeCJK

\defaultfontfeatures{Mapping=tex-text}

\def\cjkrm{Adobe Song Std}
\def\cjksf{Adobe Kaiti Std}
\def\cjktt{Adobe Fangsong Std}

\def\cjkbd{Adobe Heiti Std}
\def\cjkit{Adobe Kaiti Std}

\setCJKfamilyfont{rm}[BoldFont=\cjkbd,ItalicFont=\cjkit]{\cjkrm}
\setCJKfamilyfont{sf}[BoldFont=\cjkbd,ItalicFont=\cjkit]{\cjksf}
\setCJKfamilyfont{tt}[BoldFont=\cjkbd,ItalicFont=\cjkit]{\cjktt}

\setCJKmainfont[BoldFont=\cjkbd,ItalicFont=\cjkit]{\cjkrm}
\setCJKsansfont[BoldFont=\cjkbd,ItalicFont=\cjkit]{\cjksf}
\setCJKmonofont[BoldFont=\cjkbd,ItalicFont=\cjkit]{\cjktt}

\setmainfont{TeX Gyre Pagella}
\setsansfont{TeX Gyre Adventor}
\setmonofont{TeX Gyre Cursor}
% \setmainfont{Arno Pro}
% \setsansfont{Myriad Pro}
% \setmonofont{Courier Std}
Jan 11

判断方程是否有重根

Art of Science 0 Comments

题目来源于SWERC2008 Wizards。

我们显然可以把方程化为根的形式：P=(x-x1)...(x-xn)=0。由于每一个可能出现的根并不能分开表示，所以这个形式对于问题的求解并没有什么帮助。我们要想办法将方程的根放到一个能够把各个根分离考虑的式子里。

回忆多项式的求导，我们发现，P的导数恰好满足的这个性质。P'=(x-x1)'...(x-xn)+...+(x-x1)...(x-xn)'。这样我们发现，如果方程P=0存在一个重根，那么这个重根必然是方程P'=0的一个根。因为n个乘积的和中，每一个乘积里各因数至少有一个是0，而原来不是重根的解只会出现n-1个0，只有在有重根的情况下，才能在该项被求导时使得它仍然为0。所以，我们得到，如果方程P=0存在重根，那么一定是(P,P')=0的一个根，这里(P,P')表示两个多项式的最大公约式。

因此，只需要判断(P,P')是否为一个常数（注意这个常数不会为0）。如果是一个常数，那么两个多项式没有共同的解，也即不存在重根；否则就是存在。

原题目和相关的程序可以在SWERC2008 - Results找到。值得一提的是，如果想要求出任意多项式的解，可以用Bairstow's Method来做，可以在Bairstow's method阅读详细情况。