Просмотр содержимого документа
«Дз 40. С4 решение эффективное и неэффективное (перебором)»
Задание 40. С4 решить двумя способами на компьютере (или хотя бы одним). Файлы прислать
9-15. Последовательность натуральных чисел характеризуется числом Y – наибольшим числом, кратным 26 и являющимся произведением двух элементов последовательности с различными номерами. Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), находящую число Y для последовательности натуральных чисел, значение каждого элемента которой не превосходит1000. Программа должна напечатать найденное число, если оно существует для заданной последовательности, или ноль в противном случае. Перед текстом программы кратко опишите используемый Вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000.
Пример входных данных:
5
40
100
130
28
51
Пример выходных данных для приведённого выше примера входных данных:
13000
1-15. Для заданной последовательности неотрицательных целых чисел необходимо найти максимальное произведение двух её элементов, номера которых различаются не менее чем на 8. Значение каждого элемента последовательности не превышает 1000. Количество элементов последовательности не превышает10000.
Вам предлагаются два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок а задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка а это задание составляет0 баллов.
А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования. Обязательно укажите, что программа является решением задания А. Максимальная оценка за выполнение задания А– 2 балла.
Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти(или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству элементов последовательности N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает1 килобайта. Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм. Обязательно укажите, что программа является решением задания Б. Максимальная оценка за правильную программу, эффективную по времении по памяти– 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла.
Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество элементов последовательности. Гарантируется, что N 8. В каждой из следующих N строк задаётся одно неотрицательное целое число– очередной элемент последовательности.
Пример входных данных:
10
100
45
55
245
35
25
10
10
10
26
Программа должна вывести одно число– описанное в условии произведение.
Пример выходных данных для приведённого выше примера входных данных:
2600
3-16. На плоскости задано множество точек с целочисленными координатами. Необходимо найти количество отрезков, обладающих следующими свойствами:
1) оба конца отрезка принадлежат заданному множеству;
2) ни один конец отрезка не лежит на осях координат;
3) отрезок пересекается ровно с одной осью координат.
Напишите эффективную по времени и по используемой памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества точек в k раз время работы возрастает не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти для хранения всех необходимых данных не зависит от количества точек и не превышает1 килобайта.
Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.
Входные данные
В первой строке задаётся N– количество точек в заданном множестве. Каждая из следующих строк содержит два целых числа x и y– координаты очередной точки. Гарантируется, что1 ≤ N ≤10 000; –1000 ≤ x, y ≤1000.
Пример входных данных:
4
6 6
-8 8
-9 -9
7 -5
Выходные данные
Необходимо вывести единственное число: количество удовлетворяющих требованиям отрезков.
Пример выходных данных для приведённого выше примера входных данных:
4
0
