博文
大数阶乘(2005-11-10 20:12:00)
摘要：// 可以计算1～20000的阶乘。在PIII 1.13G CPU上计算20000！约需2.2秒。
#define nRadix 100000
#define MAXSIZE 16000
long in[MAXSIZE]= {0};
void fact(long n)
{
long m_nPrecision = 1;
long temp;
long carry = 0;
int i;
for(i=0; i<MAXSIZE; ++i)
in[i] = 0;
in[0] = 1;
for(i=2; i<=n; ++i)
{
for(long j=0; j<m_nPrecision; j++)
{
temp = in[j]*i+carry;
carry = temp / nRadix;
in[j] = temp - carry * nRadix;
}
temp = carry;
while(temp > 0)
{
carry = temp / nRadix;
in[m_nPrecision++] = temp-carry*nRadix;
temp = carry;
}
}
}......
Divisibility(2005-11-06 20:11:00)
摘要：（题目来自http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1745）
#include <stdio.h>
#include <math.h>
long abs_sum(long nums[], long nCount);
bool Knap(long nums[], long nCount, long k)
{
if(nCount == 0)
{
if(k == 0)
{
return true;
}
else
{
return false;
}
}
else
{
bool bRet = Knap(nums, nCount-1, k - nums[nCount-1]);
if(bRet == true)
{
return true;
}
else
{
bRet = Knap(nums, nCount-1, k + nums[nCount-1]);
if(bRet)
{
nums[nCount-1] *= -1;
}
return bRet;
}
}
}
long abs_sum(long nums[], long nCount)
{......
统计并输出能被3整除或能被5整除或能被7整除的所有三位数(2005-11-06 20:01:00)
摘要：long Div357_m(long m, long n)
{
long count = 0;
int start, end;
static int inc[16] = {0, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 6, 7, 8, 8};
int i;
start = (m/3+1)*3;
for(i=start; i<=n; i+=3)
{
++count;
}
start = (m/15+1)*15+1;
end = n/15*15;
for(i=start; i<=end; i+=15)
{
count += 2;
}
long temp = start - m;
if(temp <= 5)
;
else if(temp <= 10)
{
......
求若干个整数的最小公倍数(2005-10-28 13:43:00)
摘要：#include <assert.h>
template <class T>
__inline void Swap(T &a, T &b)
{
T t;
t = a;
a = b;
b = t;
}
// 辗转相除法求最大公约数
template <class T>
__inline T GCD(T m, T n)
{
assert(m >= 0 && n >= 0);
if(m == 0)
return n;
if(n == 0)
return m;
if(m < n)
{
Swap(m, n);
}
T d = m % n;
while(d > 0)
{
m = n;
n = d;
d = m % n;
}
return n;
}
#include <stdio.h>
#include <time.h>
#include <conio.h>
int main()
{
long x[100];
long n;
printf("Input the number of numbers: ");
scanf("%d", &n);
printf("Input %d numbers: ", n);
for(int i=0; i<n; ++i)
scanf("%d", x+i);
......
获取系统硬件信息(2005-10-09 08:52:00)
摘要：转自http://www.programfan.com/club/showbbs.asp?id=94578
#include <STDIO.H>
#include <WINDOWS.H>
void main( void )
{
unsigned long ProcSpeed = 0;
HKEY hKey;
LONG rt = RegOpenKeyEx( HKEY_LOCAL_MACHINE, "HARDWARE\\DESCRIPTION\\System\\CentralProcessor\\0", 0, KEY_READ, &hKey);
if( ERROR_SUCCESS == rt )
{
unsigned long buflen = sizeof( ProcSpeed );
RegQueryValueEx( hKey, "~MHz", NULL, NULL, (LPBYTE)&ProcSpeed, &buflen );
RegCloseKey(hKey);
}
if( 0 != ProcSpeed )
printf( "%ldMHz\n", ProcSpeed );
else
&n......
支票兑换问题(2005-10-08 21:54:00)
摘要：转自http://community.csdn.net/Expert/topic/3969/3969800.xml?temp=.384289
Problem Description:
There are three kinds of coins:1$,2$,3$.Given a chique of N$(0<n<=10^9),calculate the number of different ways to exchange the cheque.
Sample Input:1 2 3
Sample Outpt:1 2 3
也就是说，将N$的支票换为1$,2$,3$三种硬币，问有多少种换法?
1. gxqcn
记 #{A}表示集合 A 中元素的个数。以下 N 表示非负整数集。
S = #{(a,b,c)|3a+2b+c=M (a、b、c∈N)}
= #{(a,b)|3a+2b≤M (a、b∈N)}
= #{(a,b)|0≤b≤(M-3a)/2 (a、b∈N)}
(1)、当 M=2k(k∈N) 时，
S = #{(a,b)|0≤b≤k-(3a)/2 (0≤a≤[M/3], a、b∈N)}
(1.1)、当取 a=2t(t∈N) 时，
S1 = #{(b,t)|0≤b≤k-3t (0≤t≤[M/6], b、t∈N)}
(1.2)、当取 a=2t+1(t∈N) 时，
S2 = #{(b,t)|0≤b≤k-3t-2 (0≤t≤[(M-3)/6], b、t∈N)}
显然 S = S1 + S2，这里 S1、S2 可直接推导出公式来。
(2)、当 M=2k+1(k∈N) 时，同理类推。。。
也就是说，本题通过简单的数论和代数知识，直接得到公式，可以避免任何循环。
2. mathe()
long Par......
大数乘法的三分方法(2005-10-08 21:37:00)
摘要：转自http://community.csdn.net/Expert/topic/4142/4142949.xml?temp=.8473169
将u分成u1,u2,u3三段，v分成v1，v2，v3三段
只需五次乘法，分别：
u1*v1
u3*v3
（u1+u2+u3）*（v1+v2+v3）
（u1-u2+u3）*（v1-v2+v3）
（u1-2*u2+2*u3）*（v1-v2+v3）
通过这五个即可得到u*v
......
称小球问题的数学证明（转贴自rickone的blog)(2005-10-05 14:18:00)
摘要：转自CSDN]由网友feng5166(枫之羽)间接提供
【问题描述】
十三个球看上去一模一样，但其中一个质量不同（不知道是重了还是轻了），现在有一个天平，要求给出一种操作的方法，使得在不超过三次之内把这个球找出来（排除一切偶然情况），给出必胜策略。
【推广到N个小球】
有N个小球外形无区别，但是有一个在质量上与其他的球不一样。用天平称最少m次一定将不同的球找出来。显然随N增大，m不会减小。现在想解决的问题是对于任何给定的次数m,找出在该次数下能解决的最大的N值,用Nmax来表示。并给出对应于(Nmax,m)的一种解法。
【关于所能解决的上限】
现在来求m次所能解决的上限Nmax(m)问题。
为解决这个问题，我们给出几个引理。
引理一：无论加上什么其他的附加条件，只要k个球中的任一个都有可能是坏球（概率不
为0），则当k>3^L时，称L次是称不出来的。这里的附加条件包括已知坏球是否重于好球,
除k个未知球外还提供若干个标准球，以及k个球中某些的质量和大于另外一些的和等等，
只要在这些条件下k个球中的任一个都还有可能是坏球就可以是引理所说的附加条件。
证明：很显然，若k>3^L，则哪个球是坏球一共有k中情况，而称L次一共有3^L种情况，
由k>3^L知不可能一定分辨出哪个球是坏球。
引理二：如果另外在提供任意多个标准球（即在N个未知球外还任给标准球作"砝码"用）?br /> 则称m次最多能从N1max(m)=(3^m+1)/2个球中找出坏球来。
证明：对该引理的证明可以采用数学归纳法。
当m=1时，显然若只有两个球，则任挑一个与另外的标准球比较（额外提供的，不是
两个中的），若相等则是剩下那一个，若不等则是这一个。所以N1max(1)>=2。
而对于三个球的情况，如果第一次称用了两个或三个未知球，则无法判断出用
过的球中谁是坏球（只称一次），而如果第一次称只用了一个未知球，则剩下
的两个球无法区分。因此一次不能解决三个球的问题。所以N1max(1)<3。
由N1max(1)<3和N1max(1)>=2知，N1max=2。
设当m<=k-1时命题都成......
穷举搜索::回溯与深搜（转贴自rickone的blog)(2005-10-05 14:14:00)
摘要：计算机常用算法大致有两大类，一类叫蛮干算法，一类叫贪心算法，前者常使用的手段就是搜索，对全部解空间进行地毯式搜索，直到找到指定解或最优解。
【建立解空间】
问题的解应该如何描述，如何建立？借助图论的思想，我们可以用图来描述，图的定义为G<V,E>，由顶点集和边集构成，顶点即实实在在的数据、对象，而边可以抽象为关系，即顶点间的关系，这种关系不一定非要在数据结构上表现出来，用数据结构的语言来描述，如果关系是一对一，则为线性表，如果关系是一对多，则为树，如果关系是多对多，则为图，如果完全没有关系，则为集合。但在数据结构中这种关系不一定非要在数据的存储性质上一开始就表现出来，譬如，你可以用一个数组表示一个线性表，也可以表示完全二叉树，同样也可以用邻接表表示一个图，对于关系的描述不是数据结构本身的描述，而是算法的描述，正如数据结构是离不开特定的算法一样，不可分开单独而谈。描述了解，那如何建立解空间，即如何对图进行搜索？
【深度优先搜索】
(Depth First Search)是用栈的机制对图的顶点进行深度优先的搜索。简易流程如下：
DFS(V0（起始顶点）)
访问V0
for(v=V0的第一个子结点 到 最后一个子结点（边所对的顶点））
如果v未被访问，DFS(v);
搜索过程是先往结点深处搜索，一旦有子结点未访问就向下遍历。这样的方法类似回溯算法，先往下试探，如果不行出退回（回溯）。
【回溯】
回溯的经典例子是8皇后问题。
例：在国际象棋地图上（8×8）放上8个皇后，使任意两个皇后都不在同一行或同一列或同一斜行，找出所有解。
每一个皇后的位置可以认为是一个顶点，而皇后之间不在同一行或同一列或同一斜行的性质认为是顶点之间的关系，我们可以用回溯试探的方法考虑：先依次试探每一个皇后的位置，如果有不满足条件的情况则退回，直到完成所有解的计数和输出。
用数组存储：int pos[8];
pos[0]表示第一个皇后的位置（0,1,...7)依次类推。
流程：
dfs(c)//c从0开始
for(v=0;v<8;++v)
如果pos[c]:=v满足条件，dfs(......
分治的实现::递归程序设计（转贴自rickone的blog)(2005-10-05 14:13:00)
摘要：【分治算法】
是一种思想，你拿到的问题往往不会是很简单的事情，而再复杂再难的问题都可以分解成一些有限的简单问题的和，这就是分治法的原理。
举个最简单的例子，计算阶乘之和n!+(n-1)!+...+1!：
n可以取大取小，问题的范围可以大可以小，如果小就比较容易，比如1！=1这是己知，如何将大问题化成小问题，找它们之间的联系：
如果n=k已经解决，那么n=k+1能否解决，如何解决？
很显然：n=k+1的情况就是将n=k的结果加上(k+1)!的值。
【递归程序设计】
是一种算法常用设计方法，在高级语言中，函数之间可以进行嵌套调用，用栈的机制实现，这样的做法可以使我们在算法设计的时候能够达到套调算法设计。
int facsum(int n)
{
if(n==1)return 1;
return fac(n)+facsum(n-1);
}
/*fac()为求阶乘函数，facsum()为阶乘求和函数*/
“if(n==1)return 1;”为小问题、简单问题解的直接描述，在递归中称为递归边界，没有设定边界的递归是只能‘递’不能‘归’的，即死循环。
“return fac(n)+facsum(n-1);”中将n的范围缩小：n-1，以此将大问题化为类似的小问题，类似很重要，如果不类似就不能调同一个函数，这很显然。——这样一个过程就是分治算法的实现。
[阶乘求和可以用更高效率的算法求解，以上只是做为一个简单例子]
再举一例，将数组的元素逆置：
void inverse(int a[],int n)
{
if(__①__)return;
swap(a[0],a[n-1]);/*swap(a,b)为交换a,b的值*/
inverse(__②__);
}
①处为小问题解描述，也是递归边界，怎样的小问题是很显然的呢？当数组的元素个数小于2时是不需要逆置的，所以填：n<2
②交换之后进行递归，分解成小问题，两端的已经交换，所......