Computer Number Systems
Recursive Functions
What does this program do?
100

Solve for x where x16=36768.


37 B E16 

convert each octal digit into base 2group by 4 bits, from right-to-leftconvert each group of 4 bits into a hex digit

100

Problem: Find g(11) given the following

g(x)={g(x−3)+13x if x>0 otherwise}

1

100

What does this code do and how does it work?

int x = 100, y = 90;

System.out.printf("The average of %d and %d is %6.2f\n",x, y, (x+y)/2.0 );

It prints the average by taking the output a floating point using a width of 6 and 2 decimal digits.

200

Convert 506210 into binary

10011110001102.

200

Problem: Find the value of h(13) given the following definition of h:


h(x) ={h(x−7)+1xh(x+3) when x>5 when 0≤x≤5 when x<0}


4

200

After the following program is executed, what is the final value of NUM?


A = “BANANAS”
NUM = 0: T = “”
for J = len(A) - 1 to 0 step –1
     T = T + A[j]
next 
for J = 0 to len(A) - 1
    if A[J] == T[J] then NUM = NUM + 1
next



Solution: 1,2,3,4,5

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. Variable NUM is incremented each time a character at position x of A is the same as the character in position x of string T. There are 5 such positions: 1, 2, 3, 4, and 5.

300

How many numbers from 100 to 200 in base 10 consist of distinct ascending digits and also have distinct ascending hex digits when converted to base 16?

Solution: There are 13 numbers that have ascending digits in both bases from 100 to 200. They are (in base 10): 123 (7B), 124, 125, 126, 127 (7F), 137 (89), 138, 139 (8B), 156 (9C), 157, 158, 159 (9F), 189 (BD)

300

Consider the following recursive algorithm for painting a square:

1. Given a square. 2. If the length of a side is less than 2 feet, then stop. 3. Divide the square into 4 equal size squares (i.e., draw a “plus” sign inside the square). 4. Paint one of these 4 small squares. 5. Repeat this procedure (start at step 1) for each of the 3 unpainted squares.

If this algorithm is applied to a square with a side of 16 feet (having a total area of 256 sq. feet), how many square feet will be painted?

175

In the first pass, we get four squares of side 8. One is painted, three are unpainted. Next, we have 3*4 squares of side 4. Three are painted (area=3*42), nine are not. Next, we have 9*4 squares of side 2. Nine are painted (area = 9*22), 27 are not. Finally, we have 27*4 squares of side 1. Twenty-seven are painted. Therefore, the total painted is 1*82 + 3*42 + 9*22 + 27*12 = 175.

300

After this program is executed, what is the value of B that is printed if the input values are 50 and 10?


input H, R
B = 0
if H>48 then
    B = B + (H - 48) * 2 * R
    H = 48
end if
if H>40 then
   B = B + (H - 40) * (3/2) * R
   H = 40
end if
B = B + H * R
output B


560

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:

Therefore, the final value of B is 2*2*10 + 8*3/2*10 + 40*10 = 40 + 120 + 400 = 560.

400

Solve for x in the following hexadecimal equation: x=F5AD16−69EB16

Combining these results of each column, we get a final answer of 8BC216.

One could convert the hex numbers into base 10, perform the subtraction, and then convert the answer back to base 16. However, working directly in base 16 isn't too hard. As in conventional decimal arithmetic, one works from right-to-left, from the least significant digits to the most.

The rightmost digit becomes 2, because D-B=2.The next column is A-E. We need to borrow a one from the 5 column, and 1A-E=CIn the next column, 4-9=B, again, borrowing a 1 from the next column.Finally, the leftmost column, E-6=8


400

Given a number and its reverse. Find that number raised to the power of its own reverse.
Note: As answers can be very large, print the result modulo 109 + 7.

Example 1:

Input:
N = 2, R = 2
Output: 4
Explanation: The reverse of 2 is 2 and after raising power of 2 by 2 we get 4 which gives remainder as 4 when divided by 1000000007.

Example 2:

Input:
N = 12, R = 21
Output: 864354781
Explanation: The reverse of 12 is 21and 1221 when divided by 1000000007 gives remainder as 864354781.

Your Task:
You don't need to read input or print anything. You just need to complete the function pow() that takes two parameters N and R denoting the input number and its reverse and returns power of (N to R)mod(109 + 7).

Expected Time Complexity: O(LogN).
Expected Auxiliary Space: O(LogN).

Constraints:
1 <= N <= 109

1221 % (109+7)

400

After the following program is executed, what is the final value of C[4]?


A(0) = 12: A(1) = 41: A(2) = 52
A(3) = 57: A(4) = 77: A(5) = -100
B(0) = 17: B(1) = 34: B(20 = 81
J = 0: K = 0: N = 0
while A(J) > 0
  while B(K) <= A(J)
    C(N) = B(K)
    N = N + 1
    k = k + 1
  end while
  C(N) = A(J): N = N + 1: J = J + 1
end while
C(N) = B(K)



Solution:

The following table traces the variables through the execution of the program.

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.

M
e
n
u