初中数学高中数学初中物理高中物理初中化学高中化学初中生物高中生物初中政治高中政治初中历史高中历史初中地理高中地理初中英语小学语文小学数学
您当前的位置:
加入试题成功,
请在""查看您已加入的习题.
移除试题成功,
请在""查看您已加入的习题.
加入收藏成功,
请在""查看您已加入的习题.
ID: 214050
点击率: 4204
题型: 填空题
当n为正整数时，函数N（n）表示n的最大奇因数，如N（3）=3，N（10）=5，…，设Sn=N（1）+N（2）+N（3）+N（4）+…+N（2n﹣1）+N（2n），则Sn=___________
由N（x）的性质可得知，当x是奇数时，x的最大奇数因子明显是它本身．因此N（x）=x，进而可得，奇数项的和；当x是偶数时，可利用数学归纳法推断出偶数项的和．因此由这样一个性质，我们就可将Sn进行分解，分别算出奇数项的和与偶数项的和进而相加．本题主要考查了数列的求和问题．考查了学生通过已知条件分析问题和解决问题的能力．
解：由N（x）的性质可得知，当x是奇数时，x的最大奇数因子明显是它本身．因此N（x）=x，当x是偶数时，参看下面的讨论，因此由这样一个性质，我们就可将Sn进行分解，分别算出奇数项的和与偶数项的和进而相加，即Sn=S奇+S偶，∴S奇=N（1）+N（3）+…+N（2n﹣1）=1+3+…2n﹣1==4n﹣1当x是偶数时，且x∈[2k，2k+1）①当k=1时，x∈[2，4）该区间包含的偶数只有2，而N（2）=1所以该区间所有的偶数的最大奇因数之和为T1=1②当k=2时，x∈[4，8），该区间包含的偶数为4，6，所以该区间所有的最大奇因数偶数之和为T2=1+3=4③当k=3时，x∈[8，16），该区间包含的偶数为8，10．，12，14，则该区间所有偶数的最大奇因数之和为T3=1+3+5+7=16，因此我们可以用数学归纳法得出当x∈[2k，2k+1）该区间所有偶数的最大奇因数和Tk=4k﹣1∴对k从1到n﹣1求和得T1+T2+…+Tn﹣1=∴S偶=T1+T2+…+Tn﹣1+N（2n）=综上可知Sn=S奇+S偶=4n﹣1+=故答案为
天翼新题库上线——快来试用“更宽的”搜索！
CopyRight (C) 2012 天翼教育. All Rights Reserved. 鄂ICP备号
手动组卷考试
智能组卷考试
&&&&&套卷考试
您的邮箱：1^2 + 2^2 + 3^2 + …… +N^2 的求解过程如下:　　 　　首先，对N^2，有　　N^2 = 1 + 3 + …… + （2N - 1）　　这个数学现象的得出，是通过鼓捣了一下等差数列后弄出来的，　　无需多写了，很简单的。　　 　　所以，列式：　　　 1　 ^2 = 1　　　 2　 ^2 = 1 + 3　　　 3　^2 = 1 + 3 + 5　　　　　
：　　　　　　：　　　　　　 ：　　（N-1）^2 = 1 + 3 + 5 + …… +（2N - 3）　　　　N　　^2 = 1 + 3 + 5 + …… +（2N - 3）+（2N - 1）　　 　　令1^2 + 2^2 + 3^2 + …… +N^2 = T　　则上面各等式的左右两边分别从上至下相加，可得：　　　　　　 T = 1*N + 3（N-1）+ 5（N-2）+ （2N-3）*2 +（2N-1）*1 　　构造：　 M = 1*N + 2（N-1）+ 3（N-2）+ （ N-1）*2 +　　 N　　 *
1　 　　则　 2M - T = 1*N + 1（N-1）+ 1（N-2）+　　 1　 *2 +　　 1　　 *　1 　　即　 2M - T =
N（N+1）/2　　　　　　　　①　　　　　　　　　　　　　　　 　　又利用（a+b）^2 = a^2 + b^2 + 2ab ，观察发现所引入的等式M右边各加数符合　　 1 + N = 2 +（N-1）=　3 +（N-2）+ …… +（ N-1）+ 2 =　N + 1　　　所以，　 M = 1/2 {[（1+N）^2 - 1^2 - N^2] + [（2 + N-1）^2 - 2^2 - (N-1)^2] + …… {[（N+1）^2 - N^2 - 1^2] }=　[N (N+1)^2 - 2 T]/2　　即　　　 M =　[N (N+1)^2 - 2 T]/2　　　　　②　　　　　　　　　　　　　　　　　　
　　联立①、② 两式，易从方程组中解出M（略）和T = N（N+1）（2N+1）/6，　　因此，1^2 + 2^2 + 3^2 + …… +N^2 = N（N+1）（2N+1）/6　　 　　 　　 于百无聊赖中解答。 　　 　　 　　
楼主发言：9次 发图：0张 | 更多
　　天哪，天书！
　　你这用到数学归纳法了吧，应该说明　　　　首先，对N^2，有　　N^2 = 1 + 3 + …… + （2N - 1）　　　　——这个肯定是用数学归纳法得出的，是不是？
　　另外说明一下　　N^2 的意思是N的2次方，呵呵
　　不是吧　　　　这么罗嗦？　　　　利用下面的等式可以很快求出，而且具有一般性　　（k+1）^3-k^3=3*k^2+3*k+1
　　利用上面的等式有：　　（n+1）^3-1=3(n^2+(n-1)^2+....+2^2+1^1)+3(n+...+2+1)+n　　　　剩下的一看就明白了　　　　利用这种方法可以求出：1^k+2^k+....+n^k
　　回光子,没用数学归纳法,这个就是等差数列,求和就是了,高斯小时候的那个直觉.　　　　青石岭人:还在行当里混吧,我是天天在校对试卷,从小学校到初中，再校到高中,你那个公式(（k+1）^3-k^3=3*k^2+3*k+1)N久没碰啊,上帝只给我自然数,我只好在有限的圆圈里一步一步的爬了.　　　　我总是把简单的东东复杂化,倒,上次圆周角也是.不过这样也好，去荒岛上也有事情可以干了。
　　我说的那个公式——完全立方公式在初二的课本理由，以前是在初一的　　　　　　我只是指出你的方法没有普适性而已 别无他意　　
　　哎　　　　又打别字了　　　　更正：理由----里有
　　但我构造出：　 M = 1*N + 2（N-1）+ 3（N-2）+ （ N-1）*2 +　　 N　　 * 1　 　　　　还是有点意思的,从97年以来,我再没碰过任何数学方面的东东,不管是初一还是初二的,我早忘了,现在三角方面的东东我也忘得差不多了，圆锥曲线也只能记得平面的椭圆公式了,现在是能记住一个算一个.　　　　没有普适性,当然不好，不能推广,只能当个玩具来玩一下了.
　　我又回头看了一下　　　　构造中间变量M，的确很用了心思　　　　不过不用解出来（1）-（2）*2就可解出T
　　怎么解T,我不管了,但构造　　M = 1*N + 2（N-1）+ 3（N-2）+ （ N-1）*2 +　　 N　　 * 1　 　　后,　　M问题的推广可以看作是解答&等差数列P*等差数列Q&的基础,也就是说S=∑P*Q 问题可以解决了。
　　依旧是特例　　　　呵呵　　　　你的M很特别 每一项的乘数之和相等　　　　一般情况如下：　　∑（a+k*b）（c+k*d）=∑[ac+(ad+bc)k+bd*k^2]　　=acn+(ad+bc)∑k+bd∑k^2　　　　呵呵　　
　　倒,这个最好是编程序了,假设MATHLAB能解决 : )　　　　{　　　　　　∑（a+k*b）（c+k*d）=∑[ac+(ad+bc)k+bd*k^2]　　　　=acn+(ad+bc)∑k+bd∑k^2　　　　}
　　呵呵　　　　写完整：　　acn+(ad+bc)n(n+1)/2+bdn(n+1)(2n+1)/6　　　　　　见到数学题会食指大动　　　　哈哈　　　　睡觉了　　　　　　
　　我现在已看到数字就跑。
　　归纳法好。这是二次等差数列，通项为二次三项式，和为三次四项式吧。用待定系数法，很快就可以搞定。
　　从实用角度出发，用插值公式去逼近，再用计算机求解，很通用的。　　　　但这个就没意思了，没有玩的乐趣了。
　　　　虽然我这个专业毕业　　但除了标题我什么也没看　　像隔着一条线一样分明　　忘却是多快的一见事啊　　
　　算一算1^m+2^m+3^m+……+N^m，我算过一次，算得我头晕。
　　可计算理论简介 　　　　在60年代的中国，如果一个大学生不懂工农业常识，例如混淆了韭菜麦子，可能会受到讥笑。本来，闻道有先后，术业有专工。要求一个领域的人理解另一个领域的知识是有些过分。在今天，如果一个计算机科学的硕士或博士不知道什么是不可判定问题，什么是停机问题，为什么停机问题不可解，什么是NP=?P问题，也有可能会受到讥笑。因为这些问题对于计算机科学而言，太基本、太重要了，它们都属于一门称为可计算理论的学科。是计算机科学研究人员应具备的修养型知识。　　可计算理论是关于计算机械本身的数学理论。20世纪前，计算机械总是”算计”别的对象，很少”算计”自己。20世纪 30年代，为了要解决一个基础问题，即是否有存在不可判定问题，数理逻辑 学家提出了几种不同的（后来证明是彼此等价的）关于算法的定义，从而建立了可计算性理论。　　科学家令计算机械 自己”算计”自己，奇迹出现了。图灵用对角线方法，把图灵机自己编码，搅进其自己的计算对象中，证明了停机问题不可解。在一定程度上说明了计算机（程序）的能力有限性。　　30年 代前期，K.哥德尔和S.C.克林尼等人创立了递归函数论， 将数论函数的算法可计算性描述为递归性。30年代中期， A.M.图灵和E.L.波斯特彼此独立地提出了理想计算机的 概念，将问题的算法可解性描述为在具有严格定义的理想计算机上的可解性。30年代发展起来的算法理论，对 在40年代后期出现的存储程序型计算机的设计思想是有影响的。图灵提出的理想计算机（称为图灵机）中的一 种通用机就是存储程序型的。　　　　 可计算理论主要内容有：自动机论与形式语言理论;程序理论(包括程序正确性证明、程 序验证等);形式语义学；算法分析和计算复杂性理 论。自动机理论和形式语言理论是50年 代发展起来的。前者的历史还可以上溯到30年代，因为图灵机就是一类自动机(无限自动机)。50年代以来一些 学者开始考虑与现实的计算机更相似的理想计算机，J. 诺伊曼在50年代初提出了有自繁殖功能的计算机的概念。　　　　王浩在50年代中期提出了一种图灵机的变种，这是一种 比原来的图灵机更接近现实机器的机器。他还提出一种 存储带上的内容不能清除的机器，并证明这种机器是与图灵机等价的。　　　　60年代前期，又有人提出具有随机存取 存储器的计算机（简称RAM）以及多带图灵机等。 形式语言理论 导源于数理语言学中的乔姆斯基理 论。在这种理论中,形式语言分为四种:①0型语言；②1 型语言;③2型语言;④3型语言。相应地存在着0型、1型、 2 型、3型四种形式文法。1型语言又名上下文有关语言， 2型语言又名上下文无关语言，3型语言又名正则语言。其中2型语言最受人注意。60年代中期,还发现了这四类 语言与四类自动机之间的对应关系（见表形式语言与自 动机的关系） 在上表中，左边所列的语言恰好是右边与之对应的自动机所能识别的语言（见形式语言理论）。 程序设计理论 包括程序正确性证明和程序验证， 它的一些基本概念和方法是40年代后期诺伊曼和图灵等 人提出的。诺伊曼等在一篇论文中提出借助于证明来验证程序正确性的方法。　　　　J.T.施瓦兹和 M.戴维斯70年代后期提出了一种他们称之为&正确程序 技术&的软件技术。这种方法是先选定成千种基本程序模块，并借助已知的各种验证方法（包括程序正确性证 明）来保证这些基本程序的正确性。然后再提出一组能 保持正确性的程序组合规则。这样，就可以通过不断的 组合，生成各种各样的程序。 　　　　有人指出，程序正确性证明技术所发展出来的&循 环不变式&，即一个程序中的某一循环的入口或出口点 上所附的谓词，有些文献中称作&归纳断言&，可以用来供程序研究用。也就是说，不像过去那样，对一个给 定的程序找出其若干个循环不变式，然后借助这些不变 式来证明这个程序的正确性；而是在编制这个程序之前， 根据对这一程序的要求，找出若干个循环不变式，然后根据这些不变式来生成这个程序。 自动程序设计的概念也是从40年代提出的。　　　　 1969年又有人独立地提出了这一想法。 程序语言的形式语法的研究，从50年代中期起有了较大的发展。而形式语义的研究自60年代以来虽有不少 研究工作者从事这方面的工作，提出几种不同的语义理 论，主要是操作语义学、指称语义学或称数学语义学、 公理语义学和代数语义学，但仍没有一种公认在软件技术中够用的形式语义学，因而需要提出一种更适于用到 实际计算中的新的语义学。 在程序正确性证明和形式语义学中应用的程序逻辑， 是60年代末发展起来的。　　　　这是谓词逻辑的一种扩充。原来的谓词逻辑中是没有时间概念的，所考虑的推理关系 是在同一时间里的关系。程序是一种过程，一个程序的 输入谓词与输出谓词之间的逻辑关系就不是同一时间里 的关系。因此，在有关程序性质的推理中，原来的谓词逻辑不够用，需要有一种新的逻辑。 60年代末，E.恩格勒等人创立了算法逻辑。C.A.R. 霍尔也创立了一种程序逻辑。这种逻辑是在原来的逻辑上增加一个程序算子而得到的。　　　　 算法分析和计算复杂性理论 关于算法的复杂性的 研究。关于这一领域的名称曾有争论。一般认为，各类具体算法的复杂性的研究称作算法分析，而一般算法复 杂性的研究称作计算复杂性理论。计算复杂性理论原是 可计算理论的一支，是以各种可计算函数(即递归函数) 的计算复杂性（在早期称作&计算难度&）为其研究对象的。可计算性分为理论可计算性和实际可计算性两种。 作为可计算性理论一支的计算复杂性理论，是以前者的 复杂程度为其研究对象的；而作为计算机科学一个领域 的复杂性理论，则是以后者的复杂程度为其研究对象的。 　　　　这一分支的基本问题是要弄清楚实际可计算函数类的结构和一些性质。实际可计算性是一个直观的概念。 如何对这一概念进行精确的描述，是一个并不容易的问 题。60年代中期以来，有关的研究工作者一般是以计算时间多项式有界的函数作为实际可计算的函数。这实际 上是一个论题，而不是一个可以在数学中加以证明或否 证的命题。有人指出，在有关的多项式次数较高时，很难说是实际可计算的。　　　　另一个带根本性的问题是：确定性机器与非确定性机器的解题能力的比较问题。人们早已知道，确定性图 灵机与非确定性图灵机的解题能力是相等的。因为非确 定性机器虽比确定性机器效率高，而如果计算时间没有 限制，则确定性机器总可以用穷举的方法来模拟非确定性机器。因此，二者的解题能力是一样的。但在计算时 间多项式有界时，二者的解题能力是否相等，这就是有 名的P=? NP问题。 关于计算和算法（包括程序）的研究，对串行计算的性质研究较多，而对并行计算性质的研究则还很不够 （特别是对异步的并行计算更是如此）。因此，关于并 行计算的研究很可能将成为计算机理论的研究重点。 　　　　　　　　　　　　　　　　　　　 对于一个判定问题，如果能够编出一个程序,以域 中任意元素作为输入，当相应的个别问题的解答是肯定 的时候, 的执行将终止并输出&是&,否则 的执行不 终止，就称该判定问题为半可判定的。可判定的问题总是半可判定的。集合是递归可枚举集的充分必要条件为 对应的判定问题是半可判定的。 图灵在1936年证明，图灵机的停机问题是不可判定 的，即不存在一个图灵机能够判定任意图灵机对于任意输入是否停机。图灵机的停机问题是半可判定的。图灵 机的停机问题是很重要的，由它可以推出计算机科学、 数学、逻辑学中的许多问题是不可判定的。　　
　　[转]　　　　　　围棋与计算机　　　　本文是biggenie发表在中国围棋网棋人棋事的系列文章,版权归biggnie所有　　作者为文章起名&胡说五道& :-), 其实文章非常精妙,故我将其改成上面的名字　　　　　　--------------------------------------------------------------------------------　　　　
一 从地球到月球　　　　从电脑诞生之日起，人们对于电脑就充满了幻想。尤其是在人工智能上，对于电脑超过人脑，有人兴奋，有人担忧，但曾经几乎所有人都认为这会是真的。尤其当“深蓝”击败卡斯帕罗夫之后，人们已经开始担忧，电脑超过人脑，会不会就发生在明天？　　　　但这种担忧实在是来的太早了。　　　　本世纪七八十年代,对人工智能学家们来说，就象是无忧无虑的童年。他们雄心勃勃，甚至排出了电脑替代人脑的时间表。在表中，现在，就已经应该是电脑超过人脑的日子了。现在，“深蓝”确实战胜了卡斯帕罗夫，但人工智能学家们的时间表早已被抛到了脑后。有人甚至打了这样一个比喻来说明人工智能上所取得的成就：人们想登上月球，他们造了一个梯子，用这个梯子爬上了一棵树，然后自豪地宣称：“现在，我们已向月球前进了一大步！”　　　　现在，电脑已经渗入到了我们生活的各个方面，在生产和生活中，我们已经有些难以想象脱离电脑的状况了，如果说这些形形色色的电脑只不过是花里胡哨的各种梯子，似乎实在是说不过去。　　　　我们先看看梯子是怎么回事吧。　　　　梯子的发明人是图灵博士。图灵在考虑可计算的机器的性质时，首先是设想一个人在计算，他把这个人的计算行为抽象成了这样一台机器：有一条无穷长的纸带子，一个有很多状态的机器在纸带上左右滑动，并且可以根据所读到的内容改变自己的状态或者改写纸带的内容。这就是大名鼎鼎的图灵机了。当前的所有计算机，在理论上都是可以被图灵机模拟的。　　　　请注意图灵机有一个重要的能力：改写纸带的能力。如果没有这个能力，那这台机器叫做有穷自动机。它和图灵机间的计算能力差着三个档次呢。（注意：在一条无穷长的纸带上读东西，在另一条纸带上写东西的机器也是有穷自动机）。　　　　判断这些东西的计算能力用的是这些机器所能接受的语言的概念。这个语言虽然是抽象的语言，但也和我们平时所说的语言差不多，你只要理解成这机器能听懂什么话也就差不太多了。乔姆斯基把语言分成了0， 1，2 ， 3四个等级，0 级能力最强，3 级最差。这四个等级之间有着难以逾越的鸿沟。　　　　这里的 3级语言也叫做正规语言，就是有穷自动机能听懂的， 2级语言叫做上下文无关语言，意思是一个词，不用管它的上下文，就可以听懂了。1 级语言就是上下文相关的了，也就是说机器还得揣摩这话前后的意思。零级语言就是图灵机可以接受的语言了。　　　　我们用数数的本事就可以体会1，2，3 型语言的能力差别了。　　　　对于数数，有这么一个笑话：两个贵族比赛，看谁说出的数更大，第一个人绞尽脑汁，冥思苦想十几分钟后说：3， 轮到第二个人，他想了很久很久，最后说：你赢了。　　　　数到 3 的本事哪型语言都会，我这里说的数数本事是从一数起，只要不老死，数多少个都行。3 型语言，也就是正规语言，是不会数数的。 2 型语言（上下文无关语言）会数数，但同时数两个数就不会了。1 型语言就是数多少个数都行的了。而 0型语言的能力又比 1型语言强的多。也就是说，图灵机看上去简单，实际上是还是很牛的。　　　　但是图灵自己就发现了图灵机也有不照的时候了，这就是图灵机的停机问题。我们可以这样说明图灵机的停机问题：假设当图灵机听懂了一句话，它就不再琢磨这句话了，现在我给图灵机一句话，问它“你听的懂吗？”如果它听的懂，它会回答“是”，但如果它听不懂，很可能它永远也不会知道自己听不懂。　　　　　　--------------------------------------------------------------------------------　　　　
二 有穷与无穷　　　　用天梯登上月球的想法，现代人也许会觉得荒谬，但在古人眼里，未必如此。梯子可以上树、可以上房、可以上城，甚至可以上山，为什么不能上天呢？　　　　因为做梯子的原材料数量不够，强度不够，天梯也没有可搭的地方，等等等等，但古人都不清楚，他们根本不知道地球和月球之间有多远。　　　　国际象棋八八六十四见方的棋盘，围棋纵横 361交叉点的棋枰，它们的变化从理论上说是有限的，因此，理论上，这些问题都是图灵机可解决的。但是，就在我们理论上严谨地一步步得出结论时，我们早已不知不觉地越过了在实际计算意义上有穷与无穷的界限。　　　　以围棋为例，围棋有多少种变化？比较常见的有两种估计方法，一是：假设不会出现大家都被提光再从头再来的情况，那么，第一步有 361种选择，第二步有 360种选择，以后的情况大致如此，我们就以 361为界，那么变化数是361!，约为10的 768次方。另一种估计方法大概是宋朝的沈括老先生首先使用的：棋盘上每个点有黑，白，空三种状态，所以围棋变化数是 3 的361次方，约为10的 172次方，用沈老先生的说法，就是“连书‘万’字四十三”。这虽然也很大，但比起前面的估计值来，小的实在是太多了。如果这种估计正确，那电脑下围棋无疑轻松了许多。　　　　不幸的是，沈老先生的估计方法是错误的。他只考虑了这种种状态，却没有考虑这些状态间的相互关系。就比如数学中的图，沈老先生只考虑了顶点的总数，却忘了把连接顶点的边算进去了。　　　　如果我们不考虑边，就考虑这“连书‘万’字四十三”的状态，如果我可以对于每个状态都精确地算出价值的话，那么电脑只需要查价值表就可以确定该怎样下棋了，这样，电脑需要储存的变化数也就是“连书‘万’字四十三”，但问题是，这些价值是怎么算出来的？总不会看到一个状态之后就能猜出它的价值吧。因此，假设有一个电脑围棋机器，虽然在执行的时候他可以只考虑不同状态的价值，但为了造这台机器，我们还得把所有这些状态的关系都考虑进去。　　　　按照第一种估计方法得到的10的 768次方又是个什么概念呢？宇宙中所有基本粒子的总数，据估计，为10的80次方。如果没有一些简化计算的措施，这比宇宙中粒子总数还要大数不清倍的数字对我们来说，又和无穷有什么区别？　　　　其实，连第一种估计方法都是错误的。围棋真正的变化数，连10的(3的361次方)次方都挡不住，大学学历的人都清楚，一旦出现指数天梯，那这个数字有多大已经是不可想象的了。　　　　这一点并不能说明围棋不是图灵机实际可解的。不过至少告诉我们，遍历的方法是不可行的。所以，我们暂时把围棋的状态当作无穷来看。在这里，我们用准无穷来称呼到达实际不可计算程度的状态数。　　　　人们在谈到围棋与国际象棋的比较时，总说围棋的变化远多于国际象棋。但如果把这作为电脑下围棋远难于下国际象棋的原因是不充分的，并不是状态越多的东西越复杂，况且国际象棋的变化同样也是天文数字。　　　　但是，如果把国际象棋的棋盘放大，棋子增多，使它的变化从绝对数值上来说接近甚至超过围棋，国际象棋还是只能给人以国际象棋的感觉而不是围棋的感觉。因为，它们的“语法”有着本质的不同。　　　　现在，我们考虑这样一个问题：国际象棋和围棋走子后棋局状态的变化，分别需要判断几个位置上的状况？　　　　国际象棋当我落下一子时，只要考虑落子点的状态就可以了，如果这里有我自己的子，这步落子无效，如果这里有敌人的子，敌子被我吃掉，如果这里空白，那么仅仅是棋子的移位。象王车易位、吃过路兵等情况，我们可以把它看作可以遍历的特例而暂时不予考虑。　　　　让我们回想一下乔姆斯基四级语言中的 2级：上下文无关语言。当排除了特殊情况之后，我们可以认为，既然国际象棋棋局某格的状态变化与周围无关，那么，它应当是可以被能听懂（专业上叫接受）2 级语言的机器听懂的。我们可以把国际象棋理解成一个上下文无关语言。　　　　回到围棋，当我们落下一子时，棋盘会变成什么样？如果周围全是敌子，有些敌子没了气，那敌子全部拿走，如果周围有自己的子，敌子没被拿走，自己的子反而没了气，那就是自填死。　　　　听起来好象也很简单，但棋盘的变化是需要看周围的情况而决定的。如果只看落子点的状态，那我们什么结论也得不到。也就是说，围棋不能用上下文无关语言来等价，至少也得用上下文有关语言，就是会数很多数的 1级语言.　　　　在考虑围棋变化数的时候，劫可是不能不提。有人说“劫乃围棋精华”，可对于 1型语言来说，劫实在是要命的东西。1 型语言的基本要求是它的语言产生式左边不长于右边，但对于劫来说，并非如此。有了劫，就意味着 1型语言也接受不了围棋了。　　　　更要命的还在后面。象三劫循环、四劫循环、长生劫等等，在现在的围棋规则中，都简单地判为“无胜负”。其实，如果用“全局同型禁止再现”，都可以从理论上解决，并且也不如人们想象中的那么复杂（以后我可能会另写文章介绍多劫循环的规律）。全局同型禁止再现也很圆满地解释了劫。但是，全局同型禁止再现对于用图灵机模拟围棋，可以说是致命的一击。因为，这意味着这台图灵机得把以前的所有状态都存储起来，而具有无限种状态数的机器不是图灵机。　　　　国际象棋一盘棋结束，有三种状态：将死对方，被对方将死，和棋。和棋除了双方自愿外，还有逼和、三次同型和，以及六十步子数不变和等等。这意味着国际象棋在这些都是可以直接检验的，其步数不会超过 32*60步。可围棋就不一样了，“全局同型禁止再现”，这意味着理论上围棋可以下 3的 361次方数量级这么多手！这是准无穷了。即使没有这一规则，围棋可走的步数依然是准无穷。　　　　而围棋的胜负又非要看整个棋盘的状态才能决定，也就是说，就算没有“全局同型禁止再现”这一规则，我们可以用图灵机来接受围棋，但判断每一步的好坏必须追溯到这一局棋的终点，这意味着这台图灵机要判断它不同情况下停机时的状态！而这是图灵机所无能为力的。这里的状态是理论状态，它和我们实际计算时会选择的状态还不一样，围棋实际对局也很少超过 361手，但这已经启示我们，既然国际象棋与围棋在复杂程度上差了 3个档次，我们能够解决国际象棋问题的算法能用来对付围棋吗？　　　　　　--------------------------------------------------------------------------------　　　　
三 迷宫之路　　　　从理论上来说，围棋的每一步都会有一个或几个最佳选择。如果我们真的可以遍历围棋的所有变化并加以比较的话，我们是可以找到这些最佳下法。只是这种遍历是实际上不可实现的。　　　　寻找围棋最佳下法的过程就象是在走一个庞大的迷宫，迷宫中有无数的分支岔路，有些通向死路，有些通向幻象，还有一些路则仅仅是自己转圈。置身于这个庞大的迷宫中，当我们知道凭一生的时间也只能走过这一迷宫的微不足道的一小部分时，我们自然会停下来，看看这迷宫之路中有没有什么规律。　　　　我们先对问题进行简化，抛开全局同型禁止再现，也不考虑三劫、四劫、长生劫等等情况。这样在走迷宫时不必判断是否会出现回路（就是绕了一圈又回来了），对于这种无回路的迷宫，最简单的走法是死贴一边走（比如，一直贴左边或者一直贴右边），这就是一种遍历搜索，术语叫深度优先遍历搜索（因为它每次都要走到头再转回来走下一条）。按上章的计算，深度优先遍历搜索走完这个迷宫大概需要10^(3^361)步。　　　　所以，我们别无选择，只有换种办法来走迷宫。我们所选的办法又怎样才能达到我们的要求呢？　　　　我们这里所谈论的迷宫的走法，也就是解决一个问题的算法，一般用是用复杂度的阶数来衡量算法复杂度好坏的。首先，一个问题有它自己的尺度。比如国际象棋是64格棋盘，我们可以把国际象棋问题的尺度定为64，围棋 361个交叉点，我们可以把围棋问题的尺度定为 361。如果你愿意把它们的尺度分别定为 8，19也可以，但考虑问题时显然不如64和 361来的自然。　　　　解决一个问题的算法的复杂度是根据问题的尺度与计算步数的函数来定义的。设 n为问题的尺度，如果一个算法需要 n步，我们就说它的复杂度是 n，如果一个算法需要 2^n步(n个2连乘)，我们说它的复杂度是 2^n。对于两种算法来说，只要他们的复杂度函数的比值不大于一个常数，我们就称它们为同阶的。也就是说，一个需要步数为 1000n的算法与一个需要步数为 n的算法是同阶的。因为我的机器只要能把速度提高一千倍，第一个算法就能达到第二个算法原先的速度。但一个步数为 n^2的算法就比一个步数为 1000n的算法复杂度高，因为不论你的机器有多快，对于尺度很大的问题，总还是第一个算法复杂。　　　　因此，我们就用 O(n)，o(n^2)，...，o(2^n)，... 来表示与步数为n，n^2，...，2^n，... 的算法同阶的算法的复杂程度。请注意这里的 2^n，一个 2^n步数的算法（其实是任何x^n(x&1)步数的算法）比任何一个多项式步数的算法（就是O(n),O(n^2)...这类算法）都来的复杂。比如说。一个算法的步数约为 2^n，第二个为n^10，当 n取64的时候（国际象棋尺度），前者需要1.84*10^19步，而后者需要1.15*10^18步，第一个比第二个要多花十多倍步数，如果问题尺度是 361（围棋尺度），后者需要3.76*10^25步，而则前者需要 4.69*10^108步，这次前者比后者复杂了一千亿亿亿亿亿亿亿亿亿亿倍.　　　　如果说一个问题可以找到复杂度为多项式的算法，我们称它属于 P类问题，我们需要的就是复杂度为多项式的算法，也就是说，如果围棋是 P类问题，我们就认为它可解。而如果我们只能找到指数等级的算法 (O(2^n)..等等)，我们就认为它不可解。　　　　而围棋的遍历需要的步数，是指数复杂度问题的排序问题，它比指数复杂度的问题还要复杂的多。　　　　在人们试图用计算机解决的各种问题中，有一大类问题，包括货郎问题，背包问题等等，总计数百个之多，被人们称为NP问题。之所以说它们是一类是因为人们已经证明了只要其中一个问题可计算（就是有多项式算法），其他的问题就都可以计算，但现在，比起找这些问题的多项式算法，人们倒宁愿去证明它们不存在多项式算法。　　　　围棋是NP问题吗？不知道，好象不是，但既然NP问题都有指数复杂度的解法，而围棋连指数复杂度的解法都找不到，看起来，围棋似乎比NP问题还要复杂的多。　　　　不过，解决一个问题，找不到最好的方法，退而求其次也不失为一种明智的选择。人们对很多NP问题的态度就是：找不到最好的答案，比较好的答案也不错。“深蓝”会输给卡斯帕罗夫一局，也说明“深蓝”找到的并非最佳下法，但它已经可以在总成绩上战胜卡斯帕罗夫了。　　　　在各种搜索算法中，有一个A*搜索算法，也叫做最佳搜索算法，它是对于问题的各种情况设定一个估值函数，假设我们选择的是值最小的道路，在搜索迷宫的时候，A*算法根据估值函数判断下一步应选择的道路，并不停地用走过的实际路线的价凵希?绻?乐岛??涝缎∮谑导事废叩募壑担?敲矗珹*算法总可以找到最优解。但这样太困难。我们还可以有这样的想法：如果A*算法的估值函数可以做到差不离的话，也许我们就可以找到一个比较好的走法。比如，如果A*算法能够把下一手的选择点降到平均 6步，计算一路变化所需的步数降到平均20步，那么总的 计算量就变成了 6^20=3.66*10^15，这就已经接近于计算机可接受的计算量了。　　　　作者曾经设想过一个围棋AI模型：把所有的棋子以连在一起的一块为基本单位，而后再根据棋子的形状，眼位情况，赋与它强度、影响力等属性，用力学模型来分析全局势力范围，并据此选择下一手的大致位置。实际上这就是对A*算法估值函数的一种设想。　　　　看起来，我们只要找到一个好的方法，把一个个围棋局面量化成适当的值，再根据这些值进行A*搜索，就可以找到相当不错的走法。唯一的问题是：存在可行的量化方法吗？　　　　--------------------------------------------------------------------------------　　
请遵守言论规则，不得违反国家法律法规回复(Ctrl+Enter)}