Для каждой задачи подготовить полусекретный набор тестовых данных – не для печати – для проверки решений детей

Стр 1 из 3Следующая ⇒

Дополнение для части 2 – обработка исключений

ОГЛАВЛЕНИЕ

Часть 1. Основы программирования и информатика

1.0. Разминка – введение в алгоритмы – элементарные алгоритмы

1.1. Геометрия

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

1.3. Массивы

1.4. Сортировки

1.5. Символьные строки (тексты)

1.6. Матрицы

1.7. Функции и рекурсия

1.8. Автоматы

1.9. Дополнительные задачи

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

Тема 1.0. Элементарные алгоритмы

Цель.

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

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

Решение задачи состоит в описании объектов и указания действий над ними с целью получения нужного результата.

Основной метод решения сложных задач - разбиение задачи на подзадачи - декомпозиция

Существует 3 механизма декомпозиции:

- линейная последовательность – задача разбивается на последовательность шагов (подзадач), которые выполняются друг за другом;

- ветвление по условию – задача разбивается на 2 или несколько параллельных подзадач и в зависимости от некоторого условия будет выполняться только одна из подзадач;

- многократное повторение – задача разбивается на последовательность одинаковых (подобных) подзадач. Эта подзадача будет выполняться несколько раз.

Эти 3 механизма используются при декомпозиции многократно до тех пор, пока задача не сведётся к очевидным (элементарным) действиям.

В каждой задаче (подзадаче) нужно уметь выделять объекты, над которыми будут выполняться действия.

Объекты характеризуются своим типом и в каждый момент времени имеют некоторое значение, которое хранится в оперативной памяти.

Действия задаются операторами и состоят в выполнении некоторых допустимых операций над объектами.

Структура простой программы:

подключения стандартных библиотек (#include)

определение главной функции (main). Внутри неё описываются объекты и операторы.

Ввод данных и печать результатов.

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

Переменная, константа, Описание. Оператор. Программа. Оператор препроцессора #include.

ПРИМЕР.

Дано натуральное число. Напечатать все его делители в порядке возрастания.

Алгоритм.

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

Решение.

// C++

# include < iostream> // используется для подключения некоторых стандартных

# include < conio.h> // возможностей для ввода-вывода информации

using namespace std; // для использования некоторых стандартных имён

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

{

setlocale (LC_ALL, " RUS" );

cout < < " Вычисление делителей числа = ";

int n;

cin > > n;

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

if ( n%i == 0 )

cout < < i < < " ";

getch (); // задержка – смотреть результаты на экране

return 0;

}

// C#

using System;

class Program

{

static void Main (string [] args) // Main - обязательное имя

{

Console.Write (" Вычисление делителей числа = " );

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

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

if ( n%i == 0 )

Console.Write (" " + i);

Console.ReadKey ();

}

Дополнительные замечания.

Простой анализ программы показывает возможности ускорения в 2 раза. Во-первых, на числа 1 и n можно не делить, а из остальных проверять только числа от 2 до n/2.

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

1.0.3.1. Обобщённый алгоритм Эвклида.

Для заданных натуральных чисел A и B найти пару целых чисел P и Q таких, что

A*P + B*Q = 1

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

2 3

Результат:

2 -1

1.0.3.2. Даны коэффициенты линейного уравнения Ax + By + C = 0 (A, B, C) и пределы изменения переменных X1 < = x < = X2 и Y1 < = y < = Y2. Сколько целочисленных решений (пар x и y) существует в указанных пределах.

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

3 5

Результат:

3 7

4 2

5 5

1.0.3.3. Вырубка деревьев. Король решил вырубить некоторые деревья, растущие перед его дворцом. Деревья перед дворцом короля посажены в ряд, всего там растет n деревьев, расстояния между соседними деревьями одинаковы. После вырубки перед дворцом должно остаться m деревьев, и расстояния между соседними деревьями должны быть одинаковыми. Написать программу, которая по заданным числам n и m определит, сколько существует способов вырубки некоторых из n деревьев так, чтобы после вырубки осталось m деревьев и соседние деревья находились на равном расстоянии друг от друга.

Входные данные содержат два целых числа n и m (0 ≤ m, n ≤ 1000). В единственную строку вывести одно целое число — искомое число способов.

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

5 3

Результат:

Примечание:

Если обозначить условно исходное расположение деревьев перед дворцом как «TTTTT», то возможные результаты после вырубки следующие:
«TTT..», «.TTT.», «..TTT», «T.T.T».

1.0.3.4. Сумма произведений. Требуется вычислить сумму произведений цифр каждого N-значного числа. При этом следует учесть, что если в числе встречается цифра 0, то произведение его цифр равно нулю. Для N=3 искомая сумма представлена следующим рядом: S = 1*0*0 + 1*0*1 + 1*0*2 + … + 9*9*8 + 9*9*9 = 91125 В единственной строке записано натуральное число N (N < 1000).

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

Результат:

1.0.3.5. Произведение цифр. Требуется найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N (0 ≤ N ≤ 10⁹). Вывести искомое число Q. В том случае, если такого числа не существует, следует вывести -1.

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

Результат:

Тема 1.1. Геометрия.

Цель.

Научиться применять знания по геометрии при решении задач с использованием компьютеров (программ). Уметь выполнять приближённые вычисления с точностью.

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

Вычисления с вещественными числами с заданной точностью. Использование математических функций: sin, cos, fabs, exp, log

Вывод вещественных чисел в нужном формате. Использование манипуляторов и форматов: setw, setiosflags, setprecision

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

Точка, уравнение прямой линии, геометрическая фигура.

ПРИМЕР.

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

Алгоритм.

Можно воспользоваться одной из формул, знакомых со школы. Для этого придётся вычислить какие-то элементы треугольника – стороны, углы, периметр. Мы воспользуемся формулой, дающей значение площади со знаком в зависимости от направления обхода вершин треугольника – через определитель 3-го порядка.

| 1 x₁ y₁ |

S = | 1 x₂ y₂ | * 0.5

| 1 x₃ y₃ |

Решение.

// C++

# include < iostream>

# include < iomanip>

# include < сstdlib>

using namespace std;

int main ()

{

setlocale (LC_ALL, " RUS" );

cout < < " Вычисление площади треугольника со знаком." < < endl;

cout < < " Введите координаты вершин." < < endl;

int x1, y1, x2, y2, x3, y3;

cin > > x1 > > y1 > > x2 > > y2 > > x3 > > y3;

double s = 0.5*(x1*y2 + x2*y3 + x3*y1 – x1*y3 – x2*y1 - x3*y2);

cout < < setiosflags (ios:: fixed) < < setw (10)

< < setprecision (2) < < s < < endl;

system (" PAUSE" ); // другой вариант задержки результатов на экране

return 0;

}

// C#

using System;

class Program

{

static void Main (string [] args)

{

Console.Write (" Вычисление площади треугольника со знаком. " );

Console.Write (" Введите координаты вершин " );

int x1, y1, x2, y2, x3, y3;

string ss = Console.ReadLine ();

string [] s = ss.Split (' ');

x1 = int.Parse (s [0]);

y1 = int.Parse (s [1]);

x2 = int.Parse (s [2]);

y2 = int.Parse (s [3]);

x3 = int.Parse (s [4]);

y3 = int.Parse (s [5]);

double sq = 0.5*(x1*y2 + x2*y3 + x3*y1 - x1*y3 - x2*y1 - x3*y2);

Console.WriteLine (sq);

Console.ReadKey ();

}

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

1.1.3.1. Выпуклый N-угольник P преобразуется в N-угольник Q путём замены середин сторон исходного многоугольника P на вершины многоугольника Q. Требуется по выпуклому N-угольнику Q, заданному координатами вершин, восстановить координаты вершин исходного N-угольника P. Входные данные содержат нечётное число вершин N (3 < = N < = 999), за которым следуют целочисленные координаты xi yi вершин многоугольника Q, перечисленные в порядке обхода по часовой стрелке. Значения координат находятся в диапазоне от –20000 до 20000. Все числа целые и разделены произвольным количеством пробелов и/или символов перевода строки.

Выведите координаты вершин N-угольника P, перечисляя их в порядке обхода по часовой стрелке. При этом первая и вторая вершина должны образовывать сторону, на которой лежит первая вершина N-угольника Q.

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

3
0 0
0 1
1 0

Результат:

1 –1
-1 1
1 1

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

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

0 0

1 1

2 2

0 2

2 0

Результат:

1 3 5

1.1.3.3. Написать программу для вычисления площади произвольного многоугольника, заданного перечислением пар координат вершин в порядке их обхода по часовой стрелке. Многоугольник не имеет самопересечений. В первой строке задаётся количество вершин n, в последующих n строках задаются пары целых чисел – координаты вершин. Результат вывести с точностью 2 знака после запятой.

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

0 0

0 2

2 2

4 1

4 0

Результат:

7.00

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

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

0 0

0 2

2 2

4 1

4 0

Результат:

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

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

0 0

1 1

0 2

2 2

2 1

4 1

4 0

Результат:

1 3 4 6 7

1.1.3.6. Десант. На полигоне установлены радары, которые обнаружат десант, если он будет выброшен ближе чем 0< R< =100000 (целое) м от радара. Полигон представляет собой квадрат размером N на N метров (0< N< =100000 м, целое), юго-западный угол полигона имеет координаты (0; 0), северо-восточный - (N; N). Необходимо найти точку выброса с целыми координатами, так чтобы десант не был обнаружен. Первая строка содержит числа N и R, разделенные пробелом. Вторая строка содержит целое число Z (количество радаров, 0< =Z< =10). Следующие Z строк содержат пары целых чисел X и Y, разделенные пробелом - координаты радаров (0< =X, Y< =N). Вывести целые координаты X и Y точки выброса (разделенные пробелом), либо " НЕТ", если точку выброса найти нельзя.

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

100 10

50 50

Результат:

0 0

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

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

Результат:

1.1.3.8. Задача коммивояжёра – 2. Найти кратчайший путь, проходящий через все заданные точки на плоскости и возвращающийся в исходную точку. В первой строке задаётся количество вершин n, в последующих n строках задаются пары целых чисел – координаты точек.

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

Результат:

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

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

Результат:

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

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

Результат:

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

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

Результат:

1.1.3.12. Вокруг звезды вращаются N планет, каждая со своим периодом обращения Ti и углом на начальный момент времени Ai. Когда в некоторый момент времени все планеты находятся под одинаковым углом A к звезде, то это явление называется парадом планет. Определить время наступления ближайшего парада планет.

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

Результат:

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

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

Результат:

1.1.3.14. Даны координаты 4-х точек в пространстве (Х₁, Y₁, Z₁), (Х₂, Y₂, Z₂), (Х₃, Y₃, Z₃), (Х₄, Y₄, Z₄). Определить, лежат ли они в одной плоскости. Если лежат – напечатать «ДА», иначе напечатать «НЕТ». В 4-х строках исходных данных находятся по 3 целых числа – координаты каждой точки.

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

Результат:

1.1.3.15. Дан произвольный многоугольник и точка. Все координаты целые числа. Напечатать «ДА», если точка внутри этого многоугольника. В противном случае напечатать «НЕТ».

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

Результат:

1.1.3.16. Точки в многоугольнике. Задан некоторый многоугольник перечислением координат своих вершин. Определить число точек (и м.б. перечислить их все) с целочисленными координатами, лежащих внутри этого многоугольника.

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

Результат:

1.1.3.17. Вычислить площадь фигуры, ограниченной отрезками прямых линий и дугами окружностей. В первой строке записано одно натуральное число n – количество вершин криволинейного многоугольника. В каждой из следующих n строк описан очередной отрезок или дуга окружности. Для отрезка в строке записаны координаты вершины и один символ +, для дуги сначала записаны координаты вершины, потом записан символ -, потом через пробел 3 целых числа – координаты центра окружности и радиус со знаком. Если радиус положительный – дуга от этой вершины к следующей идёт по часовой стрелке, если отрицательный – против часовой стрелки.

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

Результат:

1.1.3.18. Найти точку на прямой, сумма расстояний до которой от заданных точек будет наименьшей. В первой строке задаётся количество точек n, в последующих n строках задаются пары целых чисел – координаты точек. В последней строке данных коэффициенты А, В, С уравнения прямой AX + BY + C = 0. Координаты найденной точки напечатать с точностью 3 знака после запятой.

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

Результат:

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

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

0 0

0 1

1 1

1 0

Результат:

ДА

1.1.3.20. Дуга на сфере. На поверхности планеты, являющейся шаром радиусом R, заданы две точки своими широтой и долготой. Требуется найти минимальную длину пути по поверхности этой планеты из одной точки в другую. В первой строке находится число R, во второй строке заданы широта и долгота первой точки, в третьей строке - широта и долгота второй точки. Широта измеряется в градусах от -90 до 90, долгота – в градусах от -180 до 180. Радиус R меняется в пределах от 100 до 10000. Все числа вещественные. Вывести длину пути с двумя знаками после запятой.

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

4000
45 120
0 120

Результат:

3141.59

1.1.3.21. Даны N точек на плоскости и треугольник. Написать программу, которая найдет среди этих точек такие, которые образуют прямоугольник, равновеликий данному треугольнику.

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

Результат:

1.1.3.22. Даны N точек на плоскости, которые являются последовательными вершинами выпуклого многоугольника. Написать программу нахождения всех четверок точек, которые образуют равнобедренную трапецию.

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

Результат:

Цель.

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

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

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

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

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

ПРИМЕР 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.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 ();

}

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

1.3.3.1. Генерировать все перестановки чисел 1…n в лексикографическом порядке по заданному натуральному числу n.

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

Результат:

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

1.3.3.2. Найти номер заданной перестановки в лексикографическом порядке. В исходных данных в первой строке задаётся число n, а во второй строке сама перестановка.

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

3 1 2

Результат:

1.3.3.3. Найти перестановку длины n по её номеру k. Исходные данные число n и номер перестановки k.

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

3 4

Результат:

2 3 1

1.3.3.4. найти следующую перестановку для заданной перестановки чисел 1…n, В первой строке задаётся длина перестановки n, во второй строке – сама перестановка.

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

2 1 3

Результат:

2 3 1

1.3.3.5. найти следующую перестановку для заданной перестановки массива (могут быть одинаковые элементы). В первой строке задаётся длина n, во второй строке – сама перестановка.

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

3 1 2 1

Результат:

3 2 1 1

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

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

1 3 0 -4 2 6 -5 2

Результат:

1.3.3.7. Генерировать ряд Фаррея для заданного n – возрастающая последовательность правильных несократимых дробей со знаменателем не большим, чем n. Число n вводится.

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

Результат:

1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5

1.3.3.8. Генерировать все цепочки из 0 и 1 длины n. Число n вводится.

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

Результат:

1.3.3.9. генерировать все цепочки из 0 и 1 длины n, в которых нет двух нулей подряд. Число n вводится.

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

Результат:

1.3.3.10. Генерировать все цепочки из 0 и 1 длины n, в которых количество 0 больше чем количество 1. Число n вводится.

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

Результат:

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

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

Результат:

Примечание. По первой команде развернуть 1 человека на 2-й позиции вправо, по второй команде развернуть 4-го.

Тема 1.4. Сортировки

Цель.

Овладеть различными методами упорядочивания данных, отличающимися как по скорости, так и по используемой памяти. Умение оценивать сложность алгоритма.

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

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

ПРИМЕР.

Обменная сортировка (пузырьком). Дан массив целых чисел из N элементов. Упорядочить элементы в порядке не убывания путём сравнения пар соседних элементов.

Алгоритм.

Будем сравнивать последовательно пары соседей. Если они стоят не правильно, меняем их местами. Пройдя один раз от начала до конца, мы получим правильно стоящий последний элемент (самый большой). Организуем второй, третий и т.д. проходы, пока все элементы не станут в нужном порядке. Максимальное количество проходов – N-1.

Решение.

// C++

# include < iostream>

# include < cstdlib>

using namespace std;

const int N = 10;

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];

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

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

if ( a [j] > a [j+1] )

swap (a [j], a [j+1]);

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 (" Ведите количество, потом числа по 1 в строке" );

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

int [] a = new int [n];

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

a [i] = int.Parse (Console.ReadLine ());

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

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

if ( a [j] > a [j+1] )

{

int temp = a [j];

a [j] = a [j+1];

a [j+1] = temp;

}

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

Console.WriteLine (a [i]);

Console.ReadKey ();

}

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

1.4.3.1. Сортировка слиянием. На каждом этапе большой массив разбивается на две части, каждая из которых отдельно упорядочивается (сортируется). Потом обе части снова сливаются в единый (уже упорядоченный) массив за один проход. К каждой части применяется та же процедура. Разбиение продолжается до тех пор, пока в массиве не останется только два элемента, которые упорядочиваются за одно сравнение.

1.4.3.2. Множество М. Вычислить и напечатать первые n ( < =10000) элементов множества M в порядке возрастания.

Определение множества М:

1) 1 принадлежит M;

2) если число x принадлежит M, то и числа 2x+1 и 3x+1 также принадлежат множеству M. Все элементы должны быть различны. Число n вводится.

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

Результат:

1 3 4 7 9 10 13 15 19 21 22

1.4.3.3. Отрицательные влево, положительные вправо. В массиве целых чисел переставить элементы так, чтобы все отрицательные числа оказались в начале массива в том же порядке, что в исходном массиве. Аналогично положительные элементы должны оказаться в конце массива, а нули – между отрицательными и положительными. В первой строке задаётся размер массива n, во второй строке – сам массив. Вывести массив-результат.

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

2 0 -1 3 0 0 -2 2 -2 3 0

Результат:

-1 -1 -2 0 0 0 0 2 3 2 3

1.4.3.4. В упорядоченном массиве для заданного значения найти номер первого элемента с таким значением, если их несколько. Нумерация с 0. В первой строке задаётся размер массива n, во второй строке – сам массив, в третье – искомое значение.

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

-2 -2 -1 0 0 0 2 2 3 3 5

Результат:

1.4.3.5. В упорядоченном массиве целых чисел для заданного значения найти номер последнего элемента с таким значением, если их несколько. Нумерация с 0. В первой строке задаётся размер массива n, во второй строке – сам массив, в третье – искомое значение.

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

-2 -2 -1 0 0 0 2 2 3 3 5

Результат:

1.4.3.6. Закраска прямой. Интервал прямой с целочисленными координатами [a, b) содержит левую границу – точку a и не содержит правую границу – точку b.

Интервал от 0 до 10⁹ выкрасили в белый цвет. Затем было выполнено N операций перекрашивания. При каждой операции цвета в интервале, границы которого задаются, меняются на противоположный (белый на черный, черный на белый). Написать программу, которая найдет самый длинный интервал белого цвета после заданной последовательности операций перекрашивания. В первой строке находится число N (1 < = N < = 500) и затем N строк с границами интервалов (числа в диапазоне от 0 до 10⁹). Вывести одно число – длину самого большого белого интервала.

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

Результат:

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

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

Результат:

Цель.

Изучение особенностей массивов, содержащих символьную информацию (строки, тексты).

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

12 3 Следующая ⇒