?View Code SCHEME;; 1.29 (define (simpson-integral f a b n) (define (coefficient i) (cond ((or (= i 0) (= i n)) 1) ((even? i) 2) (else 4))) (let ((h (/ (- b a)n ))) (* (/ h 3) (sum (lambda (i) (* (f (+ a (* i h))) (coefficient i))) 0 (lambda (i) (+ i [...]
?View Code SCHEME;; 1.1-2 略 ;; 1.3 (define (greater-two a b c) (- (+ a b c) (min a b c))) ; 或 (define (greater-two a b c) (cond ((and (> b a) (> c a)) (+ b c)) ((and (> a b) (> c b)) (+ a c)) (else (+ a b)))) [...]
昨天，ACM/ICPC杭州赛区以金奖（第五名）谢幕。对于Genesis队，本赛季的所有比赛已经结束，以后不大可能再在比赛中看到我们这支队伍了，希望Genesis得到的两块regional金牌以及一直以来的表现能让关注我们的人满意。 对于我已经研一的两名队友，这大约是他们最后一次以队员的身份出现在ACM/ICPC的赛场上；与高远(xgy)、杨克特(T_T)两位学长的无间配合是太过愉快的经历，学长的经验也让我受益良多。 而对于我，一名正式进入大学才三个月的大一新生，一切才刚刚开始；前方还长的路让人激动憧憬，请相信我会带来更多惊喜。 其实，这赛季能够连拿两金，取得对于我这种新手来说可称辉煌的成绩，不仅取决于全队的努力，对于我自己来说，其实不乏运气成分。这学期我主要的突破是仔细读了本《简明数论》（其实这书只有一半名副其实，“明晰”是无疑的，“简单”则谈不上），打下了还算扎实的数论基础，差不多能应付Regional中通常的数论题了，结果我们队参加的哈尔滨和杭州两个赛区正好都有数论题出现，特别是我们在哈尔滨最后才解出的B题更是我们夺金的关键。另外，在杭州赛的前几天，我匆匆浏览了《柔性字符串匹配》的后半部分，主要内容是用有限自动机做正则表达式匹配。对那本书的主题我自然是一知半解，不过倒对有限自动机有了较多的感受和认识。没想到杭州赛区的H题就是判断两个有限确定性自动机是否等价的题目。虽然没见过，但正好这几天见识了很多与自动机有关的内容，灵光一现就得出了算法，使我们队解出了第6题，也是场上解出的最后一道关键题目。 这样看来，我第一年的ACM/ICPC征程真可称顺风顺水，似乎幸运眷顾，完全没遇到挫折地走下来。当然，以后还是老老实实提高自身实力才是王道，近期打算学学Java，读读SICP之类的书。 这个学期还剩下大约一半，除了为了保持状态做点SRM以外，就不再寻求编程竞赛方面的突破了，应该多尝试点不同的内容。学Java达到与目前的C++近似的熟练程度，读SICP、Concrete Maths、Programming Pearls是必须完成的内容，如果还有闲暇就打算读读Algorithm Design以及一些AI方面的书目。最近一本《数学分析原理》让我多少发现了纯数学的美感，虽然这学期应该不大可能了，但以后还是要读些纯数学的经典教材的。物理是这学期多少令人头疼的科目，得抓紧看一下，希望能培养出兴趣。 好吧，读书去了。
注：凡“旁注”性质的笔记，都是无规划不成系统的读书随想。尤其与我大多数短篇的读书笔记一样，并不求别人也看懂。 第1章 (2008.11.16) 1.24：引入复数的一切都很完美，只是这个乘法的定义还是略显突兀。能否通过M1~M5以及零元、幺元等内容将这个定义更顺畅地推导或引入呢？换句话说，有了很自然的加法的定义，要满足(1,0)为幺元以及M1~M5，有了这些条件能否得出“合理”的乘法定义有哪些？于是就是函数方程了。如果这是唯一满足的定义那就完美了，不过我的推测是：它是函数方程所有解中明显、特殊、或朴素的一个。 1.35：又是那种“神来之笔”的证明……怎样理解这优美的构造？ 1.A.9：任何两个具有最小上界性的有序域同构。我会找到它的证明。 第2章 (2008.11.17) 这章的目的为何？完全不明白，也没办法搞清定理之间的联系。 2.12：可数个可数集的并是可数集。 2.23：所以同为开集与闭集的集就仅有空集和全集。 2.23：紧集，对于集合的每个开覆盖，存在一个有限子集也是开覆盖。 2.44：Cantor集的概念。 第3章 (2008.11.17) 这章的目的应该是判断及求得数列以及级数的极限。 3.1：极限的概念可以直接在度量空间中定义。 3.21：定理能按数列与级数两种语言来叙述与应用。 3.27：正项不增序列a_i的级数收敛当且仅当2^k a_{2^k}的级数收敛。这可以用相对很稀疏的项判断级数的收敛性。 3.38：幂级数的收敛圆（由根值法推出）。 3.42：∑a_n有界，b_n单调递减到0，∑a_n b_n收敛。（分部法）推论：交错递减则收敛。 3.47：级数乘积的定义有卷积的味道。 3.53：对（收敛但非绝对收敛的）级数重排会改变收敛的值！奇妙…… 数列：单调有界定理，比较法，Cauchy准则。 级数：比较法，3.27，另一种形式叙述的Cauchy准则，比率法与根值法（3.37说明前者有效的后者一定有效），收敛半径，分部法及推论。 第4章 (2008.11.18) 4.8：函数 f: X->Y 连续，当且仅当对于Y的每个开集V，f-1(V)是是X中的开集。（由于开集的补集是闭集，所以叙述中可以换成闭集。） 4.18：一致连续是函数（在某个定义域上）的性质，而连续是函数在点上的性质。然而在紧集上，这两个概念等价。 4.23：函数的连续性保持定义域的连通性。 这章应该是探讨了函数的连续性与第2章中集合的特性的关系。2、4两章应该都是构建后文微分、积分理论大厦的基石与原材料。 第5章 (2008.11.19) 5.9：直接证一般中值定理，很赞。 5.12：导函数可以不连续，但不能有第一类间断，且在区间内能像连续函数一样取到所有中间值。 5.13：L’Hospital法则的证明，看上去很不直观。Wikipedia上的证明似乎更优美。 5.15：这个证Taylor定理/Lagrange余项的方法简洁得很诡异，其实没看懂……Wikipedia上的先证integral reminder再用积分中值定理直接得到Lagrange reminder的方法直接且精炼。 第6章 (2008.11.20-21) 6.1：这个定义与Wikipedia上的Darboux integral完全相同。上积分、下积分——它们必定存在，可积性便等价于二者是否相等——于我是新鲜的概念。以下便用这些定义（还有一个“加细”）证明了若干关于可积性的性质。 6.2：在概念中增添“-Stieltjes”之后，让关于x的Riemann积分可以关于任意函数α(x)，扩充的要点是，α不必可导，甚至不必连续。 6.15：有点绕……第一遍没看明白。不过的确是一下子让人发现Riemann-Stieltjes对于Riemann的扩充，然后函数值、级数(6.16)都可用一个Riemann-Stieltjes积分来表示，6.18是点出本质的总结。 6.20-21：微积分基本定理的两部分。我总是觉得Wikipedia上的证明一下子就能看懂，这书故作高深的倾向却要让人看很久才知道他是怎么证出来的……这种从定义就开始“立意求高”类似于“伤人乎不？问马。”，教材中的例子有萧树铁的《大学数学——代数与几何》中对行列式的定义。这样的教材的确有境界，不过最好还是借助大众化的Wikipedia补充一下。
Euler函数φ(m)，定义，积性不完全； ； ； 。 用积性证很简单；证明二：按与m的最大公约数分类。 f(n)的Mobius变换：； Mobius逆变换：； 以上两式等价，f(n)与F(n)的积性也等价。 f与g的Dirichlet卷积：，h保持f与g的积性。 同余： a对模m的最小非负剩余、绝对最小剩余； 同余式是等价关系；同余式可加减乘；ca≡cb (mod m)等价于a≡b (mod m/(c,m) )； 对模m的逆的定义。 同余类、完全剩余系定义； 既约剩余系包含的同余类个数即φ(m)。 (a,m)=1时，x遍历m的完全/既约剩余系当且仅当ax遍历m的完全/既约剩余系。 用这个可轻松证明Fermat-Euler定理。 Wilson定理，即(p-1)! ≡ -1 (mod p)。 证：除了-1外，其它因子可与（不相等的）逆元配对抵消。 即，p的既约剩余系的积模p得-1。 扩展：p可换成pk，2pk（这两者p是奇素数）。 事实上，r不取1,2,4,pk,2pk时，r的既约剩余系的积模r得1。 ax≡b (mod m) 型的同余方程。 (a,m)|b 是有解的充要条件，解有(a,m)个。 可求a对m的所有逆元。 注意到一个解是 ，也可用扩展欧几里德求特解。 所有解是，其中0<=t<(a,m)。 形如的一次同余方程组。 若{m_i}两两既约，则解数必为1（中国剩余定理）。 解为。 其中，。 当a_i分别遍历m_i的完全/既约剩余系时，x遍历m的完全/既约剩余系。 若{m_i}并非两两既约，例如(m_i,m_j)=a时，可将模m_i与m_j的两个方程化成模a、m_i/a、m_j/a的三个方程。 编程时，直接化为若干个模p^k的方程似更简便，其中p^k || [m_1,m_2,...,m_i,...]。 f(x)≡0 (mod n) 的解数设为 T(f;n)，则T(f;n)是关于n的积性函数。 [...]