计算机问题求解

计算机问题求解–论题1-1-为什么计算机能解题2018年09月18日计算机问题求解计算机问题求解Beyondformaleducation,normalmaturationoragingitselfissadlyaccompaniedbythemonotonicdimmingofone'scuriosity.-BulentAtalayAmazingMachineEvenMoreAmazing注意：每个operation有相应的operand（1个或多个）你试试让计算机比较两个1-bit二进制数是否相等，只用前面提到的运算，如果需要，你可以使用辅助的bits,注意：这里testing操作有两个不同的operands.xyeqEqualitytest(x,y)zeroeq;flipeq;/*equalityontestxflipeq;testyflipeq;Ifx=yeq=1Otherwiseeq=0你能将这个操作扩展到,比如,32位内的整数吗?增加两个操作，可间接地利用判断相等的操作实现加法计算两个1-bit二进制数的和xyz1z0x+yadd(x,y)1.zeroz0;2.zeroz1;3.equalitytest(x,y);4.testeqgoto75.flipz0;/*x,y不同，和为1(01)6.exit;7.testxflipz1;/*x,y是1，则结果是2(10)goto,exit没法分支，没法分情况处理。add(x,y)1.zeroz0;2.flipz0;3.zeroz1;4.equalitytest(x,y);5.zerot6.testeqflipt;7.testtflipz0;8.testtflipz1;……(是否有可能让x=y=0时z1变为0）xyz1z0tx+y输出置为01(t=0),假如x,y不等，结果正确。若x=y,输出置为10(t=1)，可能错我们很容易区分两加数是否相等，但确难以判断在相等的前提下是0还是1，这体现了“语言表达能力”的差别。多层次抽象用一位的加法“间接操作”可以实现普通加法操作；加法操作又可以作为一步操作用在更复杂的“间接操作”中。实际上现在计算机内部电路能提供的操作远不只是那几个最简单的“直接”操作。内部与外部也许可以这样回答：计算机本身做不了什么，但在人的“指挥”下，计算机似乎什么都能做，因为“间接”有无限的“想象空间”。写程序？学会了“语言”就会写程序吗？我们如何解题?GeorgePolya:“HowtoSolveIt?”–Understandingtheproblem:“Whatyouaregivenandwhatyouaresupposedtofigureout”–Devisingaplan:“Howwillyouattacktheproblem?”–Carryingouttheplan:Solvetheproblem.–Lookingback:checktheresult,and…我们如何解题,用计算机?计算机如何理解问题?–输入是什么?输出是什么?如何针对计算机制定计划?–什么样的”计划”可能在计算机上实现?–什么样的形式才能让计算机知道该怎么做?执行计划–“计算机解题”–只有这个才真正是计算机做的!回头看–为什么结果是正确的?–效率能提高吗?一个例子–“渡河问题”问题：人、狼、羊、菜用一条只能同时载两位的小船渡河，“狼羊”、“羊菜”不能在无人在场时共处，当然只有人能驾船。图模型：顶点表示“原岸的状态”，两点之间有边当且仅当一次合理的渡河“操作”能够实现该状态的转变。起始状态是“人狼羊菜”，结束状态是“空”。“允许状态”只有10个。问题的解：找到一条从起始状态到结束状态的尽可能短的通路。空(成功)人羊狼菜人狼菜人羊狼人羊菜狼菜狼菜人羊羊计算机问题求解与数学对问题的理解必须用严格的数学语言描述。其前提是必须建立问题的数学模型。可用的数学模型必须是计算机能对其进行操作的。让计算机能理解的解题plan必须建立在严密的数学基础上。将plan表示为计算机能执行的“指示”的语言必须建立在严密的数学基础上。分析计算机计算的结果必须使用数学方法：–用逻辑证明结果正确；–动用必要的数学手段分析解法的效率。如何安排数据也很重要题解=“算法+数据结构”它为什么能找出你要的内容，而且很快？它为什么能将你可能最想要的放在最前面？任何小方块不能旋转，但可以两两交换位置。边界两边颜色相同得1分。最高分为172。穷举法显然不现实！铺砖算法多次反复执行：1温度降低少许2随机选择要交换的两块花砖3如果交换后游戏得分值下降：4随机决定是否保留这次交换5保留交换的概率值随着温度值下降逐步下降6如果决定不保留则撤销本次交换操作得分：171我们最不愿意看到的前景也许，我们该区分“智能”与“智慧”。算法是用计算机解题的关键AssoonasanAnalyticalEngineexists,itwillnecessarilyguidethefuturecourseofthescience.Wheneveranyresultissoughtbyitsaid,thequestionwillthenarise–Bywhatcourseofcalculationcantheseresultsbearrivedatbythemachineintheshortesttime?-CharlesBabbage,1864至少在可以看见的未来仍会如此课外作业UD1.2–1.6;1.8探讨用我们所介绍的3个基本操作实现加法的可能性，如果你认为不可能请给出你的论据。采用类似渡河问题的方法解如下问题：–3个容积分别为8，5，3升的油桶，没有容量刻度，最大的桶装满油，其它两个是空的，你可以将任一桶中的油的全部或部分倒入另外的桶，但不可溢出。要分出4升油，至少要倒多少次？