算法题每日一练 --- 第 3 天：一步之遥

作者：知心宝贝

2022 年 7 月 20 日
本文字数：780 字
阅读完需：约 3 分钟

一、问题描述

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

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

小明飞快地计算，至少要多少次操作，才能把矿车准确地停在前方 1 米远的地方。

二、解题思路

假设小明站在 x 轴上面，坐标为 0。前面有两个按钮，按 F,前进 97 米。按 B 后退 127 米。向 x 轴正方向移动+97m，向 x 轴负方向移动-127 米。

对于这种题，我们依旧可以选择两种方法，第一种暴力求解，第二种巧用条件。

方法一暴力法

使用两重 for 循环，第一重表示向前移动 97m 的次数，第二重表示向后移动 127m 的次数。限定最大移动次数，找到需要移动最少的一个。

方法二公式法

在限定的范围内，加上求解最小值公式 min(a,b)，返回 a，b 两个中数据较小的一个,max 则相反

三、编码实现

1.暴力法

#include<iostream>//暴力using namespace std;int main(){  int i,j;  for(i=0;i<300;i++)//限定循环次数  {    for(j=0;j<300;j++)    {      if(97*i-127*j==1)//判断是否符合条件      {                            cout<<i<<" "<<j<<" "<<i+j<<"\n"; //输出范围内符合条件的结果        }    }  }   return 0;}

复制代码

2.公式法

#include<iostream>//暴力using namespace std;int main(){  int i,j,ans=600;  for(i=0;i<300;i++)//限定循环次数  {    for(j=0;j<300;j++)    {      if(97*i-127*j==1)//判断是否符合条件      {                            ans=min(ans,i+j);//公式法在原本输出结果的一行加了一个最小值判断      }    }  }         cout<<ans;//输出结果  return 0;}

复制代码

四、输出结果

输出结果 97。

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/85124a649c5e9fe5e26d79d0d】。文章转载请联系作者。

知心宝贝

关注

公众号：穿越计算机的迷雾 2022.03.07 加入

生于尘埃溺于人海死于理想高台

发布

暂无评论

创作场景