欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

一步之遥——蓝桥杯

程序员文章站 2022-04-24 20:26:16
原创 一步之遥 从昏迷中醒来,小明发现自己被关在X星球的废矿车里。矿车停在平直的废弃的轨道上。他的面前是两个按钮,分别写着“F”和“B”。 小明突然记起来,这两个按钮可以控制矿车在轨道上前进和后退。按F,会前进97米。按B会后退127米。透过昏暗的灯光,小明看到自己前方1米远正好有个监控探头。他必须 ......

原创


一步之遥

从昏迷中醒来,小明发现自己被关在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\n",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