erutan_pku-CSDN博客

学过的东西可以还给老师，但最好还是写下来，提醒自己学过...做过的事情可以抛在脑后，但最好还是写下来，提醒自己做过...

原创北京大学科学道德与学术规范基本知识测试题库

【题库太大了，只试出了一部分，运气不是特别差的话通过应该没问题了吧...目测题库规模应该有300+】1．是以人的观念、精神、情感和价值，即以人的主观精神世界及其所沉淀的精神文化为研究对象的领域。A 人文学科B 社会科学C 自然科学D 心理学正确答案为 A2．学术研究指在精神和精神指引下，用科学的方法进行探索、求知，获

2016-09-04 11:04:33 316152 5

原创北京大学学生校规校纪考试 2016级研究生部分题库及答案

1.研究生在一学期内累计请病假一个月以上者，需报（）备案。C.研究生院培养办公室2.冒用学校或他人名义，侵害学校或他人利益，给学校或他人造成不良影响或损失者，除给予记过以上处分外，还需要：（）。D.赔偿经济损失3.研究生如确需请事假，一周以上由（）批准。C.学院/系所主管负责人4. （此题为多选题）为达到个人目的有下列行为者，视其情节，给予记过以上处

2016-08-23 22:21:08 50292 1

原创北京大学直博申请夏令营上机考试题目分析

## 2014年北大直博夏令营 ##1.人民币支付计算概论A无☆2.排队游戏计算概论A栈★3.取石子游戏计算概论A(不是百练上的)递归★4.去除C程序中的注释数据结构与算法A有限状态自动机★★5.求逆序对数数据结构与算法A归并排序★★★6.Battle City

2015-07-24 19:50:25 4130 1

原创【fun】自制程序运行时间监测头文件

首先，先看一下头文件所提供的接口：

2014-06-02 12:52:11 1019

原创随机快速排序

随机快速排序算是快速排序

2014-05-31 16:22:36 1044

原创方差分析

方差分析是数理统计中的一种方法。

2014-05-24 19:45:04 2374

原创 Karp的21个NPC问题及其规约

备注：主要参考的内容是1、 SAT问题(SATISFIABILITY) （判断合取范式（有限个简单析取式的合取）是否可满足）判断析取范式（有限个简单合取式的析取）是否为永真式。 2、 0-1整数规划(0-1 INTEGERPROGRAMMING) 对整形矩阵C和整形向量d，判断是否存在0-1向量x，s.t. Cx

2014-05-18 18:54:26 17803

原创【论文概述】analysis of alpha-beta pruning

这是Andreas Zeller 的一篇论文，原文，是北京大学本科生算法设计与分析2014年春季课程的选读论文之一。以下是其梗概。特别鸣谢小班课上做这篇论文pre的同学...仓促间写的，并且有些地方我都觉得我理解得不到位，欢迎提出疑问以及就疑问点和我讨论。

2014-05-04 14:38:46 4130

原创【论文概述】delta debugging

这是Knuth 的一篇论文，原文下载在这里有：http://download.csdn.net/detail/u013012544/6982095，是北京大学本科生算法设计与分析2014年春季课程的必读论文之一。

2014-05-02 23:11:40 5527 3

原创【fun】贪吃蛇源码

曾经写过一个贪吃蛇，代码补偿

2014-04-26 00:10:26 1146

原创 POJ 1945 Power Hungry Cows 我的解法

【这篇文章之前在我自己的人人日志中发过一次~】

2014-04-26 00:01:54 2525 5

原创 windows下安装配置Haskell的IDE leksah

【我会说这篇日志】

2014-04-21 12:40:08 5970

原创小游戏 Untrusted 推荐及攻略

Untrusted 是 Berkeley 的Alex Nisnevich 和 Greg Shuflin 开发的yi

2014-04-16 16:26:12 1893

原创 openjudge 高速公路（非prim算法）

这道题是POJ 2485 Highways

2014-04-16 15:33:58 1782

原创【fun】自制chrome疯狂刷新器

chrome中

2014-04-04 18:27:57 2532

原创 Poj 1651 Multiplication Puzzle

题目链接：Multiplication Puzzle总时间限制: 1000ms 内存限制: 65536kB描述：有若干个矩阵{Ai}，元素都为整数且已知矩阵大小。如果要计算所有矩阵的乘积A1 * A2 * A3 .. Am，最少要多少次整数乘法？输入：第一行一个整数n(n 第二行n个整数B1, B2, B3

2014-03-17 13:06:47 996

翻译【翻译】Fast Fourier Transform

这是Stefan Wörner的一篇介绍快速傅里叶变换的论文，原文下载在这里有：http://download.csdn.net/detail/u013012544/7045283，是北京大学本科生算法设计与分析2014年春季课程的选读论文之一。【这篇论文中的公式图表太多了...所以有很多部分都是截图...】以下是它的全文翻译：瑞士联邦理工学院快速傅里叶

2014-03-15 16:10:35 2627

原创 openjudge k大数

题目链接：3:k大数总时间限制: 10000ms 内存限制: 655360kB描述求互异整数序列中第k大的数输入第一行一个正整数n第二行一个正整数0输出序列中第k大的数（对于最小的数k=0）【题目分析】这是一个经典的求第K大的数的问题。首先看时间要求，看起来nlog(n)的时间复杂度的算法是可以的。所以首先考虑直接排序

2014-03-11 13:54:25 933

原创 Poj 2299 Ultra-QuickSort

题目链接：Ultra-QuickSort总时间限制: 10000ms 内存限制: 65536kB描述：Ultra-QuickSort算法处理一个由n个不相同整数组成的序列，通过交换序列中相邻两个整数从而使得序列达到升序排列。比如输入：9 1 0 5 4Ultra-QuickSort算法给出输出： 0 1 4 5 9请算出Ultra-QuickSort算法需要进行

2014-03-11 13:38:37 755

原创 openjudge 双数组找中位数

题目链接：1:双数组找中位数总时间限制: 1000ms 内存限制: 1000000kB描述:设A和B都是从小到大已经排好序的n个不等的整数构成的数组，如果把A和B合并后的数组记做C，设计一个算法找出C的中位数。输入:第一行：整数n，0 第二行：n个数，表示数组A第三行：n个数，表示数组B输出:一个整数，表示数组C的中位数

2014-03-11 13:27:45 2275

翻译【翻译】Mathematical Analysis of Algorithms

这是Knuth 的一篇论文，原文下载在这里有：http://download.csdn.net/detail/u013012544/6982095，是北京大学本科生算法设计与分析2014年春季课程的必读论文之一。以下是它的全文翻译：（我的翻译通常采用：达、信、永远不雅的原则...即通常宁可说错话不说人看不懂的话，并且从不考虑所谓的雅，通俗易懂即可...）算法的数学性分析

2014-03-02 15:32:36 12126 5

原创 projecteuler No.100 Arranged probability

题目链接：Problem 100 Arranged probability题目100：要使取到两个蓝碟子的几率是50%需要有多少个蓝碟子？通过人数：7708题目分析：这道题记盘子数为n，蓝盘子为p，则相当于要解方程：n(n-1)=2p(p-1)的第一组使得n>10^12的正整数解的p值。对于这个方程我最开始还是尝试蛮力解，

2014-02-18 20:15:34 1380

原创 projecteuler No.104 Pandigital Fibonacci ends

题目链接：Problem 104 Pandigital Fibonacci ends题目104：找出前九位和后九位数字为pandigital的斐波那契数。通过人数：8537题目分析：这道题就是从斐波那契数列中选择最小的符合条件的项。由于涉及的数比较大，考虑利用java的高精度类。我最初的代码是这样的：BigInteger F[

2014-02-18 13:10:51 892

原创 projecteuler No.66 Diophantine equation

题目链接：Problem 66 Diophantine equation题目66：考察丢番图方程x^2 − Dy^2 = 1。通过人数：9417题目分析：这道题实质上需要面临的是求佩尔方程的最小正整数解。至于接下来的寻找使得最小正整数解最大的方程系数就是比较容易的了。而关于佩尔方程的解法，这篇来自网络的文章较详细地介绍了连分数解法。

2014-02-17 22:26:51 1098

原创 projecteuler No.83 four ways

题目链接：Problem 83 four ways题目83：允许向上下左右移动的情况下从左上角到右下角的最小路径和是多少？通过人数：8961题目分析：前面的两道题都用动态规划做了，而这一问缺是典型的单源最短路径问题，我使用了Dijkstra算法。解题过程（代码仅供参考，因为偷懒，代码风格什么的实在不好意思...）：【原谅我因为偷懒，使用纯c风格写了这

2014-02-17 17:41:01 685

原创 projecteuler No.121 Disc game prize fund

题目链接：Problem 121 Disc game prize fund题目121：考察彩色圆盘的游戏。通过人数：4953题目分析：这道题等价于：15次抽签，每次抽到蓝色的概率分别为1/2~1/16，问最终抽到蓝色比红色多的概率是多少，为多次独立事件求复合的概率问题。而这又等价于求多项式(1/2*x+1/2)(2/3*x+1/3)(

2014-02-17 16:00:56 1516

原创 projecteuler No.90 Cube digit pairs

题目链接：Problem 90 Cube digit pairs题目90：用两个立方体表示平方数的奇怪方式。通过人数：5276题目分析：这道题总情况不多，只有不超过C(10,6)^2 = 44100种情况，蛮力算法完全可行。故直接蛮力枚举筛选计数。解题过程（代码仅供参考，因为偷懒，代码风格什么的实在不好意思...）

2014-02-17 15:45:24 626

原创 projecteuler No.116,117 Red, green, blue tiles

题目链接：Problem 116 Red, green or blue tiles题目116：考察方块的替换方法的数量Problem 117 Red, green and blue tiles题目117：考察使用不同型号的砖块铺满一行的方法。通过人数：NO.116 6169 NO.117 5683题目分析：这两道题都是

2014-02-17 15:32:28 984

原创 projecteuler No.145 How many reversible numbers are there below one-billion?

原文题目链接：http://projecteuler.net/problem=145翻译题目链接：http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/147-14510通过人数：8630题目分析：这道题其实情况数不多，可以对10^9进行枚举，大概几分钟就可以做

2014-02-16 21:57:43 770

原创 projecteuler No.91 Right triangles with integer coordinates

原文题目链接：http://projecteuler.net/problem=91翻译题目链接：http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/92-91通过人数：7727题目分析：这道题为一个枚举筛选的模型。因为一共可以涉及到的点的位置不多，于是依直角顶点的

2014-02-16 21:16:23 815

原创 projecteuler No.78 Coin partitions

原文题目链接：http://projecteuler.net/problem=78翻译题目链接：http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/79-78通过人数：8032题目分析：粗一看，像是一道很经典的动态规划问题。于是我设基本状态(m,n)为m个硬币分n堆放

2014-02-16 16:19:13 1231

原创 projecteuler No.124 Ordered radicals

原文题目链接：http://projecteuler.net/problem=124翻译题目链接：http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/126-124k通过人数：7687题目分析：看起来就是个输入排序检索~很简单~数据量不大，求rad(n)也不用

2014-02-16 13:33:46 629

原创 projecteuler No.120 Square remainders

原文题目链接：http://projecteuler.net/problem=120翻译题目链接：http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/122-120a-1n--a1na2通过人数：7370题目分析：这题比较水，可以作为纯数学题。以下给出数学解法

2014-02-16 13:06:11 861

原创 projecteuler No.77 Prime summations

原文题目链接：http://projecteuler.net/problem=77翻译题目链接：http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/78-77通过人数：9126题目分析：用大脑估算了一下，1000的2、3、5分解的数目就在5000以上，此题答案

2014-02-16 12:24:15 1052

原创 projecteuler No.96 Su Doku

原文题目链接：http://projecteuler.net/problem=96翻译题目链接：http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/97-96通过人数：8333题目分析：哇塞，居然是数独~ 数独高手最鄙视用假设用搜索了~ 所以我才不要用搜索...于是可

2014-02-15 21:41:42 1499

原创 projecteuler No.205 Dice Game

原文题目链接：http://projecteuler.net/problem=205翻译题目链接：http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/208-205通过人数：8100题目分析：粗略来看，是一道概率题，古典概型，基本事件空间有基本事件4^9 *

2014-02-15 00:06:11 1169 2

原创 projecteuler No.80 Square root digital expansion

原文题目链接：http://projecteuler.net/problem=80翻译题目链接：http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/81-80通过人数：9843这道题目和projecteuler No.64 Odd period square roots的内容

2014-02-14 17:09:39 855

原创 projecteuler No.64 Odd period square roots

原文题目链接：http://projecteuler.net/problem=64翻译题目链接：http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/65-6410000通过人数：10607题目分析：粗略来看，是一个计算并统计计算结果的模型。不过计算部分比较复杂，涉及到开方运算。最开始，我只是

2014-02-14 15:27:18 930

原创 projecteuler No.68 Magic 5-gon ring

原文题目链接：http://projecteuler.net/problem=68翻译题目链接：http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54/69-6816题目分析：粗略来看，题目是属于有限种情况的筛选，而情况数比较少，只有10!=3628800种，于是考虑直接枚举排除。

2014-02-13 23:49:43 895

原创关于projecteuler上的题目

projecteuler上的题目挺有意思的，因为不同于一般的OJ平台，在这个平台上只需要最终的结果而无论获得的方式，于是就可以最大程度地发挥做题者和各种做题工具的能力了。这上面的题目很多，我姑且通过通过人数来估算难易，只发通过人数不到10000人的题目吧~毕竟那些简单的题目网上各种东西都不少，不用我来浪费笔墨。我的解题方法一般比较灵活，希望最大地发挥计算机在几秒钟内的计算能力以及人脑的协同

2014-02-13 23:28:41 1043