Before I do that, allow me to bring up a random number like 43 and ask you to do the following. I want you to add 1, then divide by two and round down, then subtract 4 twice, double the result of that, and subtract 4 three more times. Did you reach 16? I bet you did. How did those steps come about? Well let's look below.
import math
def linked_list_specific_sts(number):
''' (int) -> LinkedList
Return the steps necessary to reach 16
>>> lnk = linked_list_specific_sts(43)
>>> print(lnk)
43 -> Add 1 -> Divide by 2 and round down -> Subtract 4 -> Subtract 4 -> Double it -> Subtract 4 -> Subtract 4 -> Subtract 4 -> You have reached 16 ->|
'''
lnk = LinkedList()
lnk.append(str(number))
while number != 16:
if number % 2 == 0 and number < 16:
number = number * 2
lnk.append('Double it')
elif number % 2 == 1 and number < 16:
number = number + 1
lnk.append('Add 1')
elif number % 2 == 0 and 16 < number < 30:
number = number - 4
lnk.append('Subtract 4')
elif number % 2 == 1 and 16 < number < 30:
number = number - 1
lnk.append('Subtract 1')
elif number % 2 == 0 and 30 <= number < 100:
number = number//2
lnk.append('Divide by 2 and round down')
elif number % 2 == 1 and 30 < number < 100:
number = number + 1
lnk.append('Add 1')
elif number >= 100:
number = round(math.log(number, 10))
lnk.append('Round the base 10 log')
lnk.append('You have reached 16')
return lnk
As you can see, there are certain restrictions that lead to certain steps.
- If number is even and less than 16, double it
- If number is odd and less than 16, add 1
- If number is even and greater than 16 but less than 30, subtract 4
- If number is odd and greater than 16 but less than 30, subtract 1
- If number is even and greater than 30 but less than 100, divide by 2 and round down
- If number is odd and greater than 30 but less than 100, add 1
- If number is greater than 100, round the base 10 log
I did get lazy when the number gets higher than 100, but that's just me exercising one of the golden rules of being a computer scientist. Now you can do this on your own without the function above but what if you wanted to be sure that you were following the algorithm correctly after a certain amount of steps? Well, worry not, for obtain_sts_step has you covered.
def obtain_sts_step(lnk, step):
''' (LinkedList, int) -> int
Precondition: step != lnk.size - 1 and step > 1
Return what the step would be based on the instructions given
>>> lnk = linked_list_specific_sts(43)
>>> obtain_sts_step(lnk, 3)
18
>>> lnk = linked_list_specific_sts(35375)
>>> obtain_sts_step(lnk, 5)
20
'''
start = int(lnk[0])
for i in range(1, step+1):
if lnk[i] == 'Add 1':
start = start + 1
elif lnk[i] == 'Divide by 2 and round down':
start = start // 2
elif lnk[i] == 'Subtract 4':
start = start - 4
elif lnk[i] == 'Double it':
start = start * 2
elif lnk[i] == 'Round the base 10 log':
start = round(math.log(start, 10))
elif lnk[i] == 'Subtract 1':
start = start - 1
return start
As you can see, it returns to you the number after finally going through all the steps. We know how 43 goes, but what about 35375? Well first we should look at what happens when you enter that number into linked_list_specific_sts:
35375 -> Round the base 10 log -> Add 1 -> Double it -> Double it -> Subtract 4 -> Subtract 4 -> You have reached 16 ->|
We would stop at the first instance of Subtract 4, meaning that the next 5 numbers would be 5, 6, 12, 24, 20. Now that's if you want a quick check to see that your approach with the algorithm was correct. If you simply just want to see the numbers rather than the actions that you need to do, you can use linked_list_sts:
As you can see, it returns to you the number after finally going through all the steps. We know how 43 goes, but what about 35375? Well first we should look at what happens when you enter that number into linked_list_specific_sts:
35375 -> Round the base 10 log -> Add 1 -> Double it -> Double it -> Subtract 4 -> Subtract 4 -> You have reached 16 ->|
We would stop at the first instance of Subtract 4, meaning that the next 5 numbers would be 5, 6, 12, 24, 20. Now that's if you want a quick check to see that your approach with the algorithm was correct. If you simply just want to see the numbers rather than the actions that you need to do, you can use linked_list_sts:
def steps_to_sixteen(number):
""" (int) -> list of ints
Precondition: number != 0
Return a list of steps it takes to get to 16
>>> steps_to_sixteen(2)
[2, 4, 8, 16]
>>> steps_to_sixteen(3)
[3, 4, 8, 16]
>>> steps_to_sixteen(10)
[10, 20, 16]
>>> steps_to_sixteen(30)
[30, 15, 16]
>>> steps_to_sixteen(100)
[100, 2, 4, 8, 16]
"""
steps = []
steps.append(number)
while number != 16:
if number % 2 == 0 and number < 16:
number = number * 2
steps.append(number)
elif number % 2 == 1 and number < 16:
number = number + 1
steps.append(number)
elif number % 2 == 0 and 16 < number < 30:
number = number - 4
steps.append(number)
elif number % 2 == 1 and 16 < number < 30:
number = number - 1
steps.append(number)
elif number % 2 == 0 and 30 <= number < 100:
number = number//2
steps.append(number)
elif number % 2 == 1 and 30 < number < 100:
number = number + 1
steps.append(number)
elif number >= 100:
number = round(math.log(number, 10))
steps.append(number)
return steps
def linked_list_sts(number):
""" (int) -> NoneType
Return steps to take to sixteen as a linked list
>>> lnk = linked_list_sts(43)
>>> print(lnk)
43 -> 44 -> 22 -> 18 -> 14 -> 28 -> 24 -> 20 -> 16 ->|
"""
steps = steps_to_sixteen(number)
lnk = LinkedList()
for step in steps:
lnk.append(step)
return lnk
As you can see, I used a helper function which simply shows them as a list, and then have each step in the list be appended to the linked list.
No comments:
Post a Comment