Thursday, May 9, 2013

Code drill 1: Factorial (Part 1)

The idea of this exercise is to come up with as many possible original solutions of a problem. Note that most of the solutions are intentionally terse, and therefore leave something to be desired when it comes to style. Statement: Write a program that calculates N! = N*(N-1)*...*2*1, for non-negative integer N.


Solution 1: straightforward
static int Fact(int n) {
    var ret = 1;
    for(var ii = 2; ii <= n; ++ii) {
        ret *= ii;
    }
    return ret;
}
Solution 2: oneliner
static int Fact(int n) {
    return Enumerable.Range(1,n).Aggregate(1,(x,y) => x*y);
}
Solution 3: recursion
static int Fact(int n) {
    return n == 0 ? 1 : n*Fact(n-1);
}
Solution 4: hidden multiplication
static int Fact(int n) 
{

    var sb = new StringBuilder("*");
    for(var ii = 1; ii < n; ++ii) {
        var str = sb.ToString();
        for(var jj = 0; jj < ii; ++jj) {
            sb.Append(str);
        }
    }
    return sb.Length;
}
Solution 5: query comprehension abuse #1
static public int Fact(int n) 
{
    if (n == 0)
        return 1;
       
    return from n1 in n 
           where n1 - 1
           select n1*n;
}

static public int Where(this int n, Func f) 
{
   return f(n);
}

static public int Select(this int n1, Func f)
{
    return f(Fact(n1));
}
Solution 6: brute-force
static public int Included(int n, int k) {
    if (k<=1) return 0;
    if (n < k) return 0;
    return (n / k) + Included(n/k, k);
}
static public int Fact(int n) 
{
    if(n == 0) {
        return 1;
    }

    for(int ii = n, jj; ; ++ii) {
        for(jj = 2; jj <= n; ++jj) {
            for(int kk = 0, temp = ii; kk < Included(n,jj); ++kk) {
                if(temp != jj*(temp /= jj)) {
                    jj = n+1;
                    break;
                
                }
            }
        }
        if(jj == n+1) {
            return ii;
        }
    }
}

No comments:

Post a Comment