Loading...
世界已冷酷至极, 让我们携手前行。
自助收录

2023年华为OD机考真题:数字加减游戏

算法刷题1年前 (2023)更新 江南白衣
232 0 0
2023年华为OD机考真题:数字加减游戏

全网最全面的华为OD机试真题汇总,100%原题题库,不需要开会员即可查看全部内容,更多考题请查看真题库。

真题库:https://www.yuque.com/codernav.com/od

题目:数字加减游戏
知识点:广搜
时间限制:1s 空间限制:256MB 限定语言:不限
题目描述:
小明在玩一个数字加减游戏,只使用加法或者减法,将一个数字s变成数字t。
每个回合,小明可以用当前的数字加上或减去一个数字。
现在有两种数字可以用来加减,分别为a,b(a!=b),其中b没有使用次数限制。
请问小明最少可以用多少次a,才能将数字s变成数字t。
题目保证数字s一定能变成数字t。
输入描述:
输入的唯一一行包含四个正整数s,t,a,b(1<=s,t,a,b<=105),并且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和-a同时存在,则正负相抵,啥都没做但已经使用了2次,所以可得-a和+a只能有一个存在,则存在下面三种情况:
a、s – a*i + b*j = t → t – (s – a*i) = b*j → (t – (s – a*i))%b = 0
b、s + a*i + b*j = t → t – (s + a*i) = b*j → (t – (s + a*i))%b = 0
c、s + a*i – b*j = t → t – (s + a*i) = -b*j → (t – (s + a*i))%b = 0
这样一来就很清楚了。
t 减去 s对a的递增或者递减 整除 b,递增或者递减的次数则是a的使用次数。递增递减同时进行,先整除b的则是最小使用次数。

满分Java解题代码:

package com.codernav.demo.hwod.exam;

import java.util.Scanner;

/**
 * @title 数字加减游戏
 * @Description 小明在玩一个数字加减游戏,只使用加法或者减法,将一个数字s变成数字t。
 * 每个回合,小明可以用当前的数字加上或减去一个数字。
 * 现在有两种数字可以用来加减,分别为a,b(a!=b),其中b没有使用次数限制。
 * 请问小明最少可以用多少次a,才能将数字s变成数字t。
 * 题目保证数字s一定能变成数字t。
 * @Author 开发者导航
 * @website https://codernav.com
 * @date 2023/5/28
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int t = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        int res = 0;
        int add = s;
        int sub = s;
        while (true) {
            if ((t - add) % b == 0) {
                break;
            }
            if ((t - sub) % b == 0) {
                break;
            }
            add += a;
            sub -= a;
            res++;
        }
        System.out.println(res);
    }
}
© 版权声明

相关文章

开发者导航新手教程

暂无评论

暂无评论...