Chapter 01 Introduction 第一章 绪论

Presentation on theme: "Chapter 01 Introduction 第一章 绪论"— Presentation transcript:

1 Chapter 01 Introduction 第一章 绪论
Prof. Qing Wang

2 A good example int a=1, b=2, c; c=a+b; float f1=1.0, f2=2.0, f3;
If c1 and c2 are two complex numbers, how to deal with c1+c2? Prof. Q. Wang

3 Solution class Complex { double real, imag; public:
Complex(double r=0.0,double i=0.0) { real=r; imag=i; } Complex(const Complex& ob) { real=ob.real; imag=ob.imag; Complex operator +(Complex c) { Complex temp; temp.real=real+c.real; temp.imag=imag+c.imag; return temp; Complex operator -(Complex c) { temp.real=real-c.real; temp.imag=imag-c.imag; Solution Complex operator *(Complex c) { Complex temp; temp.real=real*c.real-imag*c.imag; temp.imag=real*c.imag+imag*c.real; return temp; } Complex& operator =(Complex c) { real=c.real; imag=c.imag; return *this; int operator ==(Complex c) { return((real==c.real)&&(imag==c.imag)) int operator !=(Complex c) { return((real!=c.real)||(imag!=c.imag)) };

4 UML diagram of a complex problem
Prof. Q. Wang

5 PermittedStatusChange
Person CourseSession Employee Applicant CourseRegistration RegistrationForm Application PermittedStatusChange Test App Status Exam ExamSession Prof. Q. Wang

6 Algorithms & Implementation
Data Structure Linear List Tree Graph Generic List Generic tree Directed graph Stack Binary tree Undirected Queue Weighted tree Net String Matrix General list Concepts & ADT Algorithms & Implementation Applications Sorting Searching Other applications Prof. Q. Wang

7 Contents What’s Data Structure? Problem solving
Basic concepts of Data Structure Abstract Data Type (ADT) (Philosophy) Algorithm Algorithm Analysis (Philosophy) Reviews of C language Conclusion Prof. Q. Wang

8 History of Programming
Non structure period 1940s-1960s Structure oriented programming 1960s-1980s Object oriented programming 1980s~ Popular in 1990s New trends: aspect oriented programming Prof. Q. Wang

9 Examples Student Form Prof. Q. Wang

10 Examples Course Form Prof. Q. Wang

11 Examples Course selection and grade report.
On the base of Student Form and Course Form A more complexity graph structure Student (Student No., Name, Gender, Native place) Course (Curriculum, Course name,Period) Selection (Student No., Curriculum, Grade, Date) Prof. Q. Wang

12 Examples File system of UNIX / (root) bin lib user etc math ds sw Wang
Zhao Queue.cpp Stack.cpp Tree.cpp Prof. Q. Wang

13 Examples Air routes Honolulu Sydney Prof. Q. Wang

14 Data structure & Algorithm
Demos Data structure & Algorithm Hanoi Tower Maze Airport Schedule Train grouping Queen Problem Return Prof. Q. Wang

15 1.1 Problem solving (问题求解)
Procedures for problem solving (用计算机解决问题的步骤) Problem Analysis Algorithm Design Programming Testing and Maintenance Go Prof. Q. Wang

16 问题分析：这阶段的任务是弄清所要解的问题是什么；并且把它用一种语言（自然语言、说明语言或数学语言）清楚地描述出来。
Problem analysis: Propose the mathematic model for specific problem, and describe the solution in high level language, such as natural language, formalization language, or mathematic equation. 问题分析：这阶段的任务是弄清所要解的问题是什么；并且把它用一种语言（自然语言、说明语言或数学语言）清楚地描述出来。 Back Prof. Q. Wang

17 算法设计：这阶段的任务是建立程序系统的结构，重点是算法的设计和数据结构的设计。对于大型的复杂的程序系统，这一阶段往往还包括模块的设计。
Algorithm design: Divide the whole problem into separable modules and decide the framework and data structures in the project, including functionality design, module design, data flow analysis. 算法设计：这阶段的任务是建立程序系统的结构，重点是算法的设计和数据结构的设计。对于大型的复杂的程序系统，这一阶段往往还包括模块的设计。 Back Prof. Q. Wang

18 Programming: Complete the source codes and debug the codes.
程序设计：采用适当的程序设计语言，编写出可执行的程序。 Back Prof. Q. Wang

19 Testing and maintenance: Testing the executive programs and refine the source codes until no error exists. It is a feedback procedure for coding and debugging. 程序测试和维护：发现和排除在前几个阶段中产生的错误，经测试通过的程序便可投入运行，在运行过程中还可能发现隐含的错误和问题，因此还必须在使用中不断维护和完善。 Back Prof. Q. Wang

20 Example for problem solving
Traffic Lights Issue Description: 为了设计一个交通信号灯的管理系统，首先需要分析一下所有车辆的行驶路线的冲突问题。这个问题可以归结为对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。 Prof. Q. Wang

21 1.1.1 Problem analysis 根据这个路口的实际情况可以确定13个可能通行方向：A→B，A→C，A→D，B→A，B→C，B→D，D→A，D→B，D→C，E→A，E→B，E→C，E→D。 可以把A→B简写成AB，用一个结点表示 ，在不能同时行驶的结点间画一条连线(表示它们互相冲突)，便可以得到如右图所示的表示。这样得到的表示可以称之为“图” 。 Prof. Q. Wang

22 通过上面的分析，我们就获得了该交通管系统的数学模型，下面就可以着手进行算法和程序的设计。
如果把上图中的一个结点理解为一个国家，结点之间的连线看作两国有共同边界，上述问题就变成著名的“着色问题”：即求出最少要几种颜色可将图中所有国家着色，使得任意两个相邻的国家颜色都不相同。 通过上面的分析，我们就获得了该交通管系统的数学模型，下面就可以着手进行算法和程序的设计。 Prof. Q. Wang

23 Algorithm design and Programming
Importance of Algorithm (算法设计的重要性) Example 1：Find out the largest one from n numbers (从n个数中找出第k大的那个数) Example 2：One hundred dollars for one hundred chickens 百钱买百鸡问题 Requirements for programming (程序设计的要求) 1、Validity (正确性) 2、Availability (有效性) 3、Maintainability (可维护性) 4、Reliability (可靠性) 5、Reusability (可重用性, 包括可移植性) 6、Simplicity (简明性) Prof. Q. Wang

24 1.1.2 Algorithm & Programming
(1) Algorithm design (算法设计) ① Thorough (穷举法) ② Greedy (贪心法) (2) Programming (程序设计) 首先，为问题中所有有关数据设计适当的表示形式，不仅包括需要表示的结点和连接，可能还有为计算过程的实现而用的辅助性数据结构。 然后选择一种适当的程序设计语言实现这些数据结构，并在设计好的数据结构上精确地描述上面提出的算法，完成一个程序，使之能在计算机上运行。 Prof. Q. Wang

25 Traffic lights: Implementation
假设需要着色的图是G，集合V1包括图中所有未被着色的结点，着色开始时V1是G所有结点集合。NEW表示已确定可以用新颜色着色的结点集合。从G中找出可用新颜色着色的结点集的工作可以用下面的程序框架描述： 置NEW为空集合; 　for 每个v  V1 do 　　if v与NEW中所有结点间都没有边 　　　　从V1中去掉v ; 将v加入NEW ; Prof. Q. Wang

26 这个程序片段里涉及对集合和图的操作，包括由集合中去掉一个元素，向集合里增加一个元素，检查两个结点之间在图中是否有边连接等。有了这些结构和操作，程序的实现非常简单。
但是，常见程序设计语言并不直接支持图和集合等数据结构，通常只提供了一些基本数据类型(例如整数、实数、字符等)和一些数据构造手段(例如数组、记录、指针等)。要解决这个计算问题，我们必须自己用选定的语言所提供的机制实现这些结构(集合、图等)和操作(对集合的元素增删、对图的边的判断等)，这些正是本课程将要讨论的基本内容。 Return Prof. Q. Wang

27 1.2 Data Structures Three concerns in Data structures:
1. Logical relationship between elements for example: Linear structure: Student Form Tree structure Graph 2. Physical form of elements in the structure 3. Actions and behaviors of the structures Prof. Q. Wang

28 1.2.1 Definitions & notations
Data Data Element Data Object Data Structure Logical vs. Physical Form Abstract Data Type Data Type Prof. Q. Wang

29 Concepts and Notations
Data: (Data Set) symbolic representation for objective Symbols inputted, stored, processed and outputted by computers Data Element: basic unit of Data Set Atomic type Such as integer, char, etc… Structural type typedef struct item { … } Prof. Q. Wang

30 Concepts and Notations
Data Object: A set containing the same type of elements Subset of Data Set Data Structure: A data object + specific existing relationships between elements No relationship, no meaning Four basic relationships in Data Structure Data_Structure = {D, R} Go Prof. Q. Wang

31 Basic relationship between elements
Sets Belonging to the same set, but no other specific relationships banana car bus strawberry melon jeep racing car lemon apple truck pumper orange pear ambulance grapefruit Automobile set Fruits Prof. Q. Wang

32 Basic relationship between elements
Linear bin dev etc lib user Prof. Q. Wang

33 Basic relationship between elements
Hierarchical Tree structure 1 1 9 2 3 4 2 3 6 13 5 6 7 8 9 10 4 5 6 3 8 10 11 12 13 14 7 8 9 1 5 7 11 Tree Binary Tree Binary Search Tree Prof. Q. Wang

34 Basic relationship between elements
Hierarchical Heap structure 12 1 11 9 2 5 7 10 6 1 6 3 10 7 3 5 4 8 2 8 9 4 11 12 “Maximum” Heap “Minimum” Heap Prof. Q. Wang

35 Basic relationship between elements
Graph (Net) 16 1 2 1 2 21 5 19 6 6 3 11 6 3 33 14 6 5 4 5 4 18 Graph Net Prof. Q. Wang

36 Logical vs Physical Form
Data items have both logical and physical forms. Logical form: definition/declaration of the data item within an ADT. E.g.: Integers in mathematical sense: +, - Physical form: implementation of the data item within a data type. E.g.: 16/32 bit integers, overflow. Return Prof. Q. Wang

37 1.2.2 Main structures learned in this course (本课程涉及的主要结构)
Linear list (线性表)：线性表是一种逻辑上十分简单但应用非常广泛的数据结构，线性表中各元素之间是一种简单的”线性”关系。顺序表和链表是两种常用的实现线性表的数据结构，它们也是许多复杂结构的基本表示形式。 Stack & Queue (堆栈与队列)：堆栈和队列是两种十分重要的数据结构。堆栈元素的存入和取出按照后进先出原则，最先取出的总是在此之前最后放进去的那个元素；而队列实现先进先出的原则，最先到达的元素也最先离开队列。 Prof. Q. Wang

38 Character string (字符串)：字符串也是一种特殊的线性结构，它以字符为元素。本书中讨论的字符串，主要采用顺序表示的形式，因此每个字符可以直接访问。
Tree & binary tree (树与二叉树)：树和二叉树都属”树形结构”，在逻辑上表示了结点的层次关系，是一种非线性结构。树最上面一层只有一个元素，称为”树根”。每个元素可以有若干相关联的下层元素，这些元素被称为是该上层元素的”子结点”；每个下层元素至多有一个对应的上层元素，称为它的”父结点”。许多实际的和理论的问题中都可以抽象出某种树形结构来。 Prof. Q. Wang

39 Graph /Net (图)：图是一种较复杂的结构，它包括一个结点集合和一个边集合，边集合中每条边联系着两个结点。信息可以存储在结点里，也可以存储在边里。许多实际问题中的数据可以用图表示，如公路网络、通信网络、不同事物间的联系，等等。 Dictionary / Index structure 字典(检索结构)：字典可以看作是一种二元组的集合，每个二元组包含着一个关键码和一个值。抽象地看，一个字典就是由关键码集合到值集合的一个映射。按关键码进行检索是字典中最常用的操作。根据对字典中进行元素插入、删除频率的不同，有所谓”动态字典”和”静态字典”之分。”散列表”是实现字典的有效结构，散列表的主要特点是可以实现对大量离散元素的有效存储和快速访问。由于树形结构便于灵活地执行插入和删除，所以经常用来表示动态字典。 Return Prof. Q. Wang

40 1.3 Abstract data type (ADT) 抽象数据类型
Abstract Data Type (ADT): a definition for a data type solely in terms of a set of values and a set of operations on that data type. Each ADT operation is defined by its inputs and outputs. Encapsulation (封装): Hide implementation details. Go Prof. Q. Wang

41 抽象数据类型(Abstract Data Type, ADT) 是指一个数学模型以及定义在该模型上的一组操作。
可以看作是定义了一组操作的一个抽象模型。 例如，集合与集合的并、交、差运算就可以定义为一个的抽象数据类型。一个抽象数据类型要包括哪些操作，这一点由设计者根据需要确定。例如，对于集合，如果需要，也可以把判别一个集合是否空集或两个集合是否相等作为集合上的操作。 Go Prof. Q. Wang

42 Basic operations (基本操作)
Attribute read/get (属性读取) Attribute write/set (属性设置) Searching / Retrieval (查找) Insertion (插入) Deletion/removal (删除) Access of relationship (关系访问) Traversal (遍历) Prof. Q. Wang

43 ADT Symbols … App3 App2 App1 Appn … …
Searching Insertion Removal Modification ADT Symbols Prof. Q. Wang

44 Example of ADT ADT of Complex number ADT Complex {
Data：D = {c1, c2 | c1, c2  R(R is the set of Real number)} Relationship：S = {<c1, c2> (c1 is real part, c2 is imaginary)} Operations： void Assign(*A, c1, c2) void Add(*A, B) void Minus(*A, B) void Multiply(*A, B) void Divide(*A, B) ... }ADT Complex Prof. Q. Wang

45 Data Type A data type is the physical implementation of an ADT.
Each operation associated with the ADT is implemented by one or more functions in the implementation. Data type usually refers to an organization for data in physical memory. File structure is an organization for data on peripheral storage, such as a disk drive. Prof. Q. Wang

46 ADT and DT ADT: Type Data Items: Operations Logical Form Data Type:
Storage Space Functions Data Items: Physical Form Prof. Q. Wang

47 C description of Complex number ADT
Declaration typedef double ItemType; typedef struct { ItemType real ; ItemType imag; }Complex; /* 复数抽象数据类型 */ void Assign(Complex *A, ItemType real, ItemType imaginary); void Add(Complex *A, Complex B); /* A+B */ void Minus(Complex *A, Complex B); /* A-B */ void Multiply (Compex *A, Complex B); /* A*B */ void Divide(Complex *A, Complex B); /* A/B */ ... Prof. Q. Wang

48 C description of Complex number ADT
Implementation void Assign(Complex *A, ItemType real, ItemType imaginary) { A->real = real; A->imag = imaginary; } /* Assign( ) */ void Add(Complex *A, Complex B) A->real += B.real ; A->imag += B.imag ; } /* Add( ) */ … Prof. Q. Wang

49 C++ Implementation class Complex { double real, imag; public:
Complex(double r=0.0,double i=0.0) { real=r; imag=i; } Complex(const Complex& ob) { real=ob.real; imag=ob.imag; Complex operator +(Complex c) { Complex temp; temp.real=real+c.real; temp.imag=imag+c.imag; return temp; Complex operator -(Complex c) { temp.real=real-c.real; temp.imag=imag-c.imag; C++ Implementation Return Complex operator *(Complex c) { Complex temp; temp.real=real*c.real-imag*c.imag; temp.imag=real*c.imag+imag*c.real; return temp; } Complex& operator =(Complex c) { real=c.real; imag=c.imag; return *this; int operator ==(Complex c) { return((real==c.real)&&(imag==c.imag)) int operator !=(Complex c) { return((real!=c.real)||(imag!=c.imag)) };

50 1.4 Algorithm Definition: A finite sequences of specific basic operations for implementing specific mission. 算法是为实现某个计算过程而规定的基本动作的执行序列。 Characteristics: (1) Finiteness (有穷性) (2) Certainty (确定性) (3) Feasibility (可行性) (4) Input (输入) (5) Output (输出) Prof. Q. Wang

51 Requirements for design (设计要求)
(1) Correctness (正确性) ① No syntax error (不含语法错) ② Output correct results for several inputs (对于几组数据能够输出正确结果) ③ Output correct results for the representative and rigorous inputs (对于典型、苛刻数据能得出正确结果) ④ Output correct results for all possible and meaningful inputs (对于一切合法数据能得出正确结果) (2) Readability (可读性) (3) Robustness (健壮性) (4) Efficiency and low storage (效率与低存储量要求) Prof. Q. Wang

52 在实际应用中，算法的表现形式千变万化，但是算法的情况也和数据结构类似，许多算法的设计思想具有相似之处，我们可以对它们分类进行学习和研究。
本课程提到的算法大致有如下一些： Greedy (贪心法)：最短路经 Divide & conquer (分治法)：如二分法检索、Hanoi塔 Backtracking (回溯法)：迷宫、皇后问题 Dynamic programming (动态规划法)：优化问题 Local searching (局部搜索法)：最优化问题 Branch & limitation (分支限界法)：检索 Return Prof. Q. Wang

53 1.5 Algorithm efficiency analysis (算法分析)
There are often many approaches (algorithms) to solve a problem. How do we choose between them? At the heart of computer program design are two (sometimes conflicting) goals. 1. To design an algorithm that is easy to understand, code, and debug. 2. To design an algorithm that makes efficient use of the resources of computer(s). Prof. Q. Wang

54 Algorithm Efficiency (cont)
Goal (1) is the concern of Software Engineering. Goal (2) is the concern of Data Structures and Algorithm Analysis. When the goal (2) is important, how do we measure an algorithm’s cost? Two goals 1. To design an algorithm that is easy to understand, code, and debug. 2. To design an algorithm that makes efficient use of the resources of computer(s). Prof. Q. Wang

55 How to measure the efficiency?
(1) Empirical Comparison (run programs) (2) Asymptotic Algorithm Analysis (theoretically) Critical resources: Factors that affect running time: For most algorithms, running time depends on the “size” (or “scale”) n of the input. Running time is expressed as T(n) for a function T on the input size n. Prof. Q. Wang

56 算法时间效率的度量 (1) Empirical Comparison (事后统计法) Disadvantage (缺陷):
a. Must implement code and run (必须先运行程序) b. Vary with the environment (所得时间统计量依赖于计算机软硬件等环境因素) (2) Asymptotic Analysis (事前估算法) Factors (因素): a. Strategy of algorithm (算法的策略)(以百钱买百鸡问题为例) b. Scale of problem itself (问题的规模) (n) c. Programming language (程序语言) d. Quality of machine code after compilation (编译程序所产生的机器代码的质量) e. Speed of machine instruction (机器执行指令的速度) Prof. Q. Wang

57 Example 1: // Find the largest value int largest(int array[], int n) {
int currlarge = 0; // Largest value seen for (int i=1; i<n; i++)// For each val if (array[currlarge] < array[i]) currlarge = i; // Remember pos return currlarge; // Return largest } Prof. Q. Wang

58 Example 2: // Compute n2 { sum = 0; for (i=1; i<=n; i++)
for (j=1; j<=n; j++) sum++; } Note: Example 1 and 2 have different costs apparently due to the different functions. Prof. Q. Wang

59 Growth Rate Graph Prof. Q. Wang

60 Best, Worst, Average Cases
Not all inputs of a given size take the same time to run. Example: Sequential search for K in an array of n integers: Begin at first element in array and look at each element in turn until K is found. Best case: 1 time of comparison Worst case: n times of comparison Average case: (n+1)/2 Prof. Q. Wang

61 Asymptotic Analysis: Big-oh
Definition: For T(n) a non-negatively valued function, T(n) is in the set O(f(n)) if there exist two positive constants c and n0 such that T(n) <= cf(n) for all n > n0. Usage: The algorithm is in O(n2) in [best, average, worst] case. Meaning: For all data sets big enough (i.e., n>n0), the algorithm always executes in less than cf(n) steps in [best, average, worst] case. upper bound Big-oh Prof. Q. Wang

62 Thinking: Big-Omega Definition: For T(n) a non-negatively valued function, T(n) is in the set (g(n)) if there exist two positive constants c and n0 such that T(n) >= cg(n) for all n > n0. Meaning: For all data sets big enough (i.e.,n>n0), the algorithm always executes in more than cg(n) steps. Big-Omega notation indicates an lower bound. Prof. Q. Wang

63 Multiplication of two matrixes
例：Multiplication of two matrixes (nxn) 两个n×n矩阵相乘的算法 for (i=1; i<=n; ++i) for (j=1; j<=n; ++j) { c[i][j] = 0; for (k=1; k<=n; ++k) c[i][j] += a[i][k]*b[k][j]; } Scale of problem (问题规模)：n Atom operation (原操作)： c[i][j] += a[i][k] * b[k][j]; Loop times (基本操作重复执行的次数)：f(n) = n3 Asymptotic Time (该算法时间度量) 记作T(n) = O(f(n)) = O(n3) Time complexity (时间复杂度)：O(n3) Prof. Q. Wang

64 Bubble sorting 有的情况下，算法中基本操作重复执行的次数会随问题的 输入数据集的不同而不同。例如：
void Bubble_Sort(int a[], int n) { int i, change=TRUE; for (i=n-1; i >1 && change; --i) change = FALSE; for(j = 0; j < i; j++) if(a[j] > a[j+1]) swap(&a[j], &a[j+1]); change = TRUE; } Prof. Q. Wang

65 Rules (规则) If f(n) is in O(g(n)) and g(n) is in O(h(n)), then f(n) is in O(h(n)). If f(n) is in O(kg(n)) for any constant k > 0, then f(n) is in O(g(n)). If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)), then (f1 + f2)(n) is in O(max(g1(n), g2(n))). If f1(n) is in O(g1(n)) and f2(n) is in O(g2(n)) then f1(n)f2(n) is in O(g1(n)g2(n)). Prof. Q. Wang

66 Running Time Examples (1)
a = b; O(1) Example 2: sum = 0; for (i=1; i<=n; i++) sum += n; O(n) Prof. Q. Wang

67 Running Time Examples (2)
sum = 0; for (j=1; j<=n; j++) for (i=1; i<=j; i++) sum++; for (k=0; k<n; k++) A[k] = k; O(n2) Prof. Q. Wang

68 Running Time Examples (3)
sum1 = 0; for (i=1; i<=n; i++) for (j=1; j<=n; j++) sum1++; sum2 = 0; for (j=1; j<=i; j++) sum2++; O(n2) Prof. Q. Wang

69 Running Time Examples (4)
sum1 = 0; for (k=1; k<=n; k*=2) for (j=1; j<=n; j++) sum1++; sum2 = 0; for (j=1; j<=k; j++) sum2++; O(nlog2n) Prof. Q. Wang

70 Binary Search // Return position of element in sorted
// array of size n with value K. int binary(int array[], int n, int K) { int l = -1; int r = n; // l, r are beyond array bounds while (l+1 != r) { // Stop when l, r meet int i = (l+r)/2; // Check middle if (K < array[i]) r = i; // Left half if (K == array[i]) return i; // Found it if (K > array[i]) l = i; // Right half } return n; // Searched value not in array Prof. Q. Wang

71 Tips: factors for algorithm complexity (对算法复杂度影响的因素)
while loop: Analyze like a for loop. if statement: Take greater complexity of then/else clauses. switch statement: Take complexity of most expensive case. Subroutine call: Complexity of the subroutine. Prof. Q. Wang

72 100 dollars for 100 chickens (百钱买百鸡问题)
100元钱买100只鸡，hen(母鸡)每只5元，rooster (公鸡)每只3元，chick(小鸡)3只1元，问共可以买多少只母鸡、多少只公鸡、多少只小鸡？ 求解：设母鸡、公鸡、小鸡各为x, y, z只。则有： x + y + z = 100 5x + 3y + z/3 = 100 只需要解出本方程就可以得到答案。 Linear algebra: under-determine linear equations Prof. Q. Wang

73 Solution 1 Method 1: (The simplest way without deep thinking) Implementation： for (i=0; i<=100i++) /* Loop for i */ for (j=0; j<=100; j++) /* Loop for j */ for (k=0; k<=100; k++) /* Loop for k */ { if (k%3 == 0 && i+j+k==100 && 5*i+3*j+k/3 ==100) printf (“%d,%d,%d\n”, i, j, k); } Cost: 1,000,000 Prof. Q. Wang

74 Solution 2 Cost: 10,000 Method 2: (Revised way) Analysis:
因总共买100只鸡，所以小鸡的数目可以由母鸡数和公鸡数得到。 Implementation： for (i=0; i<100; i++) for (j=0; j<100; j++) { k=100 – i – j ; if (k%3==0 && 5*i+3*j+k/3==100) printf (“%d,%d,%d\n”, i, j, k); } Cost: 10,000 Prof. Q. Wang

75 Solution 3 Cost: 660 Method 3: (Revised way on the special boundaries)
Analysis: 钱共100元，而母鸡5元1只，所以母鸡数不可能超过20只。同样，公鸡数也不超过33只。 Implementation： for (i=0; i<20; i++) for (j=0; j<33; j++) { k=100 – i – j ; if (k%3==0 && 5*i+3*j+k/3 == 100) printf (“%d,%d,%d\n”, i, j, k); } Cost: 660 Prof. Q. Wang

76 Solution 4 Cost: 4 Method 4: (The most optimized way)
Analysis: 由 x+y+z = 100和5*x+3*y+z/3=100可以合并为一个方程： 14*x+8*y = 200, 进一步简化为: 7*x+4*y=100 从上面方程可见，x不超过14，并可以进一步判断x必为4 的倍数，于是有： Implementation： for (i=0; i<=14; i+=4) { j = (100 –7*i)/4; k=100 – i – j; printf (“%d,%d,%d\n”, i, j, k); } Cost: 4 Prof. Q. Wang

77 Result and Analysis Loop times: Method 1：100*100*100, one million
Method 2：100*100, ten thousand Method 3：20*33, 660 Method 4：4 Remark: The algorithm is important. Best algorithm, best efficiency. Return Prof. Q. Wang

78 Review of C programming language (C语言知识回顾)
数组 (array) 函数 (function) 指针 (pointer) 结构体与共用体 (struct and union) ★ ★ ★ ★ ★ ★ ★ ★ Prof. Q. Wang

79 Conclusion (小结) 在用计算机解题过程中，算法和数据结构是相辅相成、缺一不可的两个方面。数据结构是算法处理的对象也是设计算法的基础。一个具体问题的数据在计算机中往往可以采用多种不同的数据结构来表示；一个计算过程的实现又常常有多种可用的算法。因此选择什么样的算法和数据结构就成为实现程序过程中最重要的一个课题。 抽象数据类型的引入，提高了程序设计的抽象层次，也为数据结构和算法的研究提供了一种分层的模型。 重点掌握数据结构和算法的基本知识，理解它们在问题求解中的作用。了解下述概念：数据的逻辑结构、存储结构和操作，静态结构和动态结构，抽象数据类型，数据结构和算法的分类，算法的分析，空间代价和时间代价等。 Prof. Q. Wang

80 “数据结构”所处的地位 数学 代数系统 编码理论 算子关系 数据类型 数据表示法 数据的运算 文件系统 数据组织 信息检索 存储装置
数据存取 机器组织 硬件 （计算机系统 设计） 软件 （计算机程序 设计） Prof. Q. Wang