博文
获取系统硬件信息(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
②交换之后进行递归，分解成小问题，两端的已经交换，所......
贪心算法::启发式搜索（转贴自rickone的blog)(2005-10-05 14:12:00)
摘要：蛮干算法的成功完全是借助于计算机运算的快速，如果问题的解比较少的时候使用起来是比较容易的。但当问题的解比较多，则不宜使用，常用的做法是剪枝，剪枝是一种形象的描述，因为按深搜的算法，图可以描述为与之对应的树或森林，而剪枝的意思就是去掉某些子树，为什么要去掉，这里要用到一个剪枝判断，判断的方法是具体问题具体分析，但是有一点是要考虑到的，剪枝的高效性是建立在判断的额外开销上的，如果这里的开销大，则剪枝只会宣告失败。
而更好的做法是运用“贪心策略”。
【贪心算法】
贪心算法（也叫贪婪算法）不是某种特定的算法，而是一类抽象的算法，或者说只是一种思想，它的具体表现在，对解空间进行搜索时，不是机械地搜索，而是对局部进行择优选取，贪心算法的目的不是为了找到全部解，也当然找不出最优解，而只是找出一种可行解，这样就会得到惊人的高效性。因此，贪心算法也叫启发式搜索，这种启发就是所谓的“贪心策略”。
以马踏棋盘问题为例，问题描述：在国际象棋的棋盘上指定一个初始马位置，一匹马从这个位置出发，经过不重复的走动，直到踏遍整个棋盘，输出一种可行路径。
对8×8的棋盘来说，马踏棋盘的解是一个天文数字，相当之多，而采用蛮干算法，求一个解的时候会非常吃力，因此采用贪心算法。这里选取的贪心策略是，在某个马位置顶点的后继顶点（子结点）中，择优选取那些出口更小的顶点进行搜索，出口的意思就是这个点能跳到的可行位置的路径数，这样的贪心策略是容易被人接受的，一开始往出口少的点跳，则往后出口多的点就多，能跳通的可能性就大，而事实也证明了，如果采用这样的策略在求一个解时几乎不需要回溯，对于更大的棋盘也如此。
C++代码：在（VC6上调试通过）
#include "stdio.h"
class horse
{
public:
horse(int,int);
~horse();
void solve(int,int);
protected:
void dfs(int,int,int);
&nb......
学C++时要注意的（从985837的帖子拷贝过来）(2005-10-05 13:46:00)
摘要：下面的是学C++时要注意的。绝对经典。！！
1.把C++当成一门新的语言学习（和C没啥关系！真的。）；
2.看《Thinking In C++》，不要看《C++变成死相》；
3.看《The C++ Programming Language》和《Inside The C++ Object
Model》,不要因为他们很难而我们自己是初学者所以就不看；
4.不要被VC、BCB、BC、MC、TC等词汇所迷惑——他们都是集成开发环境，而我们要学的是一门语言；
5.不要放过任何一个看上去很简单的小编程问题——他们往往并不那么简单，或者可以引伸出很多知识点；
6.会用Visual C++，并不说明你会C++；
7.学class并不难，template、STL、generic
programming也不过如此——难的是长期坚持实践和不遗余力的博览群书；
8.如果不是天才的话，想学编程就不要想玩游戏——你以为你做到了，其实你的C++水平并没有和你通关的能力一起变高——其实可以时刻记住：学C++是为了编游戏的；
9.看Visual C++的书，是学不了C++语言的；
10.浮躁的人容易说：XX语言不行了，应该学YY；——是你自己不行了吧！？
11.浮躁的人容易问：我到底该学什么；——别问，学就对了；
12.浮躁的人容易问：XX有钱途吗；——建议你去抢银行；
13.浮躁的人容易说：我要中文版！我英文不行！——不行？学呀！
14.浮躁的人容易问：XX和YY哪个好；——告诉你吧，都好——只要你学就行；
15.浮躁的人分两种：a)只观望而不学的人；b)只学而不坚持的人；
16.把时髦的技术挂在嘴边，还不如把过时的技术记在心里；
17.C++不仅仅是支持面向对象的程序设计语言；
18.学习编程最好的方法之一就是阅读源代码；
19.在任何时刻都不要认为自己手中的书已经足够了；
20.请阅读《The Standard C++ Bible》(中文版：标准C++宝典)，掌握C++标准；
21.看得懂的书，请仔细看；看不懂的书，请硬着头皮看；
22.别指望看第一遍书就能记住和掌握什么——请看第二遍、第三遍； ......
如何使应用程序只能创建一个实例(2005-10-05 13:29:00)
摘要：作者：qq590240
1.利用互斥句柄
AppName = "test";
HANDLE m_hMutex = CreateMutex(NULL, FALSE, AppName);
// 检查错误代码
if (GetLastError() == ERROR_ALREADY_EXISTS)
{
// 如果已有互斥量存在则释放句柄并复位互斥量
CloseHandle(m_hMutex);
m_hMutex = NULL;
// 程序退出
return FALSE;
}
2.利用FindWindow()
BOOL IsRun (LPSTR szClassName=NULL, LPSTR szCaption=NULL)
{
HWND Hwnd;
Hwnd = FindWindow (szClassName,szCaption); //通过类名和程序标题查找
if ((int)Hwnd > 0)
//如找到则(int)Hwnd > 0.这是以前写的比较傻.可以写成if(Hwnd).如果没发现程序就会返回NULL
{
ShowWindow (Hwnd,SW_RESTORE); //将程序Restore
SetForegroundWindow (Hwnd); //将程序提到最前
return TRUE;
}
return FALSE;
} ......
不查日历怎么知道任何一天是星期几2 ( 转载）(2005-09-10 14:13:00)
摘要：（声明一下，本文不是我的原创，只是我从网上搜下来的，如果原作者认为不合适，请告诉我删除）
假如，我们再变通一下，把1月和2月当成是上一年的“13月”和“14月”，不仅仍然符合这个公式，而且因为这样一来，闰日成了上一“年”（一共有14个月）的最后一天，成了d的一部分，于是平闰年的影响也去掉了，公式就简化成：
D = [ 13 * (M+1) / 5 ] - 7 + (M-1) * 28 + d． （3≤M≤14） (4)
上面计算星期几的公式，也就可以进一步简化成：
W = (Y-1) + [(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400] + [ 13 * (M+1) / 5 ] - 7 + (M-1) * 28 + d．
因为其中的-7和(M-1)*28两项都可以被7整除，所以去掉这两项，W除以7的余数不变，公式变成：
W = (Y-1) + [(Y-1)/4] - [(Y-1)/100] + [(Y-1)/400] + [ 13 * (M+1) / 5 ] + d．
(5)
当然，要注意1月和2月已经被当成了上一年的13月和14月，因此在计算1月和2月的日子的星期时，除了M要按13或14算，年份Y也要减一。比如，2004年1月1日是星期四，用这个公式来算，有：
W = (2003-1) + [(2003-1)/4] - [(2003-1)/100] + [(2003-1)/400] + [13*(13+1)/5] + 1
= 2002 + 500 - 20 + 5 + 36 + 1
= 2524；
2524 / 7 = 360……4．这和实际是一致的。
公式(5)已经是从年、月、日来算星期几的公式了，但它还不是最简练的，对于年份的处理还有改进的方法。我们先来用这个公式算出每个世纪第一年3月1日的星期，列表如下：
年份： 1(401,801,…,2001) 101(501,901,…,2101)
----......