Задачи для самостоятельного решения. 1.3.2.1. Рассматриваются все числа от 1 до n

1.3.2.1. Рассматриваются все числа от 1 до n. Сколько раз встречается каждая цифра от 0 до 9 во всех этих числах вместе взятых? Вводится натуральное n. Нужно вывести 10 строк по одному числу: количество нулей, единиц и т.д. девяток.

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

Результат:

1.3.2.2. Вычисление мультиномиального коэффициента (K₁ + K₂ +...+ K_n)! / K₁! / K₂!... / K_n! В первой строке задаётся количество n, во второй – сами числа K_1, K₂,... K_n. Все числа K_1, K₂,... K_n - не отрицательные целые числа.

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

1 2 3

Результат:

1.3.2.3. Написать программу вычисления и печати через пробел всех простых чисел от 1-го (число 2) до К-го

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

Результат:

2 3 5 7 11 13 17 19 23 29 31 37 41

1.3.2.4. Написать программу вычисления и печати всех простых чисел от 2 до заданного n методом решета Эратосфена. В первой строке задаётся число n.

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

Результат:

2 3 5 7 11 13

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

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

12 4 16 8 6

Результат:

1.3.2.6. Написать функцию, которая вычисляет и печатает все пары простых чисел-близнецов от 2 до заданного N (их значения отличаются на 2, например, 17 и 19). Пары печатать в отдельных строках.

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

Результат:

2 3

3 5

5 7

11 13

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

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

1302 8

Результат:

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

1.3.2.9. Напечатать треугольник Паскаля из n строк (значение n вводится).

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

Результат:

1 1

1 2 1

1 3 3 1

…

1.3.2.10. Для набора целых чисел X1,X2,… …,Xn найти целое значение А такое, что сумма (|X1-A| + |X2-A| + … … + |Xn-A|) минимальна, т.е. такую точку А, до которой сумма расстояний от заданных точек минимальна. В первой строке задаётся размер массива, во второй – сам массив.

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

1 7 6 1 2

Результат:

1.3.2.11. в подстановке (перестановке 1…n) найти все элементарные циклы. В первой строке задаётся число n, во второй – сама перестановка.

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

2 5 4 3 1

Результат:

1 2 5

3 4

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

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

3 1 5 3 1 7 1

Результат:

1 3 5 7

1 3

1.3.2.13. В массиве из n целых чисел найти и напечатать элемент, на который делятся все остальные (или напечатать слово «НЕТ»). В первой строке задаётся размер массива, во второй – сам массив.

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

1 3 2 5 7 4 6 8

Результат:

1.3.2.14. В массиве из n натуральных чисел найти и напечатать элемент, который делится на все остальные (или напечатать слово «НЕТ»). В первой строке задаётся размер массива n, во второй строке – сам массив.

Исходный массив:

1 3 2 5 7 4 6 8

Результат:

НЕТ

1.3.2.15. Секретное сообщение. На секретную базу в Арктике поступила шифровка – последовательность из n десятичных цифр. Она содержит номер секретной базы в Антарктиде, который является последовательностью из k десятичных цифр. При этом для того, чтобы отличить его от ненужной Вам информации, он повторен в шифровке хотя бы два раза (возможно, эти два вхождения перекрываются). Написать программу, которая по шифровке и длине номера секретной базы определяет, содержит ли шифровка номер базы. Учтите, что у базы может быть несколько номеров, и все они могут быть переданы в шифровке. Первая строка содержит два целых числа: n (1 ≤ n ≤ 10⁵) и k (1 ≤ k ≤ 5) – длину шифровки и длину номера секретной базы соответственно. Вторая строка содержит n цифр – шифровку. Цифры в шифровке не разделяются пробелами. Вывести «YES», если шифровка содержит номер секретной базы, и «NO» в противном случае.

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

13 2
0123400056789

Результат:

YES

1.3.2.16. Сверхпростые числа. Простым числом будем называть натуральное число, большее единицы и делящееся только на единицу и на само себя. Выпишем все простые числа в порядке возрастания и i-ое в этом порядке число обозначим pi (число 2 при этом будет иметь номер 1). Так, например, p₁ = 2, p₂ = 3, p₃ = 5, p₅₂ = 239. Скажем, что число p_i является сверхпростым, если i = p_k для некоторого k. Иными словами, сверхпростое число — это простое число, номер которого в списке простых чисел, упорядоченном по возрастанию, является простым числом. Дано натуральное число k (1 ≤ k ≤ 500). Упорядочим все сверхпростые числа по возрастанию. Найдите k-ое сверхпростое число в этом порядке.

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

Результат:

1.3.2.17. Дан массив вещественных чисел x₁, x₂, x₃,.., x_N (N=5000). Написать программу, которая вычислит произведение сумм (x₁)(x₂+x₃)( x₄+x₅+x₆)..., где в каждой следующей скобке на одно слагаемое больше, чем в предыдущей, а в последней - все оставшиеся.

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

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 ();

}

}