《算法设计与分析》课程简介

****大学

算法设计与分析课程设计

专业：软件工程

学号：

姓名：

一、课设内容分析

1） 问题描述

输入某年某月某日，判断这一天是这一年的第几天？

2） 问题分析

首先判断输入的的年份是闰年还是平年，其次只要计算出从这年的一月一日到输入的日期的天数就行了

二、课设目的

通过课程设计，提高用计算机解决实际问题的能力，提高独立实践的能力，将课本上的理论知识和实际有机的结合起来，锻炼分析解决实际问题的能力。提高适应实际，实践编程的能力。在实际的编程和调试综合试题的基础上，把高级语言程序设计的思想、编程巧和解题思路进行总结与概括，通过比较系统地练习达到真正比较熟练地掌握计算机编程的基本功，为后续的学习打下基础。了解一般程序设计的基本思路与方法。

三、算法原理及思路

输入一个年、月、日，计算这是这一年的第几天。首先，整体思路是只要计算出从这一年的一月一日到这一天的总天数就行了。其次，要考虑这一年是闰年还是平年，闰年二月是29天，平年是28天。还有从一月到输入的月份中间有多少个大月多少个小月，大月是31天，小月是30天。最后，总天数=（大月的个数*31 + 小月的个数*30 + 二月 ）+ 输入的“日”。

四、程序流程图

开始

输入年月日

判断闰年、平闰年二月29平年二月28判断从一月到输入的月份大月、小月各几个

总天数（第多少天）

五、源程序

import java.util.Scanner;

public class SomeDay {

//输入年月日，判断是这一年的第几天

public static void main(String[] args) {

Scanner input = new Scanner(System.in);

System.out.println("请输入年：");

int year = input.nextInt();

System.out.println("请输入月：");

算法设计与分析教学大纲

一、课程介绍

1.1 课程背景

算法设计与分析是计算机科学的一门重要课程，其主要目的是教授学生算法设计的基本原理、常用算法的实现技巧以及算法性能的分析方法。本课程旨在培养学生的算法设计能力和问题解决能力，为其今后从事计算机领域的研究和开发工作打下坚实的基础。

1.2 课程目标

本课程的目标是使学生：

- 掌握算法设计的基本思想和方法；

- 熟悉常见的算法设计和实现技巧；

- 理解算法的正确性和效率分析方法；

- 能够运用所学算法解决实际问题。

二、教学内容

2.1 算法基础 - 算法的定义与特性；

- 算法的表示方法；

- 算法设计的基本思想；

- 算法分析的基本概念。

2.2 常见算法设计技巧

- 递归与分治法；

- 贪心法；

- 动态规划；

- 回溯法。

2.3 数组与矩阵算法

- 线性查找；

- 二分查找；

- 排序算法（如冒泡排序、快速排序等）；

- 矩阵运算与应用。 2.4 图算法

- 图的基本概念与表示方法；

- 图的遍历算法（如深度优先搜索、广度优先搜索等）；

- 最短路径算法（如Dijkstra算法、Floyd算法等）；

- 最小生成树算法（如Prim算法、Kruskal算法等）。

2.5 字符串算法

- 字符串匹配算法（如朴素匹配算法、KMP算法等）；

- 字符串编辑距离算法；

- 字符串压缩与编码算法。

三、教学方法

3.1 理论讲授

通过课堂讲授，介绍算法设计与分析的基本概念、原理和方法，并结合具体案例进行讲解，帮助学生深刻理解算法的设计思想和实现技巧。

3.2 课堂练习 在理论讲授的基础上，组织学生进行算法设计的实践与练习，通过编写代码解决问题，培养学生的分析和解决问题的能力。

3.3 实验教学

设置相关实验项目，让学生通过实验操作来巩固和应用所学算法知识，培养学生独立分析和解决实际问题的能力。

3.4 作业与考核

布置实践作业，要求学生独立完成算法设计与实现，以检验学生对所学知识的掌握程度。通过考核测试学生对算法设计和分析的理解与应用能力。

用分治法解决快速排序问题及用动态规划法解决最优二叉搜索树问题及用回溯法解决图的着色问题

一、 课程设计目的：

《计算机算法设计与分析》这门课程是一门实践性非常强的课程，要求我们能够将所学的算法应用到实际中，灵活解决实际问题。通过这次课程设计，能够培养我们独立思考、综合分析与动手的能力，并能加深对课堂所学理论和概念的理解，可以训练我们算法设计的思维和培养算法的分析能力。

二、课程设计内容：

1、分治法：

（2）快速排序；

2、动态规划：

（4）最优二叉搜索树；

3、回溯法：

（2）图的着色。

三、概要设计：

 分治法—快速排序：

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。分治法的条件：

（1) 该问题的规模缩小到一定的程度就可以容易地解决；

（2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质；

（3) 利用该问题分解出的子问题的解可以合并为该问题的解；

（4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

抽象的讲，分治法有两个重要步骤：

（1）将问题拆开； 《计算机算法设计与分析》课程设计报告

2 （2）将答案合并；

 动态规划—最优二叉搜索树：

动态规划的基本思想是将问题分解为若干个小问题，解子问题，然后从子问题得到原问题的解。设计动态规划法的步骤：

（1）找出最优解的性质，并刻画其结构特征；

（2）递归地定义最优值（写出动态规划方程）；

（3）以自底向上的方式计算出最优值；

（4）根据计算最优值时得到的信息，构造一个最优解。

 回溯法—图的着色

回溯法的基本思想是确定了解空间的组织结构后，回溯法就是从开始节点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始节点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的或节点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前的扩展结点就成为死结点。换句话说，这个节点，这个结点不再是一个活结点。此时，应往回（回溯）移动至最近一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归的在解空间中搜索，直到找到所要求的解或解空间中以无活结点为止。

《算法设计与分析》

实验指导书

曹严元

计算机与信息科学学院

2007年5月 目 录

实验一 递归算法与非递归算法 ............................................................ 2

实验二 分治算法 ...................................................................................... 4

实验三 贪心算法 .................................................................................... 6

实验四 动态规划 .................................................................................... 8

实验五 回溯法 ...................................................................................... 10

实验六 分枝—限界算法 ...................................................................... 13

实验七 课程设计 .................................................................................. 16

实验一 递归算法与非递归算法

实验目的

1. 了解并掌握递归的概念，递归算法的基本思想；

2. 掌握基于归纳法的递归的思想方法；

3. 了解适用于用递归求解的问题类型，并能设计相应递归算法；

4. 掌握递归算法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。