第八届蓝桥杯程序设计大赛国赛填空题第一题平方十位数-白红宇的个人博客

第八届蓝桥杯程序设计大赛国赛填空题第一题平方十位数

发布日期：2021-05-09 04:15:20 浏览次数：11 分类：博客文章

本文共 3148 字，大约阅读时间需要 10 分钟。

平方十位数

题目描述

由0~9这10个数字不重复、不遗漏，可以组成很多10位数字。

这其中也有很多恰好是平方数（是某个数的平方）。

比如：1026753849，就是其中最小的一个平方数。

请你找出其中最大的一个平方数是多少？

注意：你需要提交的是一个10位数字，不要填写任何多余内容。

思路分析

既然是找最大的一个平方数，就倒着找，找到的第一个就是最大的那个数：

有两种方法：

1.从99999循环到sqrt（1026753849）（因为只有5位数的平方是十位数，所以从99999开始）依次求平方，

　再拆分平方十位数，判断是否有重复数字

2.从9876543210循环到1026753849，对每个十位数开根，如果得到的是整数，那这第一个最大的平方十位数就是它了，

比较两种方法：

第一种方法看似复杂，还得拆分进行比较，实则简单，用就能解决，因为hashset有一个特征，就是自动去重，

　　将平方十位数拆分后add到hashset后，判断hashset的size（）是否等于10，就能得出这个平方十位数是否有无重复数字，

　　说明一点，这个平方运算，需要用到大整数相乘，因为long存不下啊啊啊，如果不明白，请看。

第二种方法看似简洁，但是由于循环变量从9876543210开始，int和long都存不下，当然可以用biginteger，

　　但是，biginteger间的运算都需要使用它自带的函数，表示头疼，例如m = i*i,就需要m= i.multiply(i)来解决，麻烦的很。

（是不是感觉这两种方式咋都那么暴力，我也这么觉得，但是暂时没有其他的好办法，扒拉扒拉别人的博客，发现都是这种方法，而且很多都没有处理大整数。如果大神们有其他思路，欢迎评论）

下面给出两种方法的代码实现：

方法1

import java.util.HashSet;public class Main {        public static void main(String[] args) {        double n = Math.sqrt(1026753849);        for (int i = 99999; i >n; i--) {            if(f1(i+"",i+""))                return;        }    }            //大整数相乘    public static boolean f1(String x,String y){        HashSet sett = new HashSet();        int[] intx = new int[x.length()];        int[] inty = new int[y.length()];        int[] intsum = new int[x.length()+y.length()];        for (int i = 0; i < x.length(); i++) {            intx[x.length()-1-i] = Integer.parseInt(x.substring(i, i+1));        }        for (int i = 0; i < y.length(); i++) {            inty[y.length()-1-i] = Integer.parseInt(y.substring(i, i+1));        }        for (int i = 0; i < intx.length; i++) {            for (int j = 0; j < inty.length; j++) {                intsum[i+j] += intx[i]*inty[j];            }            for (int j = 0; j < intsum.length-1; j++) {                if(intsum[j]>9){                    intsum[j+1]+=intsum[j]/10;                    intsum[j] = intsum[j]%10;                }            }        }        String str="";        for (int i = intsum.length-1; i >=0; i--) {            sett.add(intsum[i]);            str = str+intsum[i];        }        if(sett.size()==10){            System.out.println(str);            return true;        }        return false;        }}

方法2

import java.math.BigInteger;  import java.util.HashSet;  import java.util.Set;  public class Main {      public static void main(String[] args) {          BigInteger x;          BigInteger y = new BigInteger("10");          BigInteger[] a = new BigInteger[10];          String s = "100000";          String s2 = "32043";          BigInteger t = new BigInteger(s2);          for (BigInteger b = new BigInteger(s); b.compareTo(t) >= 0; b = b.subtract(new BigInteger("1"))) {      //for循环递减            x = b.multiply(b);     //b*b            for (int m = 9; m >= 0; m--) {                  a[m] = x.remainder(y);     //a[m] = x % y                x = x.divide(y);      // x = x / y            }              Set set = new HashSet();              for (int i = 0; i < a.length; i++) {   //Set属性：不重复                set.add(a[i]);              }              if (set.size() == a.length) {                  System.out.println(b.multiply(b));     //修改原文：b*b                break;              }          }      }  }

上一篇：蓝桥杯每周一练第一周（3n+1问题）

下一篇：拼多多 2018 校招编程题六一儿童节

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章