Archive for the “summary” Category

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

想当年学C#的时候.Net还是2.0,学了就直接丢掉了,要不是到MS来实习,估计也未必会再捡起来了,结果.Net都4.0了。最近coding才发现C# 3.0多了好多新特性,而自己还把一些C# 2.0的特性彻底忘了,真不敢说自己会C#了。于是总结一下最近遇到并且常用到的特性吧。

1. ? – Nullable<T>

[SerializableAttribute]
public struct Nullable<T> where T : struct, new()

C#里像int, bool, double这样的struct和enum类型都不能为null。如果确实想在值域上加上null的话,Nullable就派上用场了。T?是Nullable&ly;T>的语法糖。要将T?转为T可以通过类型转换,或者通过T?的Value属性,当然后者要高雅些。

// Nullable<int> arg = -1;
int? arg = -1;
if (arg.HasValue) {
    // int value = (int)arg;
    int value = arg.Value;
}

2. ?? – operator ??

o ?? v可以看作是o == null ? v : o的语法糖。??运算符在左操作数非null时返回左操作数,否则返回右操作数。

string result = gao();
Console.WriteLine(result ?? "<NULL>");

3. => – lambda expression

看别人代码的过程中才发现原来C#也有lambda了,也才发现自己真的out了。当然,感觉C#里的lambda并没有带来什么革命性的变化,更像是一个语法糖。毕竟这不是Scale,MS也有F#了。

Func<double, double, double> hypot = (x, y) => Math.Sqrt(x * x + y * y);
Func<double, double, string> gao = (x, y) =>
    {
        double z = hypot(x, y);
        return String.Format("{0} ^ 2 + {1} ^ 2 = {2} ^ 2", x, y, z);
    };
Console.WriteLine(gao(3, 4));

4. {} – initializer

collection initializer使得初始化一个List, Dictionary变得简单。

List<string> list = new List<string>{"watashi", "rejudge"};
Dictionary<string, string> dic = new Dictionary<string, string>
{
    {"watashi", "watashi wa watashi"},
    {"rejudge", "-rejudge -pia2dea4"}
};

而object initializer其实就是调用完成构造后执行属性操作的语法糖,它使得代码更加简洁,段落有致。试比较:

Comments 11 Comments »