寒光博客

[LanQiao]一步之遥
题目 从昏迷中醒来,小明发现自己被关在X星球的废矿车里。 矿车停在平直的废弃的轨道上。 他的面前是两个按钮,分别...
扫描右侧二维码阅读全文
26
2019/07

[LanQiao]一步之遥

题目

从昏迷中醒来,小明发现自己被关在X星球的废矿车里。
矿车停在平直的废弃的轨道上。
他的面前是两个按钮,分别写着“F”和“B”。
小明突然记起来,这两个按钮可以控制矿车在轨道上前进和后退。
按F,会前进97米。按B会后退127米。
透过昏暗的灯光,小明看到自己前方1米远正好有个监控探头。
他必须设法使得矿车正好停在摄像头的下方,才有机会争取同伴的援助。
或许,通过多次操作F和B可以办到。
矿车上的动力已经不太足,黄色的警示灯在默默闪烁…
每次进行 F 或 B 操作都会消耗一定的能量。
小明飞快地计算,至少要多少次操作,才能把矿车准确地停在前方1米远的地方。
请填写为了达成目标,最少需要操作的次数。

思路1:暴力,非常简单

volence(97,-127);

private static void violence(long f, long b) {    
    for (int i = 0; i < 1000; i++) {              
        for (int j = 0; j < 1000; j++) {          
            if(i*f+j*b==1){                       
                System.out.println(i+" "+j);      
                return;                           
            }                                     
        }                                         
    }                                             
}                                                 

思路2:扩展欧几里得算法

根据题目列出方程:97 x - 127 y = 1,这是一个不定方程,要求不定方程的整数解,用扩展欧几里得算法。
【扩展欧几里得算法是用来在已知a,b求解一组x,y,使它们满足贝祖等式:ax + by = gcd(a,b) = d(解一定存在,根据数论中的相关定理)】

package BlueCup.Six_MathQuestion;                                                 

public class 一步之遥 {                                                               
    public static void main(String[] args) {                                      
        //97*x-127*y=1;                                                           
        long F=97;                                                                
        long B=-127;                                                                                                                       
        try {                                                                     
            LinearEquation(F,B,1);                                                
            System.out.println(x+" "+y);                                          
        }catch (Exception e){                                                     
            System.out.println(e.getMessage());                                   
        }                                                                         
    }                                                                                                                                                        
    private static void LinearEquation(long a, long b, long m)throws Exception {  
        long d=ext_gcd(a,b);                                                      
        if(m%d!=0)throw new Exception("无解");                                      
        long t=m/d;                                                               
        x*=t;                                                                     
        y*=t;                                                                     
    }                                                                             
    static long x,y;                                                              
    private static long ext_gcd(long a, long b) {                                 
        if(b==0){                                                                 
            x=1;                                                                  
            y=0;                                                                  
            return a;                                                             
        }                                                                         
        long res=ext_gcd(b,a%b);                                                  
        long x0=x;                                                                
        x=y;                                                                      
        y=x0-a/b*y;                                                               
        return res;                                                               
    }                                                                                                                                                                                                                             
}                                                                                 

关于思路二的详细分析

本文作者:Author:     文章标题:[LanQiao]一步之遥
本文地址:https://dxoca.cn/Algorithm/195.html       百度未收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:July 31st, 2019 at 12:16 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment