C#实现24点游戏算法实例解析
最编程
2024-01-23 20:44:58
...
本文实例讲述了C#实现的算24点游戏算法。分享给大家供大家参考。具体如下:
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.IO; namespace Calc24Points { public class Cell { public enum Type { Number, Signal } public int Number; public char Signal; public Type Typ; public Cell Right; public Cell Left; /// <summary> /// 符号优先级 /// </summary> public int Priority { get { if (Typ == Type.Signal) { switch (Signal) { case '+': return 0; case '-': return 0; case '*': return 1; case '/': return 1; default: return -1; } } return -1; } } /// <summary> /// 基本单元构造函数 /// </summary> /// <param name="t">单元类型,数值或符号</param> /// <param name="num">数值</param> /// <param name="sig">符号</param> public Cell(Type t, int num, char sig) { Right = null; Left = null; Typ = t; Number = num; Signal = sig; } public Cell() { Right = null; Left = null; Number = 0; Typ = Type.Number; } public Cell(Cell c) { Right = null; Left = null; Number = c.Number; Signal = c.Signal; Typ = c.Typ; } } public class Calc24Points { string m_exp; bool m_stop; Cell[] m_cell; int[] m_express; StringWriter m_string; public Calc24Points(int n1, int n2, int n3, int n4) { m_cell = new Cell[8]; m_cell[0] = new Cell(Cell.Type.Number, n1, '?'); m_cell[1] = new Cell(Cell.Type.Number, n2, '?'); m_cell[2] = new Cell(Cell.Type.Number, n3, '?'); m_cell[3] = new Cell(Cell.Type.Number, n4, '?'); m_cell[4] = new Cell(Cell.Type.Signal, 0, '+'); m_cell[5] = new Cell(Cell.Type.Signal, 0, '-'); m_cell[6] = new Cell(Cell.Type.Signal, 0, '*'); m_cell[7] = new Cell(Cell.Type.Signal, 0, '/'); m_stop = false; m_express = new int[7]; m_string = new StringWriter(); m_exp = null; } public override string ToString() { if (m_exp == null) { PutCell(0); m_exp = m_string.ToString(); } if (m_exp != "") return m_exp; return null; } /// <summary> /// 在第n位置放置一个单元 /// </summary> /// <param name="n"></param> void PutCell(int n) { if (n >= 7) { if (Calculate()) { m_stop = true; Formate(); } return; } int end = 8; if (n < 2) end = 4; for (int i = 0; i < end; ++i) { m_express[n] = i; if (CheckCell(n)) PutCell(n + 1); if (m_stop) break; } } /// <summary> /// 检查当前放置是否合理 /// </summary> /// <param name="n"></param> /// <returns></returns> bool CheckCell(int n) { int nums = 0, sigs = 0; for (int i = 0; i <= n; ++i) { if (m_cell[m_express[i]].Typ == Cell.Type.Number) ++nums; else ++sigs; } if (nums - sigs < 1) return false; if (m_cell[m_express[n]].Typ == Cell.Type.Number) //数值不能重复,但是符号可以重复 { for (int i = 0; i < n; ++i) if (m_express[i] == m_express[n]) return false; } if (n == 6) { if (nums != 4 || sigs != 3) return false; if (m_cell[m_express[6]].Typ != Cell.Type.Signal) return false; return true; } return true; } /// <summary> /// 计算表达式是否为24 /// </summary> /// <returns>返回值true为24,否则不为24</returns> bool Calculate() { double[] dblStack = new double[4]; int indexStack = -1; for (int i = 0; i < 7; ++i) { if (m_cell[m_express[i]].Typ == Cell.Type.Number) { ++indexStack; dblStack[indexStack] = m_cell[m_express[i]].Number; } else { switch (m_cell[m_express[i]].Signal) { case '+': dblStack[indexStack - 1] = dblStack[indexStack - 1] + dblStack[indexStack]; break; case '-': dblStack[indexStack - 1] = dblStack[indexStack - 1]-+ dblStack[indexStack]; break; case '*': dblStack[indexStack - 1] = dblStack[indexStack - 1] * dblStack[indexStack]; break; case '/': dblStack[indexStack - 1] = dblStack[indexStack - 1] / dblStack[indexStack]; break; } --indexStack; } } if (Math.Abs(dblStack[indexStack] - 24) < 0.1) return true; return false; } /// <summary> /// 后缀表达式到中缀表达式 /// </summary> void Formate() { Cell[] c = new Cell[7]; for (int i = 0; i < 7; ++i) c[i] = new Cell(m_cell[m_express[i]]); int[] cStack = new int[4]; int indexStack = -1; for (int i = 0; i < 7; ++i) { if (c[i].Typ == Cell.Type.Number) { ++indexStack; cStack[indexStack] = i; } else { c[i].Right = c[cStack[indexStack]]; --indexStack; c[i].Left = c[cStack[indexStack]]; cStack[indexStack] = i; } } ToStringFormate(c[cStack[indexStack]]); } void ToStringFormate(Cell root) { if (root.Left.Typ == Cell.Type.Number) { m_string.Write(root.Left.Number); m_string.Write(root.Signal); } else { if (root.Priority > root.Left.Priority) { m_string.Write("("); ToStringFormate(root.Left); m_string.Write(")"); } else ToStringFormate(root.Left); m_string.Write(root.Signal); } if (root.Right.Typ == Cell.Type.Number) m_string.Write(root.Right.Number); else { if (root.Priority >= root.Right.Priority) { m_string.Write("("); ToStringFormate(root.Right); m_string.Write(")"); } else ToStringFormate(root.Right); } } } }
希望本文所述对大家的C#程序设计有所帮助。
推荐阅读
-
贪婪算法在 Python、JavaScript、Java、C++ 和 C# 中的多种实现及其在硬币变化、分数骑士、活动选择和使用哈夫曼编码的最小生成树问题中的应用实例
-
C#实现24点游戏算法实例解析
-
用JavaScript实现24点游戏算法的代码实例详解
-
【Netty】「萌新入门」(七)ByteBuf 的性能优化-堆内存的分配和释放都是由 Java 虚拟机自动管理的,这意味着它们可以快速地被分配和释放,但是也会产生一些开销。 直接内存需要手动分配和释放,因为它由操作系统管理,这使得分配和释放的速度更快,但是也需要更多的系统资源。 另外,直接内存可以映射到本地文件中,这对于需要频繁读写文件的应用程序非常有用。 此外,直接内存还可以避免在使用 NIO 进行网络传输时发生数据拷贝的情况。在使用传统的 I/O 时,数据必须先从文件或网络中读取到堆内存中,然后再从堆内存中复制到直接缓冲区中,最后再通过 SocketChannel 发送到网络中。而使用直接缓冲区时,数据可以直接从文件或网络中读取到直接缓冲区中,并且可以直接从直接缓冲区中发送到网络中,避免了不必要的数据拷贝和内存分配。 通过 ByteBufAllocator.DEFAULT.directBuffer 方法来创建基于直接内存的 ByteBuf: ByteBuf directBuf = ByteBufAllocator.DEFAULT.directBuffer(16); 通过 ByteBufAllocator.DEFAULT.heapBuffer 方法来创建基于堆内存的 ByteBuf: ByteBuf heapBuf = ByteBufAllocator.DEFAULT.heapBuffer(16); 注意: 直接内存是一种特殊的内存分配方式,可以通过在堆外申请内存来避免 JVM 堆内存的限制,从而提高读写性能和降低 GC 压力。但是,直接内存的创建和销毁代价昂贵,因此需要慎重使用。 此外,由于直接内存不受 JVM 垃圾回收的管理,我们需要主动释放这部分内存,否则会造成内存泄漏。通常情况下,可以使用 ByteBuffer.clear 方法来释放直接内存中的数据,或者使用 ByteBuffer.cleaner 方法来手动释放直接内存空间。 测试代码: public static void testCreateByteBuf { ByteBuf buf = ByteBufAllocator.DEFAULT.buffer(16); System.out.println(buf.getClass); ByteBuf heapBuf = ByteBufAllocator.DEFAULT.heapBuffer(16); System.out.println(heapBuf.getClass); ByteBuf directBuf = ByteBufAllocator.DEFAULT.directBuffer(16); System.out.println(directBuf.getClass); } 运行结果: class io.netty.buffer.PooledUnsafeDirectByteBuf class io.netty.buffer.PooledUnsafeHeapByteBuf class io.netty.buffer.PooledUnsafeDirectByteBuf 池化技术 在 Netty 中,池化技术指的是通过对象池来重用已经创建的对象,从而避免了频繁地创建和销毁对象,这种技术可以提高系统的性能和可伸缩性。 通过设置 VM options,来决定池化功能是否开启: -Dio.netty.allocator.type={unpooled|pooled} 在 Netty 4.1 版本以后,非 Android 平台默认启用池化实现,Android 平台启用非池化实现; 这里我们使用非池化功能进行测试,依旧使用的是上面的测试代码 testCreateByteBuf,运行结果如下所示: class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeDirectByteBuf class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeHeapByteBuf class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeDirectByteBuf 可以看到,ByteBuf 类由 PooledUnsafeDirectByteBuf 变成了 UnpooledUnsafeDirectByteBuf; 在没有池化的情况下,每次使用都需要创建新的 ByteBuf 实例,这个操作会涉及到内存的分配和初始化,如果是直接内存则代价更为昂贵,而且频繁的内存分配也可能导致内存碎片问题,增加 GC 压力。 使用池化技术可以避免频繁内存分配带来的开销,并且重用池中的 ByteBuf 实例,减少了内存占用和内存碎片问题。另外,池化技术还可以采用类似 jemalloc 的内存分配算法,进一步提升分配效率。 在高并发环境下,池化技术的优点更加明显,因为内存的分配和释放都是比较耗时的操作,频繁的内存分配和释放会导致系统性能下降,甚至可能出现内存溢出的风险。使用池化技术可以将内存分配和释放的操作集中到预先分配的池中,从而有效地降低系统的内存开销和风险。 内存释放 当在 Netty 中使用 ByteBuf 来处理数据时,需要特别注意内存回收问题。 Netty 提供了不同类型的 ByteBuf 实现,包括堆内存(JVM 内存)实现 UnpooledHeapByteBuf 和堆外内存(直接内存)实现 UnpooledDirectByteBuf,以及池化技术实现的 PooledByteBuf 及其子类。 UnpooledHeapByteBuf:通过 Java 的垃圾回收机制来自动回收内存; UnpooledDirectByteBuf:由于 JVM 的垃圾回收机制无法管理这些内存,因此需要手动调用 release 方法来释放内存; PooledByteBuf:使用了池化机制,需要更复杂的规则来回收内存; 由于池化技术的特殊性质,释放 PooledByteBuf 对象所使用的内存并不是立即被回收的,而是被放入一个内存池中,待下次分配内存时再次使用。因此,释放 PooledByteBuf 对象的内存可能会延迟到后续的某个时间点。为了避免内存泄漏和占用过多内存,我们需要根据实际情况来设置池化技术的相关参数,以便及时回收内存; Netty 采用了引用计数法来控制 ByteBuf 对象的内存回收,在博文 「源码解析」ByteBuf 的引用计数机制 中将会通过解读源码的形式对 ByteBuf 的引用计数法进行深入理解; 每个 ByteBuf 对象被创建时,都会初始化为1,表示该对象的初始计数为1。 在使用 ByteBuf 对象过程中,如果当前 handler 已经使用完该对象,需要通过调用 release 方法将计数减1,当计数为0时,底层内存会被回收,该对象也就被销毁了。此时即使 ByteBuf 对象还在,其各个方法均无法正常使用。 但是,如果当前 handler 还需要继续使用该对象,可以通过调用 retain 方法将计数加1,这样即使其他 handler 已经调用了 release 方法,该对象的内存仍然不会被回收。这种机制可以有效地避免了内存泄漏和意外访问已经释放的内存的情况。 一般来说,应该尽可能地保证 retain 和 release 方法成对出现,以确保计数正确。