Содержание
1. Постановка задачи
2. Комментарии
3. Алгоритм А и его программная реализация
4. Алгоритм Б и его программная реализация
1. Постановка задачи
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны.
Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен).
Необходимо определить количество таких пар, для которых произведение элементов делится на 29.
Вам предлагается два задания, связанных с этой задачей: задание А и задание Б.
Вы можете решать оба задания или одно из них по своему выбору.
Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание – 0 баллов.
Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.
Задание А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве,
после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования.
ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А. Максимальная оценка за выполнение задания А – 2 балла.
Задание Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N,
т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.
ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б.
Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла.
НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000).В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.
Пример входных данных:
7
58
2
3
5
4
1
29
Пример выходных данных для приведённого выше примера входных данных:
5
2. Комментарии
1. Первое обсуждаемое понятие, это эффективность программы по времени. На примере задач Линейного и бинарного поиска и Сортировки оцениваем число операций сравнения, когда число элементов массива N > 1000000000. Второе понятие — эффективность по памяти с разбором примеров, когда данные можно обрабатывать в темпе с процессом их поступления, не используя их накопление в массиве.
2. После этого школьник готов к поиску алгоритма и структур данных, позволяющих выполнить задание Б. Следует потратить несколько занятий для того, чтобы он отказался от запоминания частных решений похожих задач и научился думать и генерировать необходимые решения.
3. Важно помнить, что получения правильного ответа в тесте, приведенном в качестве примера, не гарантирует правильности программы. При проверке может быть использован широкий набор тестов (как на международной студенческой олимпиаде по программированию ACM/ICPC), так и ручной просмотр текста и анализ логики программы (чаще всего, к сожалению).
4. Решение задания начинаем с последовательного ввода данных, считываемых из файла. Далее решаем задание А, после чего переходим к заданию Б. Уделяем внимание типу поступающих данных (целое положительное число), количеству данных, результату — количество таких пар, для которых произведение элементов делится на 29, между моментами передачи которых прошло не менее 4 минут.
3. Алгоритм А и его программная реализация
1. Ввод данных. Считаем, что исходные данные хранятся в текстовом файле: одно число — одна строка, причем первое число — количество переданных показаний. Фактически часто это количество данных в серии неизвестно, но тем не менее это число считывается из файла первым. Имя файла может быть жестко зафиксировано. Пример работы с текстовыми файлами приведен в статье Чтение и запись текстовых файлов. Данные заносим в одномерный массив mas[], индекс элемента которого соответствует, например, времени ежеминутного поступления сигнала (начальное время t = 0), а значение которого и есть сам сигнал.
2. Находим номера элементов, делящихся нацело на 29, заносим их (номера) в новый массив mak[ ] .Подсчет пар показаний, между моментами передачи которых прошло не менее 4 минут, выполняем с учетом временного лага (запаздывание).
3. Подсчет числа пар назад и вперед. При этом, чтобы не было двойного счета
4. После вывода результата — числа пар — решение задания А завершено. Оформляем его в методе Main().
using System;
using System.IO;
namespace Задача_27_1__массив
{
class Program
{
static void Main(string[] args)
{
int N, k = 0, s = 0;
string data = "data.txt"; // имя файла исходных данных
StreamReader sr = new StreamReader(data);
// число сигналов
N = Convert.ToInt32(sr.ReadLine());
// массив сигналов
int[] mas = new int[N];
// массив номеросигналов, кратных 29
int[] mak = new int[N];
// считывание данных
for (int i = 0; i < N; i++)
mas[i] = Convert.ToInt32(sr.ReadLine());
// цикл выборки номеров сигналов
for (int i = 0; i < N; i++)
{
if (mas[i] % 29 == 0)
{
mak[s] = i;
s++;
}
}
подсчет пар
if (s > 0)
{
for (int j = 0; j < s; j++)
{
if (mak[j] > 3)
k = k + mak[j] - 3;
if ((N - mak[j] - 4) > 0)
k = k + (N - 4 - mak[j]);
k = k - del(mak, j);
}
}
else
k = 0;
// результат
Console.WriteLine(k);
Console.ReadKey();
}
// для удаления близких пар
static int del(int [] mak, int j)
{
int p = 0;
for (int q = 0; q < j; q++)
if ((mak[j] - mak[q]) > 3)
p++;
return p;
}
}
}
3. Алгоритм Б и его программная реализация
Массив для хранения всех сигналов не объявляется. Если новое число кратно 29, то оно образует пару со всеми будушими числами, исключающими близлежащие, а также с предшествующими за вычетом близлежащих (номера в массиве m[ ]).
Программа:
using System;
using System.IO;
namespace Задача_27_1_
{
class Program
{
static void Main(string[] args)
{
int N; // число элементов
int k; // номер точки
int r = 0; // число пар (ответ)
int a; // текущий сигнал
int q=0; // кол-во кратных нарастанием
int p = 0; // вспомогательная
int[] m = new int[4]; // массив номеров
int n_m = 0; // число элементов в m[4]
string data = "data.txt"; // исх.данные
StreamReader sr = new StreamReader(data);
N = Convert.ToInt32(sr.ReadLine());
k = 0;
while (! sr.EndOfStream)
{
a = Convert.ToInt32(sr.ReadLine());
if (a % 29 == 0)
{
p = N - (k + 4);
if (p > 0)
r = r + p;
p = k - 3;
if (p > 0)
r = r + p;
r = r - q + povt(k, m, n_m);
q++;
sdvig4(k, m, ref n_m);
}
k++;
Console.WriteLine("Число {0}", r); // пром печать
}
Console.WriteLine("Число пар = {0}", r);
Console.ReadKey();
}
// заполнение или сдвиг/заполнение, изменяет n !
private static void sdvig4( int k, int [] m, ref int n)
{
const int g=4;
if (n<g)
{
m[n] = k;
n++;
}
else
{
for (int j = 0; j < g - 1; j++)
m[j] = m[j + 1];
m[g - 1] = k;
}
}
// отнять повторы назад на расстояниях < 4
private static int povt(int k, int[] m, int n)
{
int h = 0;
for (int j = 0; j < n; j++)
if (k - m[j] < 4)
h++;
return h;
}
}
}
Исседуйте программу для различных наборов данных.
NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.