博文
人工智能(2007-03-30 22:30:00)
摘要：
八数码问题—A*搜索
先把问题简化一下吧：
在控制台显示这样一个矩阵
[1][2][3]
[8] [4]
[7][6][5]
手动把它打乱，然后让程序将其复原。
和野人传教士问题类似，这也是一个对解空间进行搜索的问题，而且更为简单，这次采用可以缩减扩展节点的规模的A*启发式搜索算法。取节点深度为g(x)，错位的数字数为h(x)，由于问题很简单，所以与有序搜索算法类似，算法框图：
评价函数封装在类里，所以没显示在框图中。
ElemType类包括了对于状态节点所需的所有操作：显然的，用一个一维数组maze[9]保存这九个位置的数，评价函数evaluate()函 数返回当前状态的评价值，对节点进行操作的运算符">>"，判断是否是最终节点的isSuccess()，以及打乱初始节点的顺序的 disrupt()等等。
#include <iostream>
#include <conio.h>
#include <windows.h> //显示矩阵时需要延时，这里有Sleep()函数。
using namespace std;
//接收键盘时使用
const enum Input { UP = 0x048, DOWN = 0x050, LEFT = 0x04b, RIGHT = 0x04d, ENTER = 0xd };
//扩展时判断方向使用
const int U = 0;
const int D = 1;
const int L = 2;
const int R = 3;
class ElemType {
private:
int depth; //当前节点的深度（就是距离初始节点有多远）
int numWrong(); //有多少错位的数字
public:
int maze[9]; &n......
用C语言实现八数码问题 (2007-03-30 22:28:00)
摘要：
#include<stdio.h>
#include<conio.h>
int n,m;
typedef struct Node
{
char matrix[10];/*存储矩阵*/
char operate;/*存储不可以进行的操作，L代表不能左移R代表不能右移U代表不能上移D代表不能下移*/
char extend;/*是否可以扩展，Y代表可以，N代表不可以*/
int father;/*指向产生自身的父结点*/
}Node;
char start[10]={"83426517 "};/*此处没有必要初始化*/
char end[10]={"1238 4765"};/*此处没有必要初始化*/
Node base[4000];
int result[100];/*存放结果的base数组下标号，逆序存放*/
int match()/*判断是否为目标*/
{
int i;
for(i=0;i<9;i++)
{
if(base[n-1].matrix[i]!=end[i])
{
return 0;
}
}
return 1;
}
void show()/*显示矩阵的内容*/
{
int i=1;
while(m>=0)
{
int mm=result[m];
clrscr();
printf("\n\n\n http://www.zhensoft.com ZHEN SHI LEI\t\tStep %d",i);
printf("\n\n\n\n\n\t\t\t%c\t%c\t%c\n",base[mm].matrix[0],base[mm].matrix[1],base[mm].matrix[2]);
&nbs......
A*算法求八数码问题总结 (2007-03-30 22:25:00)
摘要：
A*算法求八数码问题总结
最近在PKU的ACM上做了八数码问题，将经验总结以下：
（1） 用A*算法， 估价函数选“Hamilton距离”比选用“在错误方各内的数字数目”强很多。
（2）A*算法的关键是要能够使“找到耗费最小的节点”和“判断是否子节点已经存在”的算法的效率尽可能高，为此，网上不少资料建议采用Binary Heap或Hash table等数据结构，然而单独使用任何一种数据结构，都有一定的缺陷，将Heap和Hash联合起来使用，应该可以提高不少效率。具体如下：
1。建一张Hash表，存放没一个节点的具体信息，如当前状态、父节点在表中的位置等。
2。open表中存放着一些节点，这些节点不同于Hash表中的节点，可以将它理解为是Hash表中节点的索引，它只包含节点的估价和节点在Hash表中的位置，这些节点按估价排列成堆（Heap）。
3。没必要再建一个closed表。
这样，程序的流程就可以写成：
初始化Hash表和open表；
将根节点放入Hash表和open表；
found = false;
while(open表不空) {
从open表中得到耗费最低的节点的索引cur; // O(1)
从open表中删除耗费最低的节点; // O(logN)
for 每个cur的子节点now do {
if ( now 是目标节点 ) {
打印输出;
&n......
求素数问题(2007-03-30 12:10:00)
摘要：求素数问题
求素数问题（很典型的问题）
以下是求解素数的三种方法，大家可以按照算法写出程序代码。
【1】求10000以内的所有素数。
素数是除了1和它本身之外再不能被其他数整除的自然数。由于找不到一个通项公式来表示所有的素数，所以对于数学家来说，素数一直是一个未解之谜。像著名的哥德巴赫猜想、孪生素数猜想，几百年来不知吸引了世界上多少优秀的数学家。尽管他们苦心钻研，呕心沥血，但至今仍然未见分晓。
自从有了计算机之后，人们借助于计算机的威力，已经找到了2216091以内的所有素数。
求素数的方法有很多种，最简单的方法是根据素数的定义来求。对于一个自然数N，用大于1小于N的各个自然数都去除一下N，如果都除不尽，则N为素数，否则N为合数。
但是，如果用素数定义的方法来编制计算机程序，它的效率一定是非常低的，其中有许多地方都值得改进。
第一，对于一个自然数N，只要能被一个非1非自身的数整除，它就肯定不是素数，所以不
必再用其他的数去除。
第二，对于N来说，只需用小于N的素数去除就可以了。例如，如果N能被15整除，实际
上就能被3和5整除，如果N不能被3和5整除，那么N也决不会被15整除。
第三，对于N来说，不必用从2到N一1的所有素数去除，只需用小于等于√N(根号N)的所有素数去除就可以了。这一点可以用反证法来证明：
如果N是合数，则一定存在大于1小于N的整数d1和d2，使得N=d1×d2。
如果d1和d2均大于√N，则有：N＝d1×d2>√N×√N＝N。
而这是不可能的，所以，d1和d2中必有一个小于或等于√N。
基于上述分析，设计算法如下：
(1)用2，3，5，7逐个试除N的方法求出100以内的所有素数。
(2)用100以内的所有素数逐个试除的方法求出10000以内的素数。
首先，将2，3，5，7分别存放在a[1]、a[2]、a[3]、a[4]中，以后每求出一个素数，只要不大于100，就依次存放在A数组中的一个单元中。当我们求100—10000之间的素数时，可依次用a[1]－a[2]的素数去试除N，这个范围内的素数可以不保存，直接打印。
【2】用筛法求素数。
简单介绍一下厄拉多塞筛法。厄拉多塞是一......
求素数法(2007-03-30 12:10:00)
摘要：
求素数法
求素数法
素数是大于１的整数，除了它本身和１以外，不能被正整数所整除.也称作“质数”.
在欧几里得的《几何原本》中，给出了素数的定义为只能被单位量除尽的数。另外还给出了算术基本定理，即如果Ａ是素数Ｐ、Ｑ…的乘积，那么将Ａ分解成素数乘积的方法是惟一的。在《几何原本》中，已经得出素数的个有选举权是无限的。
与欧几里得同时代的数学家埃拉托色尼首先给出了求素数的方法，现在人们称之为“埃拉托尼筛子”。他求素数的方法如下。
他首先从２开始，写出自然数：２，３，４，５，６，７，８，９…１００，然后，把其中的一切合数划去，划掉合数的原则是，在这一列数中，第一个数２满足素数的定义，把它保留下来。随后把能被２整除的数都划去，因为它们都是合数。接着在数２后的没有被划去的第一个数是３，因为它只被１和它本身整除，所以它是一个合数，把它也划去。剩下没有被划去的第一个有选举权是５，它只能被这和它本身整除，所以它也是一个素数。如此连续不断地划下去，最后剩下的数都是素数。
为什么把这种方法叫做“厄拉多塞筛子”呢？因为厄拉多塞在求素数时，把自然数写在一块白蜡的木板上，并逐个在写着合数的位置上刺一个孔，这样白蜡板上被刺了很多的小孔，好像一个筛子。把所有的合数“筛掉”剩下的就都是素数。
用“厄拉多塞筛子”可得到１００以内的２５个素数：２，３，５，７，１１，１３，１７，１９，２３，２９，３１，３７，４１，４３，４７，５３，５９，６１，６７，７１，７３，７９，８３，８９，９７。
后来由于素数没有多少用处，所以数学家们就把求素数的方法“束之高阁”。直到１７世纪解析几何与微积分兴起后，许多数学家又开始对整数论进行探讨，所以对素数的研究又提到了议事的日程上，而且取得很大进展。
从厄拉多塞筛子可以得到一个复杂的公式，如果已知小于√Ｎ的素数，它能确定小于Ｎ的素数的数目，１８７０年德国人梅塞尔对此作了改进，成功地证明了１０ 8的素数是５７６１４５５个。１８９３年丹麦人贝特森证明了10 9的素数是５０８０７４７８个，１９５９年，美国数学家莱麦成功地证明了10 ９的开绿灯数应该是５０８４７５３４个，并且得到了１０ 10的素数是４......
二十世纪数学家排名(前100位): (2007-03-30 12:09:00)
摘要：二十世纪数学家排名(前100位):
点击数：8 发布日期：2007-3-29 23:04:00
【收藏】 【评论】 【打印】 【编程爱好者论坛】 【关闭】
二十世纪数学家排名(前100位):
1,A.N.Kolmogorov
2,H.Poincare
3,D.Hilbert
4,A.E,Nother
5,von Neumann
6,H.weyl
7,A.Weil
8,I.M.Gelfand
9,Wiener
10,Alxsandrff
11,Ledesque
12,Shafarevich
13,V.I.Arnold
14,Dedekind
15,Markov
16,Klein
17,E.Artin
18,Jordan
19,Siegel
20,Sobolev
21,J.P.Serre
22,Gorthenideck
23,Whiteny
24,E.Cartan
25,Thom
26,Milnor
27,Hadamand
28,Godel
29,Landau
30,Hecke
31,陈省身
32,Zermelo
33,Puntrijagin
34,H.Cartan
35,Hopf
36,小平邦彦
37,Cantor
38,Chx......
数学大事年表 (2007-03-28 12:25:00)
摘要：数学大事年表
来源：百科全书 发布时间：2006-06-29
约公元前3000年 •埃及象形数字
公元前2400～ •早期巴比伦泥版楔形文字，采用60进位值制记数法。
前1600年 已知勾股定理
公元前1850～ •埃及纸草书（莫斯科纸草书与莱茵德纸草书），使
前1650年 用10进非位值制记数法
公元前1400～ •中国殷墟甲骨文，已有10进制记数法
前1100年 •周公(公元前11世纪)、商高时代已知勾三、股四、弦五
约公元前600年 •希腊泰勒斯开始了命题的证明
约公元前540年 •希腊毕达哥拉斯学派，发现勾股定理，并导致不可
通约量的发现
约公元前500年 •印度《绳法经》中给出平方根相当精
确的值，并知勾股定理
约公元前460年 •希腊智人学派提出几何作图三大问题：化圆为方、
三等分角和二倍立方
约公元前450年 •希腊埃利亚学派的芝诺提出悖论
公元前430年 •希腊安提丰提出穷竭法
约公元前380年 •希腊柏拉图在雅典创办"学园"，主张通过几何的
学习培养逻辑思维能力
公元前370年 •希腊欧多克索斯创立比例论
约公元前335年 •欧多莫斯著《几何学史》
•中国筹算记数，采用十进位值制
约公元前300年 •希腊欧几里得著《几何原本》，
是用公理法建立演绎数学体系的最早典范&nb......
中国软件业缺自信 应尽快走出单一印度模式 (2007-03-26 22:31:00)
摘要：中国软件业缺自信 应尽快走出单一印度模式
时间：2006年05月21日10:30 我来说两句(45)
【来源：南方日报报业集团-21世纪经济报道】
本报记者 刘涓涓 北京报道
“首先需要厘清的是，这只是一个商业模式而已。”5月17日，一位国际知名咨询管理机构的中国区总经理向记者指出，只有中国才把印度的外包模式称为软件业，连印度本身都从来没有将其提升到软件业的高度。
但是，这并不妨碍在软件产业发展上，印度屡屡被国人树为标杆。事实上，上述专家也同样认为，“但要看到，这个外包市场是多么巨大，中国软件业的确有必要重新考量软件外包在整个产业链上的位置。”
时至今日，当中央将长期以来的“引入型”思路全面调整为“自主创新”并提升为国家战略的时候，面对曾经与我们站在同一起跑线、如今却已形成规模并发挥效应的印度，我们还要不要再向它看齐？
“中国软件业最缺自信”
《21世纪》：数年来，业界乃至政府有关部门都有同一个论调，那就是中国软件业应该向印度学习，中国软件业该不该学印度？他们各自的特征是什么？怎么学？
倪光南：学习印度经验是不错的，印度外包出口的成功，确实对中国很有吸引力，但同时，更值得中国学习的榜样却往往被“忽略”。
数据表明，印度现时的外包出口额是173亿美元，它大约有85万软件人员，人均产值约为2万美元，这当然是很可观的经济效益。然而，微软公司一年的销售收入就达到414亿美元，等于2.4个印度。微软只有6万名员工，因此，微软的人均产值约为69万美元。也就是说，一个微软员工创造的价值等于34名印度软件人员。造成这种差别的原因主要不是人员的素质(在微软也有不少印度员工)，而在于微软是做基础软件的，印度是做外包的，微软在上游，印度在下游。
既然有微软这样的榜样，那为什么只说学习印度而不说学习微软呢？印度缺乏国内市场，走外包道路是不得已。而中国有巨大的内需市场，为什么不学微软，不学美国，依靠内需市场的支撑，全方位地发展包括基础软件在内的自主软件产业体系呢？
这里的障碍主要不是人员的素质，也不是物质......
印度软件业崛起(2007-03-26 22:30:00)
摘要：印度软件业崛起的三大内因http://tech.QQ.com 2005年07月18日15:27 IT时代周刊 (0)广东省信息协会秘书长/黄观辉（供《IT时代周刊》专稿）
印度是曾经创造了古代文明的大国，印度综合国力不强，人均GDP比中国低，多年来印度GDP增长速度亦不高，信息产业的基础设施也较差，但印度软件业的发展却一枝独秀。其实，印度软件业的高速发展，主要是政府部门在其中扮演了主要的角色。他山之石，可以攻玉，本刊刊登此文，希望政府部门能借鉴印度的做法，提升国内软件业的发展。
印度软件业的发展，正以世人瞩目的速度高速前进。一个GDP增长速度并不高的国家，为何在短短的时间内成长为世界软件大国？这离不开印度政府对软件的支持。
据资料显示，印度软件业自1993年以来的年均增长速度为50%左右，1998~1999年度印度软件业产值为39亿美元，其中出口为26亿多美元，是仅次于美国之后的世界第二大软件生产和出口国。印度软件业占据世界软件市场16.7%以上的份额，印度软件产品大多输出到美国，其次是欧洲。印度的软件公司承揽了美国航空公司、瑞士航空公司、新加坡航空公司等航空公司的运行软件，以及伦敦地铁的运行软件，其设计技术堪称一流。
世界银行的一份调查称，80%的美国公司把印度作为国外软件来源的首选市场。难怪，微软的比尔·盖茨访印时惊呼：“21世纪的软件大国，不是美国，也不是欧洲，而可能是印度。”
政策引导产业发展
印度是个发展中国家，综合国力不强。但印度政府的发展策略是从几个主要产业入手，使用有限的资源和集中的政策扶持发展相关产业。其成效就是使印度成为了世界软件第二大国。
上世纪80年代初，拉吉夫·甘地政府明确提出：“要用电子革命把印度带入21世纪。”其政府推动和政策切入点就是软件业。1984年印度政府颁布了计算机政策，明确了软件业为产业，可以获得相应的补贴和优惠（中国在2000年国务院的18号文才明确了软件业的税收优惠等政策）。1986年印度政府又颁布了《计算机软件出口发展和培训政策》，为软件生产提供了一切必需的投入，如提供进出口用汇便利、金融支持、人员培训、高速数额传输、简化投资和进出口手续等；并给予税收优惠，如免交国内货物税、进出口生产的软件......
考研十大热门专业深度解析之计算机应用技术(2007-03-26 22:30:00)
摘要：考研十大热门专业深度解析之计算机应用技术
http://www.sina.com.cn 2007年02月05日 17:06 海文学校
近年来IT产业对于高级专业人才的需求持续上升，使得报考这一专业的研究生竞争日趋激烈。2007年计算机应用专业的报考人数排名由06年的第六位上升到第三位，仅次于工商管理和法学硕士。
计算机应用技术专业是一应用十分广泛的专业，它以计算机基本理论为基础，突出计算机和网络的实际应用。学生将系统地学习计算机的软、硬件与应用的基本理论、基本技能与方法，具有初步运用专业基础理论及工程技术方法进行系统开发、应用、管理和维护的能力。
你知道计算机专业的分类吗？
根据海文教育集团资讯中心提供的资料，目前我国计算机专业主要分为三大类：计算机基础专业、与理工科交叉的计算机专业、与文科艺术类交叉的计算机专业。
一、计算机基础专业：
专业要求与就业方向：这些专业不但要求学生掌握计算机基本理论和应用开发技术，具有一定的理论基础，同时又要求学生具有较强的实际动手能力。学生毕业后能在企事业单位、政府部门从事计算机应用以及计算机网络系统的开发、维护等工作。
推荐院校：北京大学、清华大学、北京工业大学、南京大学、上海交通大学、东南大学
二、与理工科交叉的计算机专业：
与理工科交叉而衍生的计算机专业很多，如数学与应用数学专业、自动化专业、信息与计算科学专业、通信工程专业、电子信息工程专业、计算机应用与维护专业等。
1.数学与应用数学专业：
专业要求与就业方向：数学与应用数学是计算机专业的基础和上升的平台，是与计算机科学与技术联系最为紧密的专业之一。该专业就业面相对于计算机科学与技术专业来说宽得多，不但适用于IT领域，也适用于数学领域。
推荐院校：同济大学、东南大学、中山大学、宁波大学、深圳大学
2.自动化专业：
专业要求与就业方向：自动化专业是一个归并了多个自动控制领域专业的宽口径专业，要求学生掌握自动控制的基本理论，并立足信息系统和信息网络的控制这一新兴应用领域制定专业课程体系，是工业制造业的核心专业。自动化专业的毕业生具有很强的就业基础和优势。
推荐院校：清华大学、东南大学、北京邮电大学、重庆大学
3.信息与计算科学专业：
专业要求与就业方向：这是......