发表更新逻辑思维4 分钟读完 (大约593个字)

斗地主所有牌型组合个数统计

序

最近业余时间在研究排列组合的相关问题,话题涉及到了在不考虑花色的情况下？54张牌按照斗地主的方式以20，17，17的方式分给3个人有多少中可能解决方案？
我觉得这个问题有点意思，并以sql脚本的形式实现了问题的求解过程，希望大家能从这篇文章中所有收获。

问题分析

以4个3为例，分给地主1，农民2，农民3的所有组合情况如下：
4个3的组合情况
既4个3在3个玩家中的可能情况有15种。在不考虑斗地主手牌数限制的情况下,因A到K有13张牌，则A到K的所有位置的组合数有$15^{13}$种可能性。
以大王为例,分给地主1，农民2，农民3的所有组合情况如下：
大王的组合情况
在不考虑斗地主手牌数限制的情况下,大王和小王在三家的可能性有3*3=9种可能性。
所以牌型组合的理论上限是$9*15^{13}$。接近于$1.75*10^{16}$。

组合情况的一种
根据计数原理,结合上图可知：
如果37在玩家1，2，3的手牌张数分别是20，0，0的可行方法是1种。
如果8Q在玩家1，2，3的手牌张数分别是0，17，3的可行方法是35种。
如果K到大王在玩家1，2，3的手牌张数分别是0，0，14的可行方法是1种。
所以三个步骤组合起来的总可行方法是$1*35*1=35$种方法。

具体细节参考Sql server版斗地主牌型组合统计的代码,最终的出来的结果是138712181744994,即$1.3871*10^{14}$。即在不区分花色的情况下，斗地主所有的牌型组合数。

总结

记录斗地主的所有牌型这种方式来做AI是不切实际的，毕竟普通PC机是没有办法存储$1.3871*10^{14}$条数据的。

参考资料

发表更新逻辑思维8 分钟读完 (大约1140个字)

m个球放到n个箱子中几种解法

序

该文的诞生源于一个问题:斗地主有多少种牌型组合?
众所周知,斗地主共54张牌分别给三个人20,17,17张牌，因为方块3和梅花3在斗地主中无区别，转化一下问题就是13种不同的颜色（不包括黑白）的球各4个,黑球，白球各1个,放到容积分别为20,17,17的三个箱子中有多少种方法？
第一想法是想到采取排列组合的方式去解，但是多久没有做排列组合的习题，我发现3红3黄3蓝1黑1白共11个球放到容积为5,3,3的三个箱子中,不考虑顺序总共有多少种方法？这个问题我都计算困难,该文简单讲一下该问题的两种解法。

正文

方案1：全排列

方案1.1 考虑黑白球

假设11个球的颜色全不相同,则所有排列顺序是1~11的全排列是11!=39916800。
再假设1,4,7为红球,2,5,8为黄球,3,6,9为蓝球，10为黑球,11为白球。
也可以1,2,3为红球,4,5,6为黄球,7,8,9为蓝球，10为白球,11为黑球。给球编号是为了计算全排列方便。
以全排列元素中的一个链表X(全排列的取值之一) **{9,8,3,5,6,4,11,7,1,2,10}**为例,
可以分成 **{9,8,3,5,6}**和 **{4,11,7}**和 **{1,2,10}三组。
将每组数据中≤9的对3取余,结果变成了A:{0,2,0,2,0}和B:{1,1,11}和C:{1,2,10}**三组数据。
∵ 在箱子中 **{4,11,7}**和 {4,7,11}是等价的。
∴ A、B、C三组都需要排序，排序后为{0,0,0,2,2}，{1,1,11},{1,2,10}
∴{9,8,3,5,6,4,11,7,1,2,10} 表示A箱子有3个蓝球，2个黄球；B箱子有2个红球,1个白球；C箱子有1个红球,1个黄球,1个黑球。
∴链表X的表达式是0,0,0,2,2,1,1,11,1,2,10
∴将39916800链表的表达式去重就可以算出序中提到的问题的解为355个。

方案1.2 先不考虑黑白球

∵黑球的可能位置只有3种,白球的可能位置也只有3种。
即黑白球都在A箱,都在B箱,都在C箱,分别在AC箱,分别在BC箱，分别在AB箱。
所有组合情况如下
黑白球位置组合
这样就只需要计算9的全排列9!=362880次数据。
计算方式如方案1.1,再次不再赘述。
结果依旧为355。
具体计算代码请参考方案一代码

方案2：笛卡尔积

在不考虑各箱子容积的前提下；
每个球都有3个箱子可以选择，则11个球的位置有3的11次方=177147中可能性。
若箱子A,B,C编号为{1,2,3}。大小分别为{5,3,3}。
则第一个球和第二球的箱子可能组合是{1,2,3}和{1,2,3}的笛卡尔积 

1
{   {1,1},{1,2},{1,3},   {2,1},{2,2},{2,3},   {3,1},{3,2},{3,3}  }

将每个球所有的可能性做笛卡尔积之后，会得到一个177147个元素个数为11的链表L的集合S。
若链表L中有5个元素1，有3个元素2，有3个元素3。则链表L符合球进入箱子的逻辑。否则不符合球进入箱子的逻辑。
假若链表L为{1,2,3,2,3,2,1,1,1,1,3}且11个球的顺序为红,红,红,黄,黄,黄,蓝,蓝,蓝,黑,白
则箱子内的颜色情况如下:
A箱：红蓝蓝蓝黑
B箱：红黄蓝
C箱：红黄白
所以链表L的表示式为 A-红蓝蓝蓝黑 B-红黄蓝 C-红黄白
将所有符合进箱逻辑的链表的表达式算出来去重,算出来结果依旧为355。
具体计算代码请参考方案二代码

注意：相同颜色的球的顺序应该连在一起，否则箱子内的球需要再做一次排序去重。

总结

该文是对排列组合知识的一个补充。如果有更好的解决m个不同颜色的球放到n个箱子中的更好的解法，欢迎留言或者直接联系我。
如果能有算出斗地主有多少种牌型组合的方法，则更希望能联系我。
方案2在箱子不够多,球不够多的情况下,的确是不错的一个计算方案。

参考资料

发表更新逻辑思维13 分钟读完 (大约1993个字)

欢乐斗地主出牌方式统计

序

在集合S取出n个元素其和为K个数统计这篇文章中提到了笛卡尔积的这种解法，但是以笛卡尔积的方式求解的时候，我中午点击运行，我晚上回来的时候才输出了168条牌型组合，然后一直没有响应，后来粗略估算了一下，需要在1.44E+18条左右数据中进行筛选，而选出总手牌数为20条相当于大海捞针，所以需要重新对问题进行思考。
先将问题明确定义——“在N张手牌中，可能的出牌方式有多少种？”

牌型分析

以地主20张手牌为例,20张手牌可能1个炸弹也没有，最多有5个炸弹。所以20张手牌,炸弹的取值范围的取值范围是[0,5];
而3张相同的牌带1张单牌也是四张牌,所以20张手牌，出三张相同的牌带一张单牌的次数也是[0,5];
如果手牌中存在66667777这样的四张牌,6667和7776这种打法和一个6炸和7炸是两种打牌的方式。
同样就算是以6,6,6,6,7,7,7,7这样的8张单牌一次打出去，欺负下家或上家手里只有3,4,5了也不是不可以。
所以66667777这样8张牌在不考虑输赢的情况下也是有很多种打法的。而巧的是，我们讨论的是不考虑输赢的情况。

20张手牌有几种打出去的方式呢？

最多以20次单牌的形式打出去。
最多以10次对子的形式打出去。
最多以3次三连对的形式打出去。
依次类推，有了以下的表格：

可能的牌型组合

具体实现

请下载C#版源代码,放到对应的控制台去执行即可。
这里列举几个示例结果：
手牌数为1

1
2
3
手牌数为1时,可能的打法情况为:
1:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌
所有牌型列举完成

手牌数为2

1
2
3
4
5
手牌数为2时,可能的打法情况为:
1:  牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
2:  牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌
3:  牌型为：单张,每次消耗1,出了2次,共消耗掉2张牌
所有牌型列举完成

手牌数为3

1
2
3
4
5
6
手牌数为3时,可能的打法情况为:
1:  牌型为：3张牌,每次消耗3,出了1次,共消耗掉3张牌
2:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
3:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌
4:  牌型为：单张,每次消耗1,出了3次,共消耗掉3张牌
所有牌型列举完成

手牌数为4

1
2
3
4
5
6
7
8
9
10
手牌数为4时,可能的打法情况为:
1:  牌型为：炸弹,每次消耗4,出了1次,共消耗掉4张牌
2:  牌型为：3张牌带1张,每次消耗4,出了1次,共消耗掉4张牌
3:  牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌    牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
4:  牌型为：对子,每次消耗2,出了2次,共消耗掉4张牌
5:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：3张牌,每次消耗3,出了1次,共消耗掉3张牌
6:  牌型为：单张,每次消耗1,出了2次,共消耗掉2张牌    牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
7:  牌型为：单张,每次消耗1,出了2次,共消耗掉2张牌    牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌
8:  牌型为：单张,每次消耗1,出了4次,共消耗掉4张牌
所有牌型列举完成

根据以上结果中的示例2和示例5可知，就算是7778也可以以777和8分两次打出去。
手牌数为5 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
手牌数为5时,可能的打法情况为:
1:  牌型为：5张牌的顺子,每次消耗5,出了1次,共消耗掉5张牌
2:  牌型为：3张牌带1对,每次消耗5,出了1次,共消耗掉5张牌
3:  牌型为：3张牌,每次消耗3,出了1次,共消耗掉3张牌    牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
4:  牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌    牌型为：3张牌,每次消耗3,出了1次,共消耗掉3张牌
5:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：炸弹,每次消耗4,出了1次,共消耗掉4张牌
6:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：3张牌带1张,每次消耗4,出了1次,共消耗掉4张牌
7:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌    牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
8:  牌型为：单张,每次消耗1,出了1次,共消耗掉1张牌    牌型为：对子,每次消耗2,出了2次,共消耗掉4张牌
9:  牌型为：单张,每次消耗1,出了2次,共消耗掉2张牌    牌型为：3张牌,每次消耗3,出了1次,共消耗掉3张牌
10:  牌型为：单张,每次消耗1,出了3次,共消耗掉3张牌    牌型为：王炸,每次消耗2,出了1次,共消耗掉2张牌
11:  牌型为：单张,每次消耗1,出了3次,共消耗掉3张牌    牌型为：对子,每次消耗2,出了1次,共消耗掉2张牌
12:  牌型为：单张,每次消耗1,出了5次,共消耗掉5张牌
所有牌型列举完成

限于篇幅，不再一一列举，根据程序列举出来的可能性如下图所示:

手牌为N时,可以的出牌方式统计

可知有17张手牌时,可以有1729种出牌方式。
可知有20张手牌时,可以有4815种出牌方式。
也许基于此，就有了赌徒说搏一搏，单车变摩托的说法。

注意,20张手牌的出牌方式并不能达到4815种，一个12张牌的顺子是12张牌,而再来两个炸弹8张牌，加起来也是20张牌。但是去掉3~A的12张牌，只能算出”2222”一个炸弹了。即”12张牌的顺子和2个炸弹”虽说符合代码的逻辑，但是并不符合现实中的牌型。换句话说，参考资料中的代码并没有考虑这种情况。

问题是还有哪些牌型组合在一起能满足总手牌数，但是不符合现实中的牌型呢？

总结

本以为在计算{1,2,3,4}中取出任意个数，与取出顺序无关时使用笛卡尔积的方式是很好的方式；结果在该问题中待处理数据竟达到了1.44E+18(1.44乘以10的18次方)条之多。
由此可知，问题并不是想当然就能够得到解决的，实践永远是检验真理的标准。
如果在每种牌型设置其对应的权重,所以在AI中的斗地主，如果能检测出手牌是10连对,或333444555666777带789JQ类型,得赶紧明牌不是么？

参考资料

发表更新逻辑思维7 分钟读完 (大约1015个字)

集合S取出n个元素其和为K个数统计

序

最近csrediscore的创作者在制作一个斗地主的机器人,他探讨性地给我出了一个问题——怎么样去统计手牌组合的可能性？
该问题算是比较复杂的,在不考虑癞子的情况下有火箭、炸弹、单牌、对牌、连对、三张牌、三带一、单顺、双顺、三顺、飞机带翅膀、四带二等等牌型。
以地主20张手牌为例：

  • 20张手牌中能打出火箭次数在[0,1]中取值。
  • 20张手牌中能打出炸弹次数在[0,5]中取值。
  • 20张手牌中能打出单牌次数在[0,20]中取值——在不考虑其他玩家的情况下,最多出20次单牌。
  • 依次类推…………
    所以问题转换为每种牌型中选取任意次数构成N张手牌的情况有多少种？

问题分解一

为了更加简单一点描述问题,我继续对问题进行了简化。
从集合{1,2,3,4}中,取出一个元素和为10的个数统计
比如集合为：{1,2,3,4}，和值为10；其中取法1,2,3,4和4,3,2,1等价。
因和值固定，且都为正数，所以每个元素的取出次数有限，可以得出结论如下图
1,2,3,4可以取出次数分析

问题分解二

1
2
3
4
5
6
从集合
{0,1,2,3,4,5,6,7,8,9,10},
{0,2,4,6,8,10},
{0,3,6,9},
{0,4,8}
中各取出一个元素组成新集合S1,S1求和为10的个数统计。

由图可知,可以取出的元素组合情况为: 11 * 6 * 4 * 3=792种。

最终只需要在这792种方案中选取出和为10的记录。
罗列792种方案的可行性的过程叫做求笛卡尔积,以下给出代码实现C#版代码实现过程。

代码实现

求笛卡尔积扩展类

1
2
3
4
5
6
7
8
9
10
11
12
13
public static class EnumerableEx
{
    /// <summary>
    /// 求集合的笛卡尔积
    /// </summary>
    public static IEnumerable<IEnumerable<T>> Cartesian<T>(this IEnumerable<IEnumerable<T>> sequences)
    {
        IEnumerable<IEnumerable<T>> tempProduct = new[] {Enumerable.Empty<T>()};
        return sequences.Aggregate(tempProduct,
            (current, sequence) =>
                (from accseq in current from item in sequence select accseq.Concat(new[] {item})));
    }
}

创建数字集合类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/// <summary>
  /// 数字集合
  /// </summary>
  public class DigitGroup
  {
      /// <summary>
      /// 元素
      /// </summary>
      public int Value;

      /// <summary>
      /// 次数
      /// </summary>
      public int Times;

      /// <summary>
      /// 和
      /// </summary>
      public int Sum;

      public DigitGroup(int value, int times)
      {
          this.Value = value;
          this.Times = times;
          this.Sum = value * times;
      }

      public override string ToString()
      {
          return string.Format("{0}个{1},和为{2}", Times, Value, Sum);
      }
  }

控制台Program类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Program
  {
      static void Main(string[] args)
      {
          List<int> numbers = new List<int> {1, 2, 3, 4};
          int Sum = 10;
          var digitGroupList = GetChooseList(numbers, Sum);

          var result = digitGroupList.Cartesian();
          result = result.Where(chooses => chooses.Sum(choose => choose.Sum) == Sum);
          PrintResult(result);

          Console.ReadKey();
      }

      private static IEnumerable<IEnumerable<DigitGroup>> GetChooseList(List<int> intList, int target)
      {
          List<List<DigitGroup>> newList = new List<List<DigitGroup>>();
          foreach (var beichushu in intList)
          {
              List<DigitGroup> temp = new List<DigitGroup>();
              var count = target / beichushu;
              for (int i = 0; i <= count; i++)
              {
                  temp.Add(new DigitGroup(beichushu, i));
              }

              newList.Add(temp);
          }

          return newList;
      }

      private static void PrintResult(IEnumerable<IEnumerable<DigitGroup>> result)
      {
          int index = 0;
          foreach (var list in result)
          {
              index += 1;
              Console.Write(index + ": ");
              foreach (var choose in list)
              {
                  if (choose.Sum != 0)
                  {
                      Console.Write(" " + choose + "   ");
                  }
              }

              Console.WriteLine();
          }
      }
  }

最终运行结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
1:  2个3,和为6    1个4,和为4
2:  1个2,和为2    2个4,和为8
3:  2个2,和为4    2个3,和为6
4:  3个2,和为6    1个4,和为4
5:  5个2,和为10
6:  1个1,和为1    3个3,和为9
7:  1个1,和为1    1个2,和为2    1个3,和为3    1个4,和为4
8:  1个1,和为1    3个2,和为6    1个3,和为3
9:  2个1,和为2    2个4,和为8
10:  2个1,和为2    1个2,和为2    2个3,和为6
11:  2个1,和为2    2个2,和为4    1个4,和为4
12:  2个1,和为2    4个2,和为8
13:  3个1,和为3    1个3,和为3    1个4,和为4
14:  3个1,和为3    2个2,和为4    1个3,和为3
15:  4个1,和为4    2个3,和为6
16:  4个1,和为4    1个2,和为2    1个4,和为4
17:  4个1,和为4    3个2,和为6
18:  5个1,和为5    1个2,和为2    1个3,和为3
19:  6个1,和为6    1个4,和为4
20:  6个1,和为6    2个2,和为4
21:  7个1,和为7    1个3,和为3
22:  8个1,和为8    1个2,和为2
23:  10个1,和为10

总结

我现在依旧不知道20张手牌,各种牌型组合的可能性有多少种,但是将问题转化成{1,2,3,4}求和为10的这种方式已经将问题做了一个很好的分解。
只需要将DigitGroup再做一下相应的替换就可以计算出可能的牌型有多少种，该问题的求解已经不在该文的范畴类，有兴趣的读者可以尝试解决一下。

参考资料

发表更新逻辑思维3 分钟读完 (大约492个字)

人狼羊菜2018年对象版本

新建Transport类,因方法和属性都有对应的详细说明，故不再赘述。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/// <summary>
/// 运输类
/// </summary>
public class Transport
{
    /// <summary>
    /// 运输对象名称
    /// </summary>
    public string ObjectName { get; set; }

    /// <summary>
    /// 运输方向描述
    /// </summary>
    public string DirectionDescription { get; set; }

    /// <summary>
    /// 校验初始状态的函数
    /// </summary>
    Func<int, bool> ValidInitStateFuc { get; set; }

    /// <summary>
    /// 校验结束状态的函数
    /// </summary>
    Func<int, bool> ValidEndStateFuc { get; set; }

    /// <summary>
    /// 单次运输函数
    /// </summary>
    Func<int, int> MoveFunc { get; set; }

    public Transport(string objectName, Func<int, bool> validInitState, Func<int, bool> validEndState,
        Func<int, int> moveFunc)
    {
        this.ObjectName = objectName;
        this.ValidInitStateFuc = validInitState;
        this.ValidEndStateFuc = validEndState;
        this.MoveFunc = moveFunc;
    }

    /// <summary>
    /// 运输方法
    /// </summary>
    /// <param name="state">初始状态</param>
    /// <returns>运输之后的状态</returns>
    public int Transfer(int state)
    {
        if (ValidInitStateFuc(state))
        {
            int result = MoveFunc(state);
            if (ValidEndStateFuc(result))
            {
                DirectionDescription = result > 8 ? "从A岸到了B岸。" : "从B岸到了A岸。";
                Console.WriteLine(ObjectName + DirectionDescription);
                return result;
            }
        }

        return state;
    }
}

调用方法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
static void Main(string[] args)
{
    Console.WriteLine("transports 开始");

    //判断是否合法状态
    bool ValidEndState(int state) => state != 3 && !(state >= 6 && state <= 9) && state != 12;

    //判断人是否和羊在一起
    bool IsPeopleWithSheep(int state) => state / 2 % 2 == 0 && state < 8 || state / 2 % 2 == 1 && state >= 8;

    //判断人是否和狼在一起
    bool IsPeopleWithWolf(int state) => !(state >= 4 && state <= 11);

    //判断人是否和菜在一起
    bool IsPeopleWithGreens(int state) => state % 2 == 0 && state < 8 || state % 2 == 1 && state >= 8;

    //运输人和青菜
    int TransferPeopleWithGreens(int i) => i ^ 9;

    //运输人和羊
    int TransferPeopleWithSheep(int i) => i ^ 10;

    //运输人和狼
    int TransPeopleWithWolf(int i) => i ^ 12;

    //运输人和狼
    int TransPeople(int i) => i ^ 8;
    Transport transport1 = new Transport("人和菜", IsPeopleWithGreens, ValidEndState, TransferPeopleWithGreens);
    Transport transport2 = new Transport("人和羊", IsPeopleWithSheep, ValidEndState, TransferPeopleWithSheep);
    Transport transport3 = new Transport("人和狼", IsPeopleWithWolf, ValidEndState, TransPeopleWithWolf);
    Transport transport4 = new Transport("人", state => true, ValidEndState, TransPeople);
    List<Transport> transports = new List<Transport> {transport1, transport2, transport3, transport4};
    int tempState = 0;
    int EndState = 15;
    while (tempState != EndState)
    {
        foreach (var actionItem in transports)
        {
            tempState = actionItem.Transfer(tempState);
        }
    }

    Console.WriteLine("transports 结束");
    Console.ReadKey();
}

运行结果如下

1
2
3
4
5
6
7
8
9
transports 开始
人和羊从A岸到了B岸。
人从B岸到了A岸。
人和菜从A岸到了B岸。
人和羊从B岸到了A岸。
人和狼从A岸到了B岸。
人从B岸到了A岸。
人和羊从A岸到了B岸。
transports 结束

参考资料

发表更新逻辑思维4 分钟读完 (大约649个字)

人狼羊菜2018年过程版本

序

分析

假设开始人狼羊菜都是在A岸，目的是将人狼羊菜运输到B岸。
人,狼,羊，菜在A岸的标识为0,在B岸的标识位为1。经过枚举可以得出16种状态中不符合的有6种。
如图所示

人狼羊菜状态图

根据以上描述的状态模式,可以将问题转化为

  • 判断运输的终止状态是否合法
  • 判断人和羊是否在一侧
  • 判断人和菜是否在一侧
  • 判断人和狼是否在一侧
  • 执行人独自过河的动作
  • 执行人和羊一起过河的动作
  • 执行人和狼一起过河的动作
  • 执行人和菜一起过河的动作

新建MoveClass类

1
2
3
4
5
6
7
/// <summary>
/// 人狼羊菜运输类
/// </summary>
public class MoveClass
{

}

依次对应的函数如下

1
2
3
4
5
6
7
8
9
/// <summary>
/// 状态合法
/// </summary>
/// <param name="state"></param>
/// <returns></returns>
public bool IsVaild(int state)
{
    return state != 3 && !(state >= 6 && state <= 9) && state != 12;
}
1
2
3
4
5
6
7
8
9
/// <summary>
/// 人和羊在一起返回真
/// </summary>
/// <param name="state"></param>
/// <returns></returns>
public bool IsPeopleWithSheep(int state)
{
    return ((state / 2) % 2 == 0 && state < 8) || ((state / 2) % 2 == 1 && state >= 8);
}
1
2
3
4
5
6
7
8
9
/// <summary>
/// 人和菜在一起返回真
/// </summary>
/// <param name="state"></param>
/// <returns></returns>
public bool IsPeopleWithGreens(int state)
{
    return state % 2 == 0 && state < 8 || state % 2 == 1 && state >= 8;
}
1
2
3
4
5
6
7
8
9
/// <summary>
/// 人和狼在一起返回真
/// </summary>
/// <param name="state"></param>
/// <returns></returns>
public bool IsPeopleWithWolf(int state)
{
    return !(state >= 4 && state <= 11);
}
1
2
3
4
5
6
7
8
9
/// <summary>
/// 只身一人过河
/// </summary>
/// <param name="state"></param>
/// <returns></returns>
public int MovePerson(int state)
{
    return state ^ 8;
}
1
2
3
4
5
6
7
8
9
/// <summary>
/// 人带羊过河
/// </summary>
/// <param name="state"></param>
/// <returns></returns>
public int MovePersonWithSheep(int state)
{
    return state ^ 10;
}
1
2
3
4
5
6
7
8
9
/// <summary>
/// 人带狼过河
/// </summary>
/// <param name="state"></param>
/// <returns></returns>
public int MovePersonWithWolf(int state)
{
    return state ^ 12;
}
1
2
3
4
5
6
7
8
9
/// <summary>
/// 人带菜过河
/// </summary>
/// <param name="state"></param>
/// <returns></returns>
public int MovePersonWithGreens(int state)
{
    return state ^ 9;
}

主要的逻辑函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public void Move()
{
int state = 0, tempState;
int EndState = 15;
while (state != EndState)
{
    tempState = MovePerson(state);
    if (IsVaild(tempState))
    {
        state = tempState;
        Console.WriteLine(state > 8 ? "人独自一人从A岸到达B岸" : "人独自一人从B岸到达A岸");
    }

    if (IsPeopleWithSheep(state))
    {
        tempState = MovePersonWithSheep(state);
        if (IsVaild(tempState))
        {
            state = tempState;
            Console.WriteLine(state > 8 ? "人带羊从A岸到达B岸" : "人带羊从B岸到达A岸");
        }
    }

    if (IsPeopleWithWolf(state))
    {
        tempState = MovePersonWithWolf(state);
        if (IsVaild(tempState))
        {
            state = tempState;
            Console.WriteLine(state > 8 ? "人带狼从A岸到达B岸" : "人带狼从B岸到达A岸");
        }
    }

    if (IsPeopleWithGreens(state))
    {
        tempState = MovePersonWithGreens(state);
        if (IsVaild(tempState))
        {
            state = tempState;
            Console.WriteLine(state > 8 ? "人带菜从A岸到达B岸" : "人带菜从B岸到达A岸");
        }
    }
}
}

执行以上逻辑函数

1
2
3
4
Console.WriteLine("MoveClass 开始");
new MoveClass().Move();
Console.WriteLine("MoveClass 结束");
Console.ReadKey();

最终运行结果如下:

1
2
3
4
5
6
7
8
9
MoveClass 开始
人带羊从A岸到达B岸
人独自一人从B岸到达A岸
人带狼从A岸到达B岸
人带羊从B岸到达A岸
人带菜从A岸到达B岸
人独自一人从B岸到达A岸
人带羊从A岸到达B岸
MoveClass 结束

参考资料

发表更新逻辑思维3 分钟读完 (大约441个字)

字典数排序

题目内容

给定一个整数 n, 返回从 1 到 n 的字典顺序。

例如，

给定 n =1 3，返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。

请尽可能的优化算法的时间复杂度和空间复杂度。 输入的数据 n 小于等于 5,000,000。

解题过程

初次接触这题,我试图用快速排序,堆排序等排序方式去解决该问题，但是程序运行之后，要么内存不足,要么复杂度达不到时间要求。
经过两天的瞎折腾，我突然茅塞顿开，找到了以下规律。

如果n<10,则1后面的数字为2，否则1后面的数组为10。

如果n<20,则2后面的数字为3，否则1后面的数组为20。

如果n<30,则3后面的数字为4，否则1后面的数组为30。

经总结如下

1
2
3
4
5
6
如果m<n
   如果 m*10<=n
   则下一位为m*10
   否则下一位为m+1;
否则
   结束。

代码示例

创建二叉树的类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/// <summary>
/// 二叉树
/// </summary>
public class TreeNode
{
    public static int Globalvalue = 1;

    public int value;
    public TreeNode leftNode;
    public TreeNode rightNode;

    /// <summary>
    /// 构造函数
    /// </summary>
    /// <param name="x"></param>
    public TreeNode(int x)
    {
        value = x;
        int leftvalue = x * 10;
        int rightvalue = x + 1;
        if (leftvalue <= Globalvalue)
        {
            leftNode = new TreeNode(leftvalue);
        }

        if (rightvalue <= Globalvalue && rightvalue % 10 != 0)
        {
            rightNode = new TreeNode(rightvalue);
        }
    }
}

二叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/// <summary>
/// 前序遍历
/// </summary>
/// <param name="tn"></param>
/// <param name="result"></param>
public void preOrder(TreeNode tn, List<int> result)
{
    result.Add(tn.value);
    if (tn.leftNode != null)
    {
        preOrder(tn.leftNode, result);
    }

    if (tn.rightNode != null)
    {
        preOrder(tn.rightNode, result);
    }
}

调用前序排序方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
/// <summary>
/// 执行排序
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public IList<int> LexicalOrder(int n)
{
    TreeNode.Globalvalue = n;
    TreeNode tn = new TreeNode(1);
    List<int> result = new List<int>();
    preOrder(tn, result);
    return result;
}

总结

该方案并不是通过测试用例耗时最短的方法，毕竟不构造TreeNode类速度会更快，但是恰好复习了一下大学时候所学的二叉树遍历的相关知识,也是挺好的。

参考资料

发表更新逻辑思维3 分钟读完 (大约435个字)

人狼羊菜2012年版本

序

这是我初接触编程时编写的Java代码,待有足够时间会重构该代码。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/**
假设开始人狼羊菜都是在A岸，目的是将人狼羊菜运输到B岸。
*/
public class Thing {
	public static void main(String[] args) {
		int i = 0, x, k = 0;
		while (i != 15) {
			k = 0;
			if (((i % 2 == 0) && i < 8) || (i % 2 == 1 && i >= 8)) {
				x = i ^ 9;
				if (x != 3 && !(x >= 6 && x <= 9) && x != 12) {
					i = x;
					k++;
					if(i>8)
					System.out.println("人带菜从A岸到达B岸");
					else
						System.out.println("人带菜从B岸到达A岸");
				}
			}
			if (((i / 2) % 2 == 0 && i < 8) || ((i / 2) % 2 == 1 && i >= 8)) {
				x = i ^ 10;
				if (x != 3 && !(x >= 6 && x <= 9) && x != 12) {
					i = x;
					k++;
					if(i>8)
						System.out.println("人带羊从A岸到达B岸");
						else
							System.out.println("人带羊从B岸到达A岸");
				}
			}
			if (!(i >= 4 && i <= 11)) {
				x = i ^ 12;
				if (x != 3 && !(x >= 6 && x <= 9) && x != 12) {
					i = x;
					k++;
					if(i>8)
						System.out.println("人带狼从A岸到达B岸");
						else
							System.out.println("人带狼从B岸到达A岸");
				}
				
			}
			x = i ^ 8;
			if (x != 3 && !(x >= 6 && x <= 9) && x != 12) {
				i = x;
				k++;
				if(i>8)
					System.out.println("人独自一人从A岸到达B岸");
					else
						System.out.println("人独自一人从B岸到达A岸");
			}
		}
	}
}

运行结果如下：

人带羊从A岸到达B岸
人独自一人从B岸到达A岸
人带菜从A岸到达B岸
人带羊从B岸到达A岸
人带狼从A岸到达B岸
人独自一人从B岸到达A岸
人带羊从A岸到达B岸

总结

该代码混乱不堪，类命名，变量命名都不符合编码规范,写出来的代码比反编译之后的更难阅读,抽时间会给出重构后的版本。

参考资料

关注我

链接

分类

最新文章

归档

标签

LeetCode1
PMP209
Svn签出1
TreeView1
centos6
hello world1
hexo6
java1
mathjax1
mysql2
panel重绘1
python4
sqlserver2
ssh1
visualstudion1
winform1
不同颜色1
不蒜子1
中年人1
乐趣1
事业环境因素1
亲情1
人狼羊菜3
人脉1
人际关系与团队技能6
代码世界1
估算成本1
估算活动持续时间6
估算活动资源4
兄弟1
关于博客1
养儿防老1
决策3
创建WBS3
制作安装包1
制定进度计划9
制定项目章程7
制定项目管理计划2
制定预算7
博客1
原创5
发展1
启动过程组9
命令行1
命题作文1
困境1
固定位置1
基本要素12
大数据1
学习2
定义活动4
定义范围3
实施定性风险分析2
实施整体变更控制2
实施采购4
实施风险应对1
实时定量风险分析2
宠物1
工作3
工具与技术19
建设团队3
引论16
手写识别2
执行整合5
执行过程组30
技能1
指南概述和目的4
指南的组成部分6
指导与管理项目工作6
排列活动顺序5
排列组合3
控制成本2
控制范围1
控制质量3
控制资源1
控制进度2
控制采购3
收尾过程组3
收集需求5
数据分析1
数据收集7
数据流向图1
数据表现2
数独3
文字切换1
斗地主1
新鲜感1
朋友圈1
权利的游戏1
欢乐斗地主2
欲望1
沟通1
流程图1
深圳1
爱情1
生活2
生活感悟1
电影观后感1
画爱心1
监控过程组23
监控项目工作4
监督沟通1
监督相关方参与1
监督风险1
知识库1
确认范围2
笛卡尔积1
简历2
管理团队1
管理沟通1
管理相关方参与2
管理质量4
管理项目知识2
红颜1
组织系统2
组织结构类型2
组织过程资产2
结束项目或阶段3
统计数量1
网站1
网站简介1
能力1
自律2
获取资源6
蓝颜1
虚荣心1
规划成本管理2
规划沟通管理2
规划相关方参与2
规划范围管理3
规划质量管理4
规划资源管理5
规划过程组92
规划进度管理2
规划采购管理9
规划风险应对5
规划风险管理1
识别相关方2
识别风险4
转载3
逆向思维1
重构3
项目成本管理12
项目整合管理26
项目沟通管理4
项目相关方管理7
项目管理1
项目管理商业文件5
项目经理的影响力范围4
项目经理的能力1
项目经理的角色10
项目范围管理17
项目质量管理11
项目资源管理20
项目运行环境5
项目进度管理28
项目采购管理16
项目风险管理16
马伯庸1
鼠标效果1

订阅更新

广告

follow.it

×