Максимум числовой последовательности
Лекция 4-5. Последовательная обработка данных.
Последовательная обработка данных с указанным количеством элементов, с указанным признаком завершения последовательности, до конца файла. Последовательная обработка числовых последовательностей.
ПОСЛЕДОВАТЕЛЬНАЯ ОБРАБОТКА
В ряде задач применяется последовательная обработка данных, если:
1. необходимо вводить и обрабатывать последовательность элементов исходных данных в том порядке, в каком она размещена в файле на внешнем носителе;
2. каждый элемент последовательности используется не более одного раза.
Такие задачи называют (однопроходной) последовательной обработкой данных. В этом случае не требуется хранения сразу всех элементов. Достаточно иметь одну переменную, содержащую текущий (очередной) элемент входной последовательности.
В некоторых случаях используются несколько текущих элементов (например, два-три соседних).
Элементами данных последовательности могут быть:
- числа;
- символы, строки;
- записи файла и др.
Последовательность исходных данных может задаваться:
1. с указанием количества элементов;
2. с признаком конца последовательности;
3. обрабатываться до конца входного файла.
1. Входная последовательность задается с указанием количества элементов n ≥ 0 в следующем порядке:
n, X1, X2, ... , Xn
Алгоритм 1. Последовательная обработка заданного количества элементов.
|
|
|
Ввод n;
for (j=1; j<=n; j++)
{ Ввод X;
Обработка X;
}
2. Входная последовательность задается с признаком конца:
X1, X2, ... , Xn, W
где n - неизвестное заранее количество элементов (n >= 0),
W -признак конца последовательности (известное заранее значение, отличающееся от элементов последовательности).
Алгоритм 2. Последовательная обработка элементов с признаком конца W.
Ввод X;
while (X != W)
{ Обработка X;
Ввод X;
}
При количестве повторений n > 1 возможно использование цикла с постусловием.
Ввод X;
do
{ Обработка X;
Ввод X;
} while (X != W);
3. Входная последовательность X1, X2, ... , Xn продолжается до конца входного файла, n - неизвестное заранее количество элементов (n >=0), признак конца отсутствует.
Алгоритм 3. Последовательная обработка элементов до конца файла.
Ввод X;
while (не конец входного файла)
{ Обработка X;
Ввод X;
}
Конец файла при вводе с клавиатуры задается комбинацией клавиш Ctrl-Z и Enter.
В программе на языке С++ конец входного файла можно обнаружить после попытки ввода данных за пределами файла.
Например, значением функции cin является количество фактически введенных элементов. Если не удалось ввести ни одного элемента, значение функции равно -1.
|
|
|
Иногда в языке C можно обойтись одной операцией ввода X, поместив ее внутри условия цикла.
while (ввод X и X != W)
Обработка X;
или
while (ввод X и не конец входного файла)
Обработка X;
Сумма числовой последовательности
Задача 3. «Сумма и среднее арифметическое числовой последовательности».
Определить сумму и среднее арифметическое значение элементов заданной числовой последовательности.
Рассмотрим все три варианта задания последовательности.
а) Входная последовательность задается с указанием количества элементов n ≥ 0 в следующем порядке:
n X1 X2 ... Xn
Тест. Вход: 4 2 3.5 1.5 5
Выход: Сумма = 12.00
Среднее арифметическое = 3.00
Используем алгоритм 1. для определения суммы элементов числовой последовательности. Используем следующие переменные:
x – текущий элемент последовательности,
s – текущее значение суммы элементов.
До начала цикла по вводу и обработке элементов величину s обнуляем. На каждом шаге цикла вводим одно очередное число и его значение добавляем к величине s.
Схема алгоритма задачи 3. «Сумма и среднее арифметическое значение числовой последовательности» представлена на рис. 4.2.
|
|
|
Рис.4.2. Схема алгоритма задачи «Сумма и среднее арифметическое значение числовой последовательности»
В табл. 4.1. представлена трассировочная таблица исполнения алгоритма задачи «Сумма и среднее арифметическое значение числовой последовательности».
Табл.3.1. Трассировочная таблица исполнения алгоритма задачи 4.1.
| n | 4 | |||||||||||||||||||
| s | 0 | 2 | 5.5 | 7 | 12 | |||||||||||||||
| i | 1 | 2 | 3 | 4 | 5 | |||||||||||||||
| x | 2 | 3.5 | 1.5 | 5 | ||||||||||||||||
| i<=n | + | + | + | + | - | |||||||||||||||
| вывод | Сумма= 12.00 Среднее= 3.00 |
/* Программа 3а. Сумма и среднее арифметическое значение */
|
|
|
/* числовой последовательности. Задано количество чисел n>=0. */
#include <iostream>
void main(void)
{ int n; /* Количество чисел */
float x, /* Текущее число */
sum=0; /* Текущая сумма */
int i; /* Номер текущего числа */
cin>>n;
if (n>0) {
for ( i = 1; i <=n; i++){
cin>>x; /* Ввод текущего числа */
sum = sum + x;
}
cout<< "\nСумма = \n "<< sum;
cout<<"Среднее арифметическое =\n "<< sum;
}
else puts(“Последовательность элементов пустая”);
}
б) Входная последовательность задается с признаком конца в следующем порядке:
X1 X2 ... Xn W
где n – количество элементов (n >= 0), заранее неизвестно.
W известное заранее значение, отличающееся от элементов последовательности.
Тест. Вход: 2 3.5 1.5 5 9999
Выход: Сумма = 12.00
Среднее арифметическое = 3.00
Используем алгоритм 2. для определения суммы элементов числовой последовательности. Признак конца последовательности обозначим именованной константой W. Для вычисления среднего арифметического значения последовательности необходимо подсчитать не только сумму, как в программе 3.1а, но и количество элементов.
/* Программа 3б. Сумма и среднее арифметическое значение */
/* числовой последовательности. Задан признак конца W = 9999 */
#include <iostream>
#define W 9999
void main(void)
{ float x, /* Текущее число */
sum = 0; /* Текущая сумма */
int k = 0; /* Количество чисел */
cin>>x;
while (x != W)
{ sum = sum + x;
k++;
cin>>x;
}
if (k>0)
{cout<<"\nСумма =\n"<< sum;
cout<<"Среднее арифметическое = \n "<< sum;
}
else puts(“Последовательность элементов пустая”);
}
в) Входная последовательность X1, X2, ... , Xn продолжается до конца входного файла, n - количество элементов (n >= 0), заранее неизвестно, признак конца последовательности не задан.
Тест. Вход: 2 3.5 1.5 5 <Ctrl-z> <Enter>
Выход: Сумма = 12.00
Среднее арифметическое = 3.00
Используем алгоритм 3. для определения суммы элементов числовой последовательности. Конец файла определим по результату работы функции scanf(). Для вычисления среднего арифметического значения последовательности подсчитаем сумму и количество элементов, как в программе 3б.
/* Программа 3в. Сумма и среднее арифметическое значение */
/* числовой последовательности, продолжающейся до конца файла */
#include <iostream>
void main(void)
{ float x, /* Текущее число */
sum; /* Текущая сумма */
int k = 0; /* Количество чисел */
sum = 0;
while ((cin>>x) >0) /* ввод чисел до конца файла */
{ sum = sum + x; k++; }
if (k>0)
{cout<<"\nСумма = \n"<< sum);
cout<<"Среднее арифметическое = \n "<< sum;
}
else puts(“Последовательность элементов пустая”);
}
Максимум числовой последовательности
Задача 4. «Максимум числовой последовательности».
Последовательность вещественных чисел продолжается до конца файла. Составить программу нахождения максимального члена последовательности.
Тест. Вход: -5 3.1 2
Выход: Максимум = 3.100000
Используем алгоритм 3. для обработки последовательности. Используем следующие переменные:
x – текущий элемент последовательности,
max – максимум просмотренной части последовательности.
Для нахождения максимума используем следующий метод. Начальное значение max равно первому члену последовательности. На каждом шаге цикла вводим одно очередное число и если очередное число оказывается больше max, оно заменяет максимум.
/* Программа 4. Определение максимального элемента */
/* числовой последовательности */
#include <iostream>
void main(void)
{ float x, max; /* Текущее число, текущий максимум */
int k; /* Количество введенных чисел */
k = cin>>max; /* 1-е число */
if (k < 1) cout<<"\nВходная последовательность пуста";
else
{ while ((k = cin>>x) > 0)
if (x > max) max = x;
cout<<"\nМаксимум=\n"<< max;
}
}
Задача 5. Задана непустая последовательность целых чисел. Определить количество чисел, принимающих наибольшее значение.
Тест. Вход: 5 3 5 2 7 5 7 4 7 5 4 Ctrl+Z
Выход: max=7, k= 3
Пошаговая прокрутка алгоритма на упрощенной трассировочной таблице.
/* Программа 5. Количество наибольших чисел */
#include <iostream>
void main(void)
{ int x, /* текущее число */
max; /* текущий максимум */
int k; /* количество наибольших чисел */
cin>>max ;
k=1;
while( (cin>>x)>0)
{ if (x == max) k++;
else if (x>max) {max=x; k=1;}
}
cout<<”\n max=”<<” k= “<<max<< k;
}
Схема работы.
Задача 6. Задана непустая числовая последовательность. Определить, является ли последовательность знакочередующейся.
Тест_1. Вход: -5 3.1 -2 1 -7
Выход: Знаки чередуются.
Тест_2. Вход: -5 3.1 -2 -1 7
Выход: Знаки не чередуются.
Используем алгоритм 3 для обработки последовательности. Но одного текущего элемента последовательности недостаточно, будем сохранять два соседних текущих элемента:
xpred – предыдущий элемент последовательности,
x – текущий элемент последовательности.
При обработке последовательности необходимо искать нарушение чередования знаков (например, по значению произведения двух соседних элементов). Используем дополнительную переменную flag:
flag = 1 – последовательность знакочередующаяся, 0 – нет, инициализация: flag =1.
/* Программа 6. Знакочередование последовательности чисел */
#include <iostream>
void main(void)
{ float xpred, x; /* предыдущее и текущее числа */
int flag = 1; /* признак знакочередования */
/* flag=1- знаки чередуются, 0 – нет */
cin>>xpred ;
while( (cin>>x)>0)
{ if (xpred * x >= 0) flag = 0;
xpred = x;
}
if (flag) cout<<"\n Знаки чередуются.";
else cout<<"\n Знаки не чередуются.";
}
Схема работы и трассировочная таблица.
Задача 7. Последовательность неотрицательных вещественных чисел заканчивается числом -1.
Составить программу нахождения ближайшего к началу последовательности локального максимума, т. е. номера и значения ближайшего к началу члена последовательности, значение которого больше обоих его соседей.
Тест. Вход: 4 5 8 10 15 8 25 11 -1
Выход: 1-й локальный максимум =15, 5 -е число
Тест. Вход: 4 5 8 10 15 25 -1
Выход: Локальный максимум отсутствует
Очередное число должно сравниваться с двумя соседями. Поэтому требуется хранить три текущих числа. Пока не обнаружен максимум (признак р равен 1), среднее из трех чисел x запоминается в качестве кандидата на максимум, и увеличивается номер числа j, для которого р служит шагом. При обнаружении первого локального максимума признак р получает значение 0, и поэтому найденные значения max и j больше не изменяются до конца входной последовательности.
/* Программа 7. Нахождение 1-го локального максимума чисел */
#include <iostream>
#define W -1 /* Признак конца чисел */
int main (void)
{ float x, xpr, xsl, /* Текущее, предыдущее и следующее число */
max; /* 1-й локальный максимум (значение x) */
int j=1, /* Номер локального максимума */
k, /* Количество введенных чисел */
p=1; /* 0 - есть локальный максимум, 1 - нет */
if ((k= cin>>xpr>> x>> xsl) < 3) xsl = W; /* < 2 чисел */
while ( xsl != W && p)
{ max = x; j++; /* Запоминание x */
if (x > xpr && x > xsl) /* Нашли локальный максимум */
p = 0; /* Прекратить запоминание x и его номера */
else {xpr = x; x = xsl; cin>>xsl;}
}
if (p)
cout<<"\nЛокальный максимум отсутствует ";
else cout<<"\n1-й локальный максимум=”<<\n число="<< max<< j;
return 0;
}
/*Программа 7а. Нахождение 1-го локального максимума чисел */
#include <iostream>
#define W -1 /* Признак конца чисел */
int main (void)
{ float x, xpr, xsl, /* Текущее, предыдущее и следующее число */
max; /* 1-й локальный максимум (значение x) */
int j=1, /* Номер локального максимума */
k, /* Количество введенных чисел */
p=1; /* 0 - есть локальный максимум, 1 - нет */
(k = cin>>"xpr>> x>> xsl);
if (k < 3) xsl = W; /* < 2 чисел */
for (j=2; xsl != W; j=j+p)
{ if (p==1) max = x; /* Запоминание x */
if (x > xpr && x > xsl) /* Нашли локальный максимум */
p = 0; /* Прекратить запоминание x */
xpr = x; x = xsl;
cin>>xsl;
}
if (p)
cout<<"\nЛокальный максимум отсутствует ";
else cout<<"\n1-й локальный максимум=”<<\n число="<< max<<j;
return 0;
}
Задача 5. Задана непустая последовательность целых чисел. Определить количество чисел, принимающих наибольшее значение.
Тест. Вход: 5 3 5 2 7 5 7 4 7 5 4 Ctrl+Z
Выход: max=7, k= 3
/* Программа 5. Количество наибольших чисел */
#include <iostream>
void main(void)
{ int x, /* текущее число */
max; /* текущий максимум */
int k; /* количество наибольших чисел */
cin>>max ; k=1;
while( (cin>>x)>0)
{ if (x == max) k++;
else if (x>max) {max=x; k=1;}
}
cout<<"\n max=<< k= “<<max<< k;
}
Задача 6. Задана непустая числовая последовательность. Определить, является ли последовательность знакочередующейся.
Тест_1. Вход: -5 3.1 -2 1 -7
Выход: Знаки чередуются.
Тест_2. Вход: -5 3.1 -2 -1 7
Выход: Знаки не чередуются.
Используем алгоритм 3 для обработки последовательности. Но одного текущего элемента последовательности недостаточно, будем сохранять два соседних текущих элемента:
xpred – предыдущий элемент последовательности,
x – текущий элемент последовательности.
При обработке последовательности необходимо искать нарушение чередования знаков (например, по значению произведения двух соседних элементов). Используем дополнительную переменную flag:
flag = 1 – последовательность знакочередующаяся, 0 – нет, инициализация: flag =1.
/* Программа 6. Знакочередование последовательности чисел */
#include <iostream>
void main(void)
{ float xpred, x; /* предыдущее и текущее числа */
int flag = 1; /* признак знакочередования */
/* flag=1- знаки чередуются, 0 – нет */
cin>>xpred ;
while( (cin>>x)>0)
{ if (xpred * x >= 0) flag = 0;
xpred = x;
}
if (flag) cout<<"\n Знаки чередуются.";
else cout<<"\n Знаки не чередуются.";
}
Задача 7. Последовательность неотрицательных вещественных чисел заканчивается числом -1.
Составить программу нахождения ближайшего к началу последовательности локального максимума, т. е. номера и значения ближайшего к началу члена последовательности, значение которого больше обоих его соседей.
Тест. Вход: 4 5 8 10 15 8 25 11 -1
Выход: 1-й локальный максимум =15, 5 -е число
Тест. Вход: 4 5 8 10 15 25 -1
Выход: Локальный максимум отсутствует
Очередное число должно сравниваться с двумя соседями. Поэтому требуется хранить три текущих числа. Пока не обнаружен максимум (признак р равен 1), среднее из трех чисел x запоминается в качестве кандидата на максимум, и увеличивается номер числа j, для которого р служит шагом. При обнаружении первого локального максимума признак р получает значение 0, и поэтому найденные значения max и j больше не изменяются до конца входной последовательности.
/* Программа 7. Нахождение 1-го локального максимума чисел */
#include <iostream>
#define W -1 /* Признак конца чисел */
int main (void)
{ float x, xpr, xsl, /* Текущее, предыдущее и следующее число */
max; /* 1-й локальный максимум (значение x) */
int j=1, /* Номер локального максимума */
k, /* Количество введенных чисел */
p=1; /* 0 - есть локальный максимум, 1 - нет */
if ((k= cin>>" xpr>> x>> xsl) < 3) xsl = W; /* < 2 чисел */
while ( xsl != W && p)
{ max = x; j++; /* Запоминание x */
if (x > xpr && x > xsl) /* Нашли локальный максимум */
p = 0; /* Прекратить запоминание x и его номера */
else {xpr = x; x = xsl; cin>>xsl;}
}
if (p)
cout<<"\nЛокальный максимум отсутствует ";
else cout<<"\n1-й локальный максимум число="<< max<< j;
return 0;
}
/*Программа 7а. Нахождение 1-го локального максимума чисел */
#include <iostream>
#define W -1 /* Признак конца чисел */
int main (void)
{ float x, xpr, xsl, /* Текущее, предыдущее и следующее число */
max; /* 1-й локальный максимум (значение x) */
int j=1, /* Номер локального максимума */
k, /* Количество введенных чисел */
p=1; /* 0 - есть локальный максимум, 1 - нет */
k = cin>>"xpr>>x>> xsl;
if (k < 3) xsl = W; /* < 2 чисел */
for (j=2; xsl != W; j=j+p)
{ if (p==1) max = x; /* Запоминание x */
if (x > xpr && x > xsl) /* Нашли локальный максимум */
p = 0; /* Прекратить запоминание x */
xpr = x; x = xsl;
cin>>xsl;
}
if (p)
cout<<"\nЛокальный максимум отсутствует ";
else cout<<"\n1-й локальный максимум=”<<”\n число="<< max<<j;
return 0;
}
Дата добавления: 2018-09-22; просмотров: 303; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!