The Guthrie sequence of a positive number n is defined to be the numbers generated by the above algorithm.

美国面试题6

1.题目：

Consider the following algorithm
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 sequence of a positive number n is defined to be the numbers generated by the above algorithm.
For example, the Guthrie sequence of the number 7 is 7, 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 from the number 7 by the above algorithm. Since 7 is odd multiply by 3 and add 1 to get 22 which is the second number of the sequence. Since 22 is even, divide by 2 to get 11 which is the third number of the sequence. 11 is odd so multiply by 3 and add 1 to get 34 which is the fourth number of the sequence and so on.
Note: the first number of a Guthrie sequence is always the number that generated the sequence and the last number is always 1.
Write a function named isGuthrieSequence which returns 1 if the elements of the array form a Guthrie sequence. Otherwise, it returns 0.
If you are programming in Java or C#, the function signature is
int isGuthrieSequence(int[ ] a)
If you are programming in C++ or C, the function signature is
int isGuthrieSequence(int a[ ], int len) when len is the number of elements in the array.

2.样例：

3.java 实现代码：

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

//          int a[] = {8,4,2,1};
//          int a[] = {8,17,4,1};
          int a[] = {8,4,1};
//          int a[] = {8,4,2};
        System.out.println(isGuthrieSequence(a));
    }

    public static int isGuthrieSequence(int[] a){
        int length = a.length;

        if(a[length-1]!=1){
            return 0;
        }
        for (int i = 0; i <length-1; i++){
            if(a[i]%2==0){
                if(a[i+1]!=a[i]/2){
                    return 0;
                };
            }else {

                if(a[i+1]!=3*a[i] +1){
                    return 0;
                };
            }
        }
        return 1;
    }
}