Форум программистов, компьютерный форум CyberForum.ru

Быстрое нахождение суммы - C++

Восстановить пароль Регистрация
 
RESTY
5 / 5 / 0
Регистрация: 30.05.2012
Сообщений: 89
05.11.2012, 02:29     Быстрое нахождение суммы #1
Дано натуральное число 1<=N<=1000000000;
как посчитать сумму чисел от 1 до N менее чем за 1 секунду?)
понятно что
C++
1
2
3
for (int i = 1; i <= n; i++){
        s += i;
}
при таком действие уйдет пара секунд...
как же быстрее сделать?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2012, 02:29     Быстрое нахождение суммы
Посмотрите здесь:

Нахождение суммы C++
Нахождение суммы C++
Нахождение суммы ряда. C++
C++ Нахождение суммы элементов
Быстрое нахождение количества делителей натурального числа C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
05.11.2012, 02:47     Быстрое нахождение суммы #2
intом тут не обойтись, тут даже unsigned long не подойдет (0..4294967295). А если в диапазон уложиться, то и полсекунды хватит (замерял через start = clock() - end = clock()).
I.M.
 Аватар для I.M.
564 / 547 / 5
Регистрация: 16.12.2011
Сообщений: 1,389
05.11.2012, 02:50     Быстрое нахождение суммы #3
RESTY, сумма арифметической прогрессии
Только вам нужно что-то придумать с хранением чисел - см. пост 2
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
05.11.2012, 03:07     Быстрое нахождение суммы #4
Сумма чисел от 1 до N это N * (N + 1) / 2. В 64-битное целое влазит с ушами.
RESTY
5 / 5 / 0
Регистрация: 30.05.2012
Сообщений: 89
05.11.2012, 03:17  [ТС]     Быстрое нахождение суммы #5
уже придумал вспомнил лекцию по вышке)
C++
1
2
3
4
5
6
#include <iostream>
void main(){
  __int64 n ;
  std::cin >> n;
  std::cout << ((1 + n)*n/2)<<".00";
}
Yandex
Объявления
05.11.2012, 03:17     Быстрое нахождение суммы
Ответ Создать тему
Опции темы

Текущее время: 16:30. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru