• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

原创


一步之遥

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


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Win7系统下C++实现客户端程序单独静音功能发布时间:2022-07-13
下一篇:
DropDownList联动的例子(c#)发布时间:2022-07-13
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap