求職問題：數字拆解(using C#)

//題目：數字拆解
//題目是這樣的：
//3 = 2+1 = 1+1+1 所以3有三種拆法
//4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五種
//5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1 //共七種
//依此類推，請問一個指定數字NUM的拆解方法個數有多少個？

//#請計算出Num=40共多少解法,需花多少時間(須印出所有合法解法)
// num = 40, count = 37338, time = 1.188
//收到此信時, 請先回覆 email告知已成功接獲此信.

//請於三天內將撰寫好的程式碼 email 給我

//Answer:

//此code的缺點是速度慢

//C# code
using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        public static int num = 40;
        public static int solution = 0;
        static void Main(string[] args)
        {
            DateTime StartTime = DateTime.Now;
            int[] ntable = new int[num];
            int index = 0, rindex = 0;
            int nlength = num;
            for (int i = 0; i < num; i++)
            {
                ntable[i] = 1;
            }
            print(ntable, nlength);
            // top = ntable[0]
            while (nlength != 1)
            {
                while (true)
                {
                    if (index < nlength - 1)//last two element
                    {
                        ntable[index]++;
                        if (0 == index) swapr(ntable, rindex, ref nlength);
                        index++;
                        fixdec(ntable, ref nlength);
                        print(ntable, nlength);
                    }
                    else break;
                }
                rindex = rsnotone(ntable, nlength);
                rindex = found(ntable, ntable[rindex], nlength);
                if (rindex < nlength - 1)//last two element
                {
                    ntable[rindex]++;
                    swapr(ntable, rindex, ref nlength);
                    index = rindex + 1;
                    fixdec(ntable, ref nlength);
                    print(ntable, nlength);
                }
                else if (rindex > 0 && ntable[rindex - 1] < ntable[0])
                {
                    rindex = found(ntable, ntable[rindex - 1], nlength);
                    ntable[rindex]++;
                    swapr(ntable, rindex, ref nlength);
                    index = rindex + 1;
                    fixdec(ntable, ref nlength);
                    print(ntable, nlength);
                }
                else
                {
                    index = 0;
                    rindex = 0;
                }
               
               
            }
            Console.Write("num = ");
            Console.Write(num);
            Console.Write(", count = ");
            Console.Write(solution);
            DateTime StopTime = DateTime.Now;
            TimeSpan duration = StopTime - StartTime;
            Console.Write(", time = ");
            Console.WriteLine(duration);
        }
        static int found(int[] ntable, int value, int nlength)
        {
            int i;
            for (i = 0; i < nlength; i++)
            {
                if(value == ntable[i])break;
            }
            return i;
        }
        //reverse scan and return index that value not equal 1
        static int rsnotone(int[] ntable, int nlength)
        {
            int i;
            for (i = nlength - 1; i >= 0; i--)
            {
                if (ntable[i] != 1) break;
            }
            return i;
        }
        //clean and fix length of ntable
        static void swapr(int[] ntable, int ri, ref int nlength)
        {
            int remain = num;
            for (int i = 0; i <= ri; i++)
            {
                remain -= ntable[i];
            }
            for (int i = ri + 1; i <= ri + remain; i++)
            {
                ntable[i] = 1;
            }
            nlength = ri + remain + 1;
            for (int i = nlength; i < num; i++)
            {
                ntable[i] = 0;
            }
        }
        static void fixdec(int[] ntable, ref int nlength)
        {
            int index=0;
            int remain = num;
            for (int i = 0; i < num; i++)
            {
                remain = remain - ntable[i];
                if (1 == ntable[i] || 0==remain)
                {
                    index = i;
                    break;
                }
            }
            if (remain > 0)
            {
                nlength = index + remain + 1;
                for (int i = index + 1; i < nlength; i++)
                {
                    ntable[i] = 1;
                }
                for (int i = nlength; i < num; i++)
                {
                    ntable[i] = 0;
                }
            }
            else
            {
                nlength = index + 1;
            }
        }
        static void print(int[] ntable, int nlength)
        {
            bool first = true;
            solution++;
            Console.Write("=");
            for(int i = 0; i < nlength; i++)
            {
                if(first)
                {
                    Console.Write(ntable[i]);
                    first = false;
                }
                else
                {
                    Console.Write("+"+ntable[i]);
                }
            }
            Console.Write("\n");
        }
    }
}

//num = 40, count = 37338, time = 00:00:06.1562500