The Guthrie index of a positive number n is defined to be how many iterations of the above algorithm it takes before n becomes 1.

美国面试题8

1.题目：

Consider the following algorithm
if a is
return
reason
{3, 0, 2, -5, 0}
2
The sum of array is 0 and 0 occurs 2 times
{9, -3, -3, -1, -1}
0
The sum of the array is 1 and 1 does not occur in array.
{1}
1
The sum of the array is 1 and 1 occurs once in the array
{0, 0, 0}
3
The sum of the array is 0 and 0 occurs 3 times in the array
Start with a positive number n
if n is even then divide by 2
if n is odd then multiply by 3 and add 1
continue this until n becomes 1
The Guthrie index of a positive number n is defined to be how many iterations of the above algorithm it takes before n becomes 1.
For example, the Guthrie index of the number 7 is 16 because the following sequence is 16 numbers long.
22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
It is easy to see that this sequence was generated by the above algorithm. Since 7 is odd multiply by 3 and add 1 to get 22 which is the first number of the sequence. Since 22 is even, divide by 2 to get 11 which is the second number of the sequence. 11 is odd so multiply by 3 and add 1 to get 34 which is the third number of the sequence and so on.
Write a function named guthrieIndex which computes the Guthrie index of its argument. Its signature is
int guthrieIndex(int n)

2. 测试样例：

3.java实现

public class GuthrieIndex {
    public static void main(String[] args) {

        System.out.println(guthrieIndex(42));
    }

    public static int guthrieIndex(int n){

        int count =0;
        while (n !=1 ){

            if(n%2==0){
                count++;
                n = n/2;

            }else{
                count++;
                n = n*3+1;
            }
        }
        return count;

    }


}