一步之遥——蓝桥杯
程序员文章站
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
下一篇: 圈地黑科技 手机厂商亟待打破技术瓶