博文
数独的基本玩法和解题模式(2008-05-11 23:54:00)
摘要：学了很久数独，同是一个人工解独的爱好者，也是计算机解独的爱好者，另外还是一个解法研究的爱好者，写下一些感想，只希望有更多的人来玩这样一个好玩的游戏，数学游戏。
1 数独的基本玩法
第一次接触数独的人，恐怕都有一个想法，这个太难了，我要试多少次才能全部填出来？其实错了，数独绝对不是试着填填数字的小游戏。所以大多数人，都不愿意去接受它，觉得它太繁琐，太复杂。其实是一个方法问题，因为一些基本的方法还不了解。我有一个愿望，做一个数独软件，一个真的能让人一步一步了解数独学习数独的软件，让更多人为这个游戏疯狂。
问：玩这个游戏，需要什么知识？
答：1，逻辑推理；2，逻辑推理；3，还是逻辑推理。
数独的定义里除了约束条件外，还有两条规则：
1，任何数独的解都是唯一的
2，数独是完全可以依靠推理，来一步一步确定数字来完成的，而不是乏味的‘猜测’+‘试探’
所以玩数独有一个心态，就是不要‘猜’，而是相信自己的推理。推理即‘解法’，有简单的，有复杂的，这和认识和学习数独的过程有关，比如有人一上来就学‘X环’，它已经习惯这个手段是‘基本方法’，那也没办法，每个人解数独的方法都不同，主要依赖的模式也不同。以下介绍一些基本的方法，我会把有些方法进行总结和归纳，有很多是异曲同工的，我会挖出方法背后的原理，同时进行一定的扩展。
a 直观法
这个名字很奇怪，言下之意，就是直接用眼睛看，就能看出来，很直观。它的基本出发点就是：在一个区域里，如果只可能位置p上是x，那x一定就在p上。听上去很废话，对，任何数独的基本出发点都很简单，关键是，你能不能运用它在一个数独题里去解题。运用这个方法解题的关键是，在各种区域间进行交运算，比如在一行上有数字3，那它将影响它所在行上的并排三个宫内的数字，那些与这一行相交的区域就不会再出现3了，这样对区域有意识地进行交运算+排除，你就有可能把另外一个区域中很多的位置‘否定’掉，那剩下唯一的位置，自然一定是3，填上去。如图1示：
图1
G1=3 => 第1列的其它位置不能是3，和第1宫求交后A1,B1,C1不可能是3，同理由A8,B5上的3可以得到第1宫中绿色区域内没有3，那么3一定在红圈所示位置C3。它的主要过程就是，考虑一个区域（行，列和宫），借助其它位置的数字排除这个区域内尽可能多的位置，从而最后确定只可能填的位置。
如果为每个格子......
数独程序(sudoku boy 2)设计报告(2008-05-07 01:52:00)
摘要：因为一些原因，又把原来写过的数独程序重新翻出来改写。有朋友说原来的就写得不错了，还要改，我改的目的主要是想实践一下C++，尤其是设计方面。
1 面向对象吗？
不知道原来的程序算不算面向对象，一个类，比如class sudoku，有构造函数，求解函数，显示函数，等等，但是总是觉得有些乱，一但有了新的需求，整个代码就看起来像盘散沙。
经过这次的实践，我总结出来的规律是，一个类的设计，要使接口最小化，就是说接口集最小，接口数目最少，为了做到这一点，对类本身就要求，只完成功能上最小单位的部分，一个类，要么封装一些数据（容器），要么封装一个数据（元素），要么做一件事情（功能），容器类，只要设计元素的访问方法，元素类只要一个最小数据结构本身（不包括帮助函数算法的辅助数据结构），数据结构的算法留给专门的类设计（功能）。如何融合它们，数据+算法，干净的数据+干净的算法，用帮助函数，别小看写在类外面的帮助函数，有时候它们比成员函数好用得多，成员函数要么设计得好，要么就是累赘。而帮助函数可以看成是粘合剂，把用户的使用和数据＋算法很好的接合起来，同时，又容易改写。还有，容器的设计包含迭代器的设计，这可以为算法更好的抽象出来，算法面向迭代器，迭代器组织数据关系。算法的设计体现在，用仿函数做嵌入式，比如sudoku的构造函数，你可以写这样一个初始化函数：
sudoku::init(char* str){...}
实现的时候，就会问，用什么样的格式初始化呢？这样吧：
4...3.......6..8..........1....5..9..8....6...7.2........1.27..5.3....4.9........
但是有的人做的数独软件就不是这样，比如
400030000
000600800
000000001
000050090
080000600
070200000
000102700
503000040
900000000
那就不好了，你又要重载一个，这样做就相当于，为你的软件增添了‘规则’，而规则越多，越使接口复杂化。解决方法，1，可以是为专门的数据写适配器，把自己的数据定为标准；2，将这件事情，移给高层解决，用仿函数在外面完成。像下面这样：
class init_functor
{
publ......
计算机产生的随机数[1](2008-05-03 01:23:00)
摘要：写在最前面。我有一个朋友，一个女程序员，她的业余爱好是写小说，我看着她的小说里栩栩如生的人物觉得很了不起，她的脑子里可以想这么多好玩的人和事，于是我问，你为什么写小说啊，她只是简单的回答，我只是想写点很好的东西。我写不来那些，但我也希望我写的东西很好，我尽全力。
这篇由几个帖子引出，也是一直争论的焦点，std::rand()的性能怎样，随机数如何才算‘随机’，随机数如何检验。
它们是：
http://www.programfan.com/club/post-273908.html
http://www.programfan.com/club/post-274446.html
1 随机数的应用
随机数应用在哪些方面？std::rand()有什么用？统计学在生产活动中有着非常广泛的应用，它深刻地影响到了科学界和人们的生活。工厂的产品检验，人口的普查，国家还有专门的统计局，资源能源等，几乎都离不开统计学。科学界，决策论，贝叶斯决策已经形成独立的理论，随机过程，计算机模拟，计算机访真，还有密码学，都是随着现代概率论和统计学的成熟而发展起来的一大批科学。
就计算机中的随机数来说，主要用处有2个：1，用于抽样的编号。这也是最原始和最主要的用途了，在没有计算机之前，人们是用随机数表来进行抽样的，做一个足够大的表，表中的数据是通过物理过程模拟得到，比如丢色子。比如，医学上有一种随机数表，叫乱数表，它是一个n*n的矩阵，每一个格子中填一个数字0-9，数字是混乱的，医学实验时，是这样得到随机数序列的，手指随便一指，指到一个格子，然后随机选一个方向，比如向右，然后延着这个方向读几个数字，组成随机数，然后将它平移到需要的范围内，比如，你要[0，150]的随机数，你得到的数字是378，那进行平移,378-150-150=78，就是78这个数。2，用于计算机模拟。比如统计计算中形成的一大类计算方法，蒙特卡罗方法，就是一种随机计算方法。比如，模拟退火算法中，会按当前温度和邻解和当前解的目标值差计算出一个概率值p，然后依这个概率p接受或者拒绝这个邻解，如果p=0.5，那就有一半的机会接受。再比如，遗传算法中的交叉概率和变异概率，都需要用到随机数来进行模拟。
2 随机数的经典产生
std::rand()算是比较经典的产生了。计算机产生之后，一开始只是将随机数表搬计算机的存储器，......
遗传算法小记(2008-04-19 15:54:00)
摘要：我的毕设是做TSP问题，给定一个图，n个顶点，求一个哈密顿圈（不连通认为以无穷大权连通），使总的权合最小，即最小哈密顿圈。它的通俗描述是，一个旅行商(traveling salesman)从一个城市出发，经过其它城市一次且仅一次，最后回到出发城市，求一个路径，使总的行程最短。
下面这个是用GA做的，城市数n=50，种群大小gn=100，交叉概率pc=0.98，变异概率pv=0.01，结束迭代的条件是，连续10个种群的平均评价值没有增长，图中值是种群平均评价值的倒数，也就是哈密顿圈总权和。从图中看出，它很好的收敛到某个较低值。但是最优个体并不一定出现在最后的种群，为什么？这很容易理解，算法是用种群为单位计算的，但我要的结果却是一个个体，以种群为单位是为了很好的避开局部最优，但是全局最优可能会存在于较后期的某个种群，而不一定是最后一个种群，以人类的历史为比喻，最聪明的人一定是今天地球上的某个人吗？人类历史也可能停止不前，只能说总体水平在优化，但我个人认为比爱因斯坦聪明的人还没有过，但它却不在最后一个种群当中。
GA收敛得很好，但是比较慢，它竟然进化了1千多代！相比SAA对一个相同数据的计算结果图如下：
它没有优化到前者那个水平，最后只能划一条直线的原因是温度已经降得过低了，已经没有可能再优化了。它的起伏比较大，但是它的优点是收敛快，它从17000左右优化到7000左右，只迭代了100次不到，而且它只迭代一个个体，相比之下GA优化到那个水平却进化了500代左右。SAA还有改进的空间，比如温度的控制，迭代次数和温度的关系，等。而GA就要从交叉的方法等改进。......
去掉C/C++源程序中的注释(2008-04-12 16:27:00)
摘要：一道题目，输入是一个正确的C/C++源程序，输出是将所有注释去掉之后的程序。不细想觉得很简单，字符串搜索，找到//后再找一个回车，删掉，找到/*后再找一个*/，删掉，还有什么好做的，太简单了。
给个测试例子：
#include "stdafx.h"
#include <iostream>
using namespace std;
int main()
{
cout<<"line 1 // hello"<<endl; // line 1
cout<<"line 2 /* haha~ */"<<endl; // line 2
cout<<"line 3 \" /* hehe */"<<endl; /* line 3 */
/* ********\\\\\\\\\\/////////********
this is test program
this is test program
this is test program
*/
return 0;
}
这是正确的C++程序，它的输出要是：
#include "stdafx.h"
#include <iostream>
using namespace std;
int main()
{
cout<<"line 1 // hello"<<endl;
cout<<"line 2 /* haha~ */"<<endl;
cout<<"line 3 \" /* hehe */"<<endl;
return 0;
}
哇，这么一来想想就觉得复杂，字符串，先要找到字符串，字符串里的不算，字符串里还有转义符。。。
用状态机做会不会很方便，输入集中比较特殊的就这几个：/,*,",\，关键是在它的构造，在本子上画个表，纵向是表示状态，横向表示......
TMP计算素数(2008-03-21 22:45:00)
摘要：这个程序不能通信编译,说明它并不是运行在运行期,它借助编译错误信息报出'指定范围的素数',比如下面程序将会在primes<x>中x是素数的类中发生错误,看错误信息吧...
#include <cstdlib>
#include <iostream>
using namespace std;
struct true_type
{
private:
true_type(){};
};
struct false_type{};
template<bool,typename,typename B>
struct IfThenElse
{
typedef B result_type;
};
template<typename A,typename B>
struct IfThenElse<true,A,B>
{
typedef A result_type;
};
template<int d,int i = d/2 >
struct is_prime
{
typedef typename IfThenElse<d%i==0,false_type,typename is_prime<d,i-1>::result_type>::result_type result_type;
};
template<int d>
struct is_prime<d,1>
{
typedef true_type result_type;......
[笔记].template 修饰 , 双重模板(2008-03-20 22:38:00)
摘要：代码：
template<int N>
void printBitset(std::bitset<N> const& bs)
{
std::cout<<bs.template to_string<char,char_traits<char>,allocator<char> >();
}
能在DevCPP里编译通过，那个.template的意思就是告诉编译器，紧跟to_string的<并不是一个小于号，而是模板参数；需要这个 template修饰的地方（.或者->）是当前正处在一个模板中，前面的bs还未具现，它是一个模板函数里的某个参数，所以编译器是不知道它是什么东西的，如果你具现了，比如std::bitset<100> bs；那就不需要再加.template了。这和typename的第二个重要用法是一样的，用以申明模板中的参数的内嵌类型是一个类型，而不是静态变量。
双重模板是在模板参数中再用模板，比如
template <typename T,template <typename> class CONT >
stack{...};
不是所有编译器都支持这个较后增加的C++特性，当然你需要在这个类里面形式化的具现这个模板模板参数，像CONT<T>...。......
我写的多维数组auto_array[续](2008-02-19 19:00:00)
摘要：实现生成器,语法更简洁:
shape是一个全局唯一对象,用来生成多维数组的'外观',可以拿传统的C语法进行比较:
定义一个三维数组(传统):
int a[3][4][5];
一个动态三维数组:
auto_array<int,3> a(shape[3][4][5]);
形式上很相似,如果你不进行特殊的操作,完全可以拿下面的a代替上面的.所不同的是,传统的[3][4][5]是需要在编译期确定的,而下面的可以是运行期的动态变量,所在的存储空间也不同,上面占用栈空间,下面的是在堆上,由指定的分配器优化分配的.
你如果随意乱用shape,比如
auto_array<int,3> a(shape[3][4]);
将会引发编译错误,同样的,对其它维度数和shape后面的[]数不同的形式都会报错.换句话说,shape的[]会返回不同的类型,这取决于你用了几次[].
shape还可以用来传给reshape,形式是
a.reshape(shape[3][4][5]);
它不能再继续加括号指定范围了,他不能指定起始下标,如果希望不从0开始下标数组,只能使用另一种形式的reshape,这种形式值得再说明一下.
reshape(dim0,width0,start0)(dim1,width1,start1)(...)...;
为了防止空间的重复无用的分配,这里的reshape,在调用operator()的时候,并没有真的去'分配'它,只是设定了相应的维度宽度等值.而需要真正分配空间,可以几种方法:
1,调用一次operator[],哪怕没任何用.
2,在reshape语句末尾,加上一句now(),如
a.reshape(0,4)(1,5).now();
则会马上发生分配.有没有真的分配,会影响到其它和容器相关的函数,包括:
safe_bool转型,可以这样使用:
if(a)
cout<<"a is not empty!"<<endl;
a可以自动转型,但这是安全的,你不能指望这样的代码通过编译:
bool b=a;
或者其它形式的头疼地隐式转换:
a && true;
[这种安全转型是从boost里学的;)]
此外还有一些标准的迭代器函数,begin(),en......
我写的多维数组auto_array(2008-02-19 00:08:00)
摘要：练手的
[定义]
auto_array<typename T, std::size_t dim, typename Allocator = _test_allocator<T> > a;
第一个参数是元素类型,第二个是最高维度,维度标记从0到dim-1,第三个是一个分配器
[重塑数组大小]
reshape(std::size_t dim_index, std::size_t width, long start = 0);
第一个参数是指定第几维,第二个参数是指定该维的宽度,第三个参数是起始下标. 这个函数可以重叠使用,如
a.reshape(0,4);
a.reshape(1,5);
等价于
a.reshape(0,4)(1,5);
[operator[]操作]
和C语言的数组[]操作一样,没有任何不同,只是多了运行时越界检查.
测试代码(编译环境Dev C++(GCC)):
#include <iostream>
#include "auto_array.hpp"
using namespace std;
int main(int argc, char *argv[])
{
auto_array<int,1> a;
a.reshape(0,5);
try {
a[0]=1;
a[0]+=2;
a[1]=3;
a[4]=a[0]*a[1];
}
catch(runtime_error &err)
{
cout<<err.what()<<endl;
system("PA......
[笔记]enable_if的原理(2008-02-16 02:34:00)
摘要：enable_if是用来(可以用来)控制重载函数的是否可用,这一点没有直观感受,比如,我写了一个形式的重载函数,但是我需要在某种条件下取消它,这时候它就可以派上用场,当然这里是模板函数.
function的构造函数有类似下面的形式:
template<typename Functor>
BOOST_FUNCTION_FUNCTION(Functor BOOST_FUNCTION_TARGET_FIX(const &) f
#ifndef BOOST_NO_SFINAE
,typename enable_if_c<
(boost::type_traits::ice_not<
(is_integral<Functor>::value)>::value),
&n......