博文
Center of Gravity(2007-04-27 19:28:00)
摘要：
Center of Gravity
Given a sector of radius R, central angle P. You are to calculate the distance between the center of gravity and the center of the circle.
InputThere multiple test cases. Each case contains only one line containing 2 real numbers R and P(in radian), representing the radius and central angle of the sector. 0<R<=100, 0<P<=2*pi
OutputFor each case, output one line containing the distance between the center of gravity and the center of the circle, accurate to 6 fractional digits.
Sample Input0.01 6.28
Sample Output0.000003
扇形面積之重心，在其所對圓心角之角平分線上，距中心點O之距離為 x。
x=(2.0/3)*r*sin(p)/p;
x=(2.0/3)*r*b/S;
r為扇形之半徑p為扇形所對圓心角之一半（以弧度計） b為弦長,S為弧長
#include<stdio.h>
#include<math.h>
#define PI 3.1415926;
int main()
{
double r,p;
double dis;
while(scanf("%lf%lf",&r,&p)!=EOF)
{
p/=2;
dis=double(((2.0/3)*r*sin(double(p)))/p);
printf("%.6lf\n",dis);
}
return 0;
}......
Number lengths(2007-04-27 10:57:00)
摘要：
Number lengths
N! (N factorial) can be quite irritating and difficult to compute for large values of N. So instead of calculating N!, I want to know how many digits are in it. (Remember that N! = N * (N - 1) * (N - 2) * ... * 2 * 1)
Input:
Each line of the input will have a single integer N on it 0 < N < 1000000 (1 million). Input is terminated by end of file.
Output:
For each value of N, print out how many digits are in N!.
Sample Input: 1
3
32000
Sample Output: 1
1
130271
/*
n!=1*2*3*....*n → lg(n!)=lg(1*2*3*....*n)=lg(1)+lg(2)+ lg(3)+..+lg(n) → n!=10^(lg(1)+lg(2)+ lg(3)+..+lg(n)) */
#include<iostream> #include<cmath> using namespace std; int main() { long n,i; double sum; long temp; while(scanf("%d",&n)!=EOF) { sum=0.0; ......
最大公约数(2007-04-17 10:47:00)
摘要：//求最大公约数int gcd(int a,int b) { if (a%b==0) return b; return gcd(b,a%b);}......
洗牌问题(2007-04-12 14:09:00)
摘要：
设2n张牌分别标记为1, 2, ..., n, n+1, ..., 2n，初始时这2n张牌按其标号从小到大排列。经一次洗牌后，原来的排列顺序变成n+1, 1, n+2, 2, ..., 2n, n。即前n张牌被放到偶数位置2, 4, ..., 2n，而后n张牌被放到奇数位置1, 3, ..., 2n-1。可以证明对于任何一个自然数n，经过若干次洗牌后可恢复初始状态。现在你的的任务是计算对于给定的n的值(n≤10^5)，最少需要经过多少次洗牌可恢复到初始状态。
输入输出格式
输入数据由多组数据组成。每组数据仅有一个整数，表示n的值。对于每组数据，输出仅一行包含一个整数，即最少洗牌次数。
样例输入10
样例输出6
Original: FZUPC 2005
#include <stdio.h>int main(){/*(2＾m)%(2n+1)=1,m即为所求*/ int n,m,temp; int num; while(scanf("%d", &n)!=EOF) { m=1; num=2;temp=n*2; while(num!=1) { if(num<=n)num*=2; else num=num*2-(temp+1); m++; } printf("%d\n", m); } return 0;}
/*数论写法：2^m = 1(mod 2n+1)，C语言写法：(2＾m)%(2n+1)=1 解上述方程，m即为所求。*/......
分解素因子(2007-04-05 12:30:00)
摘要：分解素因子
Time Limit:1s
Memory limit:32M
Accepted Submit:227
Total Submit:439
假设x是一个正整数，它的值不超过65535(即1<x<=65535)，请编写一个程序，将x分解为若干个素数的乘积。
输入输入的第一行含一个正整数k (1<=k<=10)，表示测试例的个数，后面紧接着k行，每行对应一个测试例，包含一个正整数x。
输出每个测试例对应一行输出，输出x的素数乘积表示式，式中的素数从小到大排列，两个素数之间用“*”表示乘法。
输入样例2
11
9828
输出样例11
2*2*3*3*3*7*13
Original: FJNU Preliminary 2005
#include<iostream>#include<cmath>using namespace std;
bool is_prime(int test){ int i; for(i=2;i<test;i++) if(test%i==0)return false; return true;}
int main(){ int n,i,j,k; int *data,divide[100]; while(scanf("%d",&n)!=EOF){ data=new int[n]; for(i=0;i<n;i++)cin>>data[i]; for(i=0;i<n;i++) { if(is_prime(data[i])){cout<<data[i]<<endl;continue;} for(j=2,k=0;j<=data[i];) { if(is_prime(data[i])){divi......
中国剩余定理(2007-04-03 21:48:00)
摘要：我国古代算书《孙子算经》中，有这样一个问题：“今有物不知其数：三三数之剩二，五五数之剩三，七七数之剩二，问物几何．”这个问题一般称孙子问题．这个问题可译成：求被3除余2，被5除余3，被7除余2的最小正整数．《孙子算经》中记载了这个问题的解法，有人将其解法编成歌诀：“三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知．”它的意思是用3除的剩余数乘70，用5除的剩余数乘21，用7除的剩余数乘15，将所得的结果相加再减去105的倍数，即可得所求数．算式是2×70＋3×21＋2×15=233，233－105×2＝23，所以，最小的正整数解是23．这种解法，实际上是特殊的一次同余式组的求解定理．1801年，德国数学家高斯在《算术探究》中明确提出一次同余式组的求解定理．西方数学著作中将一次同余式的求解定理称为中国剩余定理．......
catalan数在数据结构中的应用 (2007-04-03 17:28:00)
摘要：catalan数在数据结构中的应用
什么是catalan数？在网上找了n久，各种关于catalan数列的资料都残缺不堪，弄了半天才理解什么是catalan数。所以干脆自己梳理一番。原理：令h(1)＝1，catalan数满足递归式：h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=2)该递推关系的解为：h(n)=c(2n-2,n-1)/n (n=1,2,3,...)
我并不关心其解是怎么求出来的，我只想知道怎么用catalan数分析问题。我总结了一下，最典型的三类应用：（实质上却都一样，无非是递归等式的应用，就看你能不能分解问题写出递归式了）1.括号化问题。
矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？(h(n)种)
2.出栈次序问题。一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?
类似：有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
3.将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域的方法数?
类似：一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果他从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？
类似：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?
不过下面这个问题似乎不好归类，它怎么来应用这个catalan递归方程呢？你说说：n个结点可构造多少个不同的二叉树? 看的人倒是不少,愿意想一想的倒是不多,唉
h(n)=c(2n-2,n-1)/n 是什么意思哈 C代表什么呀
c代表组合数,即2n-2个体种选取n-1个的种类
re: catalan数在数据结构中的应用 2006-11-10 13:19
不过好像有些问题还不是那么好处理呵 例如“有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多......
重要定理和公式(2007-04-03 17:25:00)
摘要：重要定理和公式
一、常见递推关系
1.Fibonacci 数列
A(1)=1; A(2)=1;
A(n)=A(n-1) + A(n-2);
2.Catalan数：
考虑具有n个结点不同形态的二叉树的个数 H(n)
H (0) = 1;
H (n) = H (0) H (n-1) + H (1) H (n-2) + H (2) H (n-3) … + H (n-2) H (1) + H (n-1) H (0) ;
-> H (n) = (1/ (n+1)) * C (n, 2n)
3. 第二类Stirling数：
s(n,k)表示含n个元素的集合划分为k个集合的情况数
A.分类：集合{An}存在，则有s(n-1,k-1); 不存在则An和放入k个集合中的任意一个，
共k*s(n-1,k)种。
0 (k=0 or n<k)
s(n,k)={
s(n-1,k-1)+k*s(n-1,k) (n>k>=1)
*:求一个集合总的划分数即为 sigema(k=1..n) s(n,k) .
4．数字划分模型
*NOIP2001数的划分
将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。
d[0,0]:=1;
for p:=1 to n do
for i:=p to n do
for j:=k downto 1 do inc(d[i,j],d[i-p,j-1]);
writeln(d[n,k]);
*变形1：考虑顺序
d[ i, j] : = d [ i-k, j-1] (k=1..i)
*变形2：若分解出来的每个数均有一个上限m
d[ i, j] : = d [ i-k, j-1] (k=1..m)
5．错位排列
d[1] = 0; d[2] = 1;
d[n] = (n-1) * (d[n-1] + d[n-2])
6.
二、图论与计算几何
1．度边定理： sigema di = 2*E
2．.三角形面积
|x1 y1 1|
s=|x2 y2 1|=x1y2+x2y3+x3y1-x3y2-x2y1-x1y3
|x3 y3 1|
*海......
进制转化(2007-04-01 16:06:00)
摘要：R进制转化成十进制 公式： 举例： 101.101(B)= 1*22+0*21+1*20+1*2-1+0*2-2+1*2-3 = 4+0+1+0.5+0+0.125 = 5.625 715(O)= 7*82+1*81+5*80 = 461 A01B(H)= 10*163+0*162+1*161+11*160 = 40987 2、十进制转化成 r 进制 方法： 整数部分：除以 r取余数，直到商为0，第一个余数是r进制数的最低位，最后的余数是最高位。 小数部分：乘以 r取整数，第一个整数是r进制数的最高位，最后的整数是最低位。 举例： 100.345(D)=1100100.01011(B) 100(D)=144(O)=64(H) 2 |100 余数 0.345 取整 8 |100 2 |50 余0 最低位 * 00002 8 |12 余4 最低位 2 |25 余0 0.690 0 最高位 8 |1 余4 2 |12 余1 * 00002 2 |0 余1 最高位 2 |6 余0 1.380 1 2 |3 余0 * 00002 16 |100 2 |1 余1 0.760 0 16 |6 余4 最低位 0 余1 最高位 * 00002 16 |0 余6 最高位 2 | 1.520 1 * 00002 01.04 1 最低位 100(D)=144(O)=64(H)=1100100(B) 3、八进制和十六进制转化成二进制 每一个八进制数对应二进制的三位。每一个十六进制数对应二进制的四位。 2C1D(H)= 0010 1100 0001 1101(B) 7123(O)= 111 001 010 011(B) 2 C 1 D 7 1 2 3 4、二进制转化成八进制和十六制 整数部分：从右向左进行分组。小数部分：从左向右进行分组。 转化成八进制三位一组。 转化成十六进制四位一组。位数不足一组时用零补够。 11 0110 1110. 1101 01(B) 0011 0110 1110. 1101 0100(B) =36F.D4(H) 3 6 F D 4 1 101 101 110. 110 1(B) 001 101 101 110. 110 100(B) =1556.64(O) 1 5 5 6 6 4......
进制转化(2007-04-01 16:04:00)
摘要：进制转化
Time Limit:1s
Memory limit:32M
Accepted Submit:18
Total Submit:26
输入十进制数n（0<=n<=10000），请输出它对应的k（2<=k<=36）进制数。
10,11…分别用A, B … 代替。
输入数据
本题有多组输入数据，你必须处理到EOF为止.
每组数据占一行，有2个整数n,k
输出数据
输出n对应的k进制数，一个数一行。
输入样例3 2
4 3
15 16
输出样例11
11
F
Original: FOJ月赛-2007年3月
#include<iostream>using namespace std;
void ten_to_r(int n,int r,char a[]){ int i,temp=1; char c; if(n==0){a[0]='0';a[1]='\0';} else{ for(i=0;n!=0;i++) { temp=n%r; n/=r; c=char(temp); if(temp>=10)c+=55; else c+=48; a[i]=c; } a[i]='\0'; }}
int main(){ int n,r,i; char a[100000]; while(scanf("%d%d",&n,&r)!=EOF) { ten_to_r(n,r,a); for(i=strlen(a)-1;i>=0;i--) cout<<a[i]; cout<......