Posts Tagged “perl”

计算机内的整数往往是固定长度的,比如32位整数,如果整数超出表示范围则会发生溢出。大数(BigInteger)则是具有任意精度的数(arbitrary precision number),是一个实际运用中常见,尤其在程序设计竞赛里频繁出现的数据结构。java因为带有BigInteger类,而成为竞赛中解决大数问题的首选,而C/C++则需要第三方库提供大数支持。至于其他很多语言,都有语言或标准库级别上的高精度运算支持,只不过其中很多除了在SPOJ和GCJ外恐怕都不怎么能用于水题。Small factorials里有在SPOJ中使用高精度的例子。

Perl: Math::BigInt

Math::BigInt提供了非常多方法,而且很多方法也有对应的运算符重载,支持bin, oct, dec, hex格式字符串与BigInt之间的相互转化,几乎没有不支持的操作,包括三角函数,二项式系数都有。不过Math::BigInt有很多不同的实现,其中最快的是Math::BigInt::GMP,效果还是非常理想的,但是默认的Math::BigInt::Calc就慢得不能忍了,远比php, java, ruby, python的都要慢。另外Math::BigFloat是基于Math::BigInt的高精度浮点数。

use Math::BigInt lib => 'GMP';
use Math::BigFloat try => 'GMP';
print Math::BigFloat->bpi(64), "\n"; # 3.14...
my $x = new Math::BigInt('0x123456789abcdef');
my $y = Math::BigInt->new('0b101010101010101');
print $x + $y, "\n";
print join(":", $x->copy()->bdiv($y)), "\n";

Bash: bc

说bash支持高精度不是很严谨,不过bc(白痴)是Linux下一个支持任意精度数字计算的语言,也算半个标配。bc支持算术运算(+, -, *, /, %, ^等),逻辑运算(<=, ==, ||等),流程控制(if, while, for等),函数定义(define)。bc本身就可以写成脚本执行。

#!/usr/bin/bc -q

define e(n) {
	auto i, p, s;
	p = 10 ^ n;
	s = 2 * p;
	for (i = 2; p > 0; ++i) {
		p /= i;
		s += p;
	}
	return s;
}

print "input a integer: "
x = read()
e(x)
quit

# input a integer: 40
# 27182818284590452353602874713526624977552

Php: BCMath

bc是Binary Calculator的

Comments 7 Comments »

SPOJ24. Small factorials[FCTRL2]就是阶乘计算加高精度运算。以下是用内置大数支持的perl, php, java, ruby, python, haskell, bash, scheme等语言实现的代码。

haskell

main = interact $ unlines . map (\i -> show $ f !! read i) . tail . words
	where f = scanl (*) 1 [1 ..]

perl

#!/usr/bin/perl -w

use strict;
use Math::BigInt lib => 'GMP';

my @f = ();
push @f, Math::BigInt->new(1);
for (my $i = 1; $i <= 100; ++$i) {
	push @f, $f[$#f]->copy()->bmul($i);
}
chomp(my $re = <STDIN>);
for (my $ri = 1; $ri <= $re; ++$ri) {
	chomp(my $n = <STDIN>);
	print "$f[$n]\n";
}

php

Comments 15 Comments »

专门针对验证码写了个识别脚本,当然不是光为识别验证码而识别的咯,至于拿来干什么“坏事”,再说吧。识别验证码也算挑战大自然了,当年百度复赛那道验证码识别就让无数人肉牛满面,所幸这需要识别的验证码只有数字,而且字迹工整,颜色统一,格式规范,背景简单。识别脚本利用基于ImageMagickImage::Magick处理验证码,分离出每个数字的二值图像,然后利用基于ImgSeekImage::Seek通过相似度比较识别验证码。

captcha

todigits是将验证码图像文件转换成每个数字的二值图像的函数。首先将验证码转为灰度图,再选择合适的阀值,将图像二值化。最后把每个数字裁剪出来并去掉白边。硬编码万岁!

# todigits.pl
use strict;
use Image::Magick;

sub todigits {
    my ($n, $threshold, $w, $h, $x, $y) = /该信息已被绿坝屏蔽/;
    my $filename = shift @_;
    my @retval = ();
    my $image = Image::Magick->new;

    $image->Read($filename);
    $image->Quantize(colorspace => 'gray');
    $image->Threshold(threshold => $threshold, channel => 'All');
    for (my $i = 0; $i < $n; ++$i) {
        my $digit = $image->Clone();
        $digit->Crop(width => $w, height => $h, x => $x + $i * $w, y => $y);
        $digit->Trim();
        push @retval, $digit;
    }
    return @retval;
}

1;

准备足够多的验证码,用脚本测试一下todigits,同时也生成了ImgSeek所需的所有数字的二值图像样本。

0123456789

Comments 19 Comments »

原文最初发表于2009年9月18日,并消失于地震

C

/* A + B Problem in C */
#include <stdio.h>

int main(void) {
	int a, b;

	while (scanf("%d%d", &a, &b) != EOF) {
		printf("%d\n", a + b);
	}

	return 0;
}

Comments 7 Comments »

要装扮一下自己的blog,最重要就是选择一个合适的主题。wordpress有着无数的免费与收费主题,但是要找到一个自己心满意足的却并非易事。当然如果你是一个css高手的话,自然能轻松搞定一切,可惜我不是,我只能找一个足够合适的主题作为一个高起点。首先当然是从wordpress的Free Themes Directory入手,很可惜,我在这里要么是搜不到满足我条件的主题,要么是安装后实际效果不理想。于是我开始求助搜索引擎,并搜到了更多的主题,依然很可惜,这些主题或者不符合我口味,或者定制性太差,或者同我blog内容结合在一起比较违和。最后,我开始用关键字搜一些同好用workpress架的blog,看看他们都用啥主题,企图rob一个合适的。搜寻过程拜到各种技术宅,包括自己写主题,插件的,还有自己做出一套华丽的素材的,无限orz。我就这样找啊找啊,找了整整三天之后,我才找到现在用的主题——mandigo

mandigo是一个在我看来非常不错的主题,首先它是fixed-width的,这样可以有效逃避自己精心打扮的blog在别人浏览器里崩掉的悲剧。它的定制性也不错,本身就有好几套不同的配色可以选择,还支持随机配色,不过我当然是毫不犹豫地选了现在的这个pink配色。最主要的还是对title和background图片个性化的支持。title的图片也支持随机功能,只要把备选图片放到指定目录下就可以了,都不用自己来实现了。

最后就是挑选背景图片了,总是搬运来搬运去的,也该到自己动动手的时候了。当然事实是我在自己的收藏,百度、google的搜索结果中都没能找到中意的。不过搜索中发现《东方活动写真馆》的截图主调确实和blog满搭配,于是自己用《东方活动写真馆》做一个。考虑到只用一张截图实在太单调了,于是用许多截图平铺起来。

首先获得截图,每秒钟来一张,利用mplayer可以轻松搞定。我写的比较圡,我想应该可以用一行脚本搞定的。

for i in `seq $1`
do
    mplayer -ss $i -noframedrop -nosound -vo png -frames 1 /media/temp/VIDEO_TS/VTS_02_1.VOB
    mv 00000001.png $i.png
done

然后利用imagemagick处理获得的截图,把过多的白边去掉,然后缩小图片并存成jpg。imagemagick是一个强大的图像处理工具,并且有很好的perl支持。

#!/usr/bin/perl -w

use strict;
use warnings;
use Image::Magick;

for my $file (@ARGV) {
    my $image = Image::Magick->new;
    $image->Read($file);
    $image->Crop(
        width => 700, height => 400,
        x => 80, y => 50);
    $image->Scale(
        width => 420, height => 240);
    $file =~ s/png$/jpg/;
    $image->Write($file);
}

最后随机选一些图片纵向平铺合成一张大的背景图片,依然通过perl脚本,借助imagemagick实现。这一步要人肉做的话不知有多痛苦……

#!/usr/bin/perl -w

use strict;
use warnings;
use Image::Magick;

sub randfile() {
    return sprintf '%08d.jpg', 15 + int rand 227;
}

srand;
my $n = 16;
my $size = sprintf '420x%d', 240 * $n;
print $size;
my $image = Image::Magick->new;
$image->Set(size => $size);
$image->Read('NULL:blank');
for (my $i = 0; $i < $n; ++$i) {
    my $img = Image::Magick->new;
    my $file = &randfile;
    print "$file\n";
    $img->Read($file);
    $image->Composite(
        image => $img, compose => 'Over',
        x => 0, y => 240 * $i);
}
$image->Write('gao2.jpg');

然后多随机几次,选个感觉最好的,上传并设置为blog的背景图片,大功告成^ ^

Comments 6 Comments »