home *** CD-ROM | disk | FTP | other *** search
/ Archive Magazine 1995 / ARCHIVE95.iso / discs / pipeline / 8_09 / Recursion / c_nCr next >
Text File  |  1995-04-09  |  4KB  |  284 lines
  1. %OP%VS4.13 (28-Apr-92), Gerald L Fitton, R4000 5966 9904 9938 
  2. %OP%TNN
  3. %OP%WRN
  4. %OP%DP0
  5. %OP%TH3
  6. %OP%IRN
  7. %OP%PL0
  8. %OP%HM0
  9. %OP%FM0
  10. %OP%BM0
  11. %OP%LM4
  12. %OP%PT1
  13. %OP%PDPipeLine
  14. %OP%WC2,1278,116,1672,0,77,0,45
  15. %OP%NDiteration_number,B58
  16. %OP%NDloop_counter,1001
  17. %OP%NDcurrent_value,B13
  18. %OP%NDloop_counter_2,1001
  19. %OP%NDtemporary_answer,B56
  20. %OP%NDanswer,B56
  21. %OP%NDiteration_number_1,B57
  22. %OP%NDiteration_number_2,B58
  23. %OP%NDinteration_number_3,B59
  24. %OP%NDiteration_number_3,B59
  25. %OP%NDr_on_entry,B57
  26. %OP%NDr_on_exit,B58
  27. %OP%NDentry_or_exit,B59
  28. %OP%FR0,2
  29. %CO:A,54,72%Comments and Commands
  30.  
  31. ------------------------------------------------------------------------
  32.  
  33. The custom function "binomial_1" calculates the value of nCr(n,r)
  34. It does so by using a Forá-áNext Loop to multiply the named variable
  35. "current_value" by n/r, then by (n-1)/(r-1), etc
  36.  
  37.  
  38. %V%%L%function("binomial_1","n:number","r:number")
  39.  
  40. Declare the name of the local variable and the slot it uses
  41. %V%%L%set_name("current_value",B13)
  42.  
  43. Initialise value of named variable
  44. %V%%L%set_value(current_value,1)
  45.  
  46. Now execute the Forá-áNext loop r times
  47. %V%%L%for("loop_counter",0,@r-1)
  48.  
  49.      Slow down the loop so we can see it operate (look at B13)
  50. %V%%L%  for("loop_counter_2",1,1000)
  51. %V%%L%  next
  52.  
  53.     The next line does the 'work'
  54. %V%%L% set_value(current_value,current_value*(@n-loop_counter)/(@r-loop_counter))
  55. %V%%L%next
  56.  
  57. Return the result
  58. %V%%L%result(current_value)
  59.  
  60.  
  61.  
  62. The custom function "binomial_2" calculates the value of nCr(n,r).
  63. It does so by using a recursive call to the function "binomial_2".
  64.  
  65. Each call to the custom function is executed only down to the point 
  66. where it becomes recursive.  I call this 'entering' because you can 
  67. imagine that each time you reach the point of recursion you enter a 
  68. gateway to the next recursion.  You can see this happening if you 
  69. observe the value of the local variable "r_on_entry" as the early part 
  70. of the function is executed for reducing values of r.
  71.  
  72. When the value of rá=á1 we have to stop the recursive procedure and 
  73. 'unwind' it by using the 'exit' part of the custom function.  You can 
  74. see this happening by observing the value of the local variable 
  75. "r_on_exit".
  76.  
  77. Also you will see that the local variable "entry_or_exit" takes 
  78. appropriate values to show which part of the loop is being executed.
  79.  
  80.  
  81. %V%%L%function("binomial_2","n:number","r:number")
  82.  
  83. Declare the 'names' of the variables and the slots they will use
  84. %V%%L%set_name("answer",B56)
  85. %V%%L%set_name("r_on_entry",B57)
  86. %V%%L%set_name("r_on_exit",B58)
  87. %V%%L%set_name("entry_or_exit",B59)
  88.  
  89. Initialise the local variables
  90. %V%%L%set_value(answer,0)
  91. %V%%L%set_value(r_on_entry,0)
  92. %V%%L%set_value(r_on_exit,0)
  93. %V%%L%set_value(entry_or_exit,"")
  94.  
  95. Show which value of r we are using during entry to recursion
  96. %V%%L%set_value(entry_or_exit,"Entry")
  97. %V%%L%set_value(r_on_entry,@r)
  98.  
  99. Slow down the operation so we can see it work
  100. %V%%L%for("loop_counter",1,1000)
  101. %V%%L%next
  102.  
  103. The next line contains the recursive call to the "binomial_2" function
  104. %V%%L%set_value(answer,if(@r>1,@n/@r*binomial_2(@n-1,@r-1),@n))
  105.  
  106. Show which iteration is being executed during exit of recursion
  107. %V%%L%set_value(entry_or_exit,"Exit")
  108. %V%%L%set_value(r_on_exit,@r)
  109.  
  110. Slow down the operation so we can see it work
  111. %V%%L%for("loop_counter",1,1000)
  112. %V%%L%next
  113.  
  114. Return the result
  115. %V%%L%result(answer)
  116. %CO:B,12,0%Value
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128. %V%%R%120
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
  157.  
  158.  
  159.  
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171. %V%%R%15180
  172. %V%%R%1
  173. %V%%R%3
  174. %V%%R%"Exit"
  175.  
  176.  
  177.  
  178.  
  179.  
  180.  
  181.  
  182.  
  183.  
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200. %CO:C,6,0%
  201.  
  202.  
  203.  
  204.  
  205.  
  206.  
  207.  
  208.  
  209.  
  210.  
  211.  
  212.  
  213.  
  214.  
  215.  
  216.  
  217.  
  218.  
  219.  
  220.  
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227.  
  228.  
  229.  
  230.  
  231.  
  232.  
  233.  
  234.  
  235.  
  236.  
  237.  
  238.  
  239.  
  240.  
  241.  
  242.  
  243.  
  244.  
  245.  
  246.  
  247.  
  248.  
  249.  
  250.  
  251.  
  252.  
  253.  
  254.  
  255.  
  256.  
  257.  
  258.  
  259.  
  260.  
  261.  
  262.  
  263.  
  264.  
  265.  
  266.  
  267.  
  268.  
  269.  
  270.  
  271.  
  272.  
  273.  
  274.  
  275.  
  276.  
  277.  
  278.  
  279.  
  280.  
  281.  
  282.  
  283.  
  284.