{VERSION 5 0 "IBM INTEL LINUX" "5.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "" -1 256 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 258 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }1 0 0 0 8 4 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 256 21 "Programmin g in Maple." }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 15 "The if command." }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 56 "In Maple, the structure of the i f command is as follows:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 17 "if boolean1 then" }}{PARA 0 "" 0 "" {TEXT -1 59 " one or more commands seperated by colons or semi-colons" }}{PARA 0 "" 0 "" {TEXT -1 18 "elif boolean2 then" }}{PARA 0 "" 0 "" {TEXT -1 59 " one or more commands seperated by colons or semi-colons" }} {PARA 0 "" 0 "" {TEXT -1 8 "elif ..." }}{PARA 0 "" 0 "" {TEXT -1 5 " \+ ..." }}{PARA 0 "" 0 "" {TEXT -1 4 "else" }}{PARA 0 "" 0 "" {TEXT -1 58 " one or more commands seperated by colons or semi-colons" }} {PARA 0 "" 0 "" {TEXT -1 6 "end if" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 194 "This entire construction is considered a s one Maple command (even though there can be many commands inside). T o run the command, you have to place a colon or semi-colon after it, a nd hit return." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 201 "There can be as many \"elif boolean then ...\" as you wa nt (there can also be 0). The output of the \"if\" command is the last evaluated expression. For example, if you give Maple the following if -command:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 11 "if x=0 then" }}{PARA 0 "" 0 "" {TEXT -1 12 " a:=3+5;" }}{PARA 0 "" 0 "" {TEXT -1 11 " b:=a+7" }}{PARA 0 "" 0 "" {TEXT -1 13 "eli f x=1 then" }}{PARA 0 "" 0 "" {TEXT -1 5 " 5" }}{PARA 0 "" 0 "" {TEXT -1 4 "else" }}{PARA 0 "" 0 "" {TEXT -1 6 " x^2" }}{PARA 0 "" 0 "" {TEXT -1 7 "end if;" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 303 "then, if x=0 the commands a:=3+5;b:=a+7 will be e xecuted, the last expression was a+7 which is 3+5+7=15 so the output o f this if-command will be 15 if x=0. If x=1 then the \"command\" 5 is \+ the only thing that gets \"executed\", the output will be 5. In all ot her cases we reach \"else\" and the output is x^2." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 77 "Note that \"fi\" (that's \+ \"if\" in reverse order) in Maple is short for \"end if\"." }}{PARA 0 "" 0 "" {TEXT 257 29 "Remark for Maple 5 and older:" }{TEXT -1 265 " I n Maple 5 you can only end the \"if\" statement with \"fi\" and not wi th \"end if\". In Maple 6 and 7, you can choose between \"fi\" and \"e nd if\". So I'm typing \"fi\" now because that way it works in Maple 5 , 6 and 7, whereas typing \"end if\" would work with Maple 6 and 7." } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 8 "Example: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "x:=-3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "if x < 0 then -x else x fi;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "x:='x';" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 27 "if x < 0 then -x else x fi;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 93 "Here an error is produced because the boolean \"x < \+ 0\" can not be simplified to true or false." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "if false then 0 else 1 fi;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 227 "The command evalb (evaluate boolean) will try to d etermine if the input is true or false. If it can, the output is true \+ or false. If it can not determine that, then the output is just the in put (or is equivalent to the input)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "evalb( 4 < 5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "evalb(10! - 10^7 > 0);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 78 "evalb( 17 ); # 17 can never become either \"true\" or \"false \" and thus an error:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 193 "e valb( y^2+y<0 ); # right now we can not determine \"true\" or \"false \", but perhaps later in the future we can if some value would be assi gned to y, so no error message, it just returns the input" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "if y^2+y < 0 then 0 else 1 fi;" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "The following command is:" }} {PARA 0 "" 0 "" {TEXT -1 93 "if \"we can evaluate if y^2+y<0 or not\" \+ and \"y^2+y is indeed < 0\" then the output is 0 else 1." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "if evalb(y^2+y < 0) = true then 0 e lse 1 fi;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "Note that the \"then \" part is not needed either." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 6 "x:=-3;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "if evalb(x < 0)=true then x:=-x fi;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "x:='x';" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "if evalb(x < 0) =true then x:=-x fi;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 121 "now ev alb(x<0) was just x<0 and was not equal to true, so the if-command exe cuted no other commands, so nothing happened." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 507 "When you have many elif' s or if you have many Maple commands then for readability you might wa nt to type the input over more than 1 line. There is one problem thoug h, whenever you hit RETURN, Maple will think it will have to start com puting. If you want to move to the next line but you have not yet fini shed typing the if command, then use shift-RETURN. So to enter an if c ommand like the following, you need shift-returns to go to the next li ne. Only when the entire command is entered can you use RETURN." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 359 "if 3^3 < 2^4 then # type sh ift return to get to the next line\n a := 2^4 - 3^3; \n b := a^2; \n a + b # Note: a (semi)-colon is not needed here (*)\nelif 1 > 2 then\n print( \"this can not possibly be right\" );\n a := \+ 11;\n b := 7+5 # Note: a (semi)-colon is not needed here\nelse \n x^2 # Note: a (semi)-colon is not needed here\nfi;" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 158 "(*) a (semi)-colon is not needed here because there is no command after a+b. However, it is not an err or if you do use one anyway, you could write a+b; here." }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 15 "The do command." }}{EXCHG {PARA 0 "" 0 " " {TEXT -1 62 "In Maple, the basic structure of the do command is as f ollows:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 2 "do" }}{PARA 0 "" 0 "" {TEXT -1 37 " commands seperated by (semi)-col ons" }}{PARA 0 "" 0 "" {TEXT -1 6 "end do" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 209 "Note: \"od\" (which is \"do\" in \+ reverse order) is the same as \"end do\". In Maple 6 and 7 you can use both \"od\" and \"end do\", but in Maple 5 you can only use \"od\", w hich is what I will use in this Maple worksheet." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 184 "The entire construction \+ is considered as one Maple command (even though there can be many comm ands inside). To run it, end it with : or ; and hit return. In the fol lowing construction:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 2 "do" }}{PARA 0 "" 0 "" {TEXT -1 11 " command1;" }}{PARA 0 "" 0 "" {TEXT -1 11 " command2;" }}{PARA 0 "" 0 "" {TEXT -1 10 " c ommand3" }}{PARA 0 "" 0 "" {TEXT -1 7 "end do;" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 85 "what will happen is: comm and1; command2; command3; command1; command2; command3;....." }}{PARA 0 "" 0 "" {TEXT -1 334 "So that's an infinite loop. Now in interactive computations that's inconvenient but sometimes acceptable because you can always click on \"STOP\" (in the graphical version of Maple) or p ress control-c (in the text version of Maple) to interrupt the computa tion. But infinite loops are of course terrible inside non-interactive programs." }}{PARA 0 "" 0 "" {TEXT -1 122 "You can get out of a do-od (do .. end do) loop by the \"break\" command. The break command will exit the loop. For example:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 163 "i := 1;\nS := 0;\ndo\n if i < 4 then\n i:=i+1\n elif i < 30 then\n i:=i+10\n else\n print( \"i =\", i);\n b reak\n fi;\n S := S + i^2\nod;\nT := S^2;" }{TEXT -1 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 344 "By the time we reach \"else\", wh en i is no longer <30, the break command is executed. When Maple sees \+ \"break\", it will search for the next \"od\" or \"end do\" and contin ue after that. So the commands between \"break\" and \"od\" will be sk ipped. As you can see, after we hit \"break\" the command S:=S+i^2 was skipped and we proceeded straight to T:=S^2;" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 156 "The command \"next\" wil l also skip the rest of the loop, but will not break the loop. So the \+ next command brings you right back to the beginning of the loop." }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "There are two other ways to use do-od without having an infinite loop. One is b y using:" }}{PARA 0 "" 0 "" {TEXT -1 33 " for ... do\n ...\n \+ od;" }}{PARA 0 "" 0 "" {TEXT -1 21 "and the other way is:" }}{PARA 0 "" 0 "" {TEXT -1 43 " while boolean do\n ...\n od;" }}{PARA 0 "" 0 "" {TEXT -1 58 "Note that for and while can also be com bined. For example:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "S := \{seq(seq(i^2+j^2,i=j+1..4),j=1..4)\};" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "S:=sort([op(S)]);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "T:=0;\nfor i in S while i<>17 do\n print( \"i =\",i );\n T := T+i\nod;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 106 "The \"fo r i in S\" will cause i to go through S. But the \"while i<>17\" will \+ cause the loop to stop whenever:" }}{PARA 0 "" 0 "" {TEXT -1 86 " \"w e are back at the beginning of the loop, and the boolean i<>17 evaluat es to false\"" }}{PARA 0 "" 0 "" {TEXT -1 76 "Half-way trough our list the boolean i<>17 becomes false and the loop stops." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 66 "See the help page for \+ \"for\" for other examples. Do this by typing:" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 4 "?for" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 10 "Procedures" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }{TEXT 258 0 "" }{TEXT -1 33 "In Maple, a procedu re looks like:" }}{PARA 0 "" 0 "" {TEXT -1 21 " proc(a1,a2,...,an)" }}{PARA 0 "" 0 "" {TEXT -1 25 " local v1,v2,..,vk;" }}{PARA 0 " " 0 "" {TEXT -1 26 " global w1,w2,..,wl;" }}{PARA 0 "" 0 "" {TEXT -1 26 " options o1,o2,..os;" }}{PARA 0 "" 0 "" {TEXT -1 28 " body of the procedure" }}{PARA 0 "" 0 "" {TEXT -1 11 " en d proc" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 135 "In Maple 5 you must end the procedure with \"end\" and not with \+ \"end proc\". In Maple 6 and 7 you can use both \"end\" as well as \"e nd proc\"" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 77 "Each of the three lines \"local .. \", \"global ...\", \"options . ..\" is optional." }}{PARA 0 "" 0 "" {TEXT -1 520 "local ...; speci fies the local variables. A local variable is different from any varia ble outside of the procedure even if the name is the same. In most pro cedures, most or all of the variables used inside the procedure are lo cal. This way one prevents messing up global variables (the variables \+ outside of the procedure). Using global variables can cause some unple asant surprises for the users, it causes that some variables change va lue when the procedure is called, which is in most cases not what a us er expects." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 225 "Nevertheless, it is sometimes convenient to use global variabl es. To indicate to Maple that a variable is global, so that it does ch ange variables that a user might be using, use global and specify the \+ names of the variables." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 227 "It is allowed to use a variable inside a procedure \+ without specifying if it is local or global. In that case Maple will g uess if it is local or global, and print its guess on the screen. This is convenient for short procedures." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 496 "The body of the procedure consists of \+ one or more commands, that are seperated by a colon or semicolon. It m akes no difference if you use colon or semicolon. Note that the purpos e of these (semi)-colons is to seperate commands. Therefore it is not \+ necessary to use a (semi)-colon after the last command. However, if yo u use one anyway even though it was not necessary, then Maple will not complain. However, if you don't use a (semi)-colon where one is neede d, then you will get an error message." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 145 "In the line \"options ...\" some opt ions can be specified. The most commonly used option is \"options reme mber;\" of which we will see examples soon." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 344 "The input of the procedure (in Maple that is called the \"arguments\") are specified after proc betw een ( ). Note that n could be 0, one could have procedures with no arg uments. Even if n=0 so you do something like proc() ... then you can \+ still give arguments to that procedure, and those arguments are visibi ble inside the procedure as follows:" }}{PARA 0 "" 0 "" {TEXT -1 30 " \+ nargs = number of arguments" }}{PARA 0 "" 0 "" {TEXT -1 27 " args[ i] = i'th argument." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 158 "In most situations, if you want to use the procedure i n a convenient way, you will have to give the procedure a name. In Map le, this is done by an assignment:" }}{PARA 0 "" 0 "" {TEXT -1 2 " " }{TEXT 259 54 "Defining a procedure is done by one single assignment. " }}{PARA 0 "" 0 "" {TEXT -1 254 "And since an assignment is a Maple c ommand, you have to end this with a colon (nothing printed to the scre en) or semi-colon (Maple will print the procedure). So if we want to d efine a procedure and give it a name, we have to do something that loo ks like:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 45 "name_of_the_procedure := proc(a1,a2,...,an)" }}{PARA 0 "" 0 "" {TEXT -1 25 " local v1,v2,..,vk;" }}{PARA 0 "" 0 "" {TEXT -1 26 " global w1,w2,..,wl;" }}{PARA 0 "" 0 "" {TEXT -1 26 " opt ions o1,o2,..os;" }}{PARA 0 "" 0 "" {TEXT -1 21 " first_command; " }}{PARA 0 "" 0 "" {TEXT -1 22 " second_command;" }}{PARA 0 "" 0 "" {TEXT -1 10 " ..." }}{PARA 0 "" 0 "" {TEXT -1 19 " la st_command" }}{PARA 0 "" 0 "" {TEXT -1 12 " end proc:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 133 "The output if the p rocedure is always the same as the output of the last command that was executed inside the procedure. For example:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "F := proc(x)\n if x=0 then\n infinity\n else \n 1/x\n fi\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "s eq(F(i), i=-2..4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 88 "If x was 0 \+ then the last \"command\" was infinity, and otherwise the last command was 1/x." }}{PARA 0 "" 0 "" {TEXT -1 48 "A procedure like this would \+ not make much sense:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "F : = proc(x)\n if x=0 then\n infinity\n else\n 1/x\n fi;\n x^ 2\nend;" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 125 "because the if-comman d is executed but that has no impact on the output, the last evaluated expression is always x^2 anyways." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 222 "The \"return\" command ends a procedure \+ right away. You can give an argument to return. If you do, that will b e the output. If you don't give an argument to return, then the output of the procedure is NULL, which looks like:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "NULL; # this prints nothing to the screen" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 5 "Note:" }}{PARA 0 "" 0 "" {TEXT -1 59 "In old versions of Maple (Maple 5 and older) the syntax is:" }} {PARA 0 "" 0 "" {TEXT -1 18 " RETURN( output )" }}{PARA 0 "" 0 "" {TEXT -1 2 "or" }}{PARA 0 "" 0 "" {TEXT -1 11 " RETURN() " }}{PARA 0 "" 0 "" {TEXT -1 49 "if you want to return \"nothing\" i.e. return NUL L." }}{PARA 0 "" 0 "" {TEXT -1 89 "This also works in Maple 6, 7, 8, 9 , 9.5, 10,..., however, in those versions you can use:" }}{PARA 0 "" 0 "" {TEXT -1 16 " return output" }}{PARA 0 "" 0 "" {TEXT -1 8 "or j ust:" }}{PARA 0 "" 0 "" {TEXT -1 9 " return" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 8 "Example:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 125 "F := proc(x)\n if x=0 then return infin ity fi;\n # After this we may assume that x<>0 so this won't give an \+ error:\n 1/x\nend;" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "seq(F(i), i=-1..2);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 39 "Now for some more interesting examples." }}{PARA 0 "" 0 "" {TEXT -1 17 "Example \"subsets\"" }}{PARA 0 "" 0 "" {TEXT -1 15 "Input: a set S." }}{PARA 0 "" 0 "" {TEXT -1 63 "Output: a set T such that every subset of S is an element of T." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 94 "Note 1: If S has n e lements, then there are precisely 2^n subsets of S. So T has 2^n eleme nts." }}{PARA 0 "" 0 "" {TEXT -1 113 "Note 2: If S = \{\} is the empty set, then S has 1 subset, namely \{\}. So then T must have \{\} as el ement. So T=\{\{\}\}." }}{PARA 0 "" 0 "" {TEXT -1 64 "Note 3: S is alw ays a subset of S, so S must be an element of T." }}{PARA 0 "" 0 "" {TEXT -1 89 "Note 4: If e is an element of S, and s is a subset of S t hen there are two possibilities:" }}{PARA 0 "" 0 "" {TEXT -1 40 " a ) e is not in s\n b) e is in s." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 222 "To write an algorithm for determining \+ all subsets of S, it is sufficient to know only \"Note 2\" and \"Note \+ 4\". Notes 1 and 3 were completely unnecessary information. Using jus t note 2 and 4 gives us the following algorithm:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 1284 "subsets := proc(S)\n local e,U,T,i; # Not e: if you replace \"local\" by \"global\" then\n # th e procedure will give wrong answers.\n if S = \{\} then\n T := \{\{\}\} # because of Note 2.\n else\n # At this point we m ay assume that S has an element.\n # This implies that the follo wing command will not\n # lead to an error:\n e := S[1];\n # Now e is some element of S. The rest of S is:\n U := S \+ minus \{e\};\n # We can now calculate all subsets of U by recurs ion.\n # Recursion means: call this procedure from itself. This \n # is OK as long as U is \"smaller\" in some sense as S,\n \+ # because then the recursion must end at some point.\n T := s ubsets(U);\n # Notice that the elements of T are precisely those \n # subsets of S that do not have the element e.\n # Now \+ we will use Note 4:\n T := T union \{seq(i union \{e\}, i=T)\}\n fi;\n # to check that our procedure is correct we can now do\n \+ # the following:\n if nops(T) <> 2^nops(S) then\n # the followi ng command will interrupt the computation\n # and will print an e rror message to the screen:\n error \"our procedure is completely wrong\"\n fi;\n # Now that the output T is sufficiently tested, l ets return it:\n T\nend; " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "S:=\{x,y,2\};" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "subsets(S);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 52 "Same proce dure but now shorter and without the test:" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 199 "subsets := proc(S)\n local e,U,T,i;\n if S = \+ \{\} then\n \{\{\}\}\n else\n e := S[1];\n U := S \+ minus \{e\};\n T := procname(U);\n T union \{seq(i union \+ \{e\}, i=T)\}\n fi\nend; " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 245 "Note: the name \"procname\" refers to \"name of this procedure\". It is convenient to call \"procname\" instead of \"subsets\" if you l ater decide to use a different name for this procedure (then you don't have to make any changes inside the procedure)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "\{\}; # In Maple, the empty set is denoted a s \{\}." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "subsets(%);" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 139 "The empty set has one subset (nam ely the empty set itself) and so subsets( \{\} ) gave a set with exact ly one element, that element being \{\}." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "subsets(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "subsets(%);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 16 "Another exam ple:" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "I nput: an integer n." }}{PARA 0 "" 0 "" {TEXT -1 40 "Output: the set of all lists, such that:" }}{PARA 0 "" 0 "" {TEXT -1 48 "1) the elemen ts of lists are positive integers" }}{PARA 0 "" 0 "" {TEXT -1 47 "2) \+ the sum of the elements of each list is n." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 8 "Remarks:" }}{PARA 0 "" 0 "" {TEXT -1 28 " n < 0 --> output is \{\}" }}{PARA 0 "" 0 "" {TEXT -1 69 "because no such lists exists, so the solution set is the empty \+ set \{\}" }}{PARA 0 "" 0 "" {TEXT -1 33 " n = 0 --> output is \{ \+ [] \}" }}{PARA 0 "" 0 "" {TEXT -1 207 " because only the empty list h as sum 0, so the empty list is the only element of the solution set.\n n > 0. If n>0 and if L is a list in the output, then L[1] must be one of the following numbers: 1,2..,n" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 82 "These three remarks are sufficient to write a complete algorithm for this problem!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 264 "sum_is_n := proc(n)\n local i,j;\n if n<0 t hen\n \{\}\n elif n=0 then\n \{ [] \}\n else\n # No te: if i is a number and j is a list j=[a,b,c,..]\n # then [i, op(j)] = [i,a,b,c,...]\n \{seq( seq([i,op(j)], j = procname(n-i)) , i=1..n)\}\n fi\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "sum_is_n(1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "sum_is_n(2 );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "sum_is_n(3);" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "sum_is_n(4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 27 "Another example:\nFibonnaci:" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 11 "F(0)=F(1)=1" }} {PARA 0 "" 0 "" {TEXT -1 29 "n>1 -> F(n) = F(n-1) + F(n-2)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 146 "F := proc(n)\n if n=0 or n=1 then \n 1\n elif n>1 then\n F(n-1) + F(n-2)\n else\n error \" input should be a non-negative integer\"\n fi\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(5);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "F(24); # This takes some time." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 121 "This procedure is slow because many things are re-c omputed over and over again. To see this, issue the following command: " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "trace(F); # this will \+ cause Maple to display the computation" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "F(4);" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 121 "As you \+ can see (especially if you type F(6) or F(7) or so), the procedure F i s entered several times with the same input." }}{PARA 0 "" 0 "" {TEXT -1 12 "If you type:" }}{PARA 0 "" 0 "" {TEXT -1 7 " F(30)" }}{PARA 0 "" 0 "" {TEXT -1 191 "then F(10) will be computed thousands of times. \+ And F(5) will be called even more often. You can prevent Maple from re computing the same result by putting \"options remember\" in the proce dure." }}{PARA 0 "" 0 "" {TEXT -1 181 "With \"options remember\", when ever an input is encountered that has already been calculated before, \+ Maple will not run the procedure but simply give the same output as it had before." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 148 "So if you type F(30) with the following F, then F(10) will not be computed thousands of times, but only once, which should of course be much faster." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 166 "F := p roc(n)\n options remember;\n if n=0 or n=1 then\n 1\n elif n>1 \+ then\n F(n-1) + F(n-2)\n else\n error \"input should be a non -negative integer\"\n fi\nend;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "F(40); # takes almost no time:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 232 "With the pre vious procedure F, computing F(40) would have taken \"forever\" (not r eally forever, it would finish in a finite amount of time but it would take longer than we are willing to wait, which is no better than taki ng forever)." }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}}{MARK "0 0 1" 21 } {VIEWOPTS 1 1 0 3 2 1804 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }