博文
杂类集(2007-02-03 21:17:00)
摘要： Great Common Divisor最大公约数
n1.Euclid算法
重复gcd(a,b) = gcd(a,b mod a)至b mod a等于0 ，
gcd(b,0)=b, b最后的取值为a,b初值的最大公约数
2.stein算法
1.
1.如果A=0，B是最大公约数，算法结束
2. 如果B=0，A是最大公约数，算法结束
3. 设置A1 = A、B1=B和C1 = 1
4. 如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(乘2整数左移一位，除2整数右移一位即可)
5.
5.如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (显然，2不可能为任何奇数的约数)
6.
6.如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (同上J)
7. 如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn
8. n++，转4
注：、Cn为两数最大公约数
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
给定两个任意正整数n和任一质数p,求将n!表示成算术基本定理的形式的时候，p的指数．
count=0;
while(n)
{
count+=n/p;
n/=p;
}
cout<<count<<endl;
......
计算几何算法概览(转)(2006-09-06 21:28:00)
摘要：
怒火之袍
计算几何算法概览
一、引言
计算机的出现使得很多原本十分繁琐的工作得以大幅度简化，但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案，比如几何问题。作为计算机科学的一个分支，计算几何主要研究解决几何问题的算法。在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中，我们将对计算几何常用的基本算法做一个全面的介绍，希望对您了解并应用计算几何的知识解决问题起到帮助。
二、目录
本文整理的计算几何基本概念和常用算法包括如下内容：
矢量的概念
矢量加减法
矢量叉积
折线段的拐向判断
判断点是否在线段上
判断两线段是否相交
判断线段和直线是否相交
判断矩形是否包含点
判断线段、折线、多边形是否在矩形中
判断矩形是否在矩形中
判断圆是否在矩形中
判断点是否在多边形中
判断线段是否在多边形内
判断折线是否在多边形内
判断多边形是否在多边形内
判断矩形是否在多边形内
判断圆是否在多边形内
判断点是否在圆内
判断线段、折线、矩形、多边形是否在圆内
判断圆是否在圆内
计算点到线段的最近点
计算点到折线、矩形、多边形的最近点
计算点到圆的最近距离及交点坐标
计算两条共线的线段的交点
计算线段或直线与线段的交点
求线段或直线与折线、矩形、多边形的交点
求线段或直线与圆的交点
凸包的概念
凸包的求法
三、算法介绍
矢量的概念：
如果一条线段的端点是有次序之分的，我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点，我们可以把它称为矢量(vector)p2。
矢量加减法：
设二维矢量P = ( x1, y1 )，Q = ( x2 , y2 )，则矢量加法定义为： P + Q = ( x1 + x2 , y1 + y2 )，同样的，矢量减法定义为： P - Q = ( x1 -......
POJ2800，Joseph's Problem解题报告(2006-07-28 14:48:00)
摘要： 题目很简单，你的解答也很简单：
int calc(int n,int k){
int ret = 0,i;
for (i = 1; i <= n; i++)ret += k%i;
return ret;}
可是，它怎么就超时了呢？
注意约束条件：
The input file contains n and k(1<= n,k <= 10^9).
n的最大值是10^9。。。。你的程序不超时才怪呢？
O(n)的算法，还能怎么优化呢？
对给定的K，所求为不大于n的所有正整数除K的余数r1,r2,......,rn的总和。假设它们对应的商为s1,s2,.....,sn.
注意到，商的可能取值只有O(sqrt(n))种情况，对每个可能的商的值，k%i成等差数列。容易看出，此问题的解的时间复杂度不大于O(sqrt(n)).
分析，解决问题
对N，K比较小的情况，写出具体的余数和商数表。
观察，分析这个表格。
现在，你能否为本问题设计出复杂度为O(sqrt(n))的算法？......
(转)ACM竞赛之新人向导(2006-07-21 17:15:00)
摘要：刚刚接触信息学领域的同学往往存在很多困惑，不知道从何入手学习，在这篇文章里，我希望能将自己不多的经验与大家分享，希望对各位有所帮助。 一、语言是最重要的基本功
无论侧重于什么方面，只要是通过计算机程序去最终实现的竞赛，语言都是大家要过的第一道关。亚洲赛区的比赛支持的语言包括C/C++与JAVA。笔者首先说说JAVA，众所周知，作为面向对象的王牌语言，JAVA在大型工程的组织与安全性方面有着自己独特的优势，但是对于信息学比赛的具体场合，JAVA则显得不那么合适，它对于输入输出流的操作相比于C++要繁杂很多，更为重要的是JAVA程序的运行速度要比C++慢10倍以上，而竞赛中对于JAVA程序的运行时限却往往得不到同等比例的放宽，这无疑对算法设计提出了更高的要求，是相当不利的。其实，笔者并不主张大家在这种场合过多地运用面向对象的程序设计思维，因为对于小程序来说这不旦需要花费更多的时间去编写代码，也会降低程序的执行效率。
接着说C和C++。许多现在参加讲座的同学还在上大一，C的基础知识刚刚学完，还没有接触过C++，其实在赛场上使用纯C的选手还是大有人在的，它们主要是看重了纯C在效率上的优势，所以这部分同学如果时间有限，并不需要急着去学习新的语言，只要提高了自己在算法设计上的造诣，纯C一样能发挥巨大的威力。
而C++相对于C，在输入输出流上的封装大大方便了我们的操作，同时降低了出错的可能性，并且能够很好地实现标准流与文件流的切换，方便了调试的工作。如果有些同学比较在意这点，可以尝试C和C++的混编，毕竟仅仅学习C++的流操作还是不花什么时间的。
C++的另一个支持来源于标准模版库（STL），库中提供的对于基本数据结构的统一接口操作和基本算法的实现可以缩减我们编写代码的长度，这可以节省一些时间。但是，与此相对的，使用STL要在效率上做出一些牺牲，对于输入规模很大的题目，有时候必须放弃STL，这意味着我们不能存在“有了STL就可以不去管基本算法的实现”的想法；另外，熟练和恰当地使用STL必须经过一定时间的积累，准确地了解各种操作的时间复杂度，切忌对STL中不熟悉的部分滥用，因为这其中蕴涵着许多初学者不易发现的陷阱。
&nb......
动态规划习题（一）(2006-07-17 20:26:00)
摘要：题目如下：
最大的和
一天，笨笨带着一道题目找到了你，希望你能帮她解决这道题目：
给你n个数a[1], a[2], ..., a[n]，(0<n<=16,000, -1,000<=a[i]<=1,000)和0<L1<=L2<=n 求长度在[L1,L2]的连续若干个数a[i], a[i+1], ..., a[j], (即L1<=j+1-i<=L2) 使得a[i]+a[i+1]+...+a[j]取到最大值, 你只需要输出那个最大值即可。
由于n非常大，所以笨笨就算数学再好也无法很好的解决这道题目。这下该看你的了，身为计算机小组的你，应该能轻松搞定这道题目吧。
输入文件：
输入文件第一行为三个整数n，L1， L2， 接下来是用空格或者换行符隔开的n个数, 第i个数表示a[i]。
输出文件：
仅一个数，表示a[i]+a[i+1]+...+a[j]的最大值。
Sample Input
5 3 4
3 -1 -2 5 3
Sample Output
6
分析：这是一道求最值问题的试题。首先很自然就想到用动态规划思想。于是小弟就试着用这种思想去试试。程序如下：
#include <iostream>using namespace std;
int N,l1,l2;int a[16000];int num[16000]; //当前取最大值时所包含的连续的元素个数 int maxValue[16000]; //第i个元素的最大值
int f(int n)//第n个元素的最大值，即为状态 { if (n == 1) { num[n] = 1; return maxValue[n] = a[1]; } &......
动态规划之PKU1088(2006-06-24 15:15:00)
摘要：题目如下：（来源于http://acm.pku.edu.cn/JudgeOnline/problem?id=1088）
滑雪
DescriptionMichael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。
Input输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。
Output输出最长区域的长度。
Sample Input5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
Sample Output25
SourceDon't know
这是一道很简单的题，用DP很容易就AC了。
以下是我的代码：#include <iostream>
using namespace std;
int height[100][100],maxLen[100][100];
int row,col;
int maxLength(int i,int j)
{
if (maxLen[i][j] != 0)return maxLen[i][j];
int left,right,up,down,maxLR,maxUD;
left = right = up = down = 1;
if (j-1 >= 0)
if (height[i][j-1] >......
动态规划思想(2006-06-24 12:20:00)
摘要： 动态规划是解决一类包含了状态转化和状态转移关系，具有最优子问题性质的，求取状态参量的确定值或最优值的算法
动态规划，最简单的例子
o台阶问题
n某人上台阶，一次走1阶或者2阶 问从地面上至第n个台阶，共有多少种不同的走法？ 状态方程：f(n)=f(n-1)+f(n-2) 数列：1 1 2 3 5 8 13 21 34 55 89 144 233……
o程序：
int a[n]={1,1};
for(int i=2;i<n;++i)a[i]=a[i-1]+a[i-2];
动态规划，基本框架
1.1.划分给定问题为若干不同的阶段，并且用统一的方式表示出每个阶段的状态。
2.2.按照某种无后效性的规则选择状态。
3.确定状态决策和转移，更新状态列表。
4.3.是否已经遍历了整个状态空间？是则终止，否则转向步骤2
5.4.至此，状态列表中保存了所有的最优子问题的解。
......