C#递归算法和排列算法

一、递归算法

递归:你打开面前这扇门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开它。若干次之后,你打开面前的门后,发现只有一间屋子,没有门了。然后,你开始原路返回,每走回一间屋子,你数一次,走到入口的时候,你可以回答出你到底用这你把钥匙打开了几扇门。

循环:你打开面前这扇门,看到屋里面还有一扇门。你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门(若前面两扇门都一样,那么这扇门和前两扇门也一样;如果第二扇门比第一扇门小,那么这扇门也比第二扇门小,你继续打开这扇门,一直这样继续下去直到打开所有的门。但是,入口处的人始终等不到你回去告诉他答案。

1、定义:

在数学与计算机科学中,递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上,递归,顾名思义,其包含了两个意思:递 和 归,这正是递归思想的精华所在。

2、实例:

static void  Main(string[] args)
{
    int[] sum = new int[30];
    for (int i = 0; i < sum.Length; i++)
    {
        sum[i] = process1(i);
        Console.WriteLine(sum[i]);
    }
}
public static int process1(int a)
{
    if (a == 0 || a == 1) return 1;

    return process1(a - 1) + process1(a - 2);
}

3、阶乘算法:

public static int process2(int n)
{
    if (n == 1) return 1;

    return n * process2(n - 1); // 相同重复逻辑,缩小问题的规模
}

二、排列算法

输出任意个字母和数字的全排列

对于一个长度为n的串或者n个字符(数字、节点)组成的字符串数组,它的全排列共有A(n, n)=n!种。这个问题也是一个递归的问题。如1,2,3,全排列可得到:{123,132,213,231,312,321}。

用递归算法实现代码如下:

      public static void Permutation(string[] nums, int m, int n)
      {
         string t;
         if (m < n - 1)
         {
            Permutation(nums, m + 1, n);
            for (int i = m + 1; i < n; i++)
            {
               //可抽取Swap方法
               t = nums[m];
               nums[m] = nums[i];
               nums[i] = t;
               Permutation(nums, m + 1, n);

               //可抽取Swap方法
               t = nums[m];
               nums[m] = nums[i];
               nums[i] = t;
            }
         }
         else
         {
                #region 存放到List
                Node root = null;
                Node currentNode;
                for (int j = 0; j < nums.Length; j++)
                {
                    currentNode = new Node(nums[j]);
                    currentNode.nextNode = root;
                    root = currentNode;
                }
                NodeList.Add(root);
                #endregion


                #region  打印控制台
                for (int j = 0; j < nums.Length; j++)
                {
                    Console.Write(nums[j]);
                }
                Console.WriteLine();

                #endregion
         }
      }

调用算法:

      static void Main(string[] args)
      {
         Nums = new string[] { "a", "b", "c" };
         Permutation(Nums, 0, Nums.Length);
         Console.ReadKey();
      }

到此这篇关于C#算法之递归和排列的文章就介绍到这了。希望对大家的学习有所帮助,也希望大家多多支持脚本之家。

你可能感兴趣的