1 курс Page
http://astr73.narod.ru/task1.doc
Тема 1. Программирование
!! В задачах 01-14 требуется за один проход (без использования массивов) вычислить ту или иную характеристику последовательности чисел, вводимых с клавиатуры.
01. Сумма и произведение элементов.
02. Номер первого и последнего максимального элемента.
03. Число минимальных элементов.
04. Число элементов, больших предыдущего.
05. Среднее квадратичное уклонение от среднего арифметического: D = ( (x1-M)2 + ... + (xn-M)2 )/n (n - число элементов, М - среднее арифметическое)
06. Есть ли в последовательности число х (вводится с экрана перед чтением файла)?
07. Номер первого и последнего элемента, равного числу х (если таких нет, считать номер равным нулю).
08. Все ли элементы последовательности равны между собой?
09. Является ли последовательность возрастающей, неубывающей?
10. Вычислить число различных элементов неубывающей последовательности.
11. Сколько раз в последовательности встречается фрагмент 1, 2, 3, 4, 5 ?
12. Сколько раз в последовательности встречается фрагмент 1, 2, 1, 3?
13. Коэффициенты многочлена сведены в последовательность в порядке возрастания степеней. Найти значение многочлена и его производной в точке х (число x вводится первым).
14. Коэффициенты многочлена сведены в последовательность в порядке убывания степеней. Найти значение многочлена и его производной в точке х (число x вводится первым).
15. Дано целое число. Получить число, десятичная запись которого содержит цифры исходного числа в обратном порядке.
16. Вычислить представление числа 1/n в виде десятичной дроби (указать ее начало и период).
17. Возвести число A в степень N, используя не более 2*log(N) умножений
!! В задачах 18-25 требуется составить программу, которая позволяет ввести массив A длины N и производит с ним определенные действия, после чего выводит результат. Использовать дополнительные массивы нельзя.
18. Симметричен ли массив?
19. Записать элементы массива в обратном порядке: первый элемент должен оказаться на последнем месте, второй - на предпоследнем и т.д.
20. Циклически сдвинуть элементы массива вправо: первый элемент должен оказаться на втором месте, второй - на третьем и т.д. Последний элемент должен оказаться на первом месте.
21. Циклически сдвинуть элементы массива из N элементов на k мест влево за время O(N).
22. Каждый элемент массива с индексом от 2 до N-1 заменить на полусумму соседей.
23. Известно, что элементы массива не убывают. Проведя не более 1+log(N) сравнений числа х с элементами массива, выяснить, встречается ли х среди элементов массива.
24. Дано,что первые N-1 элементов массива не убывают. Переставить все N элементов так, чтобы они не убывали.
25. Переставить элементы массива так, чтобы они не убывали.
26. Даны k отрезков на прямой. Вычислить, образуют ли они покрытие отрезка [0,1]
27. Даны k отрезков на прямой. Найти максимальное n, для которого существует точка, принадлежащая одновременно n отрезкам.
!! В задачах 28-29 известно, что первые N элементов массива А возрастают и первые M элементов массива В возрастают.
28. Найти число К и построить массив С, в котором первые K элементов возрастают, причем число х встречается среди первых K элементов С если и только если оно встречается либо в А либо в В.
29. Найти число К и построить массив С, в котором первые K элементов возрастают, причем число х встречается среди первых K элементов С если и только если оно встречается и в А и в В (пересечение).
!! Элемент называется локальным максимумом, если у него нет соседа, большего, чем он сам. Например, в последовательности из одного элемента - один локальный максимум. В последовательности 3, 3, 1, 0, 2, -1 три локальных максимума: первый, второй и предпоследний элементы.
30. Вычислить число локальных максимумов в одномерном массиве.
31. Вычислить число локальных максимумов в двумерном массиве.
!! Число n называется периодом последовательности, если любые два элемента последовательности начиная с некоторого, номера которых отличаются на n совпадают.
32. Отображение целочисленного отрезка [1,N] в себя задано в виде y=f(x). Найти минимальный период последовательности 1, f(1), f(f(1)), ...
33. Вывести в файл "tmp.res" список а) всех подмножеств б) всех K-элементных подмножеств множества чисел (1,2,...,n)
!! Стандартным прямоугольником на плоскости называется множество точек ( x1,x2 : a1<=x1<=b1, a2<=x2<=b2 ). Прямоугольник может вырождаться в вертикальный или горизонтальный отрезок, в точку или в пустое множество.
34. Найти периметр и площадь пересечения и объединения двух стандартных прямоугольников на плоскости (периметром отрезка считается его удвоенная длина).
!! k-мерным яшиком называется множество (x1, ..., xk : a1<=x1<=b1, ..., ak<=xk<=bk ).
35. Найти плошадь поверхности и объем пересечения и объединения двух k-мерных яшиков (k>=1).