我最终得到的代码非常简单，如下所示：
Code:
public delegate void R(
R delg, int pow, int rdx=10, int prod=1, int msd=0);
R digitProd=
default(R)!=(digitProd=default(R))?default(R):
(delg, pow, rdx, prod, msd) => {
var x=pow>0?rdx:1;
for(var call=(pow>1?digitProd:delg); x-->0; )
if(msd>0)
call(delg, pow-1, rdx, prod*x, msd);
else
call(delg, pow-1, rdx, x, x);
};
msd is the most significant digit, it's like most significant bit in binary.
我没有选择使用迭代器模式的原因是它比方法调用需要更多时间。带有测试的完整代码放在本回答的末尾。
请注意，行
default(R)!=(digitProd=default(R))?default(R): ... 只是用于分配
digitProd，因为委托在赋值之前不能使用。实际上，我们可以将其写成：
Alternative syntax:
var digitProd=default(R);
digitProd=
(delg, pow, rdx, prod, msd) => {
var x=pow>0?rdx:1;
for(var call=(pow>1?digitProd:delg); x-->0; )
if(msd>0)
call(delg, pow-1, rdx, prod*x, msd);
else
call(delg, pow-1, rdx, x, x);
};
这种实现方式的缺点是无法从某个特定数字开始，而只能从最大位数开始。
我提供几个简单的解决方案:
Recursion
The delegate(Action) R is a recursive delegate definition which is used as tail call recursion, for both the algorithm and the delegate which receives the result of digit product.
And the other ideas below explain for why recursion.
No division
For consecutive numbers, use of the division to extract each digit is considered low efficiency, thus I chose to operate on the digits directly with recursion in a down-count way.
For example, with 3 digits of the number 123, it's one of the 3 digits numbers started from 999:
9 8 7 6 5 4 3 2 [1] 0 -- the first level of recursion
9 8 7 6 5 4 3 [2] 1 0 -- the second level of recursion
9 8 7 6 5 4 [3] 2 1 0 -- the third level of recursion
Don't cache
As we can see that this answer
How to multiply each digit in a number efficiently
suggested to use the mechanism of caching, but for the consecutive numbers, we don't, since it is the cache.
For the numbers 123, 132, 213, 231, 312, 321, the digit products are identical. Thus for a cache, we can reduce the items to store which are only the same digits with different order(permutations), and we can regard them as the same key.
However, sorting the digits also takes time. With a HashSet implemented collection of keys, we pay more storage with more items; even we've reduced the items, we still spend time on equality comparing. There does not seem to be a hash function better than use its value for equality comparing, and which is just the result we are calculating. For example, excepting 0 and 1, there're only 36 combinations in the multiplication table of two digits.
Thus, as long as the calculation is efficient enough, we can consider the algorithm itself is a virtual cache without costing a storage.
Reduce the time on calculation of numbers contain zero(s)
For the digit products of consecutive numbers, we will encounter:
1 zero per 10
10 consecutive zeros per 100
100 consecutive zeros per 1000
and so on. Note that there are still 9 zeros we will encounter with per 10 in per 100. The count of zeros can be calculated with the following code:
static int CountOfZeros(int n, int r=10) {
var powerSeries=n>0?1:0;
for(var i=0; n-->0; ++i) {
var geometricSeries=(1-Pow(r, 1+n))/(1-r);
powerSeries+=geometricSeries*Pow(r-1, 1+i);
}
return powerSeries;
}
For n is the count of digits, r is the radix. The number would be a power series which calculated from a geometric series and plus 1 for the 0.
For example, the numbers of 4 digits, the zeros we will encounter are:
(1)+(((1*9)+11)*9+111)*9 = (1)+(1*9*9*9)+(11*9*9)+(111*9) = 2620
For this implementation, we do not really skip the calculation of numbers contain zero. The reason is the result of a shallow level of recursion is reused with the recursive implementation which are what we can regard as cached. The attempting of multiplication with a single zero can be detected and avoided before it performs, and we can pass a zero to the next level of recursion directly. However, just multiply will not cause much of performance impact.
完整的代码如下：
public static partial class TestClass {
public delegate void R(
R delg, int pow, int rdx=10, int prod=1, int msd=0);
public static void TestMethod() {
var power=9;
var radix=10;
var total=Pow(radix, power);
var value=total;
var count=0;
R doNothing=
(delg, pow, rdx, prod, msd) => {
};
R countOnly=
(delg, pow, rdx, prod, msd) => {
if(prod>0)
count+=1;
};
R printProd=
(delg, pow, rdx, prod, msd) => {
value-=1;
countOnly(delg, pow, rdx, prod, msd);
Console.WriteLine("{0} = {1}", value.ToExpression(), prod);
};
R digitProd=
default(R)!=(digitProd=default(R))?default(R):
(delg, pow, rdx, prod, msd) => {
var x=pow>0?rdx:1;
for(var call=(pow>1?digitProd:delg); x-->0; )
if(msd>0)
call(delg, pow-1, rdx, prod*x, msd);
else
call(delg, pow-1, rdx, x, x);
};
Console.WriteLine("--- start --- ");
var watch=Stopwatch.StartNew();
digitProd(printProd, power);
watch.Stop();
Console.WriteLine(" total numbers: {0}", total);
Console.WriteLine(" zeros: {0}", CountOfZeros(power-1));
if(count>0)
Console.WriteLine(" non-zeros: {0}", count);
var seconds=(decimal)watch.ElapsedMilliseconds/1000;
Console.WriteLine("elapsed seconds: {0}", seconds);
Console.WriteLine("--- end --- ");
}
static int Pow(int x, int y) {
return (int)Math.Pow(x, y);
}
static int CountOfZeros(int n, int r=10) {
var powerSeries=n>0?1:0;
for(var i=0; n-->0; ++i) {
var geometricSeries=(1-Pow(r, 1+n))/(1-r);
powerSeries+=geometricSeries*Pow(r-1, 1+i);
}
return powerSeries;
}
static String ToExpression(this int value) {
return (""+value).Select(x => ""+x).Aggregate((x, y) => x+"*"+y);
}
}
在代码中，
doNothing、
countOnly和
printProd用于在获取数字乘积的结果时要执行什么操作。我们可以将它们中的任何一个传递给实现完整算法的
digitProd。例如，
digitProd(countOnly, power)只会增加
count，最终结果将与
CountOfZeros返回的结果相同。请注意保留HTML标记。
