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

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

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


Задача 19: до минимального элемента списка вставить среднее арифметическое всех элементов.

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

1.  Надо создать список с методами добавления (пусть в голову), печати.

Эти задачи уже рассматривались ранее.

2. Так  же  для  решения  этой  задачи  необходимо  найти  среднее арифметическое элементов    списка. Для этого надо сумму всех элементов разделить на их количество. А для этого нужно найти сумму всех элементов и их количество. А для этого надо объявить сумму всех элементов и их количество.

Если    количество     элементов      равно  0          (т. е.    список            пуст),  то        надо выкинуть исключение. Ловить его будем в главной программе.

Что бы пройти по всем элементам, мы должны идти от головы до конца списка включительно, т. е. пока текущий элемент существует.

В виде кодов реализация довольно проста:

public double getMiddle() {

int count = 0;

double sum = 0;

for (ListNode temp = head; temp != null; temp = temp.next) {

sum += temp.data;

count++;

}

if (count == 0) {

throw new ApplicationException("Список  пуст");

}

return sum / count;

}

 

3. Теперь надо найти минимальный элемент, что бы до него вставить данные. А для этого надо пройтись по всему списку. В целом алгоритм поиска идентичен поиску в массиве. Приведем реализацию данного алгоритма:

public int getMin() {

if (head == null) {

throw new ApplicationException("Список  пуст");

}

int min = head.data;

for (ListNode temp = head.next; temp != null; temp =

temp.next) {

if (temp.data < min) {

min = temp.data;

}

}

return min;

}

4.  Теперь осталось вставить среднее арифметическое (вернее округление от  него,    потому            что      в            списке мы       храним            целые  числа) перед

минимальным. Список характеризуется головой, поэтому надо рассмотреть случай, когда минимальное число находится в голове и не в голове.

5.  Рассмотрим 2 ситуации:

1   ситуация:

 

Среднее арифметическое элементов будет 3,25, т. е. 3. После вставки элемента будет следующая картина:

 

Т. е. изменится голова.

Если  минимальное  значение  находится  в  голове,  то  выполняются следующие шаги:

1 шаг

 

2 шаг

3 шаг

 

В виде кодов реализация довольно проста:

public void process() {

if (head == null) {

throw new ApplicationException("Список  пуст");

}

int middle = (int)Math.Round(getMiddle());

int min = getMin();

if (head.data == min) {

ListNode temp = new ListNode(middle, null);

temp.next = head;

head = temp;

} else {

//логика вставки  не   в голову

}

}

 

2          ситуация:

 

Очевидно,  что  после  обработки  второй  ситуации  список  будет  иметь следующий вид:

 

Нарисуем промежуточные шаги:

1 шаг

 

2 шаг

 

3 шаг

 

Очевидно, что в рисунке изменился указатель на next в элементе со значением 7. Поэтому для выполнения задания нам надо найти этот элемент (пусть мы его нашли и записали в переменную curNode). Это элемент, который стоит перед минимальным. Т. е. минимальный стоит после него (curNode.temp). А минимальный элемент – этот тот, данное в котором равно минимальному, т. е.   curNode.temp.data   ==   min.   Если   мы   пишем   curNode.temp.data,   то curNode.temp должно  быть  не  равно  null.  Так  же  очевидно,  что  поиск  мы должны начать с головы списка. Естественно, при поиске мы должны перемещаться на следующий элемент. При этом ситуация, когда минимальный элемент  находится  в  голове,  уже  обработана.  Поэтому  алгоритм  поиска элемента перед минимальным материализуется в следующем виде:

public void process() {

if (head == null) {

throw new ApplicationException("Список  пуст");

}

int middle = (int)Math.Round(getMiddle());

int min = getMin();

if (head.data == min) {

ListNode temp = new ListNode(middle, null);

temp.next = head;

head = temp;

} else {

ListNode prevNode = head;

for (; prevNode.next != null; prevNode = prevNode.next) {

if (prevNode.next.data == min) {

break;

}

}

//логика  вставки  нового элемента

}

}

Логику  вставки  легко  реализовать,  глядя  на  рисунки  промежуточных шагов во второй ситуации:

ListNode temp = new ListNode(middle, null);

temp.next = prevNode.next;

prevNode.next = temp;

Приведем полный код реализации обработки списка:

public void process() {

if (head == null) {

throw new ApplicationException("Список  пуст");

}

int middle = (int)Math.Round(getMiddle());

int min = getMin();

if (head.data == min) {

ListNode temp = new ListNode(middle, null);

temp.next = head;

head = temp;

} else {

ListNode prevNode = head;

for (; prevNode.next != null; prevNode = prevNode.next) {

if (prevNode.next.data == min) {

break;

}

}

ListNode temp = new ListNode(middle, null);

temp.next = prevNode.next;

prevNode.next = temp;

}

}

Очевидно, что ее можно немного оптимизировать:

public void process() {

if (head == null) {

throw new ApplicationException("Список  пуст");

}

int middle = (int)Math.Round(getMiddle());

int min = getMin();

if (head.data == min) {

head = new ListNode(middle, head);

} else {

ListNode prevNode = head;

for (; prevNode.next != null; prevNode = prevNode.next) {

if (prevNode.next.data == min) {

break;

}

}

prevNode.next = new ListNode(middle, prevNode.next);

}

}

И приведем полный код задачи:

using System;

 

namespace ConsoleApplication17 {

class Program {

static void Main() {

try {

SimpleList myList = new SimpleList(); Console.Write("Введите  количество  элементов списка:  "); int n = Int32.Parse(Console.ReadLine());

Random r = new Random();

for (int i = 0; i < n; i++) {

int curValue = r.Next(100);

myList.addToHead(curValue);

}

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

myList.print();

myList.process();

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

myList.print(); Console.ReadKey();

} catch {

Console.WriteLine("Список  пуст");

}

}

}

class ListNode { public int data; public ListNode next;

public ListNode(int _data, ListNode _next) {

data = _data;

next = _next;

}

}

 

class SimpleList {

public ListNode head = null;

public void addToHead(int newData) {

head = new ListNode(newData, head);

}

public void process() {

if (head == null) {

throw new ApplicationException("Список  пуст");

}

int middle = (int)Math.Round(getMiddle());

int min = getMin();

if (head.data == min) {

head = new ListNode(middle, head);

} else {

ListNode prevNode = head;

for (; prevNode.next != null; prevNode = prevNode.next) {

if (prevNode.next.data == min) {

break;

}

}

prevNode.next = new ListNode(middle, prevNode.next);

}

}

public int getMin() {

if (head == null) {

throw new ApplicationException("Список  пуст");

}

int min = head.data;

for (ListNode temp = head.next; temp != null; temp =

temp.next) {

if (temp.data < min) {

min = temp.data;

}

}

return min;

}

public double getMiddle() {

int count = 0;

double sum = 0;

for (ListNode temp = head; temp != null; temp = temp.next) {

sum += temp.data;

count++;

}

if (count == 0) {

throw new ApplicationException("Список  пуст");

}

return sum / count;

}

public void print() {

for (ListNode curNode = head; curNode != null; Console.Write(curNode.data + " "), curNode = curNode.next) ;

Console.WriteLine();

}

}

}