Название: Алгоритмическое мышление при решении задач (Шамшев А. Б.)

Жанр: Информационные системы и технологии

Просмотров: 1394


Задача 8: удалить те элементы массива, которые встречаются в нем ровно два раза.

Рассуждения:

1.  Данная задача может быть рассмотрена в виде трех шагов:

a.  Ввод данных (задача рассматривалась ранее)

b.  Обработка данных

c.  Вывод обработанных данных (задача рассматривалась ранее)

2.  Очевидно, что из данных у нас есть массив (для конкретики возьмем массив целых чисел) и назовем его data.

3. Для обработки массива необходимо знать только сам массив. Других данных для его обработки не надо. Очевидно, что если обработка заключается в удалении тех элементов массива, которые встречаются в

нем ровно два раза, то в результате обработки массив будет изменятся (а вернее может измениться). Поэтому сигнатура функции обработки будет следующая:

public static void processArray(ref int[] data) {

4.  Как выполнить     обработку       массива?         Для      ответа на        этот     вопрос

переформулируем задание: «Если элемент массива встречается в нем ровно два раза, то удалить его». Казалось бы это верная формулировка, но это не так. Приведем конкретный пример. Пусть у нас есть массив (1,2,3,4,1). Мы проверяем нулевой элемент массива (1). Этот элемент входит в массив два раза. После удаления останется массив (2,3,4,1). И обратите внимание на то, что последняя единица осталась, а по заданию она должна была удалиться. Поэтому сделаем верную переформулировку задания: «Если элемент массива встречается в нем ровно два раза, то удалить все элементы массива, которые равны текущему».

5.  В последней фразе четко просматривается конструкция «Если …, то

…».     При   этом   «удалить   все   элементы   массива,   которые   равны текущему» является удалением по значению, которое рассматривалось

выше. Вспомним сигнатуру функции:

public static void delByValue(ref int[] data, int delValue) { Удаляемое значение равно тому значению элемента массива, который входит в него два раза.

6.  Теперь  возникает  вопрос,  как  найти  условие  в  «Если  …,  то  …».

На естественном языке условие звучит: «Элемент массива встречается в нем ровно два раза». Для ответа на вопрос, сколько раз встречается

элемент массива в массиве, надо знать значение элемента массива и сам массив. Поэтому сигнатура функции будет иметь следующий вид:

/// <summary>

/// Получение количества  вхождений в  массив

/// </summary>

/// <param name="data">массив</param>

/// <param name="curValue">значение, количество  вхождений

///которого  ищется</param>

/// <returns>количество  вхождений</returns>

public static int getCount(int[] data, int curValue) {

 

}

7.  Для того, что бы найти количество вхождений значения в массив, надо

объявить  количество  вхождений.  Очевидно,  что  начальное  значение количества вхождений должно быть равно 0.

8. Для того, что бы найти количество вхождений в  массив, надо просмотреть весь массив. Если текущий элемент равен искомому, то надо увеличить количество вхождений на 1. Поэтому реализация в виде кода этой задачи будет следующая:

public static int getCount(int[] data, int curValue) {

int count = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] == curValue) {

count++;

}

}

return count;

}

 

9.  Вернемся к нашей фразе «элемент массива встречается в нем ровно два раза» и переформулируем ее: «если количество вхождений текущего элемента массива равно двум».

10. Логично предположить, что для выполнения задания надо просмотреть весь       массив.   Поэтому   алгоритм   на   псевдокоде   будет   выглядеть

следующим образом:

 

Для каждого элемента массива

НачалоЦикла

Если количество вхождений текущего элемента равно 2, то

НачалоЕсли

Удалить из массива по значению текущий элемент

ОкончаниеЕсли.

ОкончаниеЦикла

 

11. Необходимо вспомнить, что удаление ведет к изменению индексации,

поэтому

 

Для каждого элемента массива

НачалоЦикла

Если количество вхождений текущего элемента равно 2, то

НачалоЕсли

Удалить из массива по значению текущий элемент Уменьшить текущую позицию в массиве. ОкончаниеЕсли.

ОкончаниеЦикла

 

12. Приведем полную реализацию алгоритма в виде кода:

using System;

 

class Program {

public static void delByValue(ref int[] data, int delValue) {

int countDel = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] == delValue) {

countDel++;

}

}

int[] newData = new int[data.Length - countDel];

int curPos = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] != delValue) {

newData[curPos++] = data[i];

}

}

data = newData;

}

 

/// <summary>

/// Получение количества  вхождений в  массив

/// </summary>

/// <param name="data">массив</param>

/// <param name="curValue">значение, количество  вхождений

которого ищется</param>

/// <returns>количество  вхождений</returns>

public static int getCount(int[] data, int curValue) {

int count = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] == curValue) {

count++;

}

}

return count;

}

 

public static void processArray(ref int[] data) {

for (int i = 0; i < data.Length; i++) {

if (getCount(data, data[i]) == 2) {

delByValue(ref data, data[i]);

i = i - 1;

}

}

}

public static void printArray(int[] data) {

for (int i = 0; i < data.Length; i++) {

Console.Write(data[i] + " ");

} Console.WriteLine();

}

 

private static void fillArray(int[] data) { Random r = new Random();

for (int i = 0; i < data.Length; i++) {

data[i] = r.Next(0, 10);

}

}

 

static void Main(string[] args) { int[] data = new int[10]; fillArray(data);

Console.Write("Массив  до   обработки: ");

printArray(data);

processArray(ref data); Console.Write("Массив  после  обработки: "); printArray(data);

Console.ReadKey();

}

}

 

12.Как видно из приведенного кода, этот пример уже приближается к программе. Поэтому возникает вопрос об элементах технологии написания          программ.   Пока   программа   написана   в   процедурно- ориентированном стиле. Этот стиль программирования уже существует давно. В нем программа состоит из множества процедур (или функций), множества данных, последовательности вызова процедур с передачей данных           (последовательность  может   быть   нелинейной).   Однако   в современном программировании намного чаще процедурно- ориентированного       стиля    используется    объектно-ориентированный стиль.

13.Возникает вопрос, как перейти от процедурно-ориентированного стиля к объектно-ориентированному. Для этого в примере надо сделать несколько шагов. Вначале заметим, что все процедуры принимают в качестве одного из параметров массив чисел. Только в части процедур это изменяемый параметр, а в части – неизменяемый. Интуитивно понятно,  что  не  изменяемый  параметр  –  «частный  случай» изменяемого параметра, только изменение никогда не происходит. Поэтому необходимо   добавить   в   каждую   процедуру   к   массиву

ключевое  слово  ref.  После  этого  код  будет  выглядить  следующим образом:

using System;

 

class Program {

 

public static void delByValue(ref int[] data, int delValue) {

int countDel = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] == delValue) {

countDel++;

}

}

int[] newData = new int[data.Length - countDel];

int curPos = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] != delValue) {

newData[curPos++] = data[i];

}

}

data = newData;

}

 

public static int getCount(ref int[] data, int curValue) {

int count = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] == curValue) {

count++;

}

}

return count;

}

 

public static void processArray(ref int[] data) {

for (int i = 0; i < data.Length; i++) {

if (getCount(ref data, data[i]) == 2) {

delByValue(ref data, data[i]);

i = i - 1;

}

}

}

 

public static void printArray(ref int[] data) {

for (int i = 0; i < data.Length; i++) { Console.Write(data[i] + " ");

} Console.WriteLine();

}

 

private static void fillArray(ref int[] data) { Random r = new Random();

for (int i = 0; i < data.Length; i++) {

data[i] = r.Next(0, 10);

}

}

 

static void Main(string[] args) { int[] data = new int[10]; fillArray(ref data);

Console.Write("Массив  до   обработки: ");

printArray(ref data); processArray(ref data); Console.Write("Массив  после  обработки: "); printArray(ref data);

Console.ReadKey();

}

}

 

14. Если внимательно посмотреть на код, то видно, что переменная data используется везде в программе. Поэтому ее надо разместить так, что бы она была видна везде в программе. Очевидно, что объявление переменной должно быть внутри класса Program. При этом data станет во всех процедурах автоматически ref, поскольку все процедуры будут работать с одним экземпляром массива. Так же следует отметить, что из-за того, что data должна быть объявленной внутри класса Program, в объявлении должно быть ключевое слово static. Поэтому код примет следующий вид:

using System;

 

class Program {

public static int[] data;

 

public static void delByValue(int delValue) {

int countDel = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] == delValue) {

countDel++;

}

}

int[] newData = new int[data.Length - countDel];

int curPos = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] != delValue) {

newData[curPos++] = data[i];

}

}

data = newData;

}

 

public static int getCount(int curValue) {

int count = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] == curValue) {

count++;

}

}

return count;

}

 

public static void processArray() {

for (int i = 0; i < data.Length; i++) {

if (getCount(data[i]) == 2) {

delByValue(data[i]);

i = i - 1;

}

}

}

 

public static void printArray() {

for (int i = 0; i < data.Length; i++) { Console.Write(data[i] + " ");

} Console.WriteLine();

}

 

public static void fillArray() { Random r = new Random();

for (int i = 0; i < data.Length; i++) {

data[i] = r.Next(0, 10);

}

}

 

static void Main() { data = new int[10]; fillArray();

Console.Write("Массив  до   обработки: ");

printArray();

processArray();

Console.Write("Массив  после  обработки: ");

printArray();

Console.ReadKey();

}

}

 

15.Обратите внимание, как теперь читается Main в программе – создать массив, заполнить массив, вывести массив, обработать массив, вывести массив. Однако класса для выполнения задачи еще нет. Поэтому объявим          класс  для  обработки  задачи,  заменив  название  Main  на mainProcedure. Так же необходимо почти везде убрать слово static (за

исключением Main). А Main оставим пустым. Код примет следующий вид:

using System;

 

class Program {

public class TaskClass {

public int[] data;

 

public void delByValue(int delValue) {

int countDel = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] == delValue) {

countDel++;

}

}

int[] newData = new int[data.Length - countDel];

int curPos = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] != delValue) {

newData[curPos++] = data[i];

}

}

data = newData;

}

 

public int getCount(int curValue) {

int count = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] == curValue) {

count++;

}

}

return count;

}

 

public void processArray() {

for (int i = 0; i < data.Length; i++) {

if (getCount(data[i]) == 2) {

delByValue(data[i]);

i = i - 1;

}

}

}

 

public void printArray() {

for (int i = 0; i < data.Length; i++) { Console.Write(data[i] + " ");

} Console.WriteLine();

}

public void fillArray() { Random r = new Random();

for (int i = 0; i < data.Length; i++) {

data[i] = r.Next(0, 10);

}

}

 

public void mainProcedure() { data = new int[10]; fillArray();

Console.Write("Массив  до   обработки: ");

printArray();

processArray();

Console.Write("Массив  после  обработки: ");

printArray();

Console.ReadKey();

}

}

 

static void Main(string[] args) {

}

}

 

16.Следующим шагом в логике будет простое действие – для того, что бы задачу решить, надо, что бы задача была создана. И после этого задачу можно решать. На самом деле класс TaskClass и есть класс, который представляет из себя задачу. А что бы решить задачу, надо вызвать mainProcedure у задачи. Приведем решение с использованием объектно- ориентированного подхода (только вынеся класс TaskClass из класса Program).

using System;

 

class Program {

static void Main(string[] args) {

TaskClass t = new TaskClass();

t.mainProcedure();

}

}

 

public class TaskClass {

public int[] data;

 

public void delByValue(int delValue) {

int countDel = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] == delValue) {

countDel++;

}

}

int[] newData = new int[data.Length - countDel];

int curPos = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] != delValue) {

newData[curPos++] = data[i];

}

}

data = newData;

}

 

public int getCount(int curValue) {

int count = 0;

for (int i = 0; i < data.Length; i++) {

if (data[i] == curValue) {

count++;

}

}

return count;

}

public void processArray() {

for (int i = 0; i < data.Length; i++) {

if (getCount(data[i]) == 2) {

delByValue(data[i]);

i = i - 1;

}

}

}

public void printArray() {

for (int i = 0; i < data.Length; i++) { Console.Write(data[i] + " ");

} Console.WriteLine();

}

 

private void fillArray() { Random r = new Random();

for (int i = 0; i < data.Length; i++) {

data[i] = r.Next(0, 10);

}

}

 

public void mainProcedure() { data = new int[10]; fillArray();

Console.Write("Массив  до   обработки: ");

printArray();

processArray();

Console.Write("Массив  после  обработки: ");

printArray(); Console.ReadKey();

}

}