Автор — Евгений К., школьник
Пример решения задачи с использованием технологии ООП, а точнее классов. Методы ввода/вывода можно использовать в аналогичных задачах.
Условие
Имя входного файла: стандартный ввод или input.txt
Имя выходного файла: стандартный вывод или output.txt
Дана последовательность из n натуральных чисел, расположенных в произвольном порядке.
Требуется отсортировать эту последовательность по возрастанию, затем применить следующие операции просеивания через «двойное решето»:
Операция просеивания: Если для первого элемента в последовательности найдется элемент в два раза больше первого, то больший элемент должен быть удален из этой последовательности, иначе последовательность не изменяется на этом шаге. Если существуют другие элементы, в два раза больше первого, то они в этой последовательности сохраняются.
Далее операция просеивания применяется к сокращающейся последовательности уже без уже использованных элементов.
В итоге должна быть получена последовательность, которая, возможно будет иметь меньшую длину — результат работы алгоритма.
Формат входных данных
В первой строке задано целое число n — число элементов массива
В последующих n строках — натуральные числа (элементы массива)
Формат выходных данных
Выведите в столбик результат — массив оставшихся чисел в решете
Пример (отсортированная последовательность)
стандартный ввод
8
1
2
2
3
4
6
8
16
стандартный вывод
1
2
3
8
Решение
Алгоритм:
1) Исходную последовательность чисел размещаем в массиве m[], метод Input().
2) Отсортируем массив по возрастанию элементов, метод Sort().
3) Так как все элементы больше нуля (натуральные числа по условию задачи) на место удаляемых элементов записываем нули-«дырки», метод Make0().
4) Удаление дырок — создание сплошного массива — результат, метод Del0().
5) Вывод результата обработки в файл, метод Output().
6) Для контроля выполнения отдельных операций — метод ConsoleOut(string s), где s — cтрока заголовка.
Создадим класс Sieve с тремя полями и шестью методами:
class Sieve
{
int[] m; // массив исходных данных
int N; // число элементов массива
int x = 0; // кол-во "дырок" в массиве м
// Ввод данных - чтение из файла
public void Input()
// Cортировка массива
public void Sort()
// Просеивание - создание "дырок" в массиве
public void Make0()
// Удаление "дырок" в массиве
public void Del0()
// Вывод для проверки
public void ConsoleOut(string s)
// Вывод в файл
public void Output()
}
Тогда метод Main() в классе Program задается последовательностью операторов:
static void Main()
{
Sieve arr = new Sieve();
arr.Input();
arr.ConsoleOut("Исходные данные:");
arr.Sort();
arr.ConsoleOut("После сортировки:");
arr.Make0();
arr.ConsoleOut("После удаления с нулями:");
arr.Del0();
arr.ConsoleOut("Результат:");
arr.Output();
Console.ReadKey();
}
Полный текст программы
using System;
using System.IO;
namespace double_sieve
{
class Sieve
{
int[] m; // массив исходных данных
int N; // число элементов массива
int x = 0; // кол-во "дырок" в массиве м
// Ввод данных - чтение из файла
public void Input()
{
StreamReader sr; // поток для чтения
try
{
// Чтение из файла input.txt
sr = new StreamReader("input.txt");
string t = sr.ReadLine(); // чтение первой (0-й) строки
N = Convert.ToInt32(t);
string[] d = new string[N];
m = new int[N];
int n = 0; // счетчик строк
do
{
t = sr.ReadLine(); // чтение остальных строк
if (t == null)
break;
d[n++] = t;
}
while (n < N);
if (n < N)
{
Console.WriteLine("Недостаточно данных в исходном файле!");
return;
}
sr.Close();
//перевод строкового массива d в целочисленный массив m
for (int k = 0; k < N; k++)
m[k] = Convert.ToInt32(d[k]);
}
catch // обработка исключений (например, если нет файла "info.txt")
{
Console.WriteLine("Ошибка в файле исходных данных!");
return;
}
}
// Cортировка массива
public void Sort()
{
int r;
for (int i = 0; i < N - 1; i++)
{
for (int j = 0; j < N - i - 1; j++)
{
if (m[j] > m[j + 1])
{
r = m[j];
m[j] = m[j + 1];
m[j + 1] = r;
}
}
}
}
// Просеивание - создание "дырок" в массиве
public void Make0()
{
int k = 0;
int j;
while (k < N - 1)
{
j = k;
while (j < N - 1)
{
j++;
if (m[k] * 2 == m[j] && m[j] != 0)
{
m[j] = 0;
x++;
break;
}
}
k++;
}
}
// Удаление "дырок" в массиве
public void Del0()
{
int[] mass = new int[N - x];
int k = 0;
foreach (int p in m)
{
if (p != 0)
{
mass[k] = p;
k++;
}
}
m = mass;
}
// Вывод для проверки
public void ConsoleOut(string s)
{
Console.WriteLine(s);
for (int i = 0; i < m.Length; i++)
Console.Write(m[i] + " ");
Console.WriteLine();
}
// Вывод в файл
public void Output()
{
StreamWriter sw;
try
{
FileInfo fi = new FileInfo("output.txt"); // информация о файле
sw = fi.CreateText(); // поток для записи
for (int j = 0; j < m.Length; j++)
sw.WriteLine(m[j].ToString()); // запись строк в файл
sw.Close();
}
catch // обработка исключений
{
Console.WriteLine("Невозможность записи в файл output.txt !");
}
}
}
class Program
{
static void Main()
{
Sieve arr = new Sieve();
arr.Input();
arr.ConsoleOut("Исходные данные:");
arr.Sort();
arr.ConsoleOut("После сортировки:");
arr.Make0();
arr.ConsoleOut("После удаления с нулями:");
arr.Del0();
arr.ConsoleOut("Результат:");
arr.Output();
Console.ReadKey();
}
}
}
Результат для контрольного примера
Исходные данные:
3 4 2 1 2 6 8 16
После сортировки:
1 2 2 3 4 6 8 16
После удаления с нулями:
1 0 2 3 0 0 8 0
Результат:
1 2 3 8
NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.
|
|
|
|