Тема 1.2. Последовательности

Цель.

Умение обрабатывать большие последовательности данных (значений) по одному без одновременного их хранения в памяти.

Основные понятия.

Многократное использование переменных. Однократная обработка данных.

Ключевые слова.

Последовательность, цикл.

ПРИМЕР 1.

Дана последовательность целых чисел. Найти самое большое, самое маленькое число и сумму всех чисел. В начале последовательности задаётся количество чисел в ней.

Алгоритм.

Будем вводить по одному числу и сравнивать его с эталонами - наибольшим и наименьшим. Сначала в качестве обоих эталонов возьмём первое число. Все числа хранить в памяти не будем, каждое новое будет помещаться в ту же ячейку, где хранилось предыдущее.

Решение.

// C++

# include <iostream>

# include <cstdlib>

using namespace std;

int main () // основная часть программы – главная функция

{

setlocale (LC_ALL, "RUS");

cout << "Вычисление МАХ, MIN, SUM" << endl;

cout << "Введите количество и сами числа " << endl;

int a, n, max, min, sum;

cin >> n;

cin >> max;

min = max;

sum = max;

for ( int i=1; i < n; i++ )

{

cin >> a;

if ( max < a ) max = a;

if ( min > a ) min = a;

sum += a;

}

cout << "MAX = " << max << " MIN = " << min << " SUM = " << sum << endl;

system ("PAUSE");

return 0;

}

// C#

using System;

class Program

{

static void Main (string [] args)

{

Console.WriteLine ("Вычисление МАХ, MIN, SUM");

Console.WriteLine ("Введите количество и сами числа по 1 в строке");

int a, n, max, min, sum;

n = int.Parse (Console.ReadLine ());

max = int.Parse (Console.ReadLine ());

min = max;

sum = max;

for ( int i=1; i < n; i++ )

{

a = int.Parse (Console.ReadLine ());

if ( max < a ) max = a;

if ( min > a ) min = a;

sum += a;

}

Console.WriteLine ("MAX = " + max + " MIN = " + min + " SUM = " + sum);

Console.ReadKey ();

}

}

ПРИМЕР 2

Та же самая задача, но программа должна проработать на серии тестов и для каждого выдать свой ответ.

// C++

# include <iostream>

# include <cstdlib>

using namespace std;

int main () // основная часть программы – главная функция

{

setlocale (LC_ALL, "RUS");

cout << "Вычисление МАХ, MIN, SUM" << endl;

cout << "Введите количество тестов" << endl;

int t;

cin >> t;

for ( int tt=0; tt < t; tt+ )

{

cout << "Введите количество и сами числа" << endl;

int a, n, max, min, sum;

cin >> n;

cin >> max;

min = max; sum = max;

for ( int i=1; i < n; i++ )

{

cin >> a;

if ( max < a ) max = a;

if ( min > a ) min = a;

sum += a;

}

cout << "MAX = " << max << " MIN = " << min << " SUM = " << sum << endl;

}

system ("PAUSE");

return 0;

}

// C#

using System;

class Program

{

static void Main (string [] args)

{

Console.WriteLine ("Вычисление МАХ, MIN, SUM");

Console.WriteLine ("Введите количество тестов");

int t = int.Parse (Console.ReadLine ());

for ( int tt=0; tt < t; tt+ )

{

Console.WriteLine ("Введите количество и сами числа по 1 в строке");

int a, n, max, min, sum;

n = int.Parse (Console.ReadLine ());

max = int.Parse (Console.ReadLine ());

min = max;

sum = max;

for ( int i=1; i < n; i++ )

{

a = int.Parse (Console.ReadLine ());

if ( max < a ) max = a;

if ( min > a ) min = a;

sum += a;

}

Console.WriteLine ("MAX = " + max + " MIN = " + min + " SUM = " + sum);

}

Console.ReadKey ();

}

}

Задачи для обязательного решения.

1.2.1.1. в последовательности из nцелых чисел найти 3-ее по величине значение, т.е. если их упорядочить по возрастанию, то ответ – третье значение с конца. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

Исходные данные:

7

6 9 2 4 0 7 3

Результат:

6

1.2.1.2. для последовательности из nцелых чисел напечатать «ДА», если числа расположены в порядке не убывания или не возрастания (монотонная). В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

Исходные данные:

6 9 2 4 0 7 3

Результат:

НЕТ

1.2.1.3. для последовательности из nцелых чисел напечатать «ДА», если числа образуют арифметическую прогрессию в порядке их следования и «НЕТ» в противном случае. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

Исходные данные:

5

-1 1 3 5 7

Результат:

ДА

1.2.1.4. для последовательности из nцелых чисел напечатать «ДА», если числа образуют геометрическую прогрессию и «НЕТ» в противном случае. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

Исходные данные:

5

32 16 8 3 2

Результат:

НЕТ

1.2.1.5. для заданного числа n найти и напечатать число Фибоначчи с этим номером. Ч

Исходные данные:

5

Результат:

5

1.2.1.6. ПОИСК ВСЕХ ПИКОВ. В последовательности целых чисел найти номера и значения всех элементов, которые строго больше предыдущего и последующего элементов. Первое и последнее число не учитываются, т.к. у них только по одному соседу. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

Исходные данные:

7

6 9 2 4 0 7 3

Результат:

3

Задачи для самостоятельного решения.

1.2.2.1. в последовательности из nцелых чисел найти самую длинную строго возрастающую цепочку, т.е. такую цепочку элементов, что A_i< A_i+1< A_i+2и т.д. Напечатать длину этой цепочки. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

Исходные данные:

5

1 5 1 2 3

Результат:

3

1.2.2.2. в последовательности из nцелых чисел найти самую длинную пилу, т.е. такую цепочку элементов, что A_i< A_i+1> A_i+2и т.д. или A_i> A_i+1< A_i+2…В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

Исходные данные:

5

1 5 1 2 3

Результат:

4

1.2.2.3. для заданного числа nнайти ближайшее сверху число Фибоначчи (большее или равное)

Исходные данные:

51

Результат:

55

1.2.2.4. для заданного числа nнайти ближайшее снизу число Фибоначчи (меньшее или равное)

Исходные данные:

51

Результат:

34

1.2.2.5. в последовательности из nцелых чисел найти пару с самым большим произведением и напечатать его. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

Исходные данные:

5

1 5 1 2 -3

Результат:

10

1.2.2.6. в последовательности из nцелых чисел найти пару с самым большим произведением, которое делится на 21, и напечатать его. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

Исходные данные:

5

1 5 14 2 3

Результат:

42

1.2.2.7. в последовательности из nцелых чисел найти пару с самым большим (маленьким) произведением, но их номера в последовательности должны отличаться не менее, чем на 5. и напечатать его. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

Исходные данные:

9

2 5 1 2 3 7 3 1 2

Результат:

15

1.2.2.8. в последовательности из nцелых чисел найти пару с самым большим (маленьким) чётным произведением, но их номера в последовательности должны отличаться не менее, чем на 5, и напечатать это произведение. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

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

Исходные данные:

19

Результат:

13 5 1

1.2.2.10. В последовательности из nцелых чисел найти наибольший перепад – наибольшую разность элементов в цепочке возрастающих или убывающих элементов. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

Исходные данные:

9

2 5 1 2 3 7 3 2 2

Результат:

6

1.2.2.11. Требуется найти самую длинную непрерывную цепочку нулей в последовательности нулей и единиц. В единственной строке записана последовательность нулей и единиц (без пробелов). Суммарное количество цифр не превышает 1000.

Вывести искомую длину цепочки нулей.

Исходные данные:

00101110000110

Результат:

4

Продвинутые задачки.

1.2.3.1. Обобщение ряда Фибоначчи. Дана бесконечная в обе стороны последовательность вещественных чисел, которая строится по правилу a_i=a_i-1+ a_i-2. Заданы значения двух произвольных членов этой последовательности a_i и a_j. Написать программу, которая по заданному числу n вычисляет элемент a_n. В первой строке задаются номер i и значение a_i, во второй номер j и значение a_j, в третьей – номер n.

Исходные данные:

Результат:

1.2.3.2. В последовательности цифр a1, a2,...ai,... каждый член, начиная с четвертого, равен последней цифре суммы трех предыдущих. Написать программу, которая по заданным значениям a₁, a₂, a₃ вычисляет a_n, где n<=1000000000.

Исходные данные:

Результат:

1.2.3.3. Общее количество цифр. Для заданного натурального числа n вычислить и напечатать общее количество цифр во всех числах от 1 до n.

Исходные данные:

147

Результат:

333

1.2.3.4. Количество цифр. Для заданного натурального числа n вычислить и напечатать количество каждой цифры во всех числах от 1 до n: количество ноликов, единичек и т.д. до девяти.

Исходные данные:

17

Результат:

1 10 2 2 2 2 2 2 1 1

1.2.3.5. Минимальная вместимость автобуса. На автобусном маршруте имеется nостановок. На каждой остановке из автобуса сначала выходятa_iчеловек, потом входятb_iчеловек. Изначально автобус пустой. Определить и напечатать минимальную возможную вместимость автобуса.

Исходные данные:

Результат: