首页 > 试题广场 >

魔法数字

[编程题]魔法数字

热度指数：2454 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹给牛牛写了一个数字n，然后又给自己写了一个数字m，她希望牛牛能执行最少的操作将他的数字转化成自己的。
操作共有三种，如下：
1.在当前数字的基础上加一，如：4转化为5
2.在当前数字的基础上减一，如：4转化为3
3.将当前数字变成它的平方，如：4转化为16

返回最少需要的操作数。

示例1

输入

3,10

输出

备注:

算法知识视频讲解

Java

宛安

import java.util.*;   public class Solution { public static void main(String[] args) {
        Solution solution = new Solution ();  System.out.println ("请输入牛牛的数字，例如：牛牛-3" );  int n = getInt ();  System.out.println ("请输入牛妹的数字，例如：牛妹-10" );  int m = getInt ();  solution.solve ( n,m );  } public static void solve (int n, int m) { // write code here  int sum = 0;  if (n < 2){
            n++;  sum++;  } while (n * n <= m){
            sum ++;  n = n * n;  } if ((n * n + n) / 2 >= m){
            sum = sum + m - n;  }else {
            sum = sum + n * n - m + 1;  }
        System.out.println (sum );  } private static int getInt() {
        Scanner sc = new Scanner(System.in);  return sc.nextInt();  }
}

发表于 2021-08-20 17:18:53 回复(0)

Java

牛客857822105号

java学的不久，纯属瞎做居然通过了，最笨的方法了吧

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 表示牛牛的数字
     * @param m int整型 表示牛妹的数字
     * @return int整型
     */
    public int solve (int n, int m) {
        // write code here
        int x=0;
        if(n==1 && m!=1){
            n++;
            x++;
        }
        List<Integer>l1=new ArrayList<>();
        List<Integer>l2=new ArrayList<>();
        Set<Integer>set=new HashSet<>();
        l1.add(n);
        while(!l1.contains(m)){
            for(int i=0;i<l1.size();i++){
                if(l1.get(i)>m){
                    l2.add(l1.get(i)-1);
                }
                else if(l1.get(i)>44){
                    if(!set.contains(l1.get(i)+1)){
                        l2.add(l1.get(i)+1);
                        set.add(l1.get(i)+1);
                    }
                    if(!set.contains(l1.get(i)-1)){
                        l2.add(l1.get(i)-1);
                        set.add(l1.get(i)-1);
                    }
                }
                else{
                     if(!set.contains(l1.get(i)+1)){
                        l2.add(l1.get(i)+1);
                        set.add(l1.get(i)+1);
                    }
                    if(!set.contains(l1.get(i)-1)){
                        l2.add(l1.get(i)-1);
                        set.add(l1.get(i)-1);
                    }
                    if(!set.contains(l1.get(i)*l1.get(i))){
                        l2.add(l1.get(i)*l1.get(i));
                        set.add(l1.get(i)*l1.get(i));
                    }
                }
            }
            x++;
            l1.clear();
            l1.addAll(l2);
            l2.clear();
        }
        return x;
    }
}

发表于 2021-05-31 18:03:15 回复(0)

Java

一级**人

相对大佬的代码来说，我的代码十分笨拙。

我的想法是这样：从m开始，一直取他的平方根，然后一直补差数。

代码可能有很多累赘的地方，希望大家帮忙改正和补全。

    //count计数  public int count=0;
    public int solve (int n, int m) {
        if(n==1&&n==m) return count-1;
        if(n>=m) return n-m+count;
        int sq=(int)Math.sqrt(m);
        int a=m-sq*sq;
               //排除掉两数相近的情况
        if(Math.abs(m-sq*sq)>Math.abs(m-n))  return count+m-n;
               //判断加一好还是减一好
        if(sq==1||Math.abs(m-(sq+1)*(sq+1))>=Math.abs(m-sq*sq)) {
            count = count + a + 1;
            return solve(n, sq);
        }
        else {
            count=count+(sq+1)*(sq+1)-m+1;
            return solve(n,sq+1);
        }
    }

发表于 2020-08-14 17:03:25 回复(0)