Параллельное программирование.

Список задач для цикла лабораторных работ.

 

1.         Найти наименьшее число n, большее заданного M, имеющее точно такое же количество различных простых делителей, какое имеет число n+1

2.         Вычислить методом последовательных приближений распределение значений температуры в параллелепипеде размером k * m * n, имеющей внутри полость в виде цилиндра. Теплопроводность материала не равна нулю. Нижняя грань параллелепипеда имеет температуру 0. Одна из сторон верхней грани имеет температуру T1, противоположная - температуру T2.

3.         Найти минимальную (или близкую к минимальной) правильную раскраску заданного графа (правильной называется такая раскраска, когда любые две смежные вершины окрашены в разные цвета; минимальной называется раскраска, использующая наименьшее количество цветов)

4.         Найти разреженную треугольную подматрицу заданного размера с минимальной суммой элементов в заданной матрице (разреженной называется подматрица, в которой индексы соседних элементов могут различаться более, чем на единицу, например, треугольная подматрица размерностью 4 строки на 4 столбца может описываться, например, такой совокупностью пар индексов: {{1:3},{2:3, 2:5}, {5:3, 5:5, 5:7}, {8:3, 8:5, 8:7, 8:8}}; в этих парах первое число – это индекс строки охватывающей матрицы, второе – это индекс ее столбца; элементов выше главной диагонали нет в отличие от обычного понимания треугольной матрицы)

5.         Определить, изоморфны ли два заданных графа

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

7.         Вычислить произведение двух заданных полиномов N переменных (например  при N=3 полиномы (x2yz2+2xy2z2–x3yz) и (3xy3z – x2y2z+2xy2z2–5xyz) представляем в виде (1212+1122-1311) и (3131-1221+2122-5111). Результат их умножения будет равен 2343-3433+2234-5321+3253+2244-5233-3442+1532+5422)

8.         Найти количество всех вхождений заданной последовательности символов в заданной строке (порядок следования символов важен, но символы последовательности не обязательно должны следовать друг за другом в исходной строке; например, в строке xxyzy последовательность xy встречается 4 раза, последовательность xz - 2 раза, последовательности xx, zy, yy и yz - по одному разу, а yx, zx и zz - ни разу)

9.         Найти наименьшие три последовательно возрастающие простые числа, большие заданного N, сумма которых является простым числом (например, при N=4 такими числами являются 5, 7 и 11)

10.     Найти количество всех различных последовательностей символов заданного размера в заданной строке с учетом порядка следования символов (например, строка xyxxz содержит подстроки x (3), y (1), z (1) размера 1, xy (1), xx (3), xz (3), yx (2), yz (1) размера 2, xyx (2) , xyz (1), xxx (1), xxz (3), yxx (1), yxz(2) размера 3, xyxx (1), xyxz (2), xxxz (1), yxxz (1) размера 4, xyxxz (1) размера 5; в скобках указано количество подстрок; других подстрок нет; таким образом, подстрок размера 1 ровно 5, размера 2 – 10, размера 3 – 10 и т.д.)

11.     Поразрядная сортировка

12.     Любое число n, большее единицы, порождает последовательность вида:

ni+1 = (ni % 2 == 0? ni / 2 : 3 * ni + 1),

последним элементом которой является 1 (например: 13->40->20->10->5->16->8->4->2->1). Найти наибольшее, меньшее заданного N, число, порождающее самую длинную такую последовательность.

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

14.     Вычислить методом последовательных приближений распределение значений температуры установившегося режима в точках верхней границы плоской прямоугольной области размером m * n, имеющей внутри вырез в форме треугольника. Теплопроводность материала области конечна и не равна нулю. Левая и нижняя граница области имеют постоянную температуру 0. Правый верхний угол имеет постоянную температуру T, значения температур точек правой границы постоянны и равномерно убывают от T до 0.

15.     Найти числа a>b>c, большие заданного числа N, имеющие одинаковые количества различных простых делителей такие, что a-b=b-c.

16.     Вычислить методом последовательных приближений последовательность значений температуры заданной точки параллелепипеда размером k * m * n, имеющего внутри полость в виде сферы. Теплопроводность материала не равна нулю. Нижняя грань параллелепипеда имеет постоянную температуру 0. Геометрический центр верхней грани имеет постоянную температуру T1, температура сторон этой грани постоянна и равна T2.Начальная температура остальных точек параллелепипеда равна T3

17.     Найти первые N последовательно возрастающих на величину k чисел, больших заданного числа, все нетривиальные делители (простые числа) которых различны (например, два таких числа, возрастающих на 1 – это 14=2*7 и 15=3*5)

18.     Решение задачи движения N тел в трехмерном пространстве с учетом сил гравитационного притяжения между ними; при упругих соударениях количество тел не меняется. Массы, радиусы, начальные координаты и векторы скоростей всех тел считать заданными. Вычислить координаты всех тел через k секунд.

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

20.     Вычислить методом последовательных приближений распределение значений температуры в точках верхней границы плоской прямоугольной области размером m * n, имеющей внутри круглый вырез. Теплопроводность материала области конечна и не равна нулю. Левая и нижняя граница области имеют постоянную температуру 0. Правый верхний угол имеет постоянную температуру T, значения температур точек правой границы постоянны и равномерно убывают от T до 0. Все остальные точки в начальный момент имеют температуру Т3.

21.     Для заданного положительного числа N найти количество различных способов его получения в результате суммирования заданного количества k положительных целых чисел (например, 5=1+1+3=1+2+2 – итого 2 способа выразить 5 как сумму 3-х чисел).

22.     Найти минимальное число, которое может быть разложено в сумму простых чисел не менее, чем N различными способами (например, для числа 10 существует ровно 5 таких способов: 10 = 7+3 = 5+5 = 5+3+2 = 3+3+2+2 = 2+2+2+2+2)

23.     Для любого целого числа n обозначим через p(n) количество способов представления n в виде суммы целых положительных чисел (например, p(5) = 6, потому что 5 = 4+1 = 3+2 = 3+1+1 = 2+2+1 = 2+1+1+1 = 1+1+1+1+1). Найти минимальное число n, для которого p(n) больше заданного N.

24.     Найти максимальное число, меньшее заданного N, которое может быть представлено как сумма степеней 2, 3 и 4 простых чисел (минимальное такое число есть 28 = 22+23+24)

25.     Любое число n, большее единицы, порождает последовательность вида:

ni+1 = (ni % 2 == 0? ni / 2 : 3 * ni + 1),

последним элементом которой является 1 (например: 13->40->20->10->5->16->8->4->2->1). Найти наибольшее, меньшее заданного N, число, порождающее последовательность заданной длины.

26.     Вычислить методом последовательных приближений распределение значений температуры точек верхней грани параллелепипеда размером k * m * n, имеющего внутри полость в виде цилиндра. Теплопроводность материала не равна нулю. Нижняя грань параллелепипеда имеет постоянную температуру 0. Одна из сторон верхней грани имеет температуру T1, противоположная - температуру T2.

27.     Найти k простых чисел, больших заданного числа N, таких что их сумма равна квадрату одного из них.

28.     Вычислить методом последовательных приближений последовательность значений температуры в заданной точке параллелепипеда размером k * m * n, имеющего внутри полость в виде сферы от начального момента до установившегося режима. Теплопроводность материала не равна нулю. Нижняя грань параллелепипеда имеет постоянную температуру 0. Геометрический центр верхней грани имеет постоянную температуру T1, температура сторон этой грани постоянна и равна T2. Все остальные точки в начальный момент имеют температуру Т3.

29.     Сортировка вставками/слиянием

30.     Найти наибольший палиндром (число, одинаково читающееся слева направо и справа налево), меньший заданного числа N, который является суммой квадратов последовательно расположенных чисел (например, число-палиндром 595 = 62+72+82+92+102+112+122)

31.     Близнецами называются простые числа, разница между которыми равна двум (например: 29 и 31, 41 и 43, …). Найти две соседние пары близнецов, расстояние между серединами которых больше заданного N (соседними называются такие пары, между которыми нет других близнецов)

32.     Найти целые числа x>y>z, большие заданного N, такие, что 5 из 6 значений вида x+y, x-y, x+z, x-z, y+z, y-z являются полными квадратами других чисел

33.     Сортировка выбором/слиянием

34.     Найти наименьшее число, большее заданного N, такое, что сумма его десятичных цифр, возведенных в заданную степень n, равна другому числу, возведенному в эту же степень (например, при n=2 таким является число 442: 42+42+22 = 36 = 62)

35.     Найти наибольшее число M, меньшее заданного числа N, которое можно представить суммой k различных простых чисел.

36.     Найти минимальное, большее заданного, число, которое равно сумме его десятичных цифр, возведенной в степень, большую 1 (например, 4913 = (4+9+1+3)3= 173, здесь 4913, 17 и 3 – искомые результаты).

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

38.     Любое число n, большее единицы, порождает последовательность вида:

ni+1 = (ni % 2 == 0? ni / 2 : 3 * ni + 1),

последним элементом которой является 1 (например: 13->40->20->10->5->16->8->4->2->1). Вычислить количество последовательностей заданной длины n среди чисел заданного интервала от N до M.

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

40.     Найти минимальное число, большее заданного N, которое может быть представлено как сумма заданных (например 2, 3, 4, 5 или 3, 5, 7 или 3, 11) степеней простых чисел (для первого набора степеней наименьшее такое число есть 60 = 22+23+24+25)

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

42.     Найти наименьшее число n, большее заданного N, для которого сумма любого его делителя d с результатом деления n/d является простым числом (таково число 30, имеющее делители 1, 2, 3, 5, 6, 10, 15, 30)

43.     Найти целые числа x и y, большие заданного N, такие, что значения вида x+y и x-y являются какими-либо степенями других чисел

(x - y = pq и x + y = mn).

44.     Найти наименьшее число M, большее заданного числа N, которое можно представить суммой нескольких простых чисел не менее, чем k различными способами.

45.     Близнецами называются простые числа, разница между которыми равна двум (например: {29, 31}, {41, 43}, …). Найти три соседние (соседними называются такие пары, между которыми нет других близнецов) пары близнецов {a, a+2}, {b, b+2} {c, c+2}, такие, что a>b>c>N и (a-b) = (b-c)

46.     Любое число n, большее единицы, порождает последовательность вида:

ni+1 = (ni % 2 == 0? ni / 2 : 3 * ni + 1),

последним элементом которой является 1 (например: 13->40->20->10->5->16->8->4->2->1). Вычислить распределение длин таких последовательностей (гистограмму пар «длина, количество») для чисел заданного интервала от N до M.

47.     Найти простое число, расстояния от которого до его ближайших меньшего и большего соседей не меньше заданного N.

48.     Вычислить определитель заданной матрицы

49.     Найти разреженную подматрицу заданного размера с максимальной суммой элементов в заданной матрице (разреженной называется подматрица, в которой индексы соседних элементов могут различаться более, чем на единицу, например, подматрица размерностью 3 строки на 4 столбца может быть задана совокупностью пар индексов: {{2:3, 2:5, 2:7, 2:8}, {3:3, 3:5, 3:7, 3:8}, 6:3, 6:5, 6:7, 6:8}}; в этих двухразрядных числах первая цифра пары – индекс строки охватывающей матрицы, вторая – индекс ее столбца)

50.     Сортировка пузырьковая

51.     Найти компактную треугольную подматрицу заданного размера с минимальной суммой элементов в заданной матрице (компактной называется подматрица, в которой индексы соседних элементов по строкам и по столбцам различаются на единицу; компактная треугольная подматрица может описываться, например, такой совокупностью пар индексов ее элементов в родительской матрице: {{5:3}, {6:3, 6:4}, {7:3, 7:4, 7:5}, {8:3, 8:4, 8:5, 8:6}}; обратите внимание, элементов выше главной диагонали нет в отличие от обычного понимания треугольной матрицы)

52.     Быстрая сортировка

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

54.     Решение задачи движения N тел на плоскости с учетом сил гравитационного притяжения между ними; при упругих соударениях количество тел не меняется. Массы, радиусы, начальные координаты и векторы скоростей всех тел считать заданными. Вычислить координаты заданного тела через k секунд.

55.     Вычислить методом последовательных приближений последовательность значений температуры в заданной точке плоской прямоугольной области размером m * n, имеющей внутри овальный вырез. Точки левой и нижней границы области имеют температуру 0. Точка, находящаяся в середине верхней границы, имеет температуру T. Температура точек верхней границы постоянна и равномерно убывает от ее середины до краев. Теплопроводность материала области не равна нулю. Все остальные точки в начальный момент имеют температуру Т3.

56.     Найти наименьшее число M, большее заданного N, такое, что сумма всех компактных подпоследовательностей его десятичных цифр равна некоторому другому числу m, возведенному в степень p, большую 1 (для числа 1234 имеются следующие компактные подпоследовательности: 1, 2, 3, 4, 12, 23, 34, 123 и 234). Результатом поиска должны быть числа M, m и p.

57.     Пирамидальная сортировка

58.     Вычислить матрицу, обратную заданной

59.     Вычислить методом последовательных приближений распределение значений температуры в точках правой границы плоской прямоугольной области размером m * n, имеющей внутри вырез в форме ромба. Точки левой и нижней границы области имеют постоянную температуру 0. Точка, находящаяся в середине верхней границы, имеет постоянную температуру T. Температура точек верхней границы постоянна и равномерно убывает от ее середины до краев. Теплопроводность материала области конечна и не равна нулю.

60.     Сортировка Шелла