Тема 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-ее по величине значение, т.е. если их упорядочить по возрастанию, то ответ – третье значение с конца. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.

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

6 9 2 4 0 7 3

Результат:

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

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

6 9 2 4 0 7 3

Результат:

НЕТ

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

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

-1 1 3 5 7

Результат:

ДА

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

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

32 16 8 3 2

Результат:

НЕТ

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

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

Результат:

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

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

6 9 2 4 0 7 3

Результат:

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

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

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

1 5 1 2 3

Результат:

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

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

1 5 1 2 3

Результат:

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

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

Результат:

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

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

Результат:

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

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

1 5 1 2 -3

Результат:

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

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

1 5 14 2 3

Результат:

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

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

2 5 1 2 3 7 3 1 2

Результат:

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

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

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

Результат:

13 5 1

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

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

2 5 1 2 3 7 3 2 2

Результат:

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

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

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

Результат:

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

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.

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

Результат:

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

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

Результат:

1 10 2 2 2 2 2 2 1 1

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

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

Результат:

Тема 1.3. Массивы

Цель.

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

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

Массив – упорядоченное множество однотипных элементов, занимающих смежные участки оперативной памяти. Они используются в тех случаях, когда элементы последовательности должны обрабатываться не в том порядке, в котором поступают в программу, или каждый элемент должен обрабатываться (просматриваться) несколько раз. Имя массива ассоциируется с адресом начала массива (первого элемента). Этот адрес является постоянным. Основная операция над массивами – операция доступа к элементу []. Можно использовать значение элемента и можно его изменять. Используя адреса можно обращаться к элементам массива с помощью операции * и операции адресной арифметики.

Ввод и вывод массивов осуществляется поэлементно (для символьных строк – см. ниже).

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

Массив, индекс, элемент, счётчик, адрес, указатель, NULL, случайное число.

ПРИМЕР 1.

Дан массив целых чисел из N элементов. Для заданных номеров k1 и k2 (1 < = k1 < = k2 < = N) переставить элементы массива от k1-го до k2-го в обратном порядке.

Алгоритм.

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

Решение.

// C++

# include < iostream>

# include < cstdlib>

using namespace std;

const int N = 10000;

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

{

setlocale (LC_ALL, " RUS" );

cout < < " Переворот части массива." < < endl;

cout < < " Введите количество, а в следующей строке числа." < < endl;

int a [N], n;

cin > > n;

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

cin > > a [i];

cout < < " С какой позицию по какую: ";

int k1, k2;

cin > > k1 > > k2;

k1--, k2--;

for ( int i=k1, j=k2; i < j; i++, j-- )

swap (a [i], a [j]);

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

cout < < a [i] < < " ";

cout < < endl;

system (" PAUSE" );

return 0;

}

// C#

using System;

class Program

{

static void Main (string [] args)

{

Console.WriteLine (" Переворот части массива." );

Console.WriteLine (" Введите количество, а в следующей строке числа." );

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

int [] a = new int [n];

string ss = Console.ReadLine (); // все числа в одной строке

string [] s = ss.Split (' '); //| через один пробел

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

a [i] = int.Parse (s [i]);

Console.WriteLine (" С какой позицию по какую: " );

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

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

k1--, k2--;

for ( int i=k1, j=k2; i < j; i++, j-- )

{

int temp = a [i];

a [i] = a [j];

a [j] = temp;

}

for ( int i=0; i < n; i++ ) // печатаем числа в одну строку

Console.Write (a [i] + " " );

Console.ReadKey ();

}

ПРИМЕР 2.

Заполнить массив случайными целыми числами в диапазоне от 0 до 999 и распечатать его.

Решение.

// C++

# include < iostream>

# include < cstdlib>

using namespace std;

const int N = 1000;

int main ()

{

setlocale (LC_ALL, " RUS" );

cout < < " Заполнение массива случайными числами." < < endl;

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

int * a, n;

cin > > n;

a = new int [n];

srand (time (0));

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

a [i] = rand () % N;

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

cout < < a [i] < < " ";

cout < < endl;

system (" PAUSE" );

return 0;

}

// C#

using System;

class Program

{

static void Main (string [] args)

{

Console.WriteLine (" Заполнение массива случайными числами." );

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

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

int [] a = new int [n];

// заполнение случайными числами

Random rnd = new Random(DateTime.Now.Millisecond);

//создание генератора случайных чисел и инициализация текущим временем

for ( int i=0; i < a.GetLength (0); i++ )

a [i] = rnd.Next ();

// GetLength(i) возращает длину массива по i-му измерению

for ( int i=0; i < n; i++ ) // печатаем числа в одну строку

Console.Write (a [i] + " " );

Console.ReadKey ();

}

⇐ Предыдущая 123 Следующая ⇒