基础算法思想（一）

递推算法

使用“步步为营”的方法 不断利用已有的信息推导出新的东西

分为

顺推法：从已知的条件出发 逐步推算出要解决问题的方法。例如：斐波拉契数列（ 斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233......  这个数列从第2项开始，每一项都等于前两项之和。）

逆推法：从已知的结果出发 用迭代表达式逐步推算出问题开始的条件。

顺推法的实际例子：

一开始有一只1月大的兔子 每1个月长大一次 到第3月长为大兔并生一只1月大的小兔 以此类推 算出兔子的总数

程序实现斐波那契数列：

static void Main(string[] args)
        {
            Console.WriteLine("请输入一个序号 最大为20：");
            int range = 20;
            int i = int.Parse(Console.ReadLine());

            int[] array = new int[20];
            array[0] = 1;
            array[1] = 1;

            if (i == 1)
            {
                Console.WriteLine("1");
            }
            else if(i == 2)
            {
                Console.WriteLine("1");
                Console.WriteLine("1");
            }
            else if(i >= 3 && i <= 20)
            {
                Console.WriteLine("1");
                Console.WriteLine("1");
                for (int j = 3; j <= i; j++)
                {
                    array[j - 1] = array[j - 2] + array[j - 3];
                    Console.WriteLine(array[j - 1]);
                }
            }
            else
            {
                Console.WriteLine("输入的数字超过范围");
            }
            Console.ReadKey();
        }

结果显示：

逆推法的实际例子：

程序实现求出每个月的月末存款：

int fetch = 1000;
            float rate = 0.0171f;
            double[] corpus = new double[49];

            corpus[48] = (double) fetch;
            Console.WriteLine("第48月末本利合计:"+corpus[48]);
            for (int i = 47; i > 0; i--)
            {
                corpus[i] = (corpus[i + 1] + 1000)/(1 + rate/12);
                Console.WriteLine("第" + i + "月末本利合计:"+corpus[i]);
            }
            Console.ReadKey();

结果显示：

---

枚举算法

枚举法的本质就是从所有候选答案中去搜索正确的解，使用该算法需要满足两个条件：
（1）可预先确定候选答案的数量
（2）候选答案的范围在求解之前必须有一个确定的集合

枚举法的实际例子一： 找出满足这样要求的的数字组合

程序实现：

static void Main(string[] args)
        {
            int i1, i2, i3, i4, i5;
            long multi, result;
            for (i1 = 1; i1 <= 9; i1++)
            {
                for (i2 = 0; i2 <= 9; i2++)
                {
                    for (i3 = 0; i3 <= 9; i3++)
                    {
                        for (i4 = 0; i4 <= 9; i4++)
                        {
                            for (i5 = 0; i5 <= 9; i5++)
                            {
                                multi = i1 * 10000 + i2 * 1000 + i3 * 100 + i4 * 10 + i5;
                                result = i5 * 100000 + i5 * 10000 + i5 * 1000 + i5 * 100 + i5 * 10 + i5;
                                if (multi * i1 == result)
                                {
                                    Console.WriteLine("  " + i1 + i2 + i3 + i4 + i5);
                                    Console.WriteLine("×    " + i1);
                                    Console.WriteLine("______________");
                                    Console.WriteLine(" " + i5 + i5 + i5 + i5 + i5 + i5);
                                }
                            }
                        }
                    }
                }
            }
            Console.ReadKey();

结果显示：

---

递归算法

递归算法，就是一种直接或者间接地调用自身的算法。递归算法的具体实现过程一般通过函数或子过程来完成，在函数或子过程的内部，编写代码直接或者间接地调用自己，即可完成递归操作

递归算法实例：求阶乘

程序实现：

static void Main(string[] args)
        {
            Console.WriteLine("请输入要求阶乘的一个整数");
            int i = int.Parse(Console.ReadLine());
            Console.WriteLine("阶乘的结果为：" + Fact(i));
            Console.ReadKey();
        }

        private static int Fact(int n)
        {
            if (n <= 1)
            {
                return 1;
            }
            else
            {
                return Fact(n - 1)*n;
            }
        }

结果: