上上次上次的题解,补上这最后一部分。这次的三道题分别是我出的程序员六级阅读理解题Crack Me II;复数表达式解析计算题(误)Complex Calculator;和大自然数值积分题(大误)Bessel Function II

ZOJ3441. Crack Me II

[cpp + indent, sorting, set_difference]

题目就是要求写一个和这段天书一样的代码(ZOJ3441txt.c)功能完全相同的程序。

这一题是程序员四级阅读理解题ZOJ1584 Crack Me的加强版。首先说说这段天书是怎么来的吧,其实最初是一段非常简单的Haskell程序(ZOJ3441hs.hs)。然后我简单的用C重写的了一遍所有函数,于是得到了下面的C语言程序(ZOJ3441c.c),因为是按Haskell的思路来写的,所以几乎没有循环,全是递归。之后就是人肉宏替换了,其实写这段代码远比看懂它要辛苦啊。

如果你直接提交这段代码,会MLE,一看程序你就会发现,不断的malloc,完全不free。即使处理了内存泄漏,依然会TLE。有的时候可以通过只修改瓶颈代码来AC,比如ZOJ1584就可以这样做,不过这一题就行不通。

解决这道题的一种办法是通过够找各种sample,测出这段程序的功能。这是一个比较可取的办法,不过如果遗漏掉了任何一个地方都会WA,通常也会设置一些这样的陷阱,比如ZOJ1584在长度大于某个阈值的时候要数出”0″,这是很难测出来的。这段程序没有太xe的地方,不过对于负数的处理,也是要花点时间来找规律的。

另一种方法就是阅读代码了,这段代码的直接阅读难度要远远大于ZOJ1584。不过我们为什么要直接阅读呢?宏展开这种事编译器不就能做么,何必人肉?gcc -E命令就可以将宏展开,其实背后就是调用了GCC中一个叫cpp的程序,cpp是The C Preprocessor,只要

cpp ZOJ3441txt.c > ZOJ3441cpp.c

就得到了宏展开的代码,不过代码缺少良好的缩进,还是不可读,再利用代码格式化工具,比如indent,来处理一下

indent ZOJ3441cpp.c

这样代码(ZOJ3441cpp.c)的可读性就比较强了,唯一的麻烦就是变量名都没有意义,你可以在阅读的同时替换成有意义的名字。

如果综合上面两种方法,效果会更好。于是很容易发现,这段天书读入两个数组,丢弃第一个数组中的负数,对第二个数组所有元素取绝对值,然后从第一个数组中删去第二个数组,如果有多个相同元素,则优先删拍在前面的。所给程序的复杂度是O(n^2)的,题目实际需要一个O(nlgn)的算法才能AC,利用hash,还可以得到O(n)的算法。

ZOJ3442. Complex Calculator

[complex, eval, regex]

题目用一句话来说就是实现一个支持复数运算的计算器。

首先要知道,C和C++都有对复数运算的支持,C++提供有一个模板类complex。而C语言对复数的支持是原生的,它提供有complex float, complex double和complex long double三种基本类型,注意,他们是基本类型,而非结构体。在complex.h中还定义了题目所需要的所有函数,不同的是,我们知道C是没有函数重载的,为了和其实数版本区分,这些函数多了个前缀c-,比如cexp, cpow, clog, csqrt, catan2…而宏I定义为单位虚数。于是下面的C语言代码就能得到sample的结果:

#include <stdio.h>
#include <stdarg.h>
#include <complex.h>

double gao(double x) {
	return -5e-7 < x && x < 5e-7 ? 0 : x;
}

void dump(const char *format, ...) {
	va_list ap;
	complex double z;

	va_start(ap, format);
	while (1) {
		z = va_arg(ap, complex double);
		if (z == 0) {
			break;
		}
		printf(format, gao(creal(z)), gao(cimag(z)));
	}
	va_end(ap);
}

int main(void) {
	dump(
		"%+lf%+lf*i\n",
		1.*I*I,
		cpow(-1.*I,2.),
		csqrt(-1.),
		8.+6.*I/8.-6.*I,
		(8.+6.*I)/(8.-6.*I),
		(8.+6.*I)*conj(8.-6.*I),
		2.*cexp(I*cacos(-1.)/6.),
		cpow(I,I),
		ccos(I),
		ccos(-1.*I),
		cacos(ccos(I)),
		cacos(ccos(I*-1.)),
		cpow(cexp(1.),cacos(-1.)*I),
		(complex double)0.
	);

	return 0;
}

更一般的,我们有这样一段C语言程序:

#include <math.h>
#include <stdio.h>
#include <complex.h>

#ifndef EXPR
#define EXPR cacos(1+2I) / csqrt(6-4I)
#endif

double f(double x) {
	return fabs(x) < 5e-7 ? 0 : x;
}

int main() {
	double complex ans = EXPR;

	printf("%+lf%+lf*i\n", f(creal(ans)), f(cimag(ans)));

	return 0;
}

我们只要对输入的每个表达式简要替换,然后定义宏EXPR就能得到正确的结果,这正是下面的perl代码所做的事。

#!/usr/bin/perl

unlink 'stdout' if -e 'stdout';
while (<>) {
	chomp;
	s/\bi\b/I/g;
	s/[a-z]+/c$&/g;
	s/(?<!\.|\d)(\d+)(?!\.|\d)/$1./g;
	s/cconj/conj/g;
#	print "$_\n";
	die if system("gcc gao.c -D'EXPR=$_' -lm") != 0;
	system("./a.out | tee -a stdout");
}

需要注意的是,除了将i替换成I,把相应的函数加上前缀c-外,因为C中的除法是整数除法,所以要把所有整数替换成浮点数。我的测试数据就是通过这段程序生成的。

可问题是,我们不可能在OJ上写一个C,并调用gcc来编译它,C/C++都是编译执行的,所以也没办法在运行时执行这个表达式。但是解释执行的脚本语言,比如Perl, Python, Ruby,他们都提供一个eval函数,实现运行时的执行,而且这些语言都对complex number提供支持。Python的complex也是原生的,一个复数可以直接写成3+4j这样的形式,而复数的数学函数可以通过import cmath载入。Puby的Complex也是标准库的一部分,只要require ‘complex’,就能够通过Math.exp等进行复数运算,原本实数的版本被alias成了Math.exp!。Perl的复数运算则需要use Math::Complex,这样所有数学函数也会被导出。于是要做的事情就很简单了,利用几步简单的正则把表达式替换成自己语言的版本,并实现几个不同名的函数,然后eval就得到答案了。同C一样,Ruby的除法也是整数除法,所以要对整数.to_f一下。Perl的除法始终是浮点数除法,所以没有这个问题。而Python可以通过”from __future__ import division”,改变/的默认行为,使它总是浮点数除法,此时的整数除法是//。不过很可惜,Perl和Ruby对asin, acos等返回值不惟一的函数的返回结果不一致,会有两到四个数据过不去,Python则和libm行为一致。所以Python要AC比较简单,Ruby和Perl则还需要发现这一点,自己重新处理这几个函数。

ZOJ3443. Bessel Function II

[math, C (programming language), yet-another-easy-problem]

题目要求n阶第二类贝塞尔函数在x处的函数值。

题目就是从求第一类贝塞尔函数的Bessel Function。这是道数值积分题,Romberg在这题的表现很差,不是TLE就是WA,相反Simpson的表现又快又好。当然,用本题的方法AC此题更不成问题。

题目里所给的积分比较复杂而不可做,所以没什么用。实际还是要从贝塞尔函数的渐进式和其它一些性质入手来做,下面的三段代码给出了求贝塞尔函数一个非常快而精度高的算法,注释中有详细的算法描述。

好的,其实上面这段东西来自(FdLibM: Freely Distributable LIBM, C math library for machines that support IEEE 754 floating-point)。估计上面的算法你不会吧,呵呵,我也不会。不过为什么要会呢,通常没有人自己写atan2吧,大家都是include “math.h”,所以这里一样的,你可以

#include <math.h>
double ans = yn(n, z);

嗯,是的,这是C语言标准库里自带的函数。上面的libm就是当我们用了”math.h”时,gcc需要加链接参数-lm的那个m,g++默认会和libm链接,所以不需要加-lm。其实上面这个y0, y1, yn函数也许对你并不陌生,很多写计算几何类型的题目曾遇到莫名其妙的编译错误

ce.cpp:3: error: ‘double y1’ redeclared as different kind of symbol
/usr/include/bits/mathcalls.h:242: error: previous declaration of ‘double y1(double)’

现在知道了吧,y1是”math.h”/”cmath”中一个神奇的函数名,所以如果取了名为y1的全局变量就会CE。

2 Responses to “[题解](续II)Let’s Celebrate the 100th Contest on ZOJ!”
  1. Navi says:

    Crack Me II人肉换行的表示压力很大…

  2. Navi says:

    -.- sf

  3.  
Leave a Reply