能量项链问题解法探讨.docVIP

能量项链问题解法探讨 　　摘要： 通过引入程序设计竞赛中的有趣题目，有利于激发学生的学习兴趣，提高学生的实践能力。文章利用动态规划方法的一个典型例子“矩阵连乘问题”解决了一道经典的竞赛题目“能量项链问题”。分析了两个问题的相似性和相异性，得到了能量项链问题的求解方法。 　　Abstract： Through the introduction of the interesting questions of programming contest， which can help to stimulate the students interest in learning and to raise the students practical ability. This paper solves a classic competition topic named energy necklace problem by using a typical example named matrix multiply problem of the dynamic programming method， analyzes the similarity and difference of this two problems， and obtains the solving method of energy necklace problem. 　　关键词： 动态规划；矩阵连乘问题；能量项链问题 　　Key words： dynamic programming；matrix multiply problem；energy necklace problem 　　中图分类号：G42；TP39 文献标识码：A 文章编号：1006-4311（2012）35-0170-02 　　0 引言 　　在软件工程专业的算法分析与设计课程中，笔者进行了相关的教学改革，其中最突出的一点就是在讲每种算法设计方法时，都从ACM竞赛或NOI竞赛中挑选有趣的且适合的竞赛题目来引入要讲的这个例子。例如，在讲动态规划算法时，通过赛题“能量项链问题”来引入矩阵连乘问题，通过赛题“回文词的构造”来引入最长公共子序列问题等。通过这些竞赛题目的引入，极大地激发了学生的学习兴趣。本文要讨论的就是如何利用所学的矩阵连乘问题来解决经典的竞赛题目“能量项链问题”。 　　1 问题描述 　　1.1 矩阵连乘问题 几乎在任何一本关于算法分析与设计课程的教材中，在介绍动态规划算法时，都无一例外的会讲授矩阵连乘问题，该问题是能用利用动态规划方法解决的典型问题。该问题是说：给定n个矩阵A1，A2，…，An，其中矩阵Ai（1≤i≤n）的维数为pi×pi+1，于是相邻的两个矩阵就是可以相乘的。考虑这n个矩阵的连乘积A1A2…An，由于矩阵乘法满足结合律，所以求解这个矩阵连乘积时可以有许多不同的计算次序，每种计算次序都对应一个乘法次数。那么矩阵连乘问题就是要确定一个矩阵连乘积的一种最???计算次序，使得计算一个矩阵连乘积时，所需要的乘法次数最少。 　　假设用二维数组m来保存问题的最优值，数组元素m[i][j]保存的是求解矩阵连乘积AiAi+1…Aj-1Aj时所需的最少乘法次数。则根据最优子结构性质，容易建立m[i][j]所满足的递推关系式如下。 　　（1）i=j m[i][j]=0 　　（2）im[i][j]） 　　m[i][j]=min； 　　} 　　} 　　} 　　调用该算法可求出n个矩阵相乘时所需的最少乘法次数，若要求n个矩阵相乘时所需的最大乘法次数则只需将matrix_min算法中if语句条件中的“”即可，为了便于描述，将求n个矩阵相乘时所需的最大乘法次数的算法命名为matrix_max算法。 　　1.2 能量项链问题 在NOIP2006提高组复赛试题中有一道题目，叫做“能量项链问题”，题目的大致含义是：在一串能量项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，这两颗珠子才能聚合成一颗珠子，同时释放出能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则这两颗能量珠聚合后释放的能量为m×r×n，新产生的珠子的头标记为m，尾标记为n。 　　显然，N颗珠子聚合成一颗珠子时会有许多不同的聚合次序，不同的聚合顺序得到的总能量是不同的，能量项链问题就是要确定N颗珠子聚合时的一种最优聚合次序，使得按照这种次序将N颗珠子聚合成一颗珠子时，释放出的总能量最大。 　　例如：设N=4，4颗珠子的头标记与尾标记依次为（2，3），（3，5），（5，10