Skip to content

20.09.2011

Первая задача с projecteuler.net

Если выписать все натуральные числа меньше 10, кратные 3 или 5, то получим 3, 5, 6 и 9. Сумма этих чисел — 23.
Найдите сумму всех чисел меньше 1000 кратных 3 или 5.

Мое предыдущее решение было мягко говоря не идеальным, но после ввода правильного ответа на сайте можно посмотреть файл с правильным решением (на англ. языке).

Итак мое прошлое решение:

<script>
sum = 0;
for(i = 1; i < 1000; i++)
{
if (i%3=0)||(i%5=0)
  sum += i;
}
alert(sum);
</script>

Но, как указано в решении, если бы вместо тысячи стоял 10000000 то выполнение этого кода было бы долгим и неправильным. В чем же правильное решение? Запишем числа, которые делятся только на 3 : 3 + 6 + 9 + 12 + 15+ … + 999. Получилась арифм. прогрессия с шагом 3. С пятеркой тоже самое : 5 + 10 + 15 … + 995. Но 15 уже входит в прогрессию с 3. Напишем функцию для вычисления суммы элем. арифм. прогрессии.

<script>
function summaprog(n, a1, a2) // n - количество суммируемых элементов; a1, a2 - первые 2
{                             //элемента
  d = a2 - a1;
  return (2*a1 + d* (n-1))*n/2;
}
</script>

Осталось определить, n для прогрессий. Для 3: 3 + 6 + 9 +…+ n = 3 * (1 + 2 + 3 +…+ n / 3). Количество элементов для прогрессии с шагом 3 = 999 / 3 = 333; для 5 = 995 / 5 = 199, для 15 = 990 / 15 = 66. Итак пишем решение:

<script>
function summaprog(n, a1, a2)
{
  d = a2 - a1;
  return (2*a1 + d* (n-1))*n/2;
}
alert(summaprog(333, 3, 6) + summaprog(199, 5, 10) - summaprog(66, 15, 30));
</script>

Но зачем самому считать кол-во элементов. Можно взять максимальное значение и поделить нацело на шаг прогрессии. В js целочисленного деления нет. Напишем еще одну функцию:

<script>
function del(a, b)
{
return ((a - a % b)/b);
}
</script>

del(999, 3) = 333, del(999, 5) = 199, del(999, 15) = 66.
Вот окончательный код:

<script>
function summaprog(n, a1, a2)
{
  d = a2 - a1;
  return (2*a1 + d* (n-1))*n/2;
}
function del(a, b)
{
return ((a - a % b)/b);
}
alert(summaprog(del(999, 3), 3, 6) + summaprog(del(999, 5), 5, 10) - summaprog(del(999, 15), 15, 30));
</script>

Share your thoughts, post a comment.

(required)
(required)

Note: HTML is allowed. Your email address will never be published.

Subscribe to comments