Как найти суммы переменных циклов

Материалы по курсу «Основы программирования»

Синтаксис цикла while выглядит так:

while ‹условие›:
    ‹тело цикла›

• ‹условие› — логическое выражение, т.е. выражение, которое может быть
  истинным или ложным.
• ‹тело цикла› — последовательность операторов с отступом

Если тело цикла состоит из одного оператора, то цикл, также как и if,
можно записать в одну строчку:

while ‹условие›: ‹тело цикла›

Но так лучше не писать из стилистических соображений.

Как он выполняется:

• Вычисляется значение выражения ‹условие›.
• Если условие ложное, цикл прерывается, ‹тело цикла› ни разу не выполняется.
• Если условие истинноое, выполняется ‹тело цикла›.
• И потом снова вычисляется ‹условие›.
• Если оно ложное — цикл прерывается, если истинное, снова выполняется ‹тело
цикла›.
• И так далее.

Т.е. пока значение ‹условия› истинное, поочерёдно вычисляется ‹условие›
и выполняется тело цикла.

Сравним с if:

Блок либо выполнится, либо не выполнится.

Блок может выполняться много раз.

Итерация — однократное выполнение тела цикла.

Пример. Просуммировать все числа от 1 до 100.

sum = 0
i = 1
while i <= 100:
    sum = sum + i
    i = i + 1

В переменной i находится очередное число. В начале оно равно 1, затем
на каждой итерации (проходе, витке) цикла оно увеличивается на 1. В результате
на первом витке i равно 1, на втором — i равно 2 и т.д. Таким образом,
в переменной i на входе в цикл находится номер текущей итерации.

Переменная sum изначально равна нулю, на каждом витке цикла её содержимое
увеличивается на номер этой итерации цикла (значение переменной i). В итоге,
значение переменной sum после завершения цикла увеличится на сумму чисел
от 1 до 100. Начальным её значением было число 0, поэтому после завершения
цикла в ней будет сумма чисел от 0 до 100.

Этот цикл обязательно завершится, т.к. до начала цикла переменная i хранила
значение меньше 100, на каждом проходе цикла переменная i увеличивается
и поэтому рано или поздно превысит 100 — условие i <= 100 станет ложным
и цикл прервётся.

Этот пример можно записать компактнее:

sum = 0
i = 1
while i <= 100:
    sum += i
    i += 1

Здесь мы использовали сокращённую запись операторов присваивания. Вспомним,
что запись вида

является сокращением для

‹перем› = ‹перем›  ‹знак›  ‹выраж›

Вернёмся к циклу while. Для цикла вида

while ‹условие›:
    ‹тело цикла›

если в теле цикла нет явных конструкций прерывания цикла (break, return),
можно быть уверенным, что после завершения цикла ‹условие› будет ложным.

А внутри самого цикла ‹условие› истинное.

Пример. Написать функцию is_prime(n), проверяющую число на простоту.

def is_prime(n):
    ‹проверить число на простоту›

Число простое, если оно больше чем 2 и делится только на себя и на единицу.
Число делится на другое, если остаток от деления равен нулю.

def is_prime(n):
    ‹перебирать все числа от 2 до бесконечности,
     пока не найдётся делитель›
    ‹сравнить делитель с n›

Считаем, что n у нас не меньше 2. Среди чисел от 2 до бесконечности
рано или поздно найдётся делитель числа n — для составного числа это будет
один из делителей n, для простого — само n.

def is_prime(n):
    divisor = 2
    while ‹n не делится на divisor›:
        ‹увеличить divisor на 1›

    return divisor == n

Уточняем дальше:

def is_prime(n):
    divisor = 2
    while n % divisor != 0:
        divisor += 1

    return divisor == n

Данная функция зациклится, если n будет отрицательным, нулём или единицей.
Она определена только для n >= 2.

Функцию можно оптимизировать, перебирая делители не до бесконечности
(фактически, до n), а до √n:

def is_prime(n):
    divisor = 2
    while (divisor <= n**0.5) and (n % divisor != 0):
        divisor += 1

    return ‹а что тут написать?›

Цикл продолжается, пока divisor <= √n и при этом n не делится на divisor
без остатка. Соответственно, чтобы цикл прекратился, должно нарушится
хотя бы одно из условий:

• divisor > √n,
• n делится на divisor без остатка.

Признаком того, что число простое, является первое условие — очередной кандидат
в делители превысил √n.

def is_prime(n):
    divisor = 2
    while (divisor <= n**0.5) and (n % divisor != 0):
        divisor += 1

    return divisor > n**0.5

Пример. Найти сумму цифр целого числа.

Нам нужно разбить число на отдельные цифры и их сложить. Разбивать число будем
справа налево: последняя цифра числа — это его остаток от деления на 10,
все цифры, кроме последней — результат целочисленного деления на 10.

Целочисленное деление в Python — это операция //, возвращает целую часть
частного:

>>> 30 / 4
7.5
>>> 36 / 4
9.0
>>> 30 // 4
7
>>> 36 // 4
9

Назовём функцию sum_digits(n):

def sum_digits(n):
    ‹найти сумму цифр›

Для хранения суммы заведём переменную-аккумулятор sum, которую на каждой
итерации будем увеличивать на величину очередной цифры. До цикла положим
в неё 0, после завершения цикла в ней будет находиться сумма цифр.

def sum_digits(n):
    sum = 0
    while ‹цифры не кончились›:
        ‹найти очередную (последнюю) цифру›
        ‹увеличить sum на очередную цифру›
        ‹отбросить последнюю цифру числа›
    return sum

Уточняем:

def sum_digits(n):
    sum = 0
    while n != 0:
        last_digit = n % 10
        sum += last_digit
        n //= 10
    return sum

В предпоследней строке мы воспользовались сокращённой записью для n = n // 10.

Приёмы использования цикла while

Перебор всех значений

Решаемая задача. Есть некоторая последовательность значений, нужно перебрать
их все и с каждым значением что-нибудь сделать.

Шаблон решения:

‹установка на начало›
while ‹значения не кончились›:
    ‹сделать что-то с текущим значением›
    ‹перейти к следующему›

Под этот шаблон хорошо подходит предыдущий пример — суммирование цифр числа:

def sum_digits(n):
    sum = 0
    while n != 0:
        last_digit = n % 10
        sum += last_digit
        n //= 10
    return sum

• Здесь ‹установки на начало› нет, т.к. в переменной n уже лежит исходное
  число.
• ‹значения не кончились› — условие n != 0 — цифры в числе не кончились.
• ‹сделать что-то с текущим› — две первые строчки тела цикла:

  last_digit = n % 10
  sum += last_digit
  

• ‹перейти к следующему› — n //= 10 — отбрасывание последней цифры.

Другой пример с сегодняшней лекции:

sum = 0
i = 1
while i <= 100:
    sum += i
    i += 1

• ‹установка на начало› — i = 1,
• ‹значения не кончились› — i <= 100,
• ‹сделать что-то с текущим› — sum += i — увеличение суммы на номер витка,
• ‹перейти к следующему› — i += 1.

Поиск значения при помощи цикла while

Решаемая задача. Есть множество каких-то значений, нужно среди них найти
первое, которое удовлетворяет заданным свойствам, в частности, равно чему-либо.

Шаблон решения.

‹установка на первое значение›
while ‹значения не кончились› and ‹текущее — не искомое›:
    ‹переходим к следующему›

if ‹значения кончились›:
    ‹сделать что-то, когда искомого значения нет›
else:
    ‹текущее значение — искомое, сделать что-то с ним›

Пример. Ранее мы рассматривали пример на определение простоты числа.
Рассмотрим его ещё раз, но уже с точки зрения приёма поиска при помощи цикла
while.

Если число составное, то у него найдутся два делителя: m = n × k, при этом
либо n == k, т.е. m = n² = k², либо один из делителей будет меньше √n,
а второй — больше, чем √n.

Поэтому, чтобы определить, составное ли это число, нужно найти делитель,
который будет не больше, чем √n. Т.е. задача проверки на простоту сводится
к проверке на поиск делителя.

def is_prime(n):
    ‹установка на начало›
    while ‹не достигли конца› and ‹не нашли›:
        ‹перейти к следующему›

    if ‹достигли конца›:
        ‹сделать что-то, когда не нашли›
    else:
        ‹сделать что-то, когда нашли›

Немного уточним фразы в псевдокоде:

def is_prime(n):
    ‹установка на первый кандидат в делители›
    while ‹кандидат в делители не больше √n› and ‹это не делитель›:
        ‹перейти к следующему›

    if ‹кандидат в делители больше √n›:
        ‹сделать что-то, когда не нашли›
    else:
        ‹сделать что-то, когда нашли›

Можем уточнить две последние фразы: если делитель найден, число составное,
функция возвращает ложь. Если не найден — простое, функция возвращает истину:

def is_prime(n):
    ‹установка на первый кандидат в делители›
    while ‹кандидат в делители не больше √n› and ‹это не делитель›:
        ‹перейти к следующему›

    if ‹кандидат в делители больше √n›:
        return True
    else:
        return False

Кандидата в делители положим в переменную divisor и перепишем на Python ещё
несколько фраз в псевдокоде:

def is_prime(n):
    divisor = 2
    while divisor <= n**0.5 and n % divisor != 0:
        divisor += 1

    if divisor > n**0.5:
        return True
    else:
        return False

Получили готовую работающую функцию. Но её можно упростить.

Как мы знаем, конструкцию вида

if ‹условие›:
    return True
else:
    return False

можно упростить до

В рассматриваемой функции мы видим похожую конструкцию:

    if divisor > n**0.5:
        return True
    else:
        return False

Теперь мы можем упростить его до одной строчки:

Целиком функция примет вид:

def is_prime(n):
    divisor = 2
    while divisor <= n**0.5 and n % divisor != 0:
        divisor += 1

    return divisor > n**0.5

Пример. Найти наибольший общий делитель. Мы будем рассматривать поиск
наибольшего общего делителя именно как задачу поиска, т.е. без алгоритма
Евклида.

def gcd(m, n):
    ‹найти НОД›

Делитель числа не превышает модуль (абсолютное значение) этого числа.

Чтобы найти общий делитель, нужно перебирать числа и искать среди них число,
на которое делятся два исходных без остатка. Чтобы общий делитель был
наибольшим, нужно перебирать числа в порядке убывания.

Поэтому в качестве начального кандидата в делители мы можем взять абсолютное
значение одного из двух аргументов.

def gcd(m, n):
    ‹установка на начало›
    while ‹не достигли конца› and ‹текущее — не искомое›:
        ‹перейти к следующему›

    if ‹достигли конца›:
        ‹случай, когда НЕ нашлось›
    else:
        ‹случай, когда нашлось›

Кандидат в делители будем хранить в переменной res. Перебирать числа будем
в порядке убывания, начнём с абсолютного значения m. На самом деле, можно
и с n, можно выбрать из них наименьшее, но это нам не важно, нам важно
рассмотреть поиск.

• ‹установка на начало — res = abs(m)
• ‹не достигли конца› — res > 0
• ‹текущее — не искомое› — НЕ общий делитель. Общий делитель — делится
  на оба числа без остатка. Т.е. НЕ общий делитель — not (m % res == 0 and
n % res == 0).
• ‹перейти к следующему› — res -= 1, т.к. перебираем по убыванию.

Вернёмся к коду:

def gcd(m, n):
    res = abs(m)
    while res > 0 and not (m % res == 0 and n % res == 0):
        res -= 1

    if ‹достигли конца›:
        ‹случай, когда НЕ нашлось›
    else:
        ‹случай, когда нашлось›

Вопрос. А может ли res быть равным нулю? Отрицательным быть не может, т.к.
это абсолютное значение числа (res = abs(m)). Нулём может, только когда
m сам равен нулю. Но если одно из чисел равно нулю, то наибольший общий
делитель — второе число.

В остальных случаях res не будет равен нулю, т.к. искомый элемент (общий
делитель) обязательно найдётся — в худшем случае это будет 1.

Поэтому, в случае, когда делителя не нашлось (m == 0), возвращаем n,
а в остальных случаях — найденный общий делитель:

def gcd(m, n):
    res = abs(m)
    while res > 0 and not (m % res == 0 and n % res == 0):
        res -= 1

    if res == 0:
        return n
    else:
        return res

Примечание. Часто для результата функции заводят переменную с именем res.

Содержание

• 1. Нахождение суммы положительных элементов массива из n целых чисел
  • 1.1. Реализация с помощью цикла for
  • 1.2. Реализация с помощью цикла while
  • 1.3. Реализация с помощью цикла do…while
• 2. Найти сумму элементов массива, которые размещаются на парных индексах
• 3. Найти произведение элементов массива, которые больше заданного числа
• 4. Определение наличия (отсутствия) заданного символа в массиве символов (тип char)
• 5. Определение наличия (отсутствия) заданного числа в массиве чисел. Массив имеет n целых чисел
• 6. Поиск позиции последнего вхождения элемента k в массиве из n целых чисел
• 7. Поиск позиции первого вхождения элемента k в массиве из n целых чисел
• 8. Подсчет количества элементов k в массиве из n целых чисел
• 9. Подсчет количества элементов в массиве из n вещественных чисел, которые меньше заданного значения k
• 10. Подсчет количества элементов в массиве из n вещественных чисел, значение которых находится в пределах диапазона [a .. b].
• 11. Подсчет количества парных элементов в массиве из n целых чисел
• Связанные темы

Поиск на других ресурсах:

1. Нахождение суммы положительных элементов массива из n целых чисел

Задан массив A из 10 целых чисел. Найти сумму положительных элементов массива

1.1. Реализация с помощью цикла for

В данном примере пропущен ввод массива A

// Нахождение суммы положительных элементов массива
const int Max = 10;
int A[Max]; // заданный массив
int i;

// ввод массива A
// ...

// вычисление суммы
int sum = 0;

for (i=0; i<MaxN; i++)
    if (A[i]>0)
        sum = sum + A[i];

1.2. Реализация с помощью цикла while

// Нахождение суммы положительных элементов массива
const int Max = 10;
int A[Max]; // заданный массив
int i; // дополнительная переменная
int sum = 0; // результат

// ввод массива A
// ...

// вычисление суммы
i=0;
while (i<MaxN)
{
    if (A[i]>0)
        sum+=A[i];
    i++;
}

1.3. Реализация с помощью цикла do…while

// Нахождение суммы положительных элементов массива
const int Max = 10;
int A[Max]; // заданный массив
int i; // дополнительная переменная
int sum = 0; // результат

// ввод массива A
// ...

// вычисление суммы
i=0;

do
{
    if (A[i]>0)
        sum+=A[i];
    i++;
}
while (i<MaxN);

  ⇑

2. Найти сумму элементов массива, которые размещаются на парных индексах

В данном примере вычисляются суммы элементов массива A, индексы которых есть парными: 0, 2, 4, … Чтобы определить есть ли число (индекс массива) парным, нужно выполнить проверку

if ((i%2)==0)
{
    // действия, если число парное
    // ...
}

Реализация решения данной задачи тремя видами цикла (ввод массива A пропущен).

// Нахождение суммы элементов массива, имеющих парные индексы (0, 2, 4,...)
const int Max = 10;
int A[Max]; // заданный массив
int i; // дополнительная переменная
int sum1, sum2, sum3; // результаты вычислений разными видами циклов

// ввод массива A
// ...

// вычисление суммы, цикл for
sum1 = 0;
for (i=0; i<Max; i++)
    if ((i%2)==0) // определение парности числа
        sum1+=A[i];

// вычисление суммы, цикл while
sum2 = 0;
i=0;
while (i<MaxN)
{
    if ((i%2)==0) sum2+=A[i];
    i++;
}

// вычисление суммы, цикл do...while
sum3 = 0;
i=0;
do
{
    if ((i%2)==0)
        sum3+=A[i];
    i++;
}
while (i<MaxN);

  ⇑

3. Найти произведение элементов массива, которые больше заданного числа

В примере находится произведение элементов массива A, которые больше числа, которое размещается в переменной number.
Реализация задачи с использованием цикла for:

// произведение элементов массива, которые больше заданного числа
const int Max = 10;
int A[Max]; // заданный массив
int number; // заданное число
int i; // дополнительная переменная
int res; // результат - произведение

// ввод массива A
for (i=0; i<MaxN; i++)
{
    A[i] = i;
}

// задание числа number
number = 5;

// поиск произведения - цикл for
res = 1;
for (i=0; i<MaxN; i++)
    if (A[i]>number)
        res = res * A[i];

// res = 3024

Если размерность массива большая, то результат произведения целесообразно держать в переменной типа double (float). Это связано с тем, что результатом произведения могут быть очень большие или очень маленькие числа. При использовании целых типов может возникнуть переполнение.

Фрагмент реализации данной задачи с использованием цикла while

...

// поиск произведения - цикл while
res = 1;
i=0;
while (i<MaxN)
{
    if (A[i]>number)
        res = res * A[i];
    i++;
}
// res = 3024

Реализация с помощью цикла do…while

// поиск произведения - цикл do...while
res = 1;
i=0;

do
{
    if (A[i]>number)
        res = res * A[i];
    i++;
}
while (i<MaxN);

// res = 3024

  ⇑

4. Определение наличия (отсутствия) заданного символа в массиве символов (тип char)

Пусть задан массив символов M. Определить, есть ли заданный символ sym в массиве M. В данном примере пропущен этап ввода массива M и символа sym. Реализация алгоритма с использованием цикла for.

// определение наличия (отсутствия) символа в массиве M
char M[10]; // заданный массив
char sym; // заданный символ
int i;
bool f; // результат: true - символ sym есть в массиве M

// ввод массива M
// ...

// вычисление
f = false;
for (i=0; i<10; i++)
    if (M[i]==sym)
        f = true;

  ⇑

5. Определение наличия (отсутствия) заданного числа в массиве чисел. Массив имеет n целых чисел

Задан массив A целых чисел. Определить, есть ли заданное число num в массиве A.
Реализация с использованием цикла while (ввод массива A и переменных n, num пропущен).

// определение наличия (отсутствия) заданного числа в массиве чисел
int A[50]; // заданный массив A
int n; // текущая размерность массива n = 1..50
int num; // искомое число
int i; // дополнительная переменная
bool f; // результат: f=true - число есть в массиве, иначе f=false

// ввод A, n, num
// ...

// вычисление
f = false;
i=0;

while (i<n)
{
    if (A[i] == num)
        f = true;
    i++;
}

  ⇑

6. Поиск позиции последнего вхождения элемента k в массиве из n целых чисел

Способ 1 (медленный).

В данном алгоритме результирующая переменная pos определяет позицию последнего вхождения элемента k в массиве из n целых чисел. Если такого символа нет в массиве, то pos = -1. Реализация с помощью цикла do…while

// поиск позиции последнего вхождения элемента k в массиве из n целых чисел
int A[50]; // заданный массив A
int n; // текущая размерность массива n = 1..50
int k; // искомое число
int i; // дополнительная переменная
int pos; // результат - номер позиции, если pos=-1, то числа k не найдено в массиве A

// ввод A, n, k
// ...

// вычисление, реализация с помощью цикла do...while

pos = -1;
i=0;

do
{
    if (A[i] == k)
        pos = i;
    i++;
}
while (i<n);

Способ 2 (быстрый).

Если перебирать (пересматривать) индексы массива от конца к началу, то первый элемент равен k будет позицией последнего вхождения. В этом случае реализация алгоритма (цикл do…while) будет следующей

// поиск позиции последнего вхождения элемента k в массиве из n целых чисел
int A[50]; // заданный массив A
int n; // текущая размерность массива n = 1..50
int k; // искомое число
int i; // дополнительная переменная
int pos; // результат - номер позиции, если pos=-1, то число k не найдено в массиве A

// ввод A, n, k
// ...

// вычисление, реализация с помощью цикла do..while

pos = -1;
i=n-1;

do
{
    if (A[i] == k)
    {
        pos = i;
        i=-1; // выход из цикла
    }
    else
        i--;
}
while (i>=0);

  ⇑

7. Поиск позиции первого вхождения элемента k в массиве из n целых чисел

Как было показано в предыдущем пункте, эту задачу можно решать разными способами. В нижеследующем коде массив пересматривается от начала к концу. Как только встречается элемент k, происходит запоминание позиции элемента k и выход из цикла.

Реализация задачи с использованием цикла for.

// поиск позиции первого вхождения элемента k в массиве из n целых чисел
int A[50]; // заданный массив A
int n; // текущая размерность массива n = 1..50
int k; // искомое число
int i; // дополнительная переменная
int pos; // результат - номер позиции, если pos=-1, то число k не найдено в массиве A

// ввод A, n, k
// ...

// вычисление, реализация с помощью цикла for
pos = -1;
for (i=0; i<n; i++)
    if (A[i]==k)
    {
        pos = i;
        break; // выход из цикла
    }

  ⇑

8. Подсчет количества элементов k в массиве из n целых чисел

В нижеследующем коде пропущен ввод массива A и значений n, k.

// подсчет количества элементов k в массиве A
int A[50]; // заданный массив A
int n; // текущая размерность массива n = 1..50
int k; // искомое число
int i; // дополнительная переменная
int count; // результат - количество найденных элементов

// ввод A, n, k
// ...

// вычисление, реализация с помощью цикла while
count=0;
i=0;
while (i<n)
    if (A[i++]==k)
        count++;

  ⇑

9. Подсчет количества элементов в массиве из n вещественных чисел, которые меньше заданного значения k

Реализация с помощью цикла do…while

// подсчет количества элементов, которые меньше заданного k
int A[50]; // заданный массив A
int n; // текущая размерность массива n = 1..50
int k; // сравниваемое значение
int i; // дополнительная переменная
int count; // результат

// ввод A, n, k
// ...

// вычисление, реализация с помощью цикла while
count=0;
i=0;

do
{
    if (A[i]<k)
        count++;
    i++;
}
while (i<n);

  ⇑

10. Подсчет количества элементов в массиве из n вещественных чисел, значение которых находится в пределах диапазона [a .. b].

// подсчет количества элементов, которые лежат в заданном диапазоне
double M[50]; // заданный массив M
int n; // текущая размерность массива n = 1..50
double a, b; // сравниваемые значения
int i; // дополнительная переменная
int count; // результат

// ввод A, n, a, b
// ...

// вычисление, реализация с помощью цикла for
count=0;
for (i=0; i<n; i++)
    if ((M[i]>=a)&&(M[i]<=b))
        count++;

  ⇑

11. Подсчет количества парных элементов в массиве из n целых чисел

// подсчет количества парных элементов в массиве целых чисел
int A[10]; // заданный массив A
int n; // текущая размерность массива n = 1..10
int i; // дополнительная переменная
int count; // результат - количество парных элементов

// ввод A, n
// ...

// вычисление, реализация с помощью цикла for
count=0;
for (i=0; i<n; i++)
    if ((A[i]%2)==0)
        count++;

  ⇑

Связанные темы

• Одномерные массивы. Циклы for, while, do…while
• Массивы. Примеры решения распостраненных задач с одномерными массивами

  ⇑