Posts Tagged “java”

接着上次4道比较简单的题的解题报告写。这次是Detect the Virus IIAn Unusual Problem的解题报告,主要涉及如何在C, C++, Java, Perl, Python中使用正则表达式与及无损压缩算法

ZOJ3440. Detect the Virus II

[regex, topSort]

题目简单来讲就是通过上下文无关语法(context-free grammar, CFG)描述了virus。问一个字符串是否存在virus形式的子串。题目保证描述不会有环/递归。

这题用正则表达式(Regular expressions, regex)来做是再自然不过了,比如sample就等价于下面这段perl代码:

# subparta:=fg|g
$subparta = qr(fg|g);
# parta:=a|b|c
$parta = qr{a|b|c};
# partb:=d|e[subparta]h
$partb = qr{d|e($subparta)h};
# virus:=[parta][partb][partb]
$virus = qr{($parta)($partb)($partb)};

printf 'abcdefghijklm' =~ $virus ? "YES\n" : "NO\n";
printf 'nopqrstuvwxyz' =~ $virus ? "YES\n" : "NO\n";

当然,因为代码是顺序执行的,所以我们调整了几个record的顺序。顺插一句,如果是函数式编程语言的话,那顺序就完全无关紧要了。于是问题就是给定的字符串能否匹配题目所描述的正则表达式,不过因为输入的顺序不确定,所以要麻烦一点,不过即然没有环,一个拓扑排序就搞定了(ZOJ3440watashi2.pl)。

Comments 15 Comments »

计算机内的整数往往是固定长度的,比如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 »

原文最初发表于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 »