华为OD机考算法题:数字加减游戏

目录

题目部分

解读与分析

代码实现


题目部分

题目数字加减游戏
难度
题目说明小明在玩一个数字加减游戏,只使用加法或者减法,将一个数字 s 变成数字 t 。
每个回合,小明可以用当前的数字加上或减去一个数字。
现在有两种数字可以用来加减,分别为 a, b (a≠b),其中 b 没有使用次数限制。
请问小明最少可以用多少次 a,才能将数字 s 变成数字 t 。
题目保证数字 s 一定能变成数字 t。
输入描述输入的唯一一行包含四个正整数s,t,a,b(1≤s,t,a,b≤10^{5}),并且a≠b。
输出描述输出的唯一一行包含一个整数,表示最少需要使用多少次 a 才能将数字 s 变成数字 t。
补充说明
------------------------------------------------------
示例
示例1
输入1 10 5 2
输出1
说明初始值 1 加一次 a 变成 6,然后加两次 b 变成 10,因此 a 的使用次数为 1。
示例2
输入11 33 4 10
输出2
说明11 减两次 a 变成 3,然后加三次 b 变成 33,因此 a 的使用次数为 2 次。


解读与分析

题目解读

由于 a 加一次后再减一次等于 0,在这里需要计算最少次数,所以我们不必做既加又减的操作。同时,也假设 b 也只做一种操作,也不存在既加又减的情况。

在这个前提下,此题要求在 s 的基础上,加减若干次 a,再加减若干次 b,最后得到 t。

本质上,由 s 变成 t ,与 由 t 变成 s相比,加减 a 、b 的次数是一样的,无非就是逆向操作,加变减,减变加。

更进一步思考,s 变成 t,与 ( s + 1) 变成 ( t  + 1 ) 也是一样的,其实就是发生 | s - t | 差值的变化。 

分析与思路

由于 s、t 是固定值,我们假设 n = | s - t |。

此题可以转变为:一个原始数据,加或减a 若干次(假设为 x),加或减 b 若干次(假设为 y),产生的变化为 n 。
此题有 3 种情况:
1.
a * x - b * y = n
2. b * y - a * x = n
3. a * x + b * y = n
其中,x、y 均为正整数。
这 3 个等式可以做如下转换。
1.  
a * x - b * y = n   \Rightarrow  y = \frac{ a * x - n }{ b} 
2.  
b * y - a * x = n  \Rightarrow  y = \frac{ a * x + n }{ b}
3.  a * x + b * y = n \Rightarrow  y = \frac{ n - a * x }{ b}
其中, 第 1 个 和 第 3 个 可以合并成 y = \frac{ | ax - n | }{ b }

在 y = \frac{ a * x + n }{ b}  y = \frac{ | ax - n | }{ b } 这两个等式中,它们的分母都能被 b 整除,这意味着这两个等式可以转换成:
1. 
( a * x ) % b  = n % b
2.  ( a * x ) % b = ( b - n % b) % b
这两个等式的右边都是常数。此题进一步简化:找出最小的 x,使其满足以上 2 个条件中的任意一个。

x 的取值范围是多少呢?由于等式对 b 进行取模操作,即意味着当 x == 0 等同于 x == b, x == 1 也等同于 x == ( b + 1)。直观地看, x 的取值范围为 0 ≤ x < b。

更进一步,假设 a、b 的最小公倍数是 L,那么 a 加 \frac{L}{a} 次与 b 加 \frac{L}{b} 次是相等的,因此 x 的取值范围可以进一步缩小到 0 ≤ x < \frac{L}{a}

那么,此题就可以简化成,把 x 从 0 到 \frac{L}{a} ,代入到等式
1. 
( a * x ) % b  = n % b
2.  ( a * x ) % b = ( b - n % b) % b
中,当这两个等式中任意一个成立时,x 的值即是最小的值。

题目中提到,“题目保证数字 s 一定能变成数字 t”,那我们在从 x = 0 开始代入等式,每次增加 1 尝试等式是否成立时,无需去计算 \frac{L}{a} 的值,必定会在 \frac{L}{a} 之前求出 x 的值。

更进一步,先求 a 与 b 的最大公约数(设为 C1),再求 n 与 b 的最大公约数(C2),接着求 C1 和 C2 的最大公约数(设为 C),那么等式就变成了:
1. 
( \frac{a}{C} * x ) % \frac{b}{C}  = \frac{n}{C} % \frac{b}{C}
2.  ( \frac{a}{C} * x ) % \frac{b}{C} = ( \frac{b}{C} - \frac{n}{C} % \frac{b}{C}) % \frac{b}{C}

此时,\frac{a}{C}  \frac{b}{C} 的最小公倍数变为原来的 \frac{1}{C}x 的范围进一步缩小。

但是,写代码的时候完全不必关心这些。尽管 x 的取值范围进一步缩小,实际上是进一步精确了,x 的值不会发生改变,从 0 开始遍历,遍历的次数不会发生改变。

此题空间复杂度为 O(1)。由于输入数字最大不超过10的5次方,运行时间很短。


代码实现

Java代码

import java.util.Scanner;/*** 数字加减游戏* * @since 2023.09.08* @version 0.1* @author Frank**/
public class NumPlusMinusGame {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();String[] numbers = input.split( " " );processNumPlusMinusGame( numbers );}}private static void processNumPlusMinusGame( String numbers[] ){int s = Integer.parseInt( numbers[0] );int t = Integer.parseInt( numbers[1] );int a = Integer.parseInt( numbers[2] );int b = Integer.parseInt( numbers[3] );int n = Math.abs( s - t );// 当modValue1 可能等于 modValue2,如 modValue1 等于0 或 等于 b/2 的情况。int modValue1 = n % b;int modValue2 = ( b - n % b ) % b;int i = 0;while( true ){int tmpModValue = ( a * i ) % b;if( tmpModValue == modValue1 || tmpModValue == modValue2 ){System.out.println(i);return;}i ++;}}
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var numberArr = line.split(" ");processNumPlusMinusGame(numberArr);}}();function processNumPlusMinusGame(numberArr) {var s = parseInt(numberArr[0]);var t = parseInt(numberArr[1]);var a = parseInt(numberArr[2]);var b = parseInt(numberArr[3]);var n = Math.abs(s - t);// 当modValue1 可能等于 modValue2,如 modValue1 等于0 或 等于 b/2 的情况。var modValue1 = n % b;var modValue2 = (b - n % b) % b;var i = 0;while (true) {var tmpModValue = (a * i) % b;if (tmpModValue == modValue1 || tmpModValue == modValue2) {console.log(i);return;}i++;}}

此题主要工作量在解题思路上,代码量非常少。

(完)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/132573.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

SAP ABAP基础知识 访问外部数据库-开发篇

前言 本文主要介绍通过ABAP语言访问外部数据库的几种方式 一、外部数据库配置 本文示例中的代码访问了两个外部数据库 MTD : 外部oracle数据库,其中示例表 ZTTEMP 字段( ZZTNO,WERKS) S4Q : 外部HANA数据库(开发系统访问测试系统的数据库), 使用表USR02,ZTTEMP 二、ABAP访问…

c语言练习58:⾃定义类型:结构体

⾃定义类型&#xff1a;结构体 结构体的概念 结构是⼀些值的集合&#xff0c;这些值称为成员变量。结构的每个成员可以是不同类型的变量。 结构体是一个种自定义的数据类型&#xff0c;它可以由很多个默认数据类型组成。它主要用于描述复杂场景下的变量。 例如&#xff0c;想…

前端深入理解JavaScript中的WeakMap和WeakSet

&#x1f3ac; 岸边的风&#xff1a;个人主页 &#x1f525; 个人专栏 :《 VUE 》 《 javaScript 》 ⛺️ 生活的理想&#xff0c;就是为了理想的生活 ! 目录 1. WeakMap和WeakSet概述 1.1 WeakMap 1.2 WeakSet 2. WeakMap深入解析 2.1 WeakMap的创建和使用 2.2 WeakMap…

软件流程图怎么画?详细画法看这里

软件流程图怎么画&#xff1f;软件流程图是软件开发过程中必不可少的一环&#xff0c;可以帮助开发人员更好地理解和规划软件开发的流程。在制作软件流程图的时候&#xff0c;我们可以使用一些制作工具。下面就给大家介绍一款好用的绘制工具。 我们可以使用【迅捷画图】来进行流…

Android端Base64解码表情emoj乱码

一、背景&#xff1a;H5端用户评论中包含表情包&#xff0c;通过JSBridge 传递给客户端&#xff0c;Android Base64解码之后&#xff0c;显示乱码&#xff08;是菱形问号&#xff09;。小程序和iOS可以正常解码出表情。用Base64在线编码解码&#xff08;Base64 在线编码解码 | …

BOM操作

文章目录 BOM事件页面加载调整窗口事件定时器停止计时器Location对象History对象Offsetleft获取元素偏移Offset与style的区别可视区client系列滚动scroll系列Mouseover和mousenter区别 动画原理实现动画封装给不同对象添加定时器缓动动画原理多个位置间移动 BOM事件 页面加载 …

BeanUtils.copyProperties的使用场景

1. 常见场景 我们如果有两个具有很多相同属性名的JavaBean对象a和b&#xff0c;想把a中的属性赋值到b&#xff0c;例如 接口中将接收到的前端请求参数XxxReqVo,我们想把这个入参转化为XxxQuery对象作为数据库的查询条件对象 传统做法是手动set&#xff0c;即 XxxBean xxxBea…

Python Opencv实践 - HoG特征计算

参考资料&#xff1a;https://www.cnblogs.com/alexme/p/11361563.html https://blog.csdn.net/qq_43348528/article/details/108638030 import cv2 as cv import numpy as np import matplotlib.pyplot as plt from skimage import exposure from skimage.feature i…

靶场溯源第二题

关卡描述&#xff1a;1. 网站后台登陆地址是多少&#xff1f;&#xff08;相对路径&#xff09; 首先这种确定的网站访问的都是http或者https协议&#xff0c;搜索http看看。关于http的就这两个信息&#xff0c;然后172.16.60.199出现最多&#xff0c;先过滤这个ip看看 这个很…

SSM - Springboot - MyBatis-Plus 全栈体系(八)

第二章 SpringFramework 四、SpringIoC 实践和应用 4. 基于 配置类 方式管理 Bean 4.4 实验三&#xff1a;高级特性&#xff1a;Bean 注解细节 4.4.1 Bean 生成 BeanName 问题 Bean 注解源码&#xff1a; public interface Bean {//前两个注解可以指定Bean的标识AliasFor…

Mendeley在linux中无法打开APPimage

原因:FUSE 库为用户空间程序提供了一个接口&#xff0c;可以将虚拟文件系统导出到 Linux 内核。由于缺少这个关键库&#xff0c;AppImage 无法按预期工作。 1 安装fuse,打开终端,输入命令 sudo apt install libfuse2 输入用户密码结,果如下 2 确保APPimage作为程序运行 右击…

docker 获取Nvidia 镜像 | cuda |cudnn

本文分享如何使用docker获取Nvidia 镜像&#xff0c;包括cuda10、cuda11等不同版本&#xff0c;cudnn7、cudnn8等&#xff0c;快速搭建深度学习环境。 1、来到docker hub官网&#xff0c;查看有那些Nvidia 镜像 https://hub.docker.com/r/nvidia/cuda/tags?page2&name11.…

【计算机视觉 | 图像模型】常见的计算机视觉 image model(CNNs Transformers) 的介绍合集(五)

文章目录 一、MoCo v3二、AmoebaNet三、Residual Multi-Layer Perceptrons四、FractalNet五、LV-ViT六、RepVGG七、Transformer in Transformer八、SimpleNet九、SpineNet十、Bottleneck Transformer十一、ZFNet十二、DetNet十三、Invertible Rescaling Network十四、SNet十五、…

SVN 索引版本与打包版本号不匹配

今天突然遇到了一个问题&#xff0c;SVN上传不了&#xff0c;错误提示如下&#xff1a; 解决方法&#xff1a; 1.其实&#xff0c;这是SVN库不小心搞坏了&#xff0c;只能重新再创建一个SVN仓库了。

Redis:分布式锁误删原因分析

一、线程阻塞 例如&#xff0c;线程一获取分布式锁&#xff0c;但是线程一阻塞时间过长&#xff0c;导致锁超时释放。此时线程二获取分布式锁。当线程一阻塞结束后&#xff0c;释放分布式锁&#xff0c;但是释放的却是线程二的锁。此时线程二就不安全了&#xff0c;线程三也可…

Linux下修改jar包中的配置文件application.conf

文件位置 jar包文件工程目录 打包后解压jar包目录 提取和上传 jar tf XXX.jar # 获取包内文件 application.conf是jar包的配置文件&#xff0c;如果修改需要 提取文件 jar xf my-app.jar application.conf 修改后上传文件 jar uf my-app.jar application.conf

解决开了burp suite ,火狐访问不了其他网站的问题

问题描述&#xff1a; 有软件正在阻止 Firefox 安全地连接至此网站 www.baidu.com 很像是一个安全&#xff08;连接加密&#xff09;的网站&#xff0c;但我们未能与它建立安全连接。这个问题是由 PortSwigger CA 所造成&#xff0c;它是您的计算机或您所在网络中的软件。 您…

为什么Proteus串口无法正常显示

我以前就可以正常显示&#xff0c;但是最近一段时间&#xff0c;发现串口无法正常显示&#xff0c;试了很多办法都不行&#xff0c; 然后今天干好有点时间就刷了个机&#xff0c;然后居然就好了&#xff0c; 这就说明&#xff1a;Proteus不正常可能是病毒破坏了某个文件导致异…

HSRP(热备份路由选择协议)的概念,原理与配置实验

作者&#xff1a;Insist-- 个人主页&#xff1a;insist--个人主页 梦想从未散场&#xff0c;传奇永不落幕&#xff0c;持续更新优质网络知识、Python知识、Linux知识以及各种小技巧&#xff0c;愿你我共同在CSDN进步 目录 一、了解HSRP协议 1. 什么是HSRP协议 2、HSRP协议的…

java和fastjson

1.java是如何跨平台通信的 java--->class字节码--->jvm虚拟机运行 2.使因为jvm只会读文件名 如果不一致 则无法找到文件 3.main 函数说明java代码的接口 被使用 4.java和class后缀的区别 java是当前编写的代码文件 class是编译后的文件 5.void 没有返回值 这…