首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >奇怪的数字

问奇怪的数字
EN

Stack Overflow用户
提问于 2011-10-10 04:27:39
回答 3查看 2.7K关注 0票数 2

下面是我正在做的问题中的“奇怪的数字”的属性:

1)它们的小数位数是偶数(没有前导零)。

2)定义左半部为原始数的最高有效位所代表的数,定义右半部为最低有效位所代表的数。右半部分可能有前导零。奇数是它的两部分之和的平方: 81 = (8 + 1)^2

下面是一些其他的例子: 998001 = (998 + 001)^2,3025 = (30 + 25)^2

我怎么才能写出一个程序,以递增的顺序列出所有不超过18位小数的奇怪数字呢?

我通过查看所有的可能性(2位数,4位数,6位数,...,18位数)了解如何做到这一点,但这将需要几天的时间来运行。有没有什么模式可以让我在几秒钟内输出所有奇怪的数字?我更喜欢用Java来回答,但伪代码也可以。

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2011-10-10 04:32:11

所有这些“奇怪”的数字都是完美的平方。因此,您可以从遍历所有数字并将其平方开始(直到平方超过18位)。对于每个正方形,检查它是否“奇怪”。

编辑我还会补充说,这大大加快了速度的原因是它将解决方案从O(n)更改为O(√n)

票数 7
EN

Stack Overflow用户

发布于 2011-10-10 05:36:42

除了@spatulamania的加速之外,你还可以使用模算法来进一步加速检查。

为了检查每一个完美的正方形,你必须将数字分成两部分,将它们相加,求和的平方,并将其与原始数字进行比较。(我将其命名为"full-check")

相反,您可以首先只检查两部分的最后一位数字(并将它们的和平方)。例如,对于数字99980001,取数字8和1,取(8+1)^2 = 9^2 = 81的平方,测试最后一个数字(在本例中为1)是否与99980001的最后一个数字相同(我将其命名为"small-check")。如果是,则继续进行全面检查。

因为只有10x10=100这样的组合,所以这只需要做一次。您将创建一个可接受的组合数组,您可以使用:

代码语言:javascript
复制
0   0
0   1
8   1
4   4
8   4
0   5
0   6
8   6
4   9
8   9

使用这种方法,你只需要对大约82%的完美方块(那些没有通过小检查的方块)进行“小检查”,对其余的18% (通过小检查的方块,所以也需要进行“全检查”)进行两次检查。因此,如果“小检查”可以足够快地完成,您将获得一些速度。

您可能会发现,对于这两个部分的最后两位数,扩展此表并使用它(当n足够大时)会更快。

票数 2
EN

Stack Overflow用户

发布于 2018-08-12 12:14:28

代码语言:javascript
复制
class strange_number
{
    int number(int n)
    {
        int x = n;
        String a = Integer.toString(n);
        int d = a.length();
        if(((int)(Math.pow(((x%(int)(Math.pow(10,d/2)))+(x/(int)(Math.pow(10,d/2)))),2))) == x)
        return 1;
        else
        return 0;
    }
}

可以试试这种方式。这可能会对你有所帮助。

票数 -1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/7706365

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档