同一个问题有多个解

  1. 云栖社区>
  2. 博客>
  3. 正文

同一个问题有多个解

ykmimi.com 2018-08-26 14:16:00 浏览767
展开阅读全文

https://www.codewars.com/kata/5592e3bd57b64d00f3000047

 

做这道kata时,有个变量的比较运算符写错了,应该设置为< ,而我设置的 != ,(更正后↓完全正确)

 

public static long findNb0(long m) {
        long n = 0;// 求得的n
        long sum = 0;// 累加值与m进行判定
        long s = 0;
        boolean rightN = false;
        while (s < m) {
            sum += (s * s * s);

            if (sum == m) {
                rightN = true;
                n = s;
                break;
            }
            if (sum > m) {
                break;
            }

            s++;

        }
        if (rightN) {
            return n;

        } else {
            return -1;
        }
    }

 

它(this kata)求的是按照1的立方,2的立方,3的立方这样的累加一直到n的立方,是否等于传入的m. 返回数值n.

很简单的想法是可以使用递增, 将 n*n*n 去 ++ .就像上面的写法,看了下CW大神的解法:

    public static long findNb2(long m) {
        long mm = 0, n = 0;
        while (mm < m)
            mm += ++n * n * n;
        return mm == m ? n : -1;
    }

写法更加简练了,但其实还是一个道理,就是递增,我在想应该有更快速的方式(因为之前做类似的题时,使用递增这样做法会超时(也就是所说的算法的时间复杂度过高了))

使用java自带的Math类方法:(但不完全正确,通过率98%),除了Math类计算失误(不支持大数值),之下的解答逻辑性应无误(98%确定)

public static long findNb(long m) {

        double x = Math.sqrt(m); << 问题出在这里,应该为有小数的结果会可能返回正整数
        if (x != (Math.round(x))) {   
            return -1;
        }

        long n = (long) (Math.floor(Math.sqrt(x * 2)));
        return n;

    }

最后经过多方论证,规律寻找,觉得这个解法是可以的,但是大多数测试通过了,有几个是通过不了的,而且都是数值非常大的情况下,

最终经过计算,得出结论: java自带的算术式以及支持的数值大小不能做这道题,如果支持的数值大小可以满足时,这种做法是对的.

但是这还不是最终结论.

但对于18位数值是可以的.19位就不准了.

再次我验证:

使用 递增的方式 s*s*s.

使用有平方根的数值:

long m = 1667089848622288897L;

这里很奇妙的是,使用百度的求平方根,对于这个数,以及这个数-1的数,结果是一样的.(问题就出在这个地方)

递增后查看结果:

......
......
......
1666827415525457025
1666958628200550400
1667089848622288896
1667221076790977409
-1

最后当最后long值超过其本身后,返回了-1.(表示没有n)

那么这里的超过之前的数值1667089848622288896 是小于m (1) 个大小的.

这里的疑问是:

>> 也许是java中的Math类计算失误(对于过大数值)

>> 或者是计算机底层的相乘出错了?(相乘使用的其实是加法),

>> 也许是我写的解答就是不对的?(对于有整型平方根的整数,其是有1³+2³+3³+......+n³的和一样的整数的这件事情,我觉得应该没问题,毕竟测试通过率为98%(当然除了这个数值和其它更大数值))

 

那么究竟是long值相乘计算出错了还是Math.sqrt的求开方出错了,这个只能在更强有力的计算机上去尝试了.(完全没有谱了,要不然就拿张白纸挨个相乘...计算)

不太靠谱的百度,给出了不太靠谱的结论. (有病去医院不要问百度)

最后我觉得先放一下这个问题,或者有哪位使用C语言的大神看到这道题,麻烦帮忙证明一下结果正确性谢谢

 

 

待看 -> 实现超大整数(超过long长度范围)的加法运算

 

 

 

 

 

 

-------------------------------------------------------长长的分割线,记录下我对家的思念--------------------------------------------------------------

 

将编程看作是一门艺术,而不单单是个技术。 敲打的英文字符是我的黑白琴键, 思维图纸画出的是我编写的五线谱。 当美妙的华章响起,现实通往二进制的大门即将被打开。

网友评论

登录后评论
0/500
评论
ykmimi.com
+ 关注