好厉害的hash。

hba

今天想解一个游戏题，题目是这样的：
计算机出任意四个数（个位数，不含0），请你用这四个数和+,-,*,/,及()算出二十四。
比如用5,5,5,1，算出得式5*(5-1/5)=24。
搜索了一下算法，下面这位的算法好像很强。

hba

24点算法分析
很久没有研究程序了，惭愧中。。。这个夏天大致地翻了一下微软亚洲研究院出的《编程之美》，很喜欢这本书的风格，里面很多题目都很有意思。书中主要突出的是一个“巧”字，最关键的，就是从变化中寻找不变的规律。 这次说的问题其实也很简单，给四个数，写一个程序输出算24点的结果，如果没有就输出“No Answer”。但是如果用我们自己算24点的思维来写程序是不行的，因为那属于一种“凑”的方法，有碰巧和经验的成分。计算机能做的，就是通过一种固定的方式来找寻结果。如果没有一般性的所谓“固定”方式，那么只有通过遍历和穷举来解决问题。这样的方法下诞生了很多所谓的NP难问题，如果原始数据规模比较大就要花很长的时间来得到结果。
24点这个问题最直接的方法就是，列举四个数所有的排列组合，加上各种运算符以及括号，所有的情况经过处理之后可以得到一个包含所有计算结果和计算式的列表，从其中寻找24的影踪就可以了。如果不计计算结果重复的情况，最终的结果有7680种，数据量还是有点大，因此这个算法需要进一步的优化。例如，考虑到加法和乘法的交换律，如果遇到相应的情况只计算一种，对于另一种直接返回。这样的剪枝处理可以减少不少的运算。
不过我用的是书中的另一种思路，采用了划分的思想。具体的算法是：
如果A是一个数组，定义f(A)为数组中的所有数经过四则运算所能得到的结果的集合。对于A中元素个数大于1的情况，可以将A分拆成两个集合，定义运算 Fork(A,B)为f(A)和f(B)中各取一个元素的四则运算得到的所有的结果的集合。这样，如果列举出集合A所有的拆分情况，那么所有Fork结果的并集就是f(A)的结果。
对于24点的情况，因为数组A有4个数，因此将其用各种方法拆分即可得到最终的f(A)，然后查询其中是否存在元素24即可得到有解或者无解的判断。
需要说明的有几点：
1.这个问题表面上需要采用递归的算法，即如果只有一个元素那么直接返回，否则将问题转化为多个f的计算，而每个f的计算又要经过转化，层层递归，直至只有一个元素的情况。但是，不要忘了递归的方法一般都是针对回溯次数不确定的问题。例如汉诺塔问题，只有一个盘子的情况和64个盘子的情况，回溯次数截然不同，千差万别；但是对于24点，因为只有4个数，实际上分拆的可能性是固定的，就那么有限种情况。递归算法的思路是从树的根部往下遍历，而且一般不知道树的大小和规模。而对于24点问题，这棵树的大小固定，完全可以从树的叶子着手，从叶子向根步进，从而得到最终的结果。
2.分拆有一定的技巧，最合适的方法是通过位运算。比如一种分拆方法是{a1,a2},{a3,a4},那么写做1100和0011。这种方法的好处在于，比如要判断1000是不是1100的一个子集，只需要将两者做与运算，最后的结果如果还等于1100则表明确实是子集，同时分拆的另一个结果便是两者的差。这样至多只需要比较 10多次就可以列举出每个集合所有的分拆情况，比较巧妙的方法。同时，位运算的速度也很快，不会对计算的时间有较大的影响。
3.这个方法的缺点在于，最终得到的只是一个无解或者有解的判断，并没有输出表达式。
所以我对这个算法进行了一定的改进，使之能输出表达式。
首先要考虑的，也是最重要的，是这个程序的数据结构。最终的目的自然是为了达到最少的时间复杂度。由于上述方法中f函数返回的是“集合”，因此不存在重复的元素。这样的情况下，哈希表自然是首选的数据结构。
为了记录表达式，需要引入另一套数据结构。每一个计算的结果都必须和一个表达式对应。这样，当最终查询到一个计算结果为24的时候，只需查找相应的表达式就可以得到结果。
这里就产生了冲突。哈希表的特点是存放是乱序的，也就是说，如果只采用一个哈希表存放计算结果，用一个vector存放表达式，那么无法产生对应关系。
因此，有两种方案：
第一种方案比较节省存储空间，将计算结果和表达式分别存在两个vector中，由于两者都是有序的集合类，因此可以在插入数据的时候令各自的下标对应，这样就可以方便地得到对应关系。但是，这样做的后果是，在插入新数据的时候需要在vector中查找是否已经存在这个计算结果，如果已有则不必插入。 vector的查找是穷举式的，效率比较低，尤其是当vector比较大的时候将很大程度上影响计算的效率。但如果不进行查找，势必会计算很多没有意义的重复结果，这样就失去了这个算法的意义了。
第二种方案在第一种方案的基础上将计算结果多存一份哈希表数据。这样做增加了存储空间，但是在时间上的优势是显而易见的。在插入的时候，通过查找哈希表来决定是否已经存在这个结果，由于哈希表的查找效率很高，因此这一步不会对这个程序造成时间上的瓶颈。如果不存在，那么同时在哈希表和两个vector中同时插入数据即可。计算结果和表达式的对应关系依然存在，同时查找的效率也大大提高，整个程序的时间复杂度大大降低。这是典型的空间换时间的方法。
写算法我首选的语言还是c++，但是很惭愧c++的HashTable我不会用，因此用java写了一个版本，还算比较成功，能输出最终的结果。在写程序前我写了一个小程序来测试java的HashSet和ArrayList的查找效率，结果很令人惊讶。在10000次查询中，HashSet所用时间为0ms，而ArrayList则用了1300多ms，看来这个效率完全不是一个数量级上的。因此我采用了上述的第二种方案，最终的效果还不错。
曾经有人问过我5，5，5，1怎么算24点，当时想了很久都没想出来。现在用这个程序可以很轻松地算出5*(5-1/5)=24。看来这个程序可以输出一些大家想不到的结果，很强大把。类似的例子还有很多，比如3，3，7，7等等。总之呢，优化了的穷举法（我这个程序实际上还是一种变相的穷举）是一种很不错的解决问题的思路，值得采用！
过几天就开学了。也许每年的开学前才有时间去研究下这种问题，等到开学之后就基本没什么时间了。嗯，好好工作把，也愿今年能开个好题，明年好好做毕设。Good luck。

PS:昨天经同学提醒才发现有更好的解决方法。主要是因为好久没用，把java的HashMap给忘了。这个数据结构用在这里正合适，也就是说不用两个HashSet加两个ArrayList解决了，直接存在一个HashMap里面就可以。
具体的做法是：把计算结果存在map的key中，而表达式存在map的value中，问题彻底解决。map中key的查找效率是很高的，同时插入也很快；当找到一个计算结果为24的时候直接根据这个key去寻找相应的value即可得到完美的答案，同时HashMap也保证了每个计算结果只保留一个表达式，避免了重复。
我做了一下性能测试，总的来这个改进后的版本效率比以前的版本略有提高，但是最关键的是大大减少了空间的存储，因此也算是对程序进行的大优化把我想。这两天看这个帖子似乎看的人比较多哈，也愿我的想法能给大家一些启发。

[ 本帖最后由 hba 于 2010-10-20 02:46 PM 编辑 ]

hba

又搜索了一下hashmap：

HashMap遍历的两种方式第一种:
Map map = new HashMap();
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
    Map.Entry entry = (Map.Entry) iter.next();
    Object key = entry.getKey();
    Object val = entry.getValue();
}
效率高,以后一定要使用此种方式！
第二种:
Map map = new HashMap();
Iterator iter = map.keySet().iterator();
while (iter.hasNext()) {
    Object key = iter.next();
    Object val = map.get(key);
}
效率低,以后尽量少使用！

例：
HashMap的遍历有两种常用的方法，那就是使用keyset及entryset来进行遍历，但两者的遍历速度是有差别的，下面请看实例：

public class HashMapTest {
public static void main(String[] args) ...{
  HashMap hashmap = new HashMap();
  for (int i = 0; i < 1000; i ) ...{
   hashmap.put("" i, "thanks");
  }

  long bs = Calendar.getInstance().getTimeInMillis();
  Iterator iterator = hashmap.keySet().iterator();   
  while (iterator.hasNext()) ...{   
   System.out.print(hashmap.get(iterator.next()));
  }
  System.out.println();
  System.out.println(Calendar.getInstance().getTimeInMillis() - bs);
  listHashMap();
}

  public static void listHashMap() ...{
  java.util.HashMap hashmap = new java.util.HashMap();
  for (int i = 0; i < 1000; i ) ...{
   hashmap.put("" i, "thanks");
  }
  long bs = Calendar.getInstance().getTimeInMillis();   
  java.util.Iterator it = hashmap.entrySet().iterator();
  while (it.hasNext()) ...{
   java.util.Map.Entry entry = (java.util.Map.Entry) it.next();
   // entry.getKey() 返回与此项对应的键
   // entry.getValue() 返回与此项对应的值
   System.out.print(entry.getValue());
  }
  System.out.println();
  System.out.println(Calendar.getInstance().getTimeInMillis() - bs);
}
}

对于keySet其实是遍历了2次，一次是转为iterator，一次就从hashmap中取出key所对于的value。而entryset只是遍历了第一次，他把key和value都放到了entry中，所以就快了。

hba

看了几遍还是不明白。
有没有高手能用hashmap的方式给我做个顶楼题目的解题程序或雏形？

hash

兴冲冲跑进来一头雾水出去

hba

原帖由 hash 于 2010-10-20 15:28 发表
兴冲冲跑进来一头雾水出去

我始终认为hash可能是隐藏的高手，就像武侠小说里写的那些稀奇古怪的老头，总喜欢乔装打扮以弱示人。

tianm

原帖由 hash 于 2010-10-20 03:28 PM 发表
兴冲冲跑进来一头雾水出去

笑喷了！

zgbl

围观悲剧帝hash

mytoy

没看懂

ddid

Hash表，是Jason的强项。