****大学
算法设计与分析课程设计
专业：软件工程
学号：
姓名：
一、课设内容分析
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 作业与考核
布置实践作业，要求学生独立完成算法设计与实现，以检验学生对所学知识的掌握程度。通过考核测试学生对算法设计和分析的理解与应用能力。
《算法设计与分析》
实验指导书
曹严元
计算机与信息科学学院
2007年5月 目 录
实验一 递归算法与非递归算法 ............................................................ 2
实验二 分治算法 ...................................................................................... 4
实验三 贪心算法 .................................................................................... 6
实验四 动态规划 .................................................................................... 8
实验五 回溯法 ...................................................................................... 10
实验六 分枝—限界算法 ...................................................................... 13
实验七 课程设计 .................................................................................. 16
实验一 递归算法与非递归算法
实验目的
1. 了解并掌握递归的概念，递归算法的基本思想；
2. 掌握基于归纳法的递归的思想方法；
3. 了解适用于用递归求解的问题类型，并能设计相应递归算法；
4. 掌握递归算法复杂性分析方法，比较同一个问题的递归算法与循环迭代算法的效率。
第一讲
第 1 页 第一章 算法分析技术
§1.1 算法及复杂性
算法从何入手，求解问题。计算机干什么？将所有想让计算机干的事全部描述成问题。
问题：什么是问题，怎么描述，日常生活中的问题描述，实际就是要让计算机干什么。输入，输出。
两个要素:输入输出，要有严格的描述。
实例：描述问题的所有参量。
询问：陈述问题所求的解的格式和解应满足的性质。
注意，计算机每次求解只是针对一个实例求解，问题的描述针对很多实例，通用的描述。
算法：对每个问题实例计算机都能计算出满足询问条件的正确答案，的计算方法。是一个过程，语句集合，语句有顺序，按照顺序执行语句，处理实例，得到正确答案。一种计算方法。对每个实例计算都能得到正确答案。
程序：算法的形式描述。
例子：求xn，求幂问题
实例(instance)：实数x和正整数n
询问(query)：xn=?
n=10，求：x10
每次计算x和n都不同，都是一个实例。
方法：算法， 第一讲
第 2 页 1 x*x*x*x*x*x*x*x*x*x
2 y=x*x, z=y*y, w=z*z, x10=y*w
3 [(x*x)2*x]2
方法1，2，3分别作9，4，4次乘法。考虑算法的总操作次数，*这个总操作次数称为算法的时间复杂度，或称为算法时间复杂性。
一个算法所需要的存储单元数目称为算法的空间复杂度，算法1，2，3的空间复杂度分别为2，4，2。
算法3的计算：两个变量，y=x*x；y=y*y；y=y*x；y=y*y。
时间复杂度和空间复杂度，不能太精确，没法太精确。因为相同的方法，两个人编出不同程序，同一个人两个时刻也编出不同程序。肯定不会完全相同。给出一个数量级来表达，数量级的参数是什么。
算法3推广到一般如何：想一种通用的办法。
1 begin
/n的m位2进制数为bm-1bm-2…b1b0
2 y=x
3 for i=m-2 down to 0 do
4 begin
