2006年四月月 发布的文章

'男女不分'

大早起来,发现外面居然飘起了大雪!要知道前几天桃花都盛开了!除了’冷’还是’冷’,在洗漱间时那身上抖成一团了!刷牙都不需要手了,把牙刷放在牙齿上,等3分钟,牙就刷好了^_^。

我在我的Blog中很少谈及工作中的趣事,不过这次太搞笑了,忍不住要说上一说。这也是一件刚才发生的趣事。

我们项目组中一般聊天都用Google Talk,自从前两周GTalk升级后,开始支持头像了。由于是升级不久很多人都使用的是Google提供的一些简单头像,今天早上突然发现一项目组的兄弟换了头像,自然很是感兴趣,特别是头像是一个小baby的照片,我猜想是他的小Baby,为了证实我的猜测,我就和他聊了一会儿,就在这聊天的过程中,一件趣事诞生了,让我自己也忍俊不禁!

这位兄弟来公司时间不长,知道是社招的,平时也只是项目上的交流,并没有涉及到生活上的。的确让我猜中了,那个是他的Baby,19个月,长得很像我们这位兄弟,他告诉我现在这个小Baby由奶奶在外地带着,他和他老婆都忙,没时间照看!他说到上周去看望小Baby,小Baby只和妈妈亲,和他不亲。这时候我插了一句话:’呵呵,男孩么,如果是女孩就不一样了’!说完这句话我就感觉有些后悔!小孩子在小的时候很难从外貌分清男女的,我又冒失了。果不其然,我的这位兄弟回答:"女孩"。我自己心里暗自哈哈大笑,想自己真是笨!男女不分!遂赶紧说抱歉的话!这位兄弟当然也不会介意我的冒失!

自己又想了想,有这么一个小Baby,的确给家庭带来了不少的欢乐,当然也有烦恼!不过这才是生活!两个大人围着一个小Baby转,其乐融融!我也向同事表示了羡慕之情!^_^

'该出手时就出手'

央视电视剧中'水浒传'主题曲中有一句叫'该出手时就出手',这话一点儿都不假!^_^。眼见着五一黄金周就要到来,各大商场都开始了'五一前热身战役',纷纷推出自己的活动,其他的我到不在乎,手机倒是我最关注的!在适当的时间和适当的地点以适当的价钱,终于拿到了我倾慕已久的MOTO-A780智能机!

有过去年五一节买机器的经验,五一的购物人流简直就像潮涌般,特别是在移动通讯商场,那真叫一个水泄不通!特别是诺基亚和摩托罗拉的柜台前面,简直就像明星签名售书一样,围了个左三层右三层,简直没有立足之地,还哪谈得上舒心购物亚,简直就是抢!所以今年我和GF商量好了,不再估计那不到百元的降价,提前2周购入心爱的机器。

走遍各大商场,发现还是国美最物美价廉,目前看来像鸿信通、北斗手机网都不保险,至于苏宁,没货,其他大商场忒贵,不敢问津。国美也不是一口价的,死说活说终于砍下来几十块RMB,加上各种礼品,也弄了个'锅满盆盈'。拿到手中沉甸甸的A780心中自然很是欣喜!开完发票,写完三包和质保,查了查没什么坏点一类的大毛病,就抱着机器闪人了!

回到小窝,坐在床上对着说明书,自然是少不了一顿'摆弄',把各种功能试了个遍,直到'筋疲力尽'想睡觉!总体来说MOTO的机器还不错,摄像头采回的照片很清晰,手写识别也没得说,棒就一个字!内置的金山词霸用起来那叫个爽!

唯一感到有些遗憾的是这款机器是简配,不带数据线,只能使用蓝牙传输数据,而我的本本由于年代'久远',并不支持蓝牙,让我有些郁闷!不过总有解决问题的办法,没有哪一款机器是完美的。已经给A780设定了闹钟,明天早起就靠它了!^_^

恼人的'素数回文'

33.00s和14.27s,两个截然不同的运行时间值,两次提交尝试解决素数回文问题,终于搞定了!用两个字形容’恼人’!算法不复杂,就是要求时间很’紧’,大部分工作都在考虑着如何缩短运行时间。桃花在冷空气袭来的日子都开了,我的心也算可以放下了!

最近项目吃紧,连续两天没有做ACM习题了,手都有些生了^_^!按照Volume1的习题顺序,该轮到1004题了!这是一道关于’素数回文(Prime Palindromes)’的习题,源自’USACO’,估计是什么比赛吧!大家一定都知道什么是素数,或者又叫质数!那么什么是回文(Palindromes),不用定义,举几个例子大家就明白了,如121、1331、14741、89098等等看起来对称的数都叫做回文数,具体的定义或者数学上的定义我也没找到,好像对解决此题关系也不大!

Ok!我们来看一下题目,题目很简单,找出输入的两个数之间的所有素数回文,并按照数值顺序输出,每行一个数!要求:运行时间在15秒以内。输入值范围[5, 1000000000]。

如果不估计时间,大家脑中一定选中了’遍历’这种方案,而达到目标前所要解决的两个问题包括如何判断一个数是否是一个素数和如何判断一个数是否为一个回文数?

如何判断素数?这个在大学学习C语言的时候好像是习题,不过算法早已经忘到了’九霄云外’,这样自己就顺手写了一个宏:
#define IS_PRIMER(i) \
        ((i <= 10) \
         ? (i == 2 || i == 3 || i == 5 || i == 7) \
         : (((i % 2 == 0) || (i % 3 == 0) || (i % 5 == 0) || ( i % 7 == 0)) ? 0 : 1))
用几个数测了一下,屡试不爽!为了更加精确的测试,还是到网上找一个素数表吧!这样有参照的测试势必比较准确无误。试着用这个宏找出500以内的所有素数,发现与素数表中的个数不符,仔细查查,一眼就看到了121这个数,按照我的算法,它就是个’素数’了,但实际上它还能被11所整除,别忘了素数的定义:"不能被1和自己之外的任何数整除",看来我的算法是’漏洞百出’,不过在100之内它是有效的,起码算是个’Uncompleted Algorithm’^_^。重新修整一下,改进版如下:
int is_primer(int x) {
        int i;
        for (i = 2; i <= sqrt(x); ++i) {
                if (x % i == 0) {
                        return 0;
                }
        }
        return 1;
}
这种算法也是网上常见的算法,如果和外层的遍历一起来看,这是个接近O(n^2)的算法,显然性能不高!不过目前还少有好算法公布在网上,就暂用这个吧,我也想不出来什么好方法!也许需要好的数学功底才能提高该算法性能!

如何判断回文?这就是个’见仁见智’的问题了。这里提供两种方案,感觉性能上差不多,各有千秋:
[方案一]
/* 获取一个数i的位数n */
#define GET_DIGITS(n, i) do { \
                n = 1; \
                while (i >= pow(10, n)) { \
                        n++; \
                } \
        } while(0)

/*
 * 从外到内,比较每一个对称位上的数值是否相等
 * 如果全相等则是回文,否则不是。
 *
 * ! 这种方法还是很容易想出来的
 */
int is_palindrome(int x) {
        int     i = 0;
        int     j = 0;
        int     n = 0;

        int     high = 0;
        int     low = 0;

        GET_DIGITS(n, x);
        j = (n % 2) ? ((n-1) / 2) : (n / 2);

        for (i = 1; i <= j; ++i) {
                low = x % (int)(pow(10, i));
                high = x/(pow(10, n-i));
                if (low != high) {
                        return 0;
                }
        }
        return 1;
}

[方案二]
/*
 * ‘回文数’再造
 * 从低位到高位,按’低位 * 10 + 高位’累加的方式得到一个数
 * 如果该最终数值与原数一致,则为回文数,否则不是
 *
 * 这个方法对后面的方法还是很有启发的!
 */
int is_palindrome(int x) {
        int     rv = 0;
        int     i = x;

        while (i != 0) {
                rv = rv * 10 + i % 10;
                i = i / 10;
        }

        return rv == x;
}

现在两个难题都解决了,我们只需要遍历加判断即可。那么是先判断素数还是先判断回文呢?看起来判断素数较浪费时间,那我们先判断回文吧!第一次提交代码,不出所料,运行时间33s(我想不止33s,也许33s只是服务器的一个时间上限,大于该时间的统一显示为33s)。看来我们的重新考量一下我们的方案了!这种遍历+判断的方法无论如何是不能够蒙混过关的了^_^。

那么怎么来做呢?方案一是拿来一个数,我们来判断是否是回文,这样绝大部分的数都不是回文数,那么这些判断也都是无效的,但却占用了大量的时间,我们能不能尽量让我们每步操作都是生成结果之路上有效的一步呢?我们来尝试自己生成一定范围内的回文数。回文数组成是有一定的规律可循的。现在我们可以将问题集中在’如何生成位数为n的所有回文数’上!我们举几个例子就能看得出来:
[例子]
6446 — 我们可以看成两个部分 — 高二位的64和低二位的46互为反序数,我们也可以理解为高二位的值随着低二位的变化而变化;
64546 — 我们可以看成三个部分 — 高二位的64和低二位的46互为反序数,再加上中间的一个独立变化的值,我们也可以理解为高二位的值随着低二位的变化而变化;中间值独立变化;

可以看出我们的算法可以将处理分为两类:奇数和偶数。
1、如何生成位数为偶数位的所有回文数?
算法名称:gen_even_palindrome
输入项:n (回文数的位数)
算法步骤:
gen_even_palindrome(n) {
 j = n/2; /* j为独立变化的低位部分的位数 */
 k = (10^j – 1); /* k为独立变化的低位部分的上限值 */
 for (i = 1; i <= k; ++i) {
     /*
      * 这里的i就是低位部分独立变化的值
      */
     if (i % 10) {
      /* 如果 i = 10、1000等这些10^n的数,它们是没有回文的 */
       continue;
     }

     rv = _gen_even_palindrome(i, n); /* rv就是一个n位回文数 */
 }
}

_gen_even_palindrome(x, n) {
        int i = x;
        int j = 1;
        int rv = 0;

 /*
  * 利用低位部分的信息,造出高位部分的数值
  */
        while (i != 0) {
                rv += ((i % 10) * pow(10, n-j));
                i = i / 10;
                j++;
        }

 /* 最后的回文数还要加上低位部分的数 */
        rv += x;
        return rv;
}

2、如何生成位数为奇数位的所有回文数?
算法名称:gen_odd_palindrome
输入项:n (回文数的位数) n > 1 对n = 1作特殊处理便是
算法步骤:
gen_odd_palindrome(n) {
 j = (n + 1)/2; /* j为独立变化的低位部分的位数 *
/
 k = (10^(j-1) – 1); /* k为独立变化的低位部分的上限值 */

 for (h = 0; h <= 9; ++h) { /* 中间位独立变化 */
  for (i = 1; i <= k; ++i) {
   /*
     * 这里的i就是低位部分独立变化的值
     */
   if (i % 10) {
    /* 如果 i = 10、1000等这些10^n的数,它们是没有回文的 */
    continue;
   }

   rv = _gen_odd_palindrome(i, h, n); /* rv就是一个n位回文数 */
  }
 }
}

_gen_odd_palindrome(x, mid, n) {
        int i = x;
        int j = 1;
        int rv = 0;

 /*
  * 利用低位部分的信息,造出高位部分的数值
  */
        while (i != 0) {
                rv += ((i % 10) * pow(10, n-j));
                i = i / 10;
                j++;
        }

 /* 最后的回文数还要加上中间数和低位部分的数 */
 rv += mid * pow(10, (n-1)/2);
        rv += x;
        return rv;
}

至此,我们算是解决了如何生成回文数的问题了,不过目前还有一点不能满足,那就是按照数值顺序来输出回文素数,不知道大家发现没有,上面的回文数生成算法不能保证按照数值顺序生成会文数,所以我们还要再动动脑筋!

这里不妨尝试一下作弊!^_^ 由于回文数生成算法不能保证按照数值顺序输出回文数,那么我们势必需要记下来已经生成的回文数,那么到底有多少回文素数需要记下来呢?我们可以利用前面提到过的’遍历’方案在本地计算一下,结果是不到10000个,那么OK!我们就分配一个大数组,并用一个static global variable记下当前数组使用情况,待所有的回文素数都写入数组,我们对该数组进行一次quick sort,这又需要有个quick sort算法(O(nlogn)级别的,简单快速是我选它的原因),不过这个比较容易,这里也不详述了。

把这个’回文生成’解决方案提交后,得出14.27s的结果,状态: Accepted。对了千万别忘了,这里还加了些优化,比如不存在位数为6的素数回文,所以当判断n = 6就直接返回,省着走冤枉路!14.27s属于刚及格范畴!该题肯定还有更快的解法,由于太烦,这里就浅尝辄止了!^_^

欢迎使用邮件订阅我的博客

输入邮箱订阅本站,只要有新文章发布,就会第一时间发送邮件通知你哦!




这里是Tony Bai的个人Blog,欢迎访问、订阅和留言!订阅Feed请点击上面图片

如果您觉得这里的文章对您有帮助,请扫描上方二维码进行捐赠,加油后的Tony Bai将会为您呈现更多精彩的文章,谢谢!

如果您希望通过微信捐赠,请用微信客户端扫描下方赞赏码:


如果您希望通过比特币或以太币捐赠,可以扫描下方二维码:

比特币:


以太币:


如果您喜欢通过微信App浏览本站内容,可以扫描下方二维码,订阅本站官方微信订阅号“iamtonybai”;点击二维码,可直达本人官方微博主页^_^:



本站Powered by Digital Ocean VPS。

选择Digital Ocean VPS主机,即可获得10美元现金充值,可免费使用两个月哟!

著名主机提供商Linode 10$优惠码:linode10,在这里注册即可免费获得。

阿里云推荐码:1WFZ0V立享9折!

View Tony Bai's profile on LinkedIn


文章

评论

  • 正在加载...

分类

标签

归档











更多