Задачи на последовательности чисел

В программировании часто встречаются задачи на последовательности чисел. Числа в цикле вводятся по одному, обрабатываются (суммируются или еще что-нибудь), при этом количество вводимых чисел заранее неизвестно. Признаком окончания ввода последовательности, как правило, служит условное число. Например, если находится сумма целых положительных чисел, то таким признаком может быть число 0.
Попробуем составить алгоритм этой задачи.

Алгорит вычисления суммы целых чисел, 0 - признак окончания ввода.

1. Начальная установка: S=0 (в ячейке S будет накапливаться сумма).
2. Ввести целое число N.
3. Если N=0 то перейти на 6.
4. S=S+N.
5. Перейти на 2.
6. Вывод S на экран.
7. Конец.

В этом алгоритме циклический процесс начанается в шаге 2 и заканчивается в 5. Сразу отметим, что реализовать этот алгоритм можно несколькими способами. Запишем первый способ - с использованием оператора break. Поскольку выход из цикла нам будет обеспечен в теле цикла, можно смело брать бесконечный цикл. Полный листинг программы:

#include <stdio.h>
int main()
{
int S=0; // S - сумма, инициализирована нулем
int n; // n - очередное число
while(1) // бесконечный цикл
{
printf("Введите целое число\n");
scanf("%d", &n); // ввод числа
if(n==0) break; // здесь выход из цикла
S=S+n; // сумма накапливается
}
printf("Сумма равна %d\n", S);
return 0;
}

Попробуем реализовать этот алгоритм, используя введенное число как условие продолжения цикла. В этом примере самое первое число надо ввести до цикла (почему?), а уж в цикле все остальные.
Фрагмент кода:

int S=0; // S - сумма, инициализирована нулем
int n; // n - очередное число
printf("Введите целое число\n");
scanf("%d", &n); // ввод первого числа
while(n!=0) // цикл: пока n не равно 0
{
S=S+n; // сумма накапливается
printf("Введите целое число\n");
scanf("%d", &n); // ввод очередного числа
}
printf("Сумма равна %d\n", S);

Отличие от предыдущей реализации в теле цикла - сначала выполняется суммирование, а затем ввод следующего числа. Мало того, этот алгоритм можно записать еще с помощью цикла do - while. Попробуйте это сделать самостоятельно!
Отметим также, что второй вариант нашей реализации с профессиональной точки зрения является более предпочтительным, нежели первый, хотя выглядит не так очевидно. Дело в том, что в первом листинге в цикле сравнение выполняется два раза: проверяется условие заголовка цикла и в теле цикла есть условный оператор. Во второй реализации условие проверяется только один раз, в заголовке цикла. С точки зрения быстродействия алгоритма проверка условия является "дорогой" операцией. Говорят, что второй алгоритм является более оптимальным, чем первый. Надо стремиться составлять свои алгоритмы так, чтобы было "удобно" компьютеру, а не программисту!

Как посчитать среднее арифметическое

Теперь попробуем посчитать среднее арифметическое введенных чисел. Как вычисляется среднее арифметическое в математике, вы наверняка знаете: вычисляется сумма чисел и делится на их количество. В нашей постановке задачи имеется особенность: количество чисел заранее неизвестно, поэтому надо не только подсчитывать сумму чисел, но также их количество. Поэтому для подсчета числа элементов надо завести еще одну переменную - счетчик; пусть это будет переменная k. Каждый раз при вводе очередного числа значение счетчика увеличивается на единицу. Фрагмент кода, вычисляющий сумму и подсчитывающий количество чисел:

int S=0, k=0; // S - сумма, k - счетчик
int n; // n - очередное число
printf("Введите целое число\n");
scanf("%d", &n); // ввод первого числа
while(n!=0)
{
S=S+n; // сумма накапливается
k++; // счетчик увеличивается
printf("Введите целое число\n");
scanf("%d", &n);
}

Теперь, когда найдена сумма и количество элементов, наступил тонкий момент. Прежде чем делить сумму на количество, вспомним, как делятся целые числа (а по описанию int они у нас целые). Совершенно верно, дробная часть будет отброшена, и мы получим неверный результат. Надо как-то перейти к вещественным числам. Здесь есть различные приемы, например, умножить S на вещественное число 1.0, тогда промежуточный результат станет вещественным, и окончательный тоже вещественным:

printf("Среднее арифметическое равно %f\n", S*1.0/k);

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

float Sr;

Теперь можно записать присваивание и дальше вывести значение на экран:

Sr=S*1.0/k;
printf("Среднее арифметическое равно %f\n", Sr);

И профессиональный способ - с помощью операции приведения типа:

Sr=(float)S/k;
printf("Среднее арифметическое равно %f\n", Sr);

Записанное в скобках описание вещественного типа (float) на самом деле является операцией приведения типа и относится к тому выражению (переменной), перед которым стоит. Таким образом, значение S преобразуется к вещественному типу, и дальше вычисление идет без проблем.
Другой тонкий момент в этом алгоритме - если первое же введенное число оказалось нулем. В этом случае S=0 и k=0 и результат операции деления непредсказуем, поэтому надо принять меры выявления этого случая и выйти из программы, не выполняя деления.

Сочетание цикла и разветвления

В задачах такого рода, кроме ввода элементов, в цикле еще выполняются операции сравнения, и в зависимости от результата происходит продолжение алгоритма в том или ином направлении. Типичная такая задача - среди вводимых чисел найти максимальное.
Раньше мы составляли этот алгоритм для двух или, самое большее, трех чисел, сохраняя эти числа в отдельных ячейках. Если чисел достаточно много, алгоритм не годится, так как мы заранее не знаем, сколько чисел будет введено и, соответственно, сколько ячеек памяти понадобится. Но, оказывается, этот алгоритм можно реализовать, обойдясь всего двумя ячейками: одной для числа и еще одной - для хранения максимального элемента. Как только число введено в ячейку и обработано - оно уже больше не нужно, и в эту ячейку можно вводить следующее число.
В словесной формулировке этот алгоритм звучит так: ввести первое число, сделать его максимальным; ввести очередное число и если оно окажется больше максимального, то становится текущим максимальным, далее цикл повторить.
Пусть число 0 по-прежнему служит признаком окончания ввода. Выделим ячейку c именем Max для хранения максимального элемента. Алгоритм нахождения максимального элемента среди вводимых чисел следующий:

1. Ввести число в ячейку N.
2. Max=N;
3. Начало цикла. Если N=0 то перейти на 7.
4. Ввести число в ячейку N.
5. Если N>Max то Max=N.
6. Конец тела цикла. Перейти на 3.
7. Вывод Max на экран.

Фрагмент листинга с циклом while:

int N; // N - очередное число
int Max; // ячейка для максимального элемента
printf("Введите целое число\n");
scanf("%d",&N);
Max=N; // текущим максимальным становится первое введенное число
while(N!=0) // цикл: пока число не 0
{
printf("Введите целое число\n");
scanf("%d",&N);
if(N>Max) Max=N; // проверка условия:
// введенное число больше максимального,
// становится текущим максимальным
}
printf("Max= %d\n", Max);

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

int N=0;
int Max;
int k,i; // k - количество чисел, i - параметр цикла
printf("Введите количество чисел\n");
scanf("%d",&k);
printf("Введите целое число\n");
scanf("%d",&N);
Max=N; // текущим максимальным становится первое введенное число
for(i=1; i<k; i++) // цикл для остальных (k-1) чисел
{
printf("Введите целое число\n");
scanf("%d",&N);
if(N>Max) Max=N;
}
printf("Max= %d\n", Max);

 

 

Задания для самостоятельной работы к уроку 11

Задания на использование операторов цикла совместно с условным оператором

1. Вывести на экран все целые числа от 100 до 200, кратные семи.

2. Вывести на экран все целые числа от a до b, кратные c.

3. Известны данные о стоимости каждого товара из группы. Найти общую стоимость тех товаров, которые стоят дороже 1000 рублей (количество таких товаров заранее неизвестно).

4. Известны данные о температуре воздуха декады месяца. Определить, сколько раз температура опускалась ниже 0 градусов.

5. Составить программу поиска трехзначных чисел, которые при делении на 47 дают в остатке 43, а при делении на 43 дают в остатке 47.

6. Найти максимальное и минимальное числа из десяти случайных однозначных чисел.

7. Найти среднее арифметическое двадцати случайных чисел, разрядностью не выше трехзначных.

8. Написать программу, которая проверяет, является ли целое число, введенное пользователем, простым (простым называется натуральное число, большее 1, не имеющее других делителей, кроме единицы и самого себя).