C++博客-CodePanada

用位操作实现的n皇后问题

熊猫呵呵 — Tue, 07 Jun 2011 16:16:00 GMT

C语言是我大一时期专业课所学习的第一门语言，离现在差不多也有将近5年的时间。最近想重拾起来，买了一本Plauger大牛的<>，简单翻了一下，觉得自己如井底之蛙一样。。。以前对C的理解只是皮毛，孰不知这门极其优秀的跨平台可移植的编译语言还有如此精彩的实现。

前几天整理文档，发现了这段用C bit实现的N皇后算法，花了半天时间才把它搞明白。。大家都知道，n皇后的一般解法是回溯，要用一个二维数组表示棋盘，按逐行（列）进行解搜索，对于每个当前解都要进行判断，如成功则继续；失败则回溯。

这段用bit实现的代码极其简明。只不过它只是用了一个一维的数组，按行搜索，将列上的、对象线上的限制归一。

感兴趣的朋友可以看下：http://jsomers.com/nqueen_demo/nqueens.html 作者的方法跟下面的方法大同小异。

1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <time.h>
4
5 long int sum = 0, upperlim = 1;
6
7 void test(long  row, long  ld, long  rd)
8 {
9     //printf("%ld\t%ld\t%ld\n",row,ld,rd);
10     //printf("%ld\t",row);
11     //printf("\n%ld\n",upperlim);
12     if(row != upperlim)
13     {
14         long pos = upperlim & ~(row|ld|rd);
15         //printf("%ld\n",pos);
16         while(pos!= 0)
17         {
18           //    printf("%ld\n",pos);
19               long p = pos & -pos;
20               pos = pos - p; //取得可以放皇后的最右边的列
21               test(row + p,(ld + p)<<1, (rd + p)>>1);
22           }
23       return;
24      }
25       else
26     {
27         sum++;
28         return;
29     }
30 }
31
32 int main(int  argc, char  *argv[])
33 {
34       time_t tm;
35       int n = 16;
36       if(argc  !=   1) n = atoi(argv[1]);
37       tm = time(0);
38       if((n < 1)||(n > 32))
39       {
40         printf("只能计算1-32之间的皇后问题\n ");
41         exit(-1);
42       }
43       printf( "%d皇后\n ",n);
44        printf("%ld\t",upperlim);
45       upperlim = (upperlim << n) - 1;      //所有位都是1
46          printf("%ld\t",upperlim);
47       test(0,0,0);
48       printf( "共有%ld种排列,计算时间%d秒\n",sum,(int)(time(0)-tm));
49       system("pause");
50       return 0;
51 }

熊猫呵呵 2011-06-08 00:16 发表评论

[转载]乱砍设计模式之一

熊猫呵呵 — Tue, 24 May 2011 19:48:00 GMT

摘要: 本系列的文章转载自：http://blog.csdn.net/junguo STRATEGY模式——赵子龙单骑救主 &... 阅读全文

熊猫呵呵 2011-05-25 03:48 发表评论

[转载]乱砍设计模式(序)

熊猫呵呵 — Tue, 24 May 2011 19:16:00 GMT

本系列的文章转载自：http://blog.csdn.net/junguo
作者以诙谐生动的例子解释了一些设计模式。

有时候想知道偶然会为人生带来什么样的意义？作为一个怀疑论者，我对人生充满了疑虑，对于偶然所起的作用也不是那么确定。但还是可以总结一些自己并不确定的结论。大学期间，成天旷课的我，那天偶然上了一堂软件工程课（我不是计算机专业的，我们开这堂课本身就有些古怪）。那天老师不知道是一时兴起，还是早有准备，在下课前他在黑板上画了一个图，标注了学习计算机的进阶图。这堂偶然的课，给我带来了后来的失落和彷徨。

一个编程工具（VC,Delphi）
一门编程语言（C，Pascal）

常用软件的熟练使用
计算机硬件（说白了就是装机的水平）

他提供的进阶图如上所示，他似乎没有说C和Pascal应该学到什么样子。而当时的我每天泡在图书馆或者宿舍里，看的是数据结构，编译原理一类的书。我为自己绘制的进阶曲线是学习计算机系得所有基础课程，然后考高级程序员。那时候对VC等工具并不感兴趣，我觉得还是打好基础容易进阶。但听完这堂课后，我的思路被打断了，放弃了自己原有的理念，跑到书店买了一本VC基础的书，那是我学生时代买的最贵的书（70多或者80多块，书借人了），书上都是一个一个的例子，其实学完后我都没弄明白MFC是怎么回事。只是学会了拖动不同的控件，在界面上做出不同的效果。凭良心说，那本书译文的文笔不错，也挺适合入门的，但它确实是本不折不扣的破书（国外图书也不都是精品，垃圾也不少），在不懂C++的情况下，它可以教会你在界面上拖拉的本事，屏蔽了你学习的路线。而我们老师的进阶图无疑也是一张误导图，编程还是以数据结构等内容为基础的，没有了基础，你也就没有了前进的依仗。经过多年的失落彷徨，终于感觉找到了入门的通道。我也想总结一幅进阶图，但我发现自己总结不出来。庞庞杂杂接触了太多的东西：汇编，破解，操作系统，C++，ASP，MFC，COM，ATL，VB，STL，数据库；但接触的东西都没有到精通的地步，只是感觉现在理解东西没有以前那么复杂了，但为什么会这样，我自己也说不清楚。只是隐隐约约感觉理解这些东西和汇编有些关系，但这些都是在我单纯学习汇编时候并没有感觉到的。我如今也只是处于从初级向中级攀升的阶段，真要搞出一个进阶路线，可能效果就和我们老师的进阶图一样只能误人子弟了。所以如今放弃了这方面的努力，也许将来有一天我会去做。如今我想做的就是提供给那些和我一样在从初级向中级攀升的人们一些共同感兴趣的话题。而设计模式绝对是这样一个话题，设计模式是帮助你真正理解OO设计的一把钥匙，也许只有它能帮助你真正进入OO设计之门。在没接触设计模式之前，对于OO只知其形，不知其意。很多OO设计的原则，不知道我买的那本巨著《C++ Primer》中有没有，反正我是一条也没记住。如果你觉得你懂了面向对象的基本原理，懂得了虚函数，需要继续紧阶，那么我们可以一起探讨这里谈到的设计模式。

GOF出的《设计模式》买了很长时间了，翻看了也不下三篇，但每次总感觉收获不大。虽被众人奉为经典，但那本书不适合我，写的太过抽象，没有完整的例子，每次看过都没留下多少印象。又是一个偶然，给我带来了惊喜。我在网上找到了一份电子版的《Head First Design Patterns》，尽管只有第三章，但我发现这本书文笔清新，事例翔实，以前看多次没记住的东西，这儿看一次就留下了深刻的印象，实是一本入门的好书。所以豪不犹豫买了本纸版的，不过如今该书只有影印版，但并不影响阅读。以我大学英语四级没过的水平都可以基本看懂这本书，我想搞计算机的应该都不成问题。

刚看到这本书的时候，第一个想法是自己能不能把它翻译一下。与大家共享，但后来想想版权什么的东西，自己并不清楚。加之文笔拙劣，怕毁了原文的意境，所以放弃了这个念头（毕竟我不是人民教师）。但总感觉有些失落，那就自己写吧，把我能理解的总结出来，配以我想到例子。经过这么一番折腾，也帮助自己加深理解，因为看书的时候，还是会忽略太多的细节，只有经过了自己的手，才会抠出很多容易忽略的东西。这就是我写这个系列的原因了。但也希望有同样兴趣的同仁共同讨论了。

冠以乱砍的名字，是因为我不想把技术的东西搞得太枯燥。尽量加一些自己感兴趣的内容进去，呵呵，有同样爱好的同仁，我们也可以一起讨论。但对于技术的内容，我还是尽最大的努力做到正确表述。

好了，要说的说完了。但声明一下，今天看到自己以前写的一篇文章被转载，但被斩头去尾，还删除了署名。虽然不是太在意，但还是感觉不舒服。所以希望有仁兄要转载的话，请保留署名；不要删除任何内容，如果你不喜欢我的废话，那就不要转了。

熊猫呵呵 2011-05-25 03:16 发表评论

[转载]5个简单的方法带给你平静的心情

熊猫呵呵 — Fri, 20 May 2011 03:02:00 GMT

以下内容转载自互联网。

当向听众解释压力管理的时候，讲师拿起一杯水问道：这杯水有多重？20克到500克众说纷纭。

讲师回答说：实际有多重并不重要，这要看我拿着它的时间。一分钟，没有问题。如果一个小时呢，我的右臂就会疼痛。再进一步，一天，你应该给我叫救护车了。当然每种情况下杯子的重量是相同的，但是我拿的越久，它就显得越沉。

他继续说道：这就像压力管理，如果总是怀揣沉重的负担，随着压力越来越大，迟早我们会崩溃掉。

正如这杯水一样，你需要放下它休息一下，调整自己，继续前行。

所以，今晚在各位回家之前，放下工作上的负担。不要把它带到家里去，你可以明天继续肩负。无论你背负怎样的负担，如果可能，暂时忘掉它们。

这里有5个简单的方法，能为你带来平静的心情。

1.将最艰巨的任务放在早晨。

人们总是倾向于用简单的任务开始一天的工作，别这样做。将艰巨的任务拖到后面就像你伸开手臂举着杯子，开始没什么，但是随着时间的推移，你会很快感觉到压力。将最艰巨的任务放在早晨，这样你就能享受到效率提升及一天中剩下时间的平静带来的惬意。

2.放开你不能控制的事情

你和朋友计划好外出，但是最后关头下雨了，这时你会怎么想？

有些人会因此而失望、愤怒，然后跟周围的人抱怨：这不公平，为什么这种事总是让我遇到！

没什么可抱怨的，雨不会因为你抱怨而停止，老天才不在乎。这种情况下我会到公园里散步（因为雨也很有魅力），或者躺在床上一边读Terry Pratchett的书，一边听着雨水打在窗户上的声音。

将你能掌控的事情做到最好，但也不用太在意不能左右的事情。

3.不必担心别人的想法

我曾经对自己的舞技感到非常羞愧，因此很少与朋友外出。即使出去我也不跳舞，仅仅笨笨的站在一边。因为我担心别人嘲笑。

然而有一天我在学校里重重的下了决心，决定要改变这一现状。下一次和朋友们出去的时候，我走进了舞池，旁若无人的跳舞。有意思的是并没有人注意到我。实际上他们还想看我再跳，因为觉得我有意思。

不要担心别怎么看你，可能他们还在担心别人会怎么看他们呢

4.列出3件你喜爱的事情

我是在Positivity Blog中的The Plague of Happiness Ever After文章中第一次和读者分享这个技巧的。

仅仅是列出生活中你喜爱的3件简单的事情，如：这个屋子我最喜欢的3个地方，或这个星期我最喜欢的3件事，或是其他的什么。

在你堵车或排队而感到无聊的时候这个技巧就会显得尤为有用，你能立即把无聊的感觉一扫而光，取而代之的是幸福和平静。

5 走向窗前望向窗外，深呼吸。

我从禅师Mary Jaksch那里学到的这个技巧。仅仅是走向窗前望向窗外，深呼吸。将注意力集中到这次呼吸上并忘掉其他的一切。这听起来及其简单，但是你很难想象这样做能立即给你带来平静的心情。

这也是最后一个技巧，你可以在读完这篇文章后马上试一试。忘掉一切，体会空气在肺里的进出。

熊猫呵呵 2011-05-20 11:02 发表评论

大整数算法之gcd(最大公约数)

熊猫呵呵 — Thu, 19 May 2011 08:18:00 GMT

欧几里德算法(Euclid)阐述了一种gcd算法。gcd(greatest common divisor)，简言之，我们想求gcd(x,y)，假设(x>y)，如果存在下式:x = q*y + r，那么则有gcd(x,y) = gcd(y,r) ，其实上式也称为gcd递归定理，即gcd(a,b) = gcd (b,a mod b)。
这个递归式看似很简单。实则它还是很值得推敲的，首先，它怎么证明？其次，该算法的运行时间为如何？
在密码学中，欧几里德算法有着相当广泛的应用，譬如求乘法逆元，大整数分解等等。。
在<<编程之美>>一书中，给出了不少gcd算法的简单实现。因为gcd算法的实现是递归，所以要特别注意栈溢出。先做个标记，以后会把栈详细分析一下。
最简单的gcd算法：

1int gcd(int x, int y)
2{
3     if(y == 0) return x;
4     if(x < y)      return gcd(y,x);
5     else        return gcd(y, x%y);
6}

ACM中常用的gcd算法：

1int gcd(int a, int b){ return a == 0 ? b : gcd(b % a, a); }

经过优化的gcd算法(分成奇偶两种情况)：

1int gcd(int x,int y )
2{
3    if(x < y) return gcd(y,x);  // x>y
4    if( y == 0) return x;  // if y=0, x is GCD
5    else
6    {
7         if( !(x%2) )
8         {
9           if( !(y%2) )  //x,y both even
10               return 2*gcd(x >> 1, y >> 1);
11           else      // x is even, y is odd
12               return gcd(x >> 1, y );
13         }
14         else
15         {
16           if( !(y%2) )  // x is  odd,  y is even
17               return gcd(x, y >> 1);
18           else       // x, y both odd
19               return gcd(y,x-y);
20         }
21    }
22}
23

熊猫呵呵 2011-05-19 16:18 发表评论

大整数算法之求阶乘

熊猫呵呵 — Thu, 19 May 2011 03:45:00 GMT

这几天闲暇时研究了一些关于大整数计算和存储的算法。关于这些方法，无非是用数组代替内置类型对大整数进行存储，然后进行适当的运算技巧进行并得到结果。下面是一个求阶乘的算法。n! = n*(n-1)*(n-2)*...*2

1#include <stdio.h>
2
3unsigned long long int fac[2570]={0},low_bit,multiplicand,carry_bit = 0;
4/* 计算阶乘 m*(m-1)*(m-2)**n    */
5void factorial(int m, int n)
6{
7     carry_bit = 0;
8     multiplicand = m;
9     //分离被乘数m，a[1]放个位，a[2]放10位
10     while(multiplicand)
11     {
12         low_bit++;    //fac数组的第0位不用
13         fac[low_bit] = multiplicand%10;
14         multiplicand = multiplicand/10;
15     }
16     for (int multiplicator = m-1 ; multiplicator >= n ; --multiplicator)
17     {
18         carry_bit = 0;     //carry_bit表示进位
19         for(int j = 1 ; j <= low_bit ; ++j)
20         {
21               fac[j] = fac[j]*multiplicator + carry_bit;
22               carry_bit = fac[j] / 10;
23               fac[j] = fac[j] % 10;
24         }
25         while(carry_bit)
26         {
27                 low_bit++;
28                 fac[low_bit] = carry_bit % 10;
29                 carry_bit=carry_bit / 10;
30         }
31     }
32
33}
34
35int main()
36{
37    factorial(40,2);
38    for(int index = low_bit ; index>=1 ; index--)
39    {
40            printf("%d",fac[index]);
41    }
42    getchar();
43    return 0;
44}
45

结果为：815915283247897734345611269596115894272000000000

前一阵子研究python时，对它的长整数那块颇感兴趣，因为在python中是有“无限精度”的整数一说的，有空要拿它的源码来学习一下。

熊猫呵呵 2011-05-19 11:45 发表评论

又是一年答辩时

熊猫呵呵 — Thu, 19 May 2011 03:02:00 GMT

      时间总是在不知不觉中消逝，这句话是句废话。可是，研三的师兄师姐们就要毕业答辩了，说起来有些许伤感。一是为他们的离校，而是为自己的仅剩的一年学校生活。肯定不会去读博了，因为已然看透了许多事情。
      孤单的奋战。
      一篇随笔，当做是在cppblog的首篇文章吧。

熊猫呵呵 2011-05-19 11:02 发表评论