{
int temp = b;
b = a;
a = temp;
}
for(int i=0;i<10;i++)
{
d[i] = 0;
}
value = 1;
deal(a, value, d);
value = -1;
deal(b - 1, value, d);
Console.WriteLine(d[1]);
}
static void deal(int n,int value,int[] d)
{
if (n <= 0)
return;
int one, ten;
one = n % 10;
n /= 10;
ten = n; for (int i = 0; i <= one; i++)
d[i] += value;
while(ten!=0)
{
d[ten % 10] += (one + 1) * value;
ten /= 10;
}
for (int i = 0; i < 10; i++)
d[i] += value * n;
d[0] -= value;
value *= 10;
deal(n - 1,value,d);
}
二、递归
（翻译）
让我们首先看一个有条理的叫“河内塔”的难听，它是由法国数学家卢卡斯在1883年发明的。我们有一个包含8个圆碟片的塔，最初按面积减少的方式依次堆叠在3个楔子中的一个。目标是转移整个塔到另外一个楔子上，通过每次移动一个圆碟片并且不能将面积较大的圆碟片放在较小的圆碟片上。
卢卡斯用关于Brahma塔的浪漫传说装扮他的玩具，而Brahma塔有着64个纯金的圆碟片放在3个钻石的针头上。他说一开始上帝把这些纯金的圆碟片放在第一个针头上，并且安排一些教士根据以上的规则去将它们转移到第三个针头上。教士们传说工作了日日夜夜。当他们完成这项任务时，这个塔就会崩溃并且世界也将走到终点。
这个难题有一个方案但并不是立刻就明显的，但有一点想法使我们信服它完全可行。现在问题提升为：我们能做的最好的是什么呢？那就是执行这个任务到底有多少次移动是必要和充足的。
处理这个问题的最好方式就是像这样去归纳为一点。Brahma塔有64个圆碟片，河内塔有8个圆碟片；先来考虑如果这里有n个圆碟片会发生什么。
这样归纳的一个优点是我们可以处理更多这样的问题。事实上，我们将在这本书中反复看到“先观察最小案例”的优点。转移包含一个或两个圆碟片的塔是很轻松的。而小数目的案例的实验展示了怎样去转移。
解决问题的下一步是介绍合适的记号：命名和征服。假设在卢卡斯的规则下从一个楔子将圆碟片移动到另一个楔子的最小移动次数是Tn。那么T1明显是1，T2明显是3。
我们还可以轻松的得到另一组数据，通过考虑其中最小的案例：T0=0,因为0个圆碟片的塔毕竟不需要移动。聪明的数学家并不羞愧与思考简单的案例，因为当极端的案例可以很好的理解时（甚至它们是不重要的）普遍的模式更容易意识到。
但现在来转变我们的观点来试着往大的方向思考，怎样去移动一个较大的塔呢？有3个圆碟片的塔的实验告诉我们赢得这一想法就是去移动最上面的2个圆碟片到中间的楔子上，然后移动第三个楔子，最后将中间楔子上的2个圆碟片移到第三个楔子上。这给了我们移动普遍上n个圆碟片的线索：我们可以最开始移动n-1个最小的圆碟片到另一个楔子上（需要Tn-1步），然后移动最大的圆碟片（需要1步），最好移动n-1个最小的圆碟片到最大的圆碟片上（需要另外Tn-1步）。因此我们可以转移n个圆碟片（n>0)通过最多2Tn-1+1步：
Tn<=2Tn-1+1, for n>0.
这个公式用“<=”代替“=”，因为我们仅仅证明了2Tn-1+1步是足以的；我们还没有展示这是必须的。一个聪明的人可能有能力想到一个捷径。
但是这是最好的方式吗？当然不是。在一些观点中我们必须移动最大的圆碟片。当我们这样做的时候，n-1个最小的圆碟片必须在一个单独的楔子上，并且这已经花费了至少Tn-1步去移动。如果我们不够警觉，我们可能移动最大的圆碟片不止一次。但是当上一次移动了一个圆碟片之后，我们必须移动n-1个最小的圆碟片（那必须再次处在单独的楔子上）返回到最大的圆碟片上；这同样花费了Tn-1步。因此：
Tn>=2Tn-1+1, for n>0.
这里和n=0的方案有一个不平衡，提出
T0 = 0;
Tn = 2Tn-1+1, for n>0. （1.1）
（注意到这三个公式和已知的T1=1，T2=2是一致。我们最小案例不仅仅帮我们发现了一个普遍的公式，还提供了一个简便的方法去检查我们有没有犯愚蠢的错误。尤其是以后当我们在后面的章节中遇到更复杂的问题是可以作为特殊值检查。）
像（1.1）这一套等式叫做递归。它从最早的方面给普遍值一个边界和等式。有时候我们单独引用一个普遍的等式作为递归，尽管严格意义上需要一个边界值去补充。
递归允许我们去计算对于任何n值的Tn。但是当n很大时没有人想去从递归中计算，因为这需要花费很长时间。递归仅仅提供了间接的本地的消息。而关于递归的一个解决方案或许会更好些。那就是我们想要一个好的有序的“closed form”给递归，因为这让我们计算得更快，即便是对于一个很大的n值。有一个封闭的列表我们就能知道Tn真正是什么。
所以我们到底怎样去解决一个递归呢？一个路径是去猜想正确的解决方案然后去证明它。但我们最希望的则是去根据更小的案例来猜想解决方案。所以我们的计算会很快速。
T3 =2*3 +1 =7;
T4 =2*7 +1 =15;
T5 =2*15+1 =31;
T6 =2*31+1 =63.
这明显看起来像是
Tn =2^n-1 for n >=0. （1.2）
至少对于n<=6成立。
数学归纳法就是一个普遍的方法去证明一些关于一个正整数对于所有的n>=n0是正确的陈述。首先我们证明当n有它最小值的陈述，这被称为基点。然后我们证明对于n>n0，假设它已经被证明在所有的n和n-1之间成立。所以这样一个结论只要很少数据的证明工作就可以得出极大量的结果。
递归最好地建立了数学归纳法。在我们的案例中，（1.2）轻松的从（1.1）得来：基点是不重要的，自从T0=2^0-1=0。而且结论遵循对于n>0如果我们假设（1.2）当n被替代为n-1时不变。
Tn =2Tn-1+1 =2(2^(n-1)-1)+1 =2^n-1.
因此（1.2）对于n也保持不变。我们对于Tn的探索已经成功结束了。
当然教士的任务还没有完成，他们仍然附和地移动着圆碟片，并将持续好一阵子。因为对于n=64来说，这里有2^64-1步（大约1844.6亿亿）。即便以不可能的速率，每微秒移动一步，他们也需要超过50