博文

数独的基本玩法和解题模式(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。它的主要过程就是,考虑一个区域(行,列和宫),借助其它位置的数字排除这个区域内尽可能多的位置,从而最后确定只可能填的位置。 如果为每个格子......

阅读全文(34310) | 评论:7 | 复制链接

数独程序(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......

阅读全文(6693) | 评论:1 | 复制链接

计算机产生的随机数[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()算是比较经典的产生了。计算机产生之后,一开始只是将随机数表搬计算机的存储器,......

阅读全文(8259) | 评论:2 | 复制链接

遗传算法小记(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就要从交叉的方法等改进。......

阅读全文(6665) | 评论:1 | 复制链接

去掉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;
}
哇,这么一来想想就觉得复杂,字符串,先要找到字符串,字符串里的不算,字符串里还有转义符。。。 用状态机做会不会很方便,输入集中比较特殊的就这几个:/,*,",\,关键是在它的构造,在本子上画个表,纵向是表示状态,横向表示......

阅读全文(10202) | 评论:12 | 复制链接

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;......

阅读全文(4020) | 评论:0 | 复制链接

[笔记].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>...。......

阅读全文(3901) | 评论:0 | 复制链接

我写的多维数组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......

阅读全文(4141) | 评论:0 | 复制链接

我写的多维数组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......

阅读全文(3875) | 评论:1 | 复制链接

[笔记]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......

阅读全文(6910) | 评论:3 | 复制链接