Question

(10 points) Does the following algorithm terminate when x = 9? Show your work. def mystery (x): while (x != 1) : if (x % 2 == 0): X = x/2 else: x = 3 * x + 1

Answer 1

Yes

The alogorithm terminates if x=9

while(9!=1) which is true

so it iterates

if(9%2==0) it was not true so goes to else block

than x=3*9+1 which is 28

again go to while block

while(28!=1) which is true so it enter into while block

if(28%2==0) it was true than

x=28/2 which is 14

now again goes to while loop

while(14!=1) which is true so enter into while loop than

if(14%2==0) which it true than it goes

x=14/2 which is 7

again it goes to while loop

than while(7!=1) which is true than

if(7%2==0) which is not true so it goes to else block

than

x=3*7+1 which is 22

now again it goes to while block

while(22!=1) true than

if(22%2==0) true than

x=x/2 which is 11

than again goes to while

while(11!=1) true

if(11%2==0) not true

so it goes else block

x=11*3+1 which is 34

now

while(34!=1) which true

than if(34%2==0) which is true

x=34/2 which is 17

than again goes to while

if 17%2==0 not true

x=17*3+1 which is 52

than again goes while than

if 52%2==0 true than

x=52%2 which is 26

than again goes to while than

if 26%2==0 true

than x=26/2 which is 13

than again goes to while loop than

if 13%2==0 not true

so x=3*13+1 which is 40 than again goes to while loop

if 40%2==0 which is true

than x=40/2 which is 20

than again goes to while loop

if 20%2==10 true

than x=20/2 which is 10

if 10%2==0 true

than x=10/2 which is 5

5%2==0 not true

than x=3*5+1 which is 16

16%2==0 true

than x=16/2 which is 8

8%2==0 true

than x=8/2 which is 4

4%2==0 true

than 4/2 which is 2

2%2==0 true

than 2/2 which is 1 it goes again while loop and check

while(1!=1) which is not true so while loop is terminated

#if you have any doubt or more information needed comment below.. i will respond as possible as soon..if you like give thumbs up..thanks..