算法实验期末测试,含有求最长递增子序列问题,用纸币购物品纸币数量最少是多少问题,还有矩阵间最小值问题.doc

期末实验测试报告班级 计算机7班 学号 105032011130 姓名 风律澈 成绩 一、测试目的检验学生运用算法知识解决问题能力，并给出期末成绩。二、测试环境1、微型计算机一台 2、WINDOWS操作系统，Java SDK，Eclipse开发环境三、测试内容 （一）给定一个整数序列，求该序列中，最长的递增子序列。样例：输入：5, 3, -1, 2, 5, 7, 3, 4, 8, 11, 12, 9输出：最长递增子序列长度为：5最长递增子序列为：3 4 8 11 12/（二）有一商品价格为n元，你手头现有面额为：1、2、5、10的钞票，请计算购买这个商品，最少需要多少张钞票。样例：输入：n=57输出：所需最少钞票张数为：7需要面额为10的钞票5张需要面额为5的钞票1张需要面额为2的钞票1张需要面额为1的钞票0张/（三）现有一m*n的棋盘，棋盘内的每个方格上都有一个数字，方格(0,0)内有一个棋子，现要求你将该棋子移动到方格(m-1,n-1)的，规定棋子只能向右，或向下移动，请编程求解一条最优移动路径，使得该路径上经过的方格数值之和最小。样例：输入：1, 2, 31, -2, 31, 2, 3输出：最优值为：5移动的方案如下：向下移向右移向下移向右移四、算法解题思路描述、实现步骤和结果(要求用中文描述算法解题思路，并附上代码和程序运行结果截图，)1. 最长递增公共子序列思路：当遇到前项比后面小或者等于的时候存入临时数组当遇到前项比后面大的时候，比较临时数组与答案数组哪个比较好，把好的设置为答案。重新开始新一轮比较。-package 最长递增增序列;import java.util.ArrayList;public class longest /* * param args */public static void main(String args) / TODO Auto-generated method stub/a数组是原序列/*/int a=5, 3, -1, 2, 5, 7, 3, 4, 8, 11, 12, 9;/b数组是答案序列int b=new inta.length;/i如同指针，用来遍历a数组的每个元素,k用来指向i的下一位；int i=0;int k=1;/l来表示b的长度int l=0;while(ka.length)/c数组用于存储所有递增子序列int c=new inta.length;/z用来指向c数组的末尾int z=0;/开始算法cz=ai;z+;while(true)if(ka.length&ai=ak)/符合要求，存入临时数组cz=ak;z+;i=k;k+;else/找到更优解if(lz)/放入bcopy_c_to_b(b,c);l=z;i=k;k+;elsei=k;k+;break;/输出结果for(int j=0;jb.length;j+)System.out.print(bj+ );private static void copy_c_to_b(int b, int c) / TODO Auto-generated method stubfor(int i=0;ib.length;i+)bi=0;for(int i=0;ic.length;i+)bi=ci;2. 钞票问题思路：按照一般逻辑可以知道，先尽量用大的，由此依次用小的，直到为1元的时候。用/获得商，用%获得余数，来回如此即可。-package 商品纸钞问题;public class main /* * param args */public static void main(String args) / TODO Auto-generated method stub/n表示物品价格int n=57;/a用于存放纸钞类型,按从大到小排好序int a=new int10,5,2,1;/c用于存放所需要的钞票数量int c=new inta.length;/ 开始算法 /k用于指向a，表示当前纸币类型int k=0;while(n!=0)/用取余数的方式获得该货币的最多使用张数，由于事前已经按从大到小排好，所以是最优解就是这样了ck=n/ak;/用掉后还有要解决的钱数量n=n%ak;/由于货币中有1，任何数都一定会在1这里变成0k+;/输出结果int sum = 0;for(int i=0;ic.length;i+)sum+=ci;System.out.print(所需最少钞票张数为：);System.out.println(sum);for(int i=0;i=0)if(answerz=1)System.out.println(向下移);if(answerz=2)System.out.println(向右移);z-;private static void search() / TODO Auto-generated method stubs00=a00;for(int i=1;in;i+)si0=si-10+ai0;ki0=1;for(int j=1;jm;j+)s0j=s0j-1+a0j;k0j=2;for(int i=1;in;i+)f