Difference between revisions of "What Does This Program Do?"
Line 11: | Line 11: | ||
|- | |- | ||
|Operators | |Operators | ||
|! (not) , ^ (exponent), *, / (real division), % (modulus), +, -, >, <, >=, <=, !=, ==, && (and), || (or) in that order of precedence | |! (not) , ^ (exponent), *, / (real division), % (modulus), +, -, >, <, >=, <=, !=, ==, && (and), <math>||</math> (or) in that order of precedence | ||
|- | |- | ||
|Variables | |Variables | ||
Line 17: | Line 17: | ||
|- | |- | ||
|Sequential statements | |Sequential statements | ||
| | |||
{| class="wikitable" style="text-align: left" | |||
|- | |||
|INPUT variable | |INPUT variable | ||
variable = expression (assignment) | |- | ||
OUTPUT variable | |variable = expression (assignment) | ||
|- | |||
|OUTPUT variable | |||
|} | |||
|- | |- | ||
|Decision statements | |Decision statements | ||
|IF boolean expression | | | ||
{| class="wikitable" style="text-align: left" | |||
|- | |||
|IF boolean expression THEN | |||
|- | |||
|Statement(s) | |||
|- | |||
|ELSE (optional) | |||
|- | |||
|Statement(s) | |||
|- | |||
|END IF | |||
|} | |||
|- | |- | ||
|Indefinite Loop statements | |Indefinite Loop statements | ||
| | |||
{| class="wikitable" style="text-align: left" | |||
|- | |||
|WHILE Boolean expression | |WHILE Boolean expression | ||
|- | |||
| Statement(s) | |||
|- | |||
|END WHILE | |||
|} | |||
|- | |- | ||
|Definite Loop statements | |Definite Loop statements | ||
| | |||
{| class="wikitable" style="text-align: left" | |||
|- | |||
|FOR variable = start TO end STEP increment | |FOR variable = start TO end STEP increment | ||
|- | |||
| Statement(s) | |||
|- | |||
|NEXT | |||
|} | |||
|- | |- | ||
|Arrays: | |Arrays: | ||
|1D arrays use a single subscript such as A[5]. | |1D arrays use a single subscript such as A[5]. 2D arrays use row major order starting with [0,0] in the upper left corner. Use [] for identifying the subscript(s) so that A[5] is the 6th item in a list and A[2,3] is row 2 (third row) and column 3 (4th column). The size of the array will be specified in the problem statement. | ||
2D arrays use row major order starting with [0,0] in the upper left corner. | |||
Use [] for identifying the subscript(s) so that A[5] is the 6th item in a list | |||
The size of the array will be specified in the problem statement. | |||
|- | |- | ||
|Strings: | |Strings: | ||
|They can contain 0 or more characters and the indexed position starts with 0 as | |They can contain 0 or more characters and the indexed position starts with 0 as the first character. An empty string has a length of 0. Errors occur if accessing a character that is in a negative position or equal to the length of the string or larger. The len(A) function will find the length of the string which is the total characters. Strings are identified with surrounding double quotes. Use [] for identifying the characters in a substring of a given string as follows: If S = “ACSL WDTPD”, then S[:3] = “ACSL” (positions 0 to 3), S[5:] = “WDTPD” (positions 5 to 9), S[2:6] = “SL WD” (positions 2 to 6), and S[0] = “A” (position 0 only). The value of len(A) is 10. | ||
The value of len(A) is 10. | |||
|} | |} | ||
Line 80: | Line 91: | ||
::120 output B | ::120 output B | ||
Solution: | '''Solution:''' | ||
This program computes an employee’s weekly salary, given the hourly rate (R) and the number of hours worked in the week (H). The employee is paid an hourly rate for the number of hours worked, up to 40, time and a half for the overtime hours, up to 48 hours, and double for all hours over 48. The table monitors variables B and H: | |||
{| class="wikitable" | |||
|- | |||
!LINE || B || H | |||
|- | |||
|20 || 0 || 50 | |||
|- | |||
|50 || 40 || 48 | |||
|- | |||
|90 || 160 || 40 | |||
|- | |||
|110 || 560 || 40 | |||
|} | |||
Therefore, the final value of B is 2*2*10 + 8*3/2*10 + 40*10 = 40 + 120 + 400 = 560. | Therefore, the final value of B is 2*2*10 + 8*3/2*10 + 40*10 = 40 + 120 + 400 = 560. | ||
Line 100: | Line 121: | ||
::80 next | ::80 next | ||
Solution: | '''Solution:''' | ||
The program first stores the reverse of variable A into variable T and then counts the number of letters that are in the same position in both strings. | |||
A B A N A N A S | A B A N A N A S | ||
T S A N A N A B | T S A N A N A B | ||
Line 109: | Line 132: | ||
After the following program is executed, what is the final value of C[4]? | After the following program is executed, what is the final value of C[4]? | ||
:10 A[0] = 12: A[1] = 41: A[2] = 52 | |||
:20 A[3] = 57: A[4] = 77: A[5] = -100 | |||
:30 B[0] = 17: B[1] = 34: B[2] = 81 | |||
:40 J = 0: K = 0: N = 0 | |||
:50 while A[J] > 0 | |||
:60 while B[K] <= A[J] | |||
:70 C[N] = B[K] | |||
:80 N = N + 1 | |||
:90 k = k + 1 | |||
:100 end while | |||
:110 C[N] = A[J]: N = N + 1: J = J + 1 | |||
:120 end while | |||
:130 C[N] = B[K] | |||
'''Solution:''' | |||
The following table traces the variables through the execution of the program. | |||
{| class="wikitable" | {| class="wikitable" |
Revision as of 05:51, 19 August 2018
Frequently, one must use or modify sections of another programmer’s code. Since the original author is often unavailable to explain his/her code, it is essential to be able to read and understand an arbitrary program. This category has been rewritten using pseudocode similar to the design of the AP CS Principles course. Pseudo-code is English-like, language independent algorithmic code and should be able to be traced by students regardless of whether they are familiar with BASIC, C++, Java, Python, or any other high level language.
Description of Pseudo-code
We will use the following constructs in writing this code for this topic in ACSL:
Construct | Code Segment | |||||
---|---|---|---|---|---|---|
Operators | ! (not) , ^ (exponent), *, / (real division), % (modulus), +, -, >, <, >=, <=, !=, ==, && (and), [math]||[/math] (or) in that order of precedence | |||||
Variables | Start with a letter, only letters and digits | |||||
Sequential statements |
| |||||
Decision statements |
| |||||
Indefinite Loop statements |
| |||||
Definite Loop statements |
| |||||
Arrays: | 1D arrays use a single subscript such as A[5]. 2D arrays use row major order starting with [0,0] in the upper left corner. Use [] for identifying the subscript(s) so that A[5] is the 6th item in a list and A[2,3] is row 2 (third row) and column 3 (4th column). The size of the array will be specified in the problem statement. | |||||
Strings: | They can contain 0 or more characters and the indexed position starts with 0 as the first character. An empty string has a length of 0. Errors occur if accessing a character that is in a negative position or equal to the length of the string or larger. The len(A) function will find the length of the string which is the total characters. Strings are identified with surrounding double quotes. Use [] for identifying the characters in a substring of a given string as follows: If S = “ACSL WDTPD”, then S[:3] = “ACSL” (positions 0 to 3), S[5:] = “WDTPD” (positions 5 to 9), S[2:6] = “SL WD” (positions 2 to 6), and S[0] = “A” (position 0 only). The value of len(A) is 10. |
The questions in this topic will cover any of the above constructs in the Intermediate and Senior Division. In the Junior Division, loops will not be included in contest 1; loops will be used in contest 2; strings will be used in contest 3; and arrays will be included in contest 4. Line numbers will be included for the purpose of explaining the solution.
Sample Problems
Sample Problem 1
After this program is executed, what is the value of B that is printed if the input values are 50 and 10?
- 10 input H, R
- 20 B = 0
- 30 if H>48 then
- 40 B = B + (H - 48) * 2 * R
- 50 H = 48
- 60 end if
- 70 if H>40 then
- 80 B = B + (H - 40) * (3/2) * R
- 90 H = 40
- 100 end if
- 110 B = B + H * R
- 120 output B
Solution:
This program computes an employee’s weekly salary, given the hourly rate (R) and the number of hours worked in the week (H). The employee is paid an hourly rate for the number of hours worked, up to 40, time and a half for the overtime hours, up to 48 hours, and double for all hours over 48. The table monitors variables B and H:
LINE | B | H |
---|---|---|
20 | 0 | 50 |
50 | 40 | 48 |
90 | 160 | 40 |
110 | 560 | 40 |
Therefore, the final value of B is 2*2*10 + 8*3/2*10 + 40*10 = 40 + 120 + 400 = 560.
Sample Problem 2
After the following program is executed, what is the final value of NUM?
- 10 A = “BANANAS”
- 20 NUM = 0: T = “”
- 30 for J = len(A) - 1 to 0 step –1
- 40 T = T + A[j]
- 50 next
- 60 for J = 0 to len(A) - 1
- 70 if A[J] == T[J] then NUM = NUM + 1
- 80 next
Solution:
The program first stores the reverse of variable A into variable T and then counts the number of letters that are in the same position in both strings. A B A N A N A S T S A N A N A B * * * * * Those positions marked with an asterisk contribute one to the value of NUM. There are 5 such positions.
Sample Problem 3
After the following program is executed, what is the final value of C[4]?
- 10 A[0] = 12: A[1] = 41: A[2] = 52
- 20 A[3] = 57: A[4] = 77: A[5] = -100
- 30 B[0] = 17: B[1] = 34: B[2] = 81
- 40 J = 0: K = 0: N = 0
- 50 while A[J] > 0
- 60 while B[K] <= A[J]
- 70 C[N] = B[K]
- 80 N = N + 1
- 90 k = k + 1
- 100 end while
- 110 C[N] = A[J]: N = N + 1: J = J + 1
- 120 end while
- 130 C[N] = B[K]
Solution:
The following table traces the variables through the execution of the program.
j | k | n | A[j] | B[k] | C[n] |
---|---|---|---|---|---|
0 | 0 | 0 | 12 | 17 | 12 |
1 | 0 | 1 | 41 | 17 | 17 |
1 | 1 | 2 | 41 | 34 | 34 |
1 | 2 | 3 | 41 | 81 | 41 |
2 | 2 | 4 | 52 | 81 | 52 |
3 | 2 | 5 | 57 | 81 | 57 |
4 | 2 | 6 | 77 | 81 | 77 |
5 | 2 | 7 | -100 | 81 | 81 |
Thus, the value of C[4] is 52. Note that this program merges two arrays in increasing order into one array until a negative number is input.
Video Resources
The following YouTube videos show ACSL students and advisors working out some ACSL problems that have appeared in previous contests. Some of the videos contain ads; ACSL is not responsible for the ads and does not receive compensation in any form for those ads.