CUNY CSci235：软件设计与分析II关键概念

需积分: 9 168 浏览量更新于2024-07-20 收藏 2.15MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

"CUNY CSci235的软件设计与分析II课程讲义，由Stewart Weiss教授主讲，涵盖了编程与软件工程的关键概念，包括软件工程的定义、重要性和应用，以及对象导向问题解决的方法。" 在CUNY CSci235的“软件设计与分析II”课程中，主要探讨了编程与软件工程的核心概念。软件工程是一个多领域交叉的学科，它结合了计算机科学、项目管理和更多领域的技术和实践，以规范、设计、开发和维护软件应用程序。课程指出，没有一种万能的最佳方法来构建软件，也没有统一的理论指导如何进行，但软件工程师们在软件开发过程中确实共享了一些共同的理念。首先，课程强调编码前缺乏解决方案设计会显著增加调试时间，因此在开始编码之前，团队需要有一个整体的计划。对于大型软件开发项目，团队需要组织结构、明确的沟通以及协调工作。这些元素确保项目的高效进行，避免因无序开发导致的问题和延误。其次，软件工程并不仅限于大规模项目。它的原则同样适用于小型程序的开发。这些原则涵盖设计方法、测试策略、文档编写和开发过程的管理。课程可能会深入讨论如何将这些原则应用于不同规模的项目，以优化开发流程。在对象导向问题解决方面，课程可能会介绍对象导向分析（OOA）和对象导向设计（OOD）。这是一种以对象为中心的方法，通过识别问题域中的实体（对象）和它们之间的关系来解决问题。OOA和OOD强调封装、继承和多态等核心概念，帮助开发者创建更灵活、可扩展和易于维护的代码。通过实例化和消息传递，对象可以相互交互，实现复杂的功能。此外，课程可能还会涉及软件生命周期模型，如瀑布模型、敏捷开发、螺旋模型等，讨论它们各自的优点和适用场景。测试是软件开发中的关键环节，课程可能会讲解单元测试、集成测试和系统测试等不同层次的测试方法，以及自动化测试工具的使用。最后，文档在整个软件开发过程中起着至关重要的作用。课程可能会涵盖需求规格说明书、设计文档、用户手册等不同类型文档的编写，强调清晰、准确的文档对软件质量和可维护性的影响。 CUNY CSci235的这门课程旨在通过理论与实践的结合，帮助学生掌握软件工程的全面知识，从而能够在实际项目中应用所学，提高软件开发的效率和质量。

资源详情

资源推荐

CSci 235 Software Design and Analysis II

Introduction to Recursion

Prof. Stewart Weiss

n = 3

A: fact(n-1) = _____

return = _____

n = 3

A: fact(n-1) = _____

return = _____

n = 2

A: fact(n-1) = ___

return = _____

n = 1

A: fact(n-1) = ____

return = ____

n = 0

return = 1

n = 3

A: fact(n-1) = _____

return = _____

n = 2

A: fact(n-1) = ___

return = _____

n = 1

A: fact(n-1) = 1

return = 1

n = 0

return = 1

n = 3

A: fact(n-1) = _____

return = _____

n = 2

A: fact(n-1) = 1

return = 2

n = 1

A: fact(n-1) = 1

return = 1

n = 0

return = 1

n = 3

A: fact(n-1) = 2

return = 6

n = 2

A: fact(n-1) = 1

return = 2

n = 1

A: fact(n-1) = 1

return = 1

n = 0

return = 1

n = 3

A: fact(n-1) = _____

return = _____

n = 2

A: fact(n-1) = ___

return = _____

n = 3

A: fact(n-1) = _____

return = _____

n = 2

A: fact(n-1) = ___

return = _____

n = 1

A: fact(n-1) = ____

return = ____

Figure 2: Box Trace of Factorial Function

Other Examples

Fibonacci Numbers

Recursion is not usually the most ecient solution, although it is usually the easiest to understand. One

example of this is the Fibonacci sequence. The Fibonacci numbers are named after Leonardo de Pisa, who

was known as Fibonacci. He did a population study of rabbits in which he simplied how they mated and

how their population grew. In short, the idea is that rabbits never die, and they can mate starting at two

months old, and that at the start of each month every rabbit pair gives birth to a male and a female (with

very short gestation period!)

From these premises, it is not hard to show that the number of rabbit pairs in month 1 is 1, in month 2 is

also 1 (since they are too young to mate), and in month 2, 2, since the pair mated and gave birth to a new

pair. Let

f(n)

be the number of rabbits alive in month

. Then, in month

, where

n > 2

, the number of

CSci 235 Software Design and Analysis II

Introduction to Recursion

Prof. Stewart Weiss

pairs must be the number of pairs alive in month

n − 1

, plus the number of new ospring born at the start

of month

. All pairs alive in month

n − 2

contribute their pair in month

, so there are

f(n − 1) + f(n − 2)

rabbit pairs alive in month

. The recursive denition of this sequence is thus

f (n) =

(

1 if n ≤ 2

f(n − 1) + f (n − 2) if n > 2

This will generate the sequence 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, and so on. A recursive algorithm to

compute the nth Fibonacci number, for

n > 0

, is given below, written as a C/C++ function.

int fibonacci (int n)

{

if ( n <= 2 )

return 1;

else

return fibonacci(n-1) + fibonacci(n-2);

}

Although this looks simple, it is very inecient. If you write out a box trace of this function you will see

that it leads to roughly

function calls to nd the

Fibonacci number. This is because it computes

many values needlessly. There are far better ways to compute these numbers.

Choosing k Out of n Objects

A well-known and common combinatorial (counting) problem is how many distinct ways there are to pick

objects from a collection of

distinct objects. For example, if I want to pick 10 students in the class of 30,

how many dierent sets of 10 students can I pick? I do not care about the order of their names, just who is

in the set. Let

c(n, k)

represent the number of distinct sets of

objects out of a collection of

objects.

The solution can be dicult to nd with a straight-forward attack, but a recursive solution is quite simple.

Let me rephrase the problem using the students in the class. Suppose I single out one student, say student

X. Then there are two possibilities: either X is in the group I choose or X is not in the group.

How many solutions are there with X in the group? Since X is in the group, I need to pick

k − 1

other

students from the remaining

n − 1

students in the class. Therefore, there are

c(n − 1, k − 1)

sets that contain

student X.

What about those that do not contain X? I need to pick

students out of the remaining

n − 1

students in

the class, so there are

c(n − 1, k)

sets.

It follows that

c(n, k) = c(n − 1, k − 1) + c(n − 1, k)

when

is large enough. Of course there are no ways to form groups of size

k > n

, so

c(n, k) = 0

k > n

. If

k = n

, then there is only one possible group, namely the whole class, so

c(n, k) = 1

k = n

. And

k = 0

, then there is just a single group consisting of no students, so

c(n, k) = 1

when

k = 0

. In all other

cases, the recursive denition applies. Therefore the recursive denition with its base cases, is

c(n, k) =











1 k = 0

1 k = n

0 k > n

c(n − 1, k − 1) + c(n − 1, k) 0 < k < n

Once again it is easy to write a C/C++ function that computes this recursively by applying the denition:

CSci 235 Software Design and Analysis II

Introduction to Recursion

Prof. Stewart Weiss

int combinations (int n, int k)

{

if ( k == 0 || k == n )

return 1;

else if ( k > n )

return 0;

else

return combinations(n-1, k-1) + combinations(n-1, k);

}

The interesting question is how to show that this always terminates. In each recursive call,

is diminished.

In some,

is not diminished. Therefore, eventually either

k >= n

k = 0

In any case, this is again a very inecient way to compute c(n,k) and it should not be used.

Binary Search Revisited

The binary search algorithm was presented in pseudo-code earlier. Now we can work out some of the

programmatic details.

•

First we consider an arbitrary array, not a dictionary with pages and words on pages. The algorithm

is given an array of values.

•

Second we remove printing from the algorithm. An algorithm should return its results to its caller, not

print them on a device.

In general, functions whose purpose is not to perform I/O should not perform

any I/O, as this makes them less portable, cohesive, and reduces their performance.

The return value

should be either the index in the array where the item is found or an indication that it is not in the

array at all. Since array indices are always non-negative, we can use -1 to indicate that the search

failed.

•

Third is the issue of how to nd the middle of the array. The middle is the index halfway between the

top index and the bottom index of the part of the array being searched. Since the part of the array

being searched must vary depending on the results of comparisons, the top and bottom of the search

range will be parameters of the function.

Putting this together, the algorithm becomes

int binary_search( const ordered_type theArray[],

int bottom,

int top,

ordered_type keyword )

{

if ( bottom > top ) {

// the function was called with an empty range

return -1;

else {

// find the middle index

int middle = ( top + bottom ) /2;

// compare keyword to value at the middle

if ( keyword < theArray[middle] )

// keyword is not in the upper half so try again in lower half

return binary_search( theArray, bottom, middle-1, keyword );

else if ( keyword > theArray[middle] )

// keyword is not in the lower half so try again in upper half

CSci 235 Software Design and Analysis II

Introduction to Recursion

Prof. Stewart Weiss

return binary_search( theArray, middle+1, top, keyword );

else

// keyword >= theArray[middle] && keyword <= theArray[middle],

// so keyword == theArray[middle] and we found it

return middle;

}

Notes.

1. The array parameter is declared constant in order to prevent the code from accidentally modifying it,

since it is passed by reference in C++ and passed as a pointer in C.

2. The type of the array must be a type for which comparison operations are dened; the type

ordered_type

represents an arbitrary ordered type such as int, char, or double.

3. The comparisons are ordered so that rst it checks if the keyword is less than the array element, then

larger, and if both fail, it must be equal. This is more ecient than checking equality rst. Why?

The prototype and its contract, using Doxygen-style comments, are

/**

* @precondition 0 <= bottom && top < ARRAYSIZE && for every i 0 <= i <= top-1

* theArray[i] <= theArray[i+1] && ARRAYSIZE is the size of the array

* @postcondition none (the array is unchanged )

* @param theArray the array to search

* @param bottom low index of range to search in the array

* @param top high index of range to search in the array

* @param keyword value to look for (the search key)

* @return if keyword is in the array between bottom and top, its index

* otherwise -1

int binary_search( const ordered_type theArray[],

int bottom,

int top,

ordered_type keyword ) ;

Exercise 1.

Suppose the array contains the integers 5, 10, 16, 17, 19, 30, 32, 33, 34, 67, 68, 69, 81, 83, 87,

91, 92 and suppose the keyword is 10.

1. What is the set of array values against which the keyword will be compared?

2. How many comparison operations will be executed?

3. What if the keyword is 3? What is the sequence of array values against which it will be compared, and

how many comparisons are executed?

Towers of Hanoi

The last problem we will consider is the famous

Towers of Hanoi

problem. You are given three pegs, labeled

A, B, and C. Each peg can hold

disks. Initially,

disks of dierent sizes are arranged on peg A in such a

way that above any disk are only smaller disks. The largest is therefore at the bottom of the pile and the

smallest at the top. The problem is to devise an algorithm that will move all of the disks to peg B moving

one disk at a time subject to the following two rules:

剩余162页未读，继续阅读

绝不原创的飞龙

粉丝: 3w+
资源: 1088

CUNY CSci235：软件设计与分析II关键概念

2010数学建模题目

Software Design and Analysis III Lecture Notes (CUNY CSci335)

四川大学 experiment of digital electronic technology lecture notes

1. 以二叉链表表示二叉树，建立一棵二叉树（算法5.3）；2. 输出二叉树的中序遍历结果（算法5.1或讲稿）；3. 输出二叉树的前序遍历结果（见讲稿）；4. 输出二叉树的后序遍历结果。

simulink经典书籍

信号处理python书籍推荐

python scipy教程

请给我这篇文献的信息Automated GeoNames Data Cleaning and Standardization

认真观看 P5 Environment Variable and Security Lecture Software Security - Kevin Du - SEED Project - Syracuse University https://www.bilibili.com/video/BV1v4411S7mv 大概说下视频的内容。

推荐一本计算几何最好的书籍

lecture和lesson的区别

an introduction to stochastic differential equations version微盘

修改（或者重建）course表，使得semester属性的值等于lecture + experiment的值

$_FILES["lecture"]["name"]代码怎么应用

UPDATE course SET semester = lecture+experiment;,这个限制怎么去掉

帮我写英语150词的关于著名学者讲座的新闻报道

自学PythonNumpy胡网站

认真观看 P7 Race Condition Vulnerability Lecture Software Security - Kevin Du - SEED Project - Syracuse University https://www.bilibili.com/video/BV1v4411S7mv 大概说下视频的内容。

最新资源