【牛客】网易2016笔试题：饥饿的小易

本是古典何须时尚 2021-10-03 02:16 377阅读 0赞

链接：[https://www.nowcoder.com/questionTerminal/5ee8df898312465a95553d82ad8898c3][https_www.nowcoder.com_questionTerminal_5ee8df898312465a95553d82ad8898c3]  
来源：牛客网

小易总是感觉饥饿，所以作为章鱼的小易经常出去寻找贝壳吃。最开始小易在一个初始位置x\_0。对于小易所处的当前位置x，他只能通过神秘的力量移动到 4 \* x + 3或者8 \* x + 7。因为使用神秘力量要耗费太多体力，所以它只能使用神秘力量最多100,000次。贝壳总生长在能被1,000,000,007整除的位置(比如：位置0，位置1,000,000,007，位置2,000,000,014等)。小易需要你帮忙计算最少需要使用多少次神秘力量就能吃到贝壳。

**输入描述:**

输入一个初始位置x_0,范围在1到1,000,000,006

**输出描述:**

输出小易最少需要使用神秘力量的次数，如果使用次数使用完还没找到贝壳，则输出-1

示例1

## 输入 ##

125000000

## 输出 ##

解题思路：

/\*\*思路：  
     \* 小易的移动方程  
     \* f(x) = 4 \* x + 3;  
     \* g(x) = 8 \* x + 7;  
     \*  
     \* 计算可以得出规律：  
     \* 1.g(f(x)) = f(g(x))  
     \* 2.f(f(f(x))) = g(g(x)) 也就是三次f(x) = 两次g(x)  
     \*  
     \* 有规律1 所以可以存在：ffggfggff = fffffgggg  
     \* 有规律2 所以可以存在：fffffgggg = ffgggggg  
     \*  
     \* 可以得出一个最有策略：f的执行次数为0,1,2。-> x,4\*x + 3,4(4\*x+3) + 3  
     \* 在f的执行基础上求最小g的执行次数

import java.util.*;
    
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            long num = sc.nextLong();
            long m = 1000000007;
            long mystery = 100000;
            long [] begin = new long[3];
            begin[0] = num;
            begin[1] = 4*begin[0]+3;
            begin[2] = 4*begin[1]+3;
            long step = 0;
            long minStep = mystery;
            long cur = 0;
            for(int i = 0;i<3;i++){
                step = i;
                cur = begin[i];
                while (cur!=0 && step<minStep ){//条件二：如果算出比当前更长的step就不需要算下去了
                    cur = (8*cur+7)%m;
                    step++;
                }
                if(step<minStep)
                    minStep = step;
            }
            if(minStep<mystery)
                System.out.println(minStep);
            else
                System.out.println(-1);
        }
    }

[https_www.nowcoder.com_questionTerminal_5ee8df898312465a95553d82ad8898c3]: https://www.nowcoder.com/questionTerminal/5ee8df898312465a95553d82ad8898c3