Цель.
Умение обрабатывать большие последовательности данных (значений) по одному без одновременного их хранения в памяти.
Основные понятия.
Многократное использование переменных. Однократная обработка данных.
Ключевые слова.
Последовательность, цикл.
ПРИМЕР 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 целых чисел найти самую длинную строго возрастающую цепочку, т.е. такую цепочку элементов, что Ai < Ai+1 < Ai+2 и т.д. Напечатать длину этой цепочки. В первой строке задаётся количество чисел в последовательности, а во второй - сами числа.
Исходные данные:
1 5 1 2 3
Результат:
1.2.2.2. в последовательности из n целых чисел найти самую длинную пилу, т.е. такую цепочку элементов, что Ai < Ai+1 > Ai+2 и т.д. или Ai > Ai+1 < Ai+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. Обобщение ряда Фибоначчи. Дана бесконечная в обе стороны последовательность вещественных чисел, которая строится по правилу ai=ai-1+ ai-2. Заданы значения двух произвольных членов этой последовательности ai и aj. Написать программу, которая по заданному числу n вычисляет элемент an. В первой строке задаются номер i и значение ai, во второй номер j и значение aj, в третьей – номер n.
Исходные данные:
Результат:
1.2.3.2. В последовательности цифр a1, a2,...ai,... каждый член, начиная с четвертого, равен последней цифре суммы трех предыдущих. Написать программу, которая по заданным значениям a1, a2, a3 вычисляет an, где 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 остановок. На каждой остановке из автобуса сначала выходят ai человек, потом входят bi человек. Изначально автобус пустой. Определить и напечатать минимальную возможную вместимость автобуса.
Исходные данные:
Результат:
Тема 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 ();
}
}