师：各位同学，大家好。今天这节课，将由我和同学们共同学习高二年级第四章第六节综合活动“问题求解”。为了更好地开展学习，请同学们提前阅读课本137 - 142页，预习今天的内容。如果已经做好预习，请准备好纸和笔，在学习过程中积极思考，做好笔记。
同学们，在本章“算法与程序实现”里，大家都掌握了哪些基本算法呢？下面跟着老师一起来回顾一下。本章我们主要学习了解析法、穷举法、查找算法、排序算法、递归算法。什么是解析法呢？就是分析各要素之间的关系，抽取数学模型，建立解析式编写程序。学习中，我们用它解决了测量高度、小球弹跳等问题。
穷举法的思路是列举所有可能的情况，逐个判断哪些符合问题要求的条件，从而得到问题的解答。我们利用穷举法解决了“百钱买百鸡”的问题。
查找算法，是在一组对象中搜索某一目标，确定对象中有没有这一目标元素，如果有，则标出它的位置，如果没有，则给出没有的信息。学习过程中，我们学习了顺序查找、折半查找算法，也就是把一组数据整理为顺序的方法。
排序的算法有很多，比如选择排序、插入排序、冒泡排序等。
递归算法是一种直接或者间接调用自身的算法，它最大的好处是可以把难以解决的问题消解于过程的自我调用之中，只需要针对最简单的情形写出解答即可。
前面几种算法的学习，相信各位同学对于算法设计的理解又加深了一步。利用计算机求解问题，还有没有其他的算法呢？请同学们课后查找相关资料。
在这一节课里，我们将通过调查结构化、非结构化、半结构化问题的实例，解决一个具体的问题，归纳解决一类问题的一般规律，学习如何运用知识来解决比较困难的问题。
请看数学家科尔的无声报告，同学们，从这个报告里，你们受到了什么样的启发？当时没有电子计算器，也没有电子计算机，要靠手算得出这一结果是多么不容易啊。这一报告当然赢得了热烈的掌声。要知道大数的因式分解是何等困难呀。由此可见，在我们这个复杂的世界里，有的问题简单，有的问题复杂，有的问题有现成的解决方案，有的却无从下手。为了寻求信息技术求解问题的有效策略，人们从不同角度对问题的类型进行了划分与研究。从问题的结构化程度来看，将其划分成了三种类型：结构化问题、半结构化问题、非结构化问题。
什么是结构化问题呢？就是能够通过形式化或公式化的方法描述和求解的一类问题。而非结构化问题，就是难以用确定的形式来描述，主要根据经验求解，也就是知识加推理。半结构化问题就介于这两者之间，有一定的规律可循，但又不能完全确定，这样的问题一般可适当地建立模型，但无法确定最优方案。
我们中小学各科教学中面临的大多数问题都是定义完善的问题，比如前面学习的测量高度、小球弹跳、百钱买百鸡、水仙花数、大整数相加等等，这些问题都可以通过简单的分析，根据现成的算法编程来解决，所以它们都是结构化的问题。同学们，在我们的日常生活里，哪些是结构化问题，哪些是非结构化问题，哪些是半结构化问题呢？大家能通过老师的讲解对问题进行分类吗？
接下来我们以一个具体的结构化问题为例，来探讨待解决问题与算法之间的关系。x和y是两个很大的正整数，最多可达1000位。如何求出它们相乘的积呢？
请同学们利用所学知识在Vscode软件中设计一个程序来解决这个问题。同学们，都完成了吗？发现了什么问题呢？接下来和老师一起来验证一下这两个程序。
首先输入第一组测试数据，第一个整数3，第二个整数7，点击相乘按钮，得到结果都是21，没有问题。接下来输入第二组测试数据，第一个整数45，第二个整数78，点击相乘按钮，得到的结果都是3510，也没有问题。下面我们再来测试一组数据，第一个整数123456789，第二个整数123456789。点击相乘按钮之后，左边的程序出现了错误提示，溢出了，而右边的程序显示出了正确的结果，大家想到原因了吗？
原来第一个程序里的数据超出了计算机所使用的数据的表示范围。受计算机资源的限制，任何语言对于数值的有效数字都是加以限制的。例如VB语言中整型数据的有效位数为10位，而浮点型的有效数据为16位。为了方便处理较长的位数，可以使用数组和字符串的方式作为数据的存储方式。字符串作为数据输入，用函数分离每一位转换成数字存储到数组中，这样存储有什么好处呢？让我们带着这个问题接着往下看。这个问题的特点是乘数很大，在我们前面学习过的算法中，有没有好的办法去解决这个问题呢？老师想问一下同学们，你们最喜欢做什么样的乘法呀？一位数乘以一位数，那我们能不能考虑把这些大数分解成一位数乘以一位数呢？办法当然有，我们可以采用分治策略的递归算法。
递归算法是我们前面学习过的内容，可什么是分治策略呢？分治策略，字面意思就是分而治之，把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题的解可以简单地直接求解，原问题的解即为子问题解的合并。这个策略具体是如何实现的呢？下面让我们一起来分析一下。
假设x和y是两个n位的正整数，若有一个不足n位的，就在它前面补0，直到n位。为了缩小相乘的规模，把x和y分成n÷2位的两段。为了让同学们更好地理解，请大家自己在草稿纸上写下这样的两个数，把这两个数用乘号连接起来，如此一来，得出这样的表示方式。
从这里我们可以看到，乘法的位数变为了原来的一半，一个n位数的乘法就转换成了4个n÷2位的乘法和3个加法，不断地重复这个过程，直到a、b、c、d都是一位数，这样我们只要写出一位数乘以一位数，问题是不是就迎刃而解了呢？下面让我们用两个具体的数把这个过程再完整地分析一遍。
为了便于分析，我们这里选择的是3278和4192。根据刚才的分析，我们将这两个数分成两段，去掉括号，得出这样的表示方式。下面合并同类项，快来看看是不是和我们刚才的分析结果一模一样呢。到目前为止仍然是两位数乘以两位数，接下来我们仍然可以对其中一个子问题进行分解。