3

How do I check if a number is sum of multiples of 3 and 5 given that the number could be as big as 100,000 . I need an optimized way to break a number into two parts such that the two parts are multiple of 3 and 5 only and the part which is multiple of 3 is greater than the part which is multiple of 5 and if that kind of splitting is not possible then I need to reject that number .

Eg:

1  => cant be split so rejected ,
35 => 30 + 5 ,
65 => 60 + 5 (Though 30 + 35 could be a split but since part which is multiple of 3 has to be                greater than the part which is multiple of 5),
11 => 6+5
4

5 回答 5

3

每个（整数）数模 3 产生 0、1 或 2。

因此，让我们检查所有情况（出于显而易见的原因，n > 3 必须屈服）：

  1. n % 3 == 0. Easy：我们只是把0 == 0 * 5和n / 3当作分裂。
  2. n % 3 == 2. 再次简单：一个数字将是5，另一个数字将是(n-5) / 3。当从 n 中减去 5 时，我们将创建第二个数字(n-5)，它属于第一种情况。

  3. n % 3 == 1. 与案例 2 相同，但这次我们减去10 == 2*5。

    一个小问题是 3 的倍数必须大于 5 的倍数的性质。为此，n 必须至少为 22。 ( 22 == 2 * 5 + 3 * 4)。

因此，所有小于 22 的数字n % 3 == 1都必须被拒绝：4, 7, 10, 13, 16 and 19。（只要倍数的因子必须是非负的）。

于 2013-09-08T12:13:05.253 回答
1

如果您想找到一种方法将一个数字分成两部分，其中第一部分是 的倍数，3第二部分是 的倍数5，另外要求第一部分（3 的倍数）大于第二部分（5的倍数）部分，那么它相当微不足道：

20 及以上的每个数字都可以这样拆分。

证明：对于给定的数字，三个数字中N的一个恰好是 3的倍数（考虑算术。）因此，这三个拆分之一满足要求：NN-5N-10modulo 3

N      0
N-5    5
N-10  10

并且因为N >= 20，第一部分大于（或等于）第二部分。

于 2013-09-08T12:16:09.240 回答
0

从我的头顶上——

令 Q = N / 3，整数除法，四舍五入。使 R 为余数。

如果 R = 0，你就完成了。

如果 R == 2，则递减 Q。

否则 R 必须为 1，从 Q 中减去 2。

你的答案是 Q * 3 和 N - (Q * 3)。检查所有结果是否为阳性并且满足 3s 倍数 > 5s 倍数限制。

（请注意，这与Sirko的答案基本相同，但我觉得值得单独考虑，所以我没有尝试先分析他。）

于 2013-09-08T12:22:55.840 回答
-2

3 和 5 的最大除数为 1。所以当 N = 3 或 N >= 5 时，它可以是 3 和 5 的倍数之和。

于 2013-09-08T12:07:42.587 回答
-5

只需使用此代码：- 享受 :)

$num = 0; // Large Number
$arr = array();
if(isset($_POST['number']) $num = $_POST['number'];
// Assuming you post the number to be checked.

$j=0;

for($i=0;$i<$num;$i++) 
{

if(($num-$i)%3==0 || ($num-$i)%5==0) { $arr[j] = $num - $i; $j++; }

 }
 //This creates an array of all possible numbers.
 $keepLooping = true;
 while($keepLooping)
 { 
  $rand = array_rand($arr,2);
  if(($rand[0] + $rand[1]) == $num) 
   {
    //Do whatever you like with them. :)
   }

    }

我还没有测试它，但只是为了你的想法。您可以选择适合您的其他方式，而不是使用 for 循环来选择可能性。

于 2013-09-08T12:23:29.613 回答