算法之我见

之前发了一篇博文“ 24点的所有组合的解法 ”，有人颇不以为然。我想说的是，发这篇文章是说明我可以用计算机求出24点的所有组合的解法。而在实际的运用中，如果要使用24点的算法有时还不见得利用查表法来得简单和快速。毕竟，要短时间内写出正确的算法并验证，也不是一件很容易的事。

24点游戏的规则：给定4个正整数（1到10），利用加减乘除运算，得出运算结果为24的运算式

例如：

网上比较常见的24点算法是动态规划算法（这个在博客园中也能搜索到）。

定义6个二元运算符：加、减、乘、除、反减、反除

然后从4个数中任选2个数，通过一种运算（6个运算中的1个）得到一个新数

问题就演化成3个数的24点

重复上面的步骤，直到剩下一个数，如果这个数是24，则之前的运算过程就是24点的解答之一。如果这个数不是24，说明之前的运算不正确，再重新计算。如果所有的数的组合和运算的组合都尝试后，仍然没有找到解答，说明这4个数没有解

算一算运算一组解需要多少种可能性

第二步，从3个数中，任选两个数，6个运算符，则一共有C（3，2）*6=3*6=18，则前两步一共有36*18=648种

第三步，6个运算符，则一共有6，最终求一组解的要搜索的可能性有648*6=3888种

上面是求一组解，要搜索的可能性，一共3888种

如果要得出所有组合的解，先要算出一共有多少种组合

则一共有210+360+45+90+10=715组

则求出所有组合的解，则一共要搜索715*3888=2779920种可能性

说白了，24点的算法就是一种穷举法

换一种思路，介绍我的24点的穷举法

上面的算法是对数和运算符进行穷举和搜索

我的算法是对运算式进行穷举

无论给什么样的是4个数，运算式总是不变的，举例来说：

N+N+N+N=24，这是一种运算式

N*N+N*N=24，这是另一种运算式

N/（N-N/N）=24，这又是另一种运算式

下面这个例子：

上面虽然是两种不同的运算式，但本质是同一种运算式（肯定同时成立或同时不成立），穷举的时候只要穷举其中一个就行了

再看下面这个例子

虽然是一个运算式，但是这个运算式是不可能成立的，也就是无解运算式，穷举的时候是不需要穷举该运算式的

下面这个表格是我整理的所有的运算式，其中有的运算式有等价运算式，有的运算式是无解运算式，按照上面的讲法，这两类运算式在穷举的时候都不需要穷举

24点运算式表

运算式等价运算式是否有解 +++ N+N+N+N=24 ++- N+N+N-N=24 ++* N+N+N*N=24 N+(N+N)*N=24 (N+N+N)*N=24 ++/ N+N+N/N=24 N+(N+N)/N=24 (N+N+N)/N=24 +-+ N+N-N+N=24 N+N+N-N=24 N+N-(N+N)=24 N+N-N-N=24 无解 +-- N+N-N-N=24 无解 N+N-(N-N)=24 N+N-N+N=24
N+N+N-N=24 +-* N+N-N*N=24 无解 N+(N-N)*N=24 (N+N-N)*N=24 +-/ N+N-N/N=24 无解 N+(N-N)/N=24 无解 (N+N-N)/N=24 无解 +*+ N+N*N+N=24 (N+N)*N+N=24 N+N*(N+N)=24 (N+N)*N+N=24 (N+N)*(N+N)=24 +*- N+N*N-N=24 (N+N)*N-N=24 N+N*(N-N)=24 N+(N-N)*N (N+N)*(N-N)=24 +** N+N*N*N=24 (N+N)*N*N=24 (N+N*N)*N=24 +*/ N+N*N/N=24 (N+N)*N/N=24 (N+N*N)/N=24 +/+ N+N/N+N=24 (N+N)/N+N=24 N+N/(N+N)=24 无解 (N+N)/(N+N)=24 无解 +/- N+N/N-N=24 无解 (N+N)/N-N=24 无解 N+N/(N-N)=24 无解 (N+N)/(N-N)=24 无解 +/* N+N/N*N=24 N+N*N/N=24 (N+N)/N*N=24 (N+N)*N/N=24 (N+N/N)*N=24 N+N/(N*N)=24 N+N/N/N=24 无解 (N+N)/(N*N)=24 (N+N)/N/N=24 无解 +// N+N/N/N=24 无解 (N+N)/N/N=24 无解 (N+N/N)/N=24 无解 N+N/(N/N)=24 N+N/N*N=24
N+N*N/N=24 (N+N)/(N/N)=24 (N+N)/N*N=24
(N+N)*N/N=24 -++ N-N+N+N=24 N+N+N-N=24 N-(N+N)+N=24 N-N-N+N=24
N+N-N-N=24 无解 N-(N+N+N)=24 N-N-N-N=24 无解 -+- N-N+N-N=24 N+N-N-N=24 无解 N-(N+N)-N=24 N-N-N-N=24 无解 N-(N+N-N)=24 N-N-N+N=24
N+N-N-N=24 无解 -+* N-N+N*N=24 N+N*N-N=24 N-(N+N)*N=24 无解 N-(N+N*N)=24 无解 (N-N+N)*N=24 (N+N-N)*N=24 (N-(N+N))*N=24 (N-N-N)*N=24 -+/ N-N+N/N=24 无解 N-(N+N)/N=24 无解 N-(N+N/N)=24 N-N-N/N=24 无解 (N-N+N)/N=24 (N+N-N)/N=24 无解 (N-(N+N))/N=24 (N-N-N)/N=24 无解 --+ N-N-N+N=24 N+N-N-N=24 无解 N-(N-N)+N=24 N-N+N+N=24
N+N+N-N=24 N-(N-N+N)=24 N-N+N-N=24
N+N-N-N=24 无解 N+N-N-N=24 N-N+N+N=24
N+N+N-N=24 N-N-(N+N)=24 N-N-N-N=24 无解 --- N-N-N-N=24 无解 N-N-(N-N)=24 N-N-N+N =24
N+N-N-N=24 无解 N-(N-N)-N=24 N-N+N-N=24
N+N-N-N=24 无解 N-(N-N-N)=24 N-N+N+N=24
N+N+N-N=24 N-(N-(N-N))=24 N-N+N-N=24
N+N-N-N=24 无解 --* N-N-N*N=24 无解 N-(N-N)*N=24 N+(N-N)*N=24 (N-N-N)*N=24 (N-(N-N))*N=24 (N-N+N)*N=24
(N+N-N)*N=24 --/ N-N-N/N=24 无解 N-(N-N)/N=24 N+(N-N)/N=24 无解 (N-N-N)/N=24 无解 (N-(N-N))/N=24 (N-N+N)/N=24
(N+N-N)/N=24 无解 -*+ N-N*N+N=24 N+N-N*N=24 无解 (N-N)*N+N=24 N+(N-N)*N=24 N-N*(N+N)=24 N-(N+N)*N=24 无解 (N-N)*(N+N)=24 (N+N)*(N-N)=24 N-(N*N+N)=24 N-N*N-N=24
N-N-N*N=24 无解 -*- N-N*N-N=24 N-N-N*N=24 无解 (N-N)*N-N=24 N-N*(N-N)=24 N+N*(N-N)=24
N+(N-N)*N=24 (N-N)*(N-N)=24 N-(N*N-N)=24 N-N*N+N=24
N+N-N*N=24 无解 -** N-N*N*N=24 无解 (N-N)*N*N=24 (N-N*N)*N=24 -*/ N-N*N/N=24 无解 (N-N)*N/N=24 (N-N*N)/N=24 无解 -/+ N-N/N+N=24 N+N-N/N=24 无解 (N-N)/N+N=24 N+(N-N)/N=24 无解 N-N/(N+N)=24 无解 (N-N)/(N+N)=24 无解 N-(N/N+N)=24 N-N/N-N=24
N-N-N/N=24 无解 -/- N-N/N-N=24 N-N-N/N=24 无解 (N-N)/N-N=24 无解 N-N/(N-N)=24 N+N/(N-N)=24 无解 (N-N)/(N-N)=24 无解 N-(N/N-N)=24 N-N/N+N=24
N+N-N/N=24 无解 -/* N-N/N*N=24 无解 (N-N)/N*N=24 (N-N)*N/N (N-N/N)*N=24 N-N/(N*N)=24 N-N/N/N=24 无解 (N-N)/(N*N)=24 (N-N)/N/N=24 无解 -// N-N/N/N=24 无解 (N-N)/N/N=24 无解 (N-N/N)/N=24 无解 N-N/(N/N)=24 N-N/N*N=24
N-N*N/N=24 无解 (N-N)/(N/N)=24 (N-N)/N*N=24
(N-N)*N/N=24 *++ N*N+N+N=24 N+N+N*N=24 N*(N+N)+N=24 N+(N+N)*N=24 N*(N+N+N)=24 (N+N+N)*N=24 *+- N*N+N-N=24 N-N+N*N=24 N*(N+N)-N=24 (N+N)*N-N=24 N*(N+N-N)=24 (N+N-N)*N=24 *+* N*N+N*N=24 N*(N+N)*N=24 (N+N)*N*N=24 (N*N+N)*N=24 (N+N*N)*N=24 N*(N+N*N)=24 (N+N*N)*N=24 *+/ N*N+N/N=24 N*(N+N)/N=24 (N+N)*N/N=24 (N*N+N)/N=24 (N+N*N)/N=24 N*(N+N/N)=24 (N+N/N)*N=24 *-+ N*N-N+N=24 N-N+N*N=24 N*(N-N)+N=24 N+(N-N)*N=24 N*(N-N+N)=24 (N+N-N)*N=24 N*N-(N+N)=24 N*N-N-N=24 N*(N-(N+N))=24 N*(N-N-N)=24
(N-N-N)*N=24 *-- N*N-N-N=24 N*(N-N)-N=24 (N-N)*N-N=24 N*(N-N-N)=24 (N-N-N)*N=24 N*N-(N-N)=24 N*N-N+N=24
N-N+N*N=24 N*(N-(N-N))=24 N*(N-N+N)=24
(N+N-N)*N=24 *-* N*N-N*N=24 N*(N-N)*N=24 (N-N)*N*N=24 (N*N-N)*N=24 N*(N-N*N)=24 (N-N*N)*N=24 *-/ N*N-N/N=24 N*(N-N)/N=24 (N-M2)*N/N=24 (N*N-N)/N=24 N*(N-N/N)=24 (N-N/N)*N=24 **+ N*N*N+N=24 N+N*N*N=24 N*N*(N+N)=24 (N+N)*N*N=24 N*(N*N+N)=24 (N+N*N)*N=24 **- N*N*N-N=24 N*N*(N-N)=24 (N-N)*N*N=24 N*(N*N-N)=24 (N*N-N)*N=24 *** N*N*N*N=24 **/ N*N*N/N=24 */+ N*N/N+N=24 N+N*N/N=24 N*N/(N+N)=24 N*(N/N+N)=24 (N+N/N)*N=24 */- N*N/N-N=24 N*N/(N-N)=24 N*(N/N-N)=24 */* N*N/N*N=24 N*N*N/N=24 N*N/(N*N)=24 N*N/N/N=24 *// N*N/N/N=24 N*N/(N/N)=24 N*N/N*N=24
N*N*N/N=24 /++ N/N+N+N=24 N+N+N/N=24 N/(N+N)+N=24 N+N/(N+N)=24 无解 N/(N+N+N)=24 无解 /+- N/N+N-N=24 N-N+N/N=24 无解 N/(N+N)-N=24 无解 N/(N+N-N)=24 无解 /+* N/N+N*N=24 N*N+N/N=24 N/(N+N)*N=24 N*N/(N+N)=24 (N/N+N)*N=24 (N+N/N)*N=24 N/(N+N*N)=24 无解 /+/ N/N+N/N=24 无解 N/(N+N)/N=24 无解 (N/N+N)/N=24 (N+N/N)/N=24 无解 N/(N+N/N)=24 无解 N/((N+N)/N)=24 N/(N+N)*N=24
N*N/(N+N)=24 /-+ N/N-N+N=24 N-N+N/N=24 无解 N/N-(N+N)=24 N/N-N-N=24 无解 N/(N-N)+N=24 N+N/(N-N)=24 无解 N/(N-N+N)=24 N/(N+N-N)=24 无解 N/(N-(N+N))=24 N/(N-N-N)=24 无解 /-- N/N-N-N=24 无解 N/N-(N-N)=24 N/N-N+N=24
N+N/N-N=24 无解 N/(N-N)-N=24 无解 N/(N-N-N)=24 无解 N/(N-(N-N))=24 N/(N-N+N)=24
N/(N+N-N)=24 无解 /-* N/N-N*N=24 无解 N/(N-N)*N=24 N*N/(N-N)=24 N/(N-N*N)=24 无解 (N/N-N)*N=24 /-/ N/N-N/N=24 无解 N/(N-N)/N=24 无解 (N/N-N)/N=24 无解 N/(N-N/N)=24 N/((N-N)/N)=24 N/(N-N)*N=24
N*N/(N-N)=24 /*+ N/N*N+N=24 N+N*N/N=24 N/N*(N+N)=24 (N+N)*N/N=24 N/(N*N+N)=24 N/(N+N*N)=24 无解 N/(N*(N+N))=24 N/N/(N+N)=24
N/(N+N)/N=24 无解 /*- N/N*N-N=24 N*N/N-N=24 N/N*(N-N)=24 N*(N-N)/N=24 N/(N*N-N)=24 无解 N/(N*(N-N))=24 N/N/(N-N)=24
N/(N-N)/N=24 无解 N/(N*N)-N=24 N/N/N-N=24 无解 /** N/N*N*N=24 N*N*N/N=24 N/(N*N)*N=24 N/N/N*N=24
N*N/N/N=24 N/(N*N*N)=24 N/N/N/N=24 无解 /*/ N/N*N/N=24 N*N/N/N=24 N/(N*N)/N=24 N/N/N/N=24 无解 N/(N*N/N)=24 N/N/N*N=24
N*N/N/N=24 //+ N/N/N+N=24 N+N/N/N 无解 N/N/(N+N)=24 无解 N/(N/N+N)=24 N/(N+N/N)=24 无解 N/(N/(N+N))=24 N/N*(N+N)=24
(N+N)*N/N=24 //- N/N/N-N=24 无解 N/N/(N-N)=24 无解 N/(N/N-N)=24 N/(N/(N-N))=24 N/N*(N-N)=24
(N-N)*N/N=24 //* N/N/N*N=24 N*N/N/N=24 N/N/(N*N)=24 N/N/N/N=24 无解 N/(N/N)*N=24 N/N*N*N=24
N*N*N/N=24 N/(N/N*N)=24 N/N*N/N=24
N*N/N/N=24 /// N/N/N/N=24 无解 N/N/(N/N)=24 N/N/N*N=24
N*N/N/N=24 N/(N/N)/N=24 N/N*N/N=24
N*N/N/N=24 N/(N/N/N)=24 N/N*N/N=24
N*N/N/N=24

算一算，要求出所有组合的解，需要穷举多少种可能

需要穷举的运算式一共有50个

之前说一共有715组，这715组每个组一共有4！=24中排列方式，24钟排列方式代入到50个运算式，则一共需要穷举

是不是远小于之前的2779920种

既然都是穷举，还不如把所有的结果都保存起来，这样穷举的可能性就只有200种不到了，秒杀所有的算法

我想说的是，有时查表计算并不是一种坏的算法。要知道很多语言中求三角函数都是利用查表来快速计算的

最后，说一句题外话，请教各位网友一个计算机的问题

我有一台电脑，WIN7系统。近阶段出现一个怪现象

在开机进入系统后，插入U盘，能正确识别使用U盘

在过了一段时间后（大约半小时后），再插入U盘，要么没有反应，要么能识别出盘符，但是不能识别U盘内的东西。

重启系统后，还是在进入系统后能识别U盘，但过了一段时间，问题照旧。

哪位网友能给出解决方案？

作者：万仓一黍

出处： http://grenet.cnblogs.com/

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

分类: 算法

前段时间准备换个工作，所以参加了几场面试，面试的中主要考察的是C#相关知识的掌握以及实际项目中的经验。项目经验没办法整理，每个人都不一样，但是考察的基础知识我们可以归纳总结，对自己是个整体总结提高的过程。

首先申明本人于2011年7月份毕业，目前工作约两年时间，面试的职位一般都是中级.Net工程师的职位。由于水平有限，文章中如果有错误或不到位的地方还请看到的大神指出，我一定改正。

好了，回到正题。类型一直是C#中最基本的问题，关于值类型和引用类型，我想每个C#程序员都知道“值类型保存在栈上，引用类型保存在堆上”。但是仅仅知道到这里是完全不够的，我们需要理解C#中的类型，了解为什么要有值类型和引用类型以及他们的特征。

一、值类型和引用类型的概念

值类型的实例是在线程栈上分配的（不能免俗的提起这句话），值类型的变量并没有一个指向实例的指针，而是变量中已经包含了实例本身的字段。

相应的引用类型的实例时在托管堆中分配的，返回的是一个指向实例对象的内存地址。

比如我们一个值类型的变量 valType, 他包含一个int的字段a，其值为5，他在栈和堆中的示意图为：

现有一个引用类型的变量refType，他指向RefType类的一个实例，下图为示意图：

另外我们都知道基元类型中除了string类型，其他的都是值类型，但是我们大部分人都没有发现他们之间的区别。只要我们进入各种基元类型的定义中就可以发现：string类型是一个class，而其他的值类型都是struct。翻阅资料发现了微软在定义值类型和引用类型的区别：

引用类型包括类和接口，所有的以class和interface修饰的类型都是引用类型；而值类型包括结构和枚举，所有的结构和枚举都是值类型。继续查找资料发现所有的结构都是抽象类型System.ValueType，所有的枚举都是派生自System.Enum类型的，而System.Enum类型也继承自System.ValueType类。所以我们可以得出值类型都是继承自System.ValueType 的结论。

值类型还有一个重要的特征是因为结构是隐式密封的，所以我们没办法由自值类型来派生一个我们想要的类型来。例如我们无法从System.Int32（int）类派生出另外一个类型来。

二、为什么要有值类型

FCL中的绝大多数类型都是引用类型，那么为什么要有值类型呢？首先我们回顾下实例化一个引用类型的步骤：

1. 计算好在托管堆上分配的内存大小，包括该类型实例的所有字段的大小，以及在托管堆中的两个“额外成员”（《CLR via C#》中的翻译）：类型对象指针和同步块索引；

2. 在托管堆中分配指定大小的内存块；

3. 初始化对象的“类型对象指针”和“同步块索引”；

4、调用类型的构造函数，如果调用的是有参构造函数，则还要向其传入参数。注意，如果要实例化子类对象，则必须先调用父类的构造函数，一直会追溯到System.Object。这部分具体的可以参看《C#入门经典》相关章节。

如果所有的类型都是引用类型，那么我们程序的性能将显著下降。引用类型在性能方面还有一个重大的问题是垃圾回收。当没有变量指向某个对象时，那么该对象就会成为垃圾，就会成为GC回收的对象，而GC是相当耗费资源的。而使用值类型是不需要垃圾回收的，对象超过了其作用域就会自动销毁。

上面这段解释了为什么我们需要值类型，讲解了值类型在性能上的又是，那么我们为何还需要引用类型呢？

我们都知道值类型的传值是要复制整个对象的，而引用类型仅仅是复制指向实例对象的指针。而且值类型不能被继承，所以值类型适合一些比较轻量和简单的类型，否则同样会出现性能问题。

那么我们应该什么时候使用值类型呢：

必须满足以下所有条件，否则不要定义成值类型
第一，类型具有基元类型的行为。类型简单，其中没有成员会修改类型的任何实例字段。

第二，类型不需要从其他任何类型继承。

第三，类型不会派生出其他任何类型。

除了满足以上全部条件，还必须满足以下条件中的一个。
第一，类型的实例较小（约是16字节或者更小）。

第二，类型实例较大，但不作为方法的实参传递，也不通过方法返回。（这样即使很大但是不需实参传递，不会进行复制的操作）

        到这里我们基本上把值类型和引用类型的一些基本知识了解完了，那么这部分面试官喜欢问什么问题呢？

             值类型和引用类型的区别

                1. 值类型分配在内存栈上，引用类型分配在托管堆上。当一个值类型的变量赋给另一个值类型的变量时，会执行一次逐字段的复制，而一个引用类型的变量赋给另一个引用类型的变量时，仅仅会复制对象的内存地址。

                2. 基于上一条，多个引用类型的变量可以同时指向同一个对象，对其中的任何一个变量执行操作都会影响到另一个变量引用的对象。而每个值类型的变量都已经包含了自己的对象，所以对值类型对象的操作不会影响到另一个值类型变量。

                3. 值类型包括结构和枚举，他们均间接或直接派生自System.ValueType类；引用类型包括类和接口，他们都派生自System.Object类（这一句是废话，所有的类型都派生自System.Object类，可说可不说）。

                4. 值类型都是隐式密封的，不能将一个值类型作为基类来定义一个新的值类型或者引用类型，也因此值类型中不能包括虚方法（不能被继承，虚方法给谁重写呢）。

                5、默认情况下，创建一个引用类型的变量时，他会被初始化为null；而创建一个值类型时，他的所有成员都会被初始化为0.

                6. 值类型的变量一旦超过了其作用域，为他分配的内存就会被立即释放；而引用类型则会在托管堆里待一段时间，直到垃圾回收器将其回收。

                7. 由于System.ValueType类重写了Equals方法，所以两个值类型的Equals方法会在两个对象的字段完全匹配的情况下返回true；而引用类型的Equals则会在两个变量引用同一个对象的情况下才返回true。（这一条不重要，不说也无所谓，但是如果被问到自己要有所了解）。

             数组是值类型还是引用类型？

                我第一次遇到的这个问题的时候并没有特别注意，但是心想他既然问这样的问题，应该是引用类型，所以坚定的回答”引用类型“，让面试官看不出来我是猜的。所以童鞋们以后如果遇到类似的问题，即使是猜的也要理直气壮，否则即使你答对了，面试官也知道你是猜的，在这个问题上还是会被扣分的。

                数组类型的确是引用类型，可能有部分童鞋不承认，那我们简单的写一个验证方法：
 　　　　　　　#region  数组的类型
             int [] intArray = {  1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ,  8 ,  9   };
              int [] copyArray =  intArray;
            intArray[  0 ] =  9  ;
            Console.WriteLine(copyArray[  0  ]);
              #endregion 
输出为：9.

            结构和类的区别

                实际上就是值类型和引用类型的区别，对照着第一题回答就行了。

        到这里，值类型和引用类型还有一个特别重要的点没有提到，那就是装箱和拆箱。实际上是一个很简答的问题，但是如果你不了解，在面试时会很难回答。并且在日常的工作中很有可能经常掉入装箱的陷阱，对程序的性能有较大的影响。所以我打算下一篇就将装箱和拆箱。

        好了，第一篇写完了，希望大家给给建议，我希望和大家共同努力成长。



作者： Kevin
出处： http://zhangkai2237.cnblogs.com/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
如果您觉得这片文章对你有帮助，请点击“推荐”让更多的人看到

分类: asp.net

作者： Leo_wl
　　　　
出处： http://www.cnblogs.com/Leo_wl/
　　　　
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息

查看更多关于算法之我见的详细内容...

声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did46587

更新时间：2022-09-24 阅读：36次