java - 给定的数字可以写成两个或多个连续正整数的和吗？

Question

我需要编写一个方法，它接受一个 int 并返回 true 如果该数字可以写成两个或多个连续正整数和 false 否则。

boolean IsSumOfConsecutiveInts(int num)

我发现所有奇数(数字1除外)都可以写成2个连续正整数之和:

return (num > 1 && num % 2 == 1);

但这不考虑可以写成 超过 2 个连续正整数之和的数字(例如 6 == 1 + 2 + 3 ).

如何确定一个数字是否可以写成两个或多个连续正整数之和？

Answer 1

这些数字称为 Polite Numbers .

而且，方便的是，唯一不礼貌的数字是 2 的幂。

所以，这给了我们两个选择。我们既可以确定一个数字是礼貌的，也可以确定它不是 2 的幂。

我都做了；后者更容易(也更有效)。

1. 这决定了一个数字是否礼貌:

   boolean IsSumOfConsecutiveInts(int num)
   {
       int sumOfFirstIIntegers = 3;
       for (int i = 2; sumOfFirstIIntegers <= num; i++)
       {
           if (i%2 == 0 ? (num%i == i/2) : (num%i == 0))
           {
               return true;
           }
           sumOfFirstIIntegers += i + 1;
       }
       return false;
   }
   

   这个很难理解。我花了一段时间才想到。

   基本上，i是我们正在检查的连续整数的数量；

   sumOfFirstIIntegers等于第一个 i 的总和整数，这意味着所有可以表示为 i 之和的数字连续整数大于或等于 sumOfFirstIIntegers .

   最后值得讨论的部分是 boolean 语句 i%2 == 0 ? (num%i == i/2) : (num%i == 0) .让我们看一些例子:

   i    all sums of i consecutive positive integers
   2    3, 5, 7, 9...
   3    6, 9, 12, 15...
   4    10, 14, 18, 22...
   5    15, 20, 25, 30...
   

   有两种情况，但在任何一种情况下，我们都可以表示所有可能的数字是 i 的总和连续的整数非常简单。

   1. 当 i是偶数，num必须等于 (i * n) + (i / 2)其中 n是一个非负整数。这当然可以写成 num % i == i / 2 .

   2. 当 i是奇数，num必须等于 i * n , 其中n是一个非负整数。这给了我们第二个条件 num % i == 0 .

   除了这些条件，num不能小于第i的总和正整数。因此，我们的 for循环的条件:sumOfFirstIIntegers <= num .

2. 判断一个数是否不是 2 的幂:

   boolean IsSumOfConsecutiveInts(int num)
   {
       return (num & (num - 1)) != 0;
   }
   

   This answer很好地解释了为什么会这样。

请注意，上述两种解决方案的结果相同，它们只是对问题的不同思考方式。