Задача «Суммирование чисел». Пример решения

Нахождение суммы чисел

Постановка задачи. Найти сумму всех целых чисел от n_min до n_max.

Вариант решения 1. Взять n_min — наименьшее число, к нему прибавить следующее, и так далее – до n_max.

Обсуждение 1. Тогда для вычисления суммы чисел от 1 до 100 необходимо выполнить 99 операций сложения или около 10 минут, если одну операцию сложения вы будете в уме выполнять за 6 секунд. Попробуйте выполнить такие действия в уме с секундомером. Но если таких чисел у вас 1 млрд = 10⁹, тогда вам понадобится чуть более 30 лет без сна и отдыха.

Реализация 1. Вы скажете, это работа для компьютера и напишите программу, реализующую принципы структурного программирования:
1) оператор goto нам не нужен:
2) будем использовать только две конструкции: последовательность и цикл;
3) программу представим как последовательность блоков: ввод, сумма, вывод; цикл суммирования является вложенным в блок сумма;
4) выделим три подпрограммы (метода класса Program), назовем их именами блоков: ввод(), сумма1(), вывод(). Для ввода данных и вывода результата воспользуемся методами классов Console и Convert. При необходимости используем и другие конструкции;
5) блок в операторе цикла выделять с помощью { } не обязательно, так как он состоит из одного оператора. Перед циклом сумматор sum следует обнулить. Затем в цикле последовательно добавлять к сумматору следующее число.
6) принцип один вход – один выход для каждого блока соблюдается;
7) принцип сверху-вниз также соблюдается, сначала выделим три блока в методе Main(), затем наполним их операторами.
Дополнительно выберем тип int для всех переменных (пока, чтобы было с чего начать). Три поля и четыре метода класса Program объявим статическими (static, подробности – в статье). Тогда программа будет выглядеть так:

// Сумма чисел от мин до макс
 using System;
 namespace Сумма_чисел
 {
    class Program
    {
       static int n_min, n_max;
       static int sum;
       static void Main(string[] args)
       {
          ввод();
          сумма1();
          вывод("Сумма чисел через цикл = ");
          Console.ReadKey();
       }
       static void ввод()
       {
          Console.Write("начальное число = ");
          n_min = Convert.ToInt32(Console.ReadLine());
          Console.Write("конечное число = ");
          n_max = Convert.ToInt32(Console.ReadLine());
       }
       static void сумма1()
       {
          sum = 0;
          for (int i = n_min; i <= n_max; i++)
          sum = sum + i;
       }
       static void вывод(string z)
       {
          z = z + sum.ToString();
          Console.WriteLine(z);
       }
    }
 }

Выполним суммирование чисел от 1 до 100:

Проверим работу программы на других данных, для чего используем следующие тесты (о технологии тестирования читайте отдельно)  и выполним тестирование:

Как мы видим, тесты 1,2,4,5 дают ожидаемый результат, на тестах 3,6,7 обнаруживаются ошибки.  На тесте 8 возникает необработанное исключение.
Тест 3 показал (сравните с тестом 1), что если начальное число больше конечного, то суммирование не производится. В отличие от компьютера, который данные и команды воспринимает буквально, человек поймет, что сумма чисел от 1 до 100 всегда равна сумме чисел от 100 до 1:
1+2+…+99+100=100+99+…+2+1 .
Поэтому в метод ввод() добавим проверку условия n_min > n_max.. И, если оно истинно, выполним перестановку, используя локальную переменную p. Это самый простой  алгоритм перестановки:

 int p;
 if (n_min > n_max)
 {
    p = n_min;
    n_min = n_max;
    n_max = p;
 }

Выполним тест 3, а также снова тесты 1, 2, 4 (изменения в программе могут приводить к появлению других ошибок), убедимся в правильности нашей корректировки.
Примечание: Обратите внимание на алгоритм перестановки, использующий дополнительную переменную и сокращенный условный оператор (только ветка if). Если условие истинно, то выполняется блок из трех операторов присваивания, заключенных в фигурные скобки. Если условие ложно, то перестановка не выполняется. Таким образом, при вводе любых двух целых чисел результатом выполнения метода ввод() будет пара чисел:    n_min <= n_max.

Какие еще полезные знания можно извлечь из анализа результатов тестирования? Главное – действовать, а не сидеть сложа руки.
Сравним теперь результаты тестов 5 и 6. Может ли сумма положительных чисел от 1 до 70000  быть отрицательной? В первом тесте сумма примерно равна 1,8·10⁹, во втором ожидаемый результат 2,45·10⁹.
Вспомним, что тип int в C# задается структурой, у которой  есть некоторое свойство, например, Int32.MaxValue. Выполним оператор:
Console.WriteLine(int.MaxValue);
Будет выведено число 2147483647, примерно равное  2,15·10⁹. То есть:
1,8·10⁹  < 2,15·10⁹  < 2,45·10⁹.
Это означает, что сумма чисел от 1 до 70000 превышает максимальное число типа int (System.Int32), происходит переполнение, которое никак не диагностируется, что приводит к неправильному результату.

Пример размышлений начинающего программиста: Каждый тип данных имеет минимальные и максимальные допустимые значения. Например, тип int занимает 4 байта (32 бита), причем один из битов используется под знак. Следовательно, максимальное число будет равно 2³¹-1=2147483647. Аналогично, число типа long (Int64) занимает 8 байт (64 бита), из них – 1 бит под знак числа. Тогда максимальное число этого типа равно:
2⁶³ – 1 = 9223372035854775807, примерно 9,2·10¹⁸.
Если все дело в типе данных, то давайте заменим тип переменной sum с int на long в классе Program:
static long sum;
Заново выполним тестирование для тестов 1-8. В первых семи тестах получим ожидаемый результат, так как переполнения не происходит.

Добавьте тесты 9 (от 1 до 2·10⁹ ) и 10 (от 1 до 3·10⁹).  Объясните результаты. Заметим, что на тесте 9 возникает уже заметная задержка в получении результата – несколько секунд (у меня – 5с).

Попробуем разобраться с тестом 8. Пользователь вашей программы иногда делает ошибки при вводе данных, поэтому можно предусмотреть обработку ошибок некоторым общим образом. Используем оператор try-catch. Оператор try-catch состоит из блока try, за которым следует одно или несколько предложений catch, задающих обработчики для различных исключений. Тогда метод ввод() будет содержать несколько больше операторов:

static void ввод()
{
   try
   {
      Console.Write("начальное число = ");
      n_min = Convert.ToInt32(Console.ReadLine());
      Console.Write("конечное число = ");
      n_max = Convert.ToInt32(Console.ReadLine());
      int p;
      if (n_min > n_max)
      {
         p = n_min;
         n_min = n_max;
         n_max = p;
      }
   }
   catch
   {
      Console.WriteLine("недопустимый формат числа");
   }
}

Примечание. Этот пример демонстрирует пользу структурного подхода. Мы изменили только метод ввод() без изменения структуры программы.

Выполните тестирование (тесты 1-10), проанализируйте результаты. Теперь реакция на недопустимый формат числа более адекватная.

Другой взгляд на задачу суммирования

А теперь, еще раз обратимся к постановке задачи «Найти сумму всех целых чисел от n_min до n_max».

Будущий великий математик Карл Фридрих Гаусс (1777-1855гг.), будучи в младшей школе, решил эту задачу (от 1 до 100), заданную на уроке учителем, за несколько секунд. Гауссу быстро удалось понять, что все крайние числа в паре составляют 101, и за считанные секунды он решил это уравнение, умножив 101 на 50. Отсюда следует и общий алгоритм:

Вариант решения 2. Найти алгебраическое выражение для суммы арифметической прогрессии (надеюсь, вы знаете, что это такое, если нет – посмотрите в Интернете) от n_min до n_max с шагом 1.

Обсуждение 2. Тогда для вычисления суммы от 1 до 1 млрд = 10⁹ вам не понадобится 30 лет без сна и отдыха, а время, затрачиваемое на вычисления, не зависит от исходных данных и будет очень малым.

Реализация 2. Вы скажете, это работа даже не для компьютера и выведите формулу:
sum = (n_min + n_max)(n_max — n_min + 1) / 2.
Подставьте в нее числа 1 и 100, получите 5050, 1 и 101, получите 5151.
Все таки добавим еще один метод, использующий вычисление по формуле:

static void сумма2()
{
   sum = (long)(n_min + n_max) *(long) (n_max - n_min + 1) / 2;
}

Операции приведения типов (расширяющее преобразование) используются для снижения риска переполнения. Уберите (long) и исследуйте, что произойдет с тестами.
Для сравнения результатов добавим два оператора в метод Main(), тогда:

static void Main(string[] args)
{
   ввод();
   сумма1();
   вывод("Сумма чисел через цикл = ");
   сумма2();
   вывод("Сумма чисел через формулу = ");
   Console.ReadKey();
}

Отметим, что структура метода Main() – последовательность. Метод вывод() мы используем дважды, а ее строковый параметр служит для  смены заголовков.
Вот пример выполнения окончательного варианта программы:

Конец обсуждения задачи 1.1

Программистский фольклор: «Формула лучше алгоритма».

Следующий пример:  Вычисление sin(x).

---

NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.

---

Помощь проекту: