上海交通大学：《程序设计基础》课程教学讲义（密西根学院）Lecture Notes_Function

上寿安通大学文大四西围 So far we learnt about parameter passing in a function is called 巴 一·联合学院一 call by value.The values are used to initialize the parameters tM-Sprt Joint Institute (local variables). nclude《cmath:>。 Hinclude sva101class.hs using namespace std: double distance(double x1,double y1,double x2,double y2)i Vg101:Introduction to Computer nt main(wold《 double x1=12.0,y1=26.0; and Programming nt1■2g 12.0 double separation=distance(,万，sqrt 1)+2 return 0; double distance (double x1,double y1,double x2,double y2) Parameter Passing return sqrt ((x2-x 1 2-x1)*021)*心2-￥ Decomposition and Algorithm main dista 12.0□25.0 12.07.0 上#文通大竿父大智网 上知父大学父大思石度 ·联合学院 巴 -·联合学院一 UM-SJTU Joint imstitute Call By Value SWAP Requirements Protect the variables in the caller environment is If we going to define a function which will untouchable in the called environment take two arguments and swap the values It also has some limit on application: of the two parameters. -It can only have one return object,so if a function try void SwapInt (int a,int b) to return two values.... First of all,the If a passed object has big size,it will take longer time return mechanism and larger time to make that copy. int temp; we learned before What should we do to solve the problem temp a; does not work, because it can In C++,there is a new mechanism called a▣b； Call by Reference b temp; only return one value SWAPPED?! Reference int main (void) A reference is an alternative name for an variable.You intintl■l,int2e2: can also think reference defines a nick name for a console.printLine ("before intl ="intl,"int2=",int2,endl); variable. swap(intl,int2); A reference is a compound type that is defined by console.printLine ("after:intl ="intl,"int2 ="int2,endl); preceding a variable name by an symbol. return 0; A reference must be initialized with an object of the void swap (int nl,int n2) same type Int intVal 1024; int temp=nl; int &refVal ival; /ok:refVal refers to ival n1■n2: int &refVal2: n2 temp; /error:a reference must be initialized int &refVal3=10; /error:initializer must be an object 1

1 Vg101:Introduction to Computer Vg101:Introduction to Computer and Programming and Programming Parameter Passing Decomposition and Algorithm • So far we learnt about parameter passing in a function is called call by value. The values are used to initialize the parameters (local variables). Call By Value Call By Value • Protect the variables in the caller environment is untouchable in the called environment • It also has some limit on application: – It can only have one return object, so if a function try to return two values,… – If a passed object has big size, it will take longer time and larger time to make that copy. • What should we do to solve the problem – In C++, there is a new mechanism called Call by Reference SWAP Requirements SWAP Requirements • If we going to define a function which will take two arguments and swap the values of the two parameters. First of all, the return mechanism we learned before does not work, because it can only return one value SWAPPED?! SWAPPED?! int main (void) { int int1 = 1, int2 = 2; console.printLine ("before : int1 = ", int1, "; int2 = ", int2, endl); swap(int1, int2); console.printLine ("after : int1 = ", int1, "; int2 = ", int2, endl); return 0; } void swap (int n1, int n2) { int temp = n1; n1 = n2; n2 = temp; } Reference Reference • A reference is an alternative name for an variable. You can also think reference defines a nick name for a variable. • A reference is a compound type that is defined by preceding a variable name by an & symbol. • A reference must be initialized with an object of the same type : int intVal = 1024; int &refVal = ival; // ok: refVal refers to ival int &refVal2; // error: a reference must be initialized int &refVal3 = 10; // error: initializer must be an object

Just an Alias Call by Reference ● Because a reference is just another name for the int main(void) object to which it is bound,all operations on a int intl=1,int2=2; reference are actually operations on the underlying console.printLine ("before intl=",intl,"int2=",int2,endl); object to which the reference is bound. swap(intl,int2): int intVal =1024; console.printLine ("after intl=",intl,"int2=",int2,endD): return 0; int &refVal =ival; refVal +=2; void swap (int &nl,int &n2) will adds 2 to intVal.Similarly, int temp=nl; int intX refVal; nl■n2: assigns to intX the value currently associated with n2 temp; intVal. ● What Get Passed Review of Reference int main (void) 1 nt intval124g int &refVal intval; 1000 int intl 1,int22; 1024 intVal /what is assgined here console.printLine ("before intI ="intl,"int2=",int2,endl); 1004 swap(intl,int2); refVal /2; console.printDige ("after intl ="intl,";int2=",int2,endD); /What is in intval return 0; intval /-2; void swap (int &nl,int &n2) V/What is in refval; int temp =nl; It is the address of the 1020 &refVal nl■n2: variable intVal get passed n2 temp; in "int &refVel=intVal;" 上海文山大平夏大石队 上海父通大学义大智否似 一·联合学院 一·联合学院 UM-SITU Joint Institute UM-sprt Joi解mstitute Dereference Use Reference in Parameter List Recall:Reference &refVal is compound type. Like all references,when reference Only use refVal instead of &refVal is equal to parameters get called and initialized,it is asking for dereferencing the reference the address of the referred variable get i.e.after define: passed instead of the value of the variable. int &refVal intVale; then refVal is the deferencing results of &refVal. Therefore,in the called program,all the operation performed on dereferenced Dereferencing means to refer to the value of the variables,they are the same as you did to referred object.Therefore,it is the dereferenced the variables defined in the caller's refVal an alias of intVal. environment. 2

2 Just an Alias Just an Alias • Because a reference is just another name for the object to which it is bound, all operations on a reference are actually operations on the underlying object to which the reference is bound. int intVal = 1024; int &refVal = ival; refVal += 2; will adds 2 to intVal. Similarly, int intX = refVal; assigns to intX the value currently associated with intVal. Call by Reference Call by Reference int main (void) { int int1 = 1, int2 = 2; console.printLine ("before : int1 = ", int1, "; int2 = ", int2, endl); swap(int1, int2); console.printLine ("after : int1 = ", int1, "; int2 = ", int2, endl); return 0; } void swap (int &n1, int &n2) { int temp = n1; n1 = n2; n2 = temp; } int main (void) { int int1 = 1, int2 = 2; console.printLine ("before : int1 = ", int1, "; int2 = ", int2, endl); swap(int1, int2); console.printLine ("after : int1 = ", int1, "; int2 = ", int2, endl); return 0; } void swap (int &n1, int &n2) { int temp = n1; n1 = n2; n2 = temp; } What Get Passed What Get Passed Review of Reference Review of Reference It is the address of the variable intVal get passed in “int &refVel=intVal;” Dereference Dereference • Recall: Reference &refVal is compound type. Only use refVal instead of &refVal is equal to asking for dereferencing the reference i.e. after define: int &refVal = intVale; then refVal is the deferencing results of &refVal. • Dereferencing means to refer to the value of the referred object. Therefore, it is the dereferenced refVal an alias of intVal. Use Reference in Parameter List Use Reference in Parameter List • Like all references, when reference parameters get called and initialized, it is the address of the referred variable get passed instead of the value of the variable. • Therefore, in the called program, all the operation performed on dereferenced variables, they are the same as you did to the variables defined in the caller’s environment

上海又通大平又大园西积 Call by Reference 一·联合学院一 ·It is why the Return More Infor.from a Function SwapInt (intX,intY); will work as we saw. 3 intX Using reference concept can also solve the problem like return more information 1004 intY void SwapInt (int &a,int &b) from the calling program Example:Solve a quadratic Equation int temp; static void Getcoefficients(double &a,double &b,double &c) temp a; static int SolveQuadratic(double a,double b 020 a b; 1000 b temp; 1024 8b GetCoefficients(a,b,c)i intRootNun SolveQuadratic(a,b,c,x1,x2); 上#文通大竿父大智网 上知父大学父大留石双 ·联合学院 巴 ·联合学院一 UM-SJTU Joint imstitute Get Coefficients Stepwise Refinement The concept of Function abstraction can Function be applied to the process of developing This function is responsible for teg9ieteeeficeat5 effici programs.When writing a large program, which are passed by referenc ran in the var nts iables a.b.and you can use the“divide and conquer” strategy,also known as stepwise static void Getcoefficients(double &pa,double &pb,double &pc) refinement,to decompose it into sub- problems.The sub-problems can be console.printLine ("Enter coefficients A.B and C:\n"); console.readLine (a.b.ch: further decomposed into smaller,more manageable problems. 上海文山大平夏大石队 一·联合学院 UM-SITU Joint Institute (main) PrintCalender Case Study Let us use the PrintCalendar example to printMonth Title print Month Body demonstrate the stepwise refinement approach. December 2005 Non Wed Thu 41185 7 9 28 0741 is Lea pYear

3 Call by Reference Call by Reference • It is why the SwapInt (intX, intY); will work as we saw. Return More Return More Infor. from a Function • Using reference concept can also solve the problem like return more information from the calling program • Example: Solve a quadratic Equation Get Coefficients Get Coefficients Stepwise Refinement Stepwise Refinement • The concept of Function abstraction can be applied to the process of developing programs. When writing a large program, you can use the “divide and conquer” strategy, also known as stepwise refinement, to decompose it into sub￾problems. The sub-problems can be further decomposed into smaller, more manageable problems. PrintCalender PrintCalender Case Study Case Study • Let us use the PrintCalendar example to demonstrate the stepwise refinement approach. December 2005 ---------------------------------------- Sun Mon Tue Wed Thu Fri Sat 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Design Diagram printCalendar (main) readInput printMonth getStartDay printMonthTitle printMonthBody getTotalNumOfDays getNumOfDaysInMonth getMonthName isLeapYear

上海安通大华交大思西四 上海又通大平又大园西积 一·联合学院一 一·联合学院一 tM-Sprt Joint UM-STTU joint Implementation:Top-Down Stub examples Top-down approach is to implement one To print a calender for a given year Function in the structure chart at a time from -Print calender for each month the top to the bottom.Stubs can be used for the To print calender for a specified month Functions waiting to be implemented. Print the title line A stub is a simple but incomplete version of a -Find how many days in the month Function.The use of stubs enables you to test Find out which day is the first day(Monday-Sunday) invoking the Function from a caller.Implement -Ident the first line to put Ist day of the month on the the main Function first and then use a stub for right weekday position the printCalendar Function. -Print rest of the day in the month 上#文通大苹文天智围 上父大大 -·联合学院 ·联合学院 UM-SJTU Joint imstitute Implementation Approaches Implement Bottom-Up The previous approach is called top-down void Givelnstructions(void); approach. int GetYearFromUser(void); void PrintCalendar(int year); Sometimes,bottom-up approach is preferred. void PrintCalendarMonth(monthT month,int year); Both top-down and bottom-up approaches are void IndentFirstLine(weekdayT weekday); fine.Both approaches implement the functions int MonthDays(monthT month,int year); incrementally and help to isolate programming weekdayT FirstDayOfMonth(monthT month,int year); errors and makes debugging easy.Sometimes, string MonthName(monthT month); they can be used together. bool IsLeapYear(int year); 上海文山大平夏大网 上海父通大学义大智否似 一·联合学院 一·联合学院 UM-SITU Joint Institute M-sTol解mstitute Function vs.Algorithm Example:Find Primes While an algorithm is an abstract strategy and is One the most aged and interesting problem is to often expressed in English,a function is a concrete realization of that algorithm in the find prime number among positive integers. context of a programming language. Prime is an integer it has only two divisors, Characteristics of an algorithm which are always '1'and 'itself Clear and Unambiguous in its definition It is of great importance today because it plays a -Effective,in the sense that its steps are executable central role in many forms of Cryptography. -Finite.in the sense that it terminates after a certain number of steps We are asked to design a function which could We will discuss several simple algorithms and determine whether an given integer is a prime leads to questions like efficiency and robustness. 4

4 Implementation: Top Implementation: Top-Down • Top-down approach is to implement one Function in the structure chart at a time from the top to the bottom. Stubs can be used for the Functions waiting to be implemented. • A stub is a simple but incomplete version of a Function. The use of stubs enables you to test invoking the Function from a caller. Implement the main Function first and then use a stub for the printCalendar Function. Stub examples Stub examples • To print a calender for a given year – Print calender for each month • To print calender for a specified month – Print the title line – Find how many days in the month – Find out which day is the first day (Monday-Sunday) – Ident the first line to put 1st day of the month on the right weekday position – Print rest of the day in the month Implementation Approaches Implementation Approaches • The previous approach is called top-down approach. • Sometimes, bottom-up approach is preferred. • Both top-down and bottom-up approaches are fine. Both approaches implement the functions incrementally and help to isolate programming errors and makes debugging easy. Sometimes, they can be used together. Implement Bottom-Up • void GiveInstructions(void); • int GetYearFromUser(void); • void PrintCalendar(int year); • void PrintCalendarMonth(monthT month, int year); • void IndentFirstLine(weekdayT weekday); • int MonthDays(monthT month, int year); • weekdayT FirstDayOfMonth(monthT month, int year); • string MonthName(monthT month); • bool IsLeapYear(int year); Function vs. Algorithm • While an algorithm is an abstract strategy and is often expressed in English, a function is a concrete realization of that algorithm in the context of a programming language. • Characteristics of an algorithm – Clear and Unambiguous in its definition – Effective, in the sense that its steps are executable – Finite, in the sense that it terminates after a certain number of steps • We will discuss several simple algorithms and leads to questions like efficiency and robustness. Example: Find Primes Example: Find Primes • One the most aged and interesting problem is to find prime number among positive integers. • Prime is an integer it has only two divisors, which are always ‘1’ and ‘itself’ • It is of great importance today because it plays a central role in many forms of Cryptography. • We are asked to design a function which could determine whether an given integer is a prime

上海安通大华交大思西四 上海文通大平又大园西积 一·联合学院·一 一·联合学院一 tM-Sprt Joint Institute UMt-STrU joint Problem Analysis Find Primesa brute force way By definition,we could design a algorithm bool IsPrime (int n) like this: int i,divisors =0; -Check each number between 1 and n to see if for(1-1:i<=n;1++) it is a divisor of n -Add 1 to a running count each time you iF(n名i-g) encounter a new divisor divisors+; : -Check if the divisor count equals 2 after all the numbers have been tested return (divisors --2): 上#文通大竿父大智网 ·联合学院 UM-STU Joint lmstitute Find Primes bool IsPrime (int n) Rethink??? 1nt1; It is clearly written and it WORKS,however, if(n名2-=0) it is not efficient.We could improve it's return FALSE; efficiency in many ways: else -If we skip the1'and 'n'in the loop,it could stop for (i 3;i <sqrt (n);i +-2) as long as a divisor has been found; 《 if(n老i=0) -if 2 is not a divisor,we could skip all of the even return FALSE; numbers It is sufficient to check up to sgrt(n)instead of n. eturn TRUE: 上海文山大平夏大石队 一·联合学院 The Final Version UM-SITU Joint Institute bool IsPrime (int n) Rethink??? int i,limit; ·Is it correct?: don't forget the special case when 誓82，et2Tu6}: n==2 return FALSE; }: ·Numerical error is a nature of computer.What dnia_gtgn:主52 result do you expect for it: iF(n名i==g) sqrt (49) 《 return FALSE; ·Can it be further move complex expressions 》； out of the iteration 》； improved？ return TRUE; 6

5 Problem Analysis Problem Analysis • By definition, we could design a algorithm like this: – Check each number between 1 and n to see if it is a divisor of n – Add 1 to a running count each time you encounter a new divisor – Check if the divisor count equals 2 after all the numbers have been tested Find Primesa Primesa brute force way brute force way Rethink??? Rethink??? • It is clearly written and it WORKS, however, it is not efficient. We could improve it’s efficiency in many ways: – If we skip the ‘1’ and ‘n’ in the loop, it could stop as long as a divisor has been found; – if 2 is not a divisor, we could skip all of the even numbers – It is sufficient to check up to sqrt (n) instead of n. Find Primes Find Primes Rethink??? Rethink??? • Is it correct? • Can it be further improved? • don’t forget the special case when n == 2 • Numerical error is a nature of computer. What result do you expect for it: sqrt (49) • move complex expressions out of the iteration The Final Version The Final Version