一步之遥——第七届蓝桥杯C语言B组（国赛）第一题

原创

一步之遥

从昏迷中醒来，小明发现自己被关在X星球的废矿车里。
矿车停在平直的废弃的轨道上。
他的面前是两个按钮，分别写着“F”和“B”。

小明突然记起来，这两个按钮可以控制矿车在轨道上前进和后退。
按F，会前进97米。按B会后退127米。
透过昏暗的灯光，小明看到自己前方1米远正好有个监控探头。
他必须设法使得矿车正好停在摄像头的下方，才有机会争取同伴的援助。
或许，通过多次操作F和B可以办到。

矿车上的动力已经不太足，黄色的警示灯在默默闪烁...
每次进行 F 或 B 操作都会消耗一定的能量。
小明飞快地计算，至少要多少次操作，才能把矿车准确地停在前方1米远的地方。

请填写为了达成目标，最少需要操作的次数。

注意，需要提交的是一个整数，不要填写任何无关内容（比如：解释说明等）

此题我用的解法是扩展欧几里德算法：

具体算法看我的另外一篇博客：http://www.cnblogs.com/chiweiming/p/8878202.html

当我们算出 97x+127y=gcd（97,127）的第一组解（x0，y0）后；

我们可以得到 97x+127y=1的第一组解：

x=x0*1/gcd（97,127）；

y=y0*1/gcd（97,127）；

然后我们输出 abs（x）+ abs（y）即可。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int x,y;

int gcd(int a,int b)    //扩展欧几里德算法 
{
    int d;
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    else
    {
        d=gcd(b,a%b);
        int temp;
        temp=x;
        x=y;
        y=temp-(a/b)*y;
        return d;
    }
}

int main()
{
    int Byue;
    Byue=gcd(97,127);    //调用后x，y作为 97x+127y=gcd(97,127)的第一组解
//  printf("%d %d
",x,y);
    printf("%d",abs( x*1/Byue  ) + abs( y*1/Byue ) );
    
    return 0;
}

下面给出直接暴力破解的代码：

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int x,y,t,flag=0;
 5     for(t=0; ;t++)    //假设需要t步完成 
 6     {
 7         for(x=0;x<t;x++)    //走x步97 
 8         {
 9             y=t-x;    //剩下走y步127 
10             if(97*x-127*y==1)
11             {
12                 printf("%d",x+y);
13                 flag=1;
14             }
15             if(flag==1)
16                 break;
17         }
18         if(flag==1)
19             break;
20     }    
21     return 0;
22 }

11:07:31

2018-04-19