1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
| using System;
using System.Collections.Generic;
using System.Linq;
namespace Rocks
{
class Rocks
{
static public int GlobalMin { get; set; } // Минимальный вес
static public int GlobalMax { get; set; } // Максимальный вес
static public int Stages { get; set; } // кол-во взвешиваний
static public int N { get; set; } // Задаваемое N
static public int LastTmpMin { get; set; } // Если список минимальных весов - нечетный, храним отдельно последний элемент
static public int LastTmpMax { get; set; } // По аналогии с предыдущим пунктом
// Число камней
static public int AmountOfRocks
{
get
{
return (2*N + 1);
}
}
// Число взвешиваний
static public int AmountOfWeighings
{
get
{
return (3*N);
}
}
// Функция разбиения массива на пары
static public List<List<int>> GetPairs(int[] weights)
{
var pairs = new List<List<int>>(); // Список пар
var pair = new List<int>(); // Пара
// Если во входном массиве больше 2х элеентов и его длина - нечетная, обрезаем последний элемент
var rightBorder = (weights.Length > 2 && weights.Length % 2 != 0) ? 1 : 0;
// Если массив единичной длины, возвращаем список из 1 элемента
if (weights.Length == 1)
{
pairs.Add(new List<int> {weights[weights.Length - 1]});
return pairs;
}
// Формируем пары элементов
for (var i = 0; i < weights.Length - rightBorder; i++)
{
pair.Add(weights[i]);
if (i % 2 != 0)
{
pairs.Add(pair);
pair = new List<int>();
}
}
return pairs;
}
// Рекурсивная функция нахождения минимакса (при первом проходе 2й массив = null, т.к. еще не было разбиения на минимумы и максимумы)
static void GetMinMax(List<List<int>> min, List<List<int>> max)
{
// Списки минимумов и максимумов во входных парах
var arrayOfMax = new List<int>();
var arrayOfMin = new List<int>();
// В случае не первого прохода
if (max != null)
{
// Если входные данные содержат по 1 элементу (последнее сравнение)
if (min[0].Count == 1 && max[0].Count == 1)
{
// Случай с нечетным числом минимаксов
if (LastTmpMin != 0 && LastTmpMax != 0)
{
// Формируем пары оставшихся элементов с последними (ранее обрезанными)
var lastMin = new[] { min[0].ElementAt(0), LastTmpMin };
var lastMax = new[] { max[0].ElementAt(0), LastTmpMax };
var minPair = GetPairs(lastMin);
var maxPair = GetPairs(lastMax);
LastTmpMax = 0;
LastTmpMin = 0;
// Последнее сравнение для пределения минимального и максимального весов
GetMinMax(minPair, maxPair);
}
else
{
// Заносим наши минимумы и максимумы в глобальные переменные
GlobalMax = max[0].ElementAt(0);
GlobalMin = min[0].ElementAt(0);
}
return;
}
}
// Стадии взвешиваний с формированием списка минимумов и максимумов
for (var i = 0; i < min.Count; i++)
{
Stages++;
arrayOfMin.Add(min[i].Min());
// Не первый проход
if (max != null)
{
Console.WriteLine("Взвешивание {0}. Сравниваем {1} и {2}. Минимум = {3}.", Stages, min[i].ElementAt(0), min[i].ElementAt(1), min[i].Min());
arrayOfMax.Add(max[i].Max());
Stages++;
Console.WriteLine("Взвешивание {0}. Сравниваем {1} и {2}. Максимум = {3}.", Stages, max[i].ElementAt(0), max[i].ElementAt(1), max[i].Max());
}
else
{
// При первом проходе массив единственный
arrayOfMax.Add(min[i].Max());
Console.WriteLine("Взвешивание {0}. Сравниваем {1} и {2}. Минимум = {3}, максимум = {4}.", Stages, min[i].ElementAt(0), min[i].ElementAt(1), min[i].Min(), min[i].Max());
}
}
// Если при первом проходе определилось нечетное число минимаксов, запоминаем последние элементы в глобальные переменные
if (max == null)
{
if (arrayOfMin.Count % 2 != 0 && arrayOfMin.Count > 2)
{
LastTmpMin = arrayOfMin[arrayOfMin.Count - 1];
LastTmpMax = arrayOfMax[arrayOfMax.Count - 1];
}
}
// Формируем пары минимаксов
var minPairs = GetPairs(arrayOfMin.ToArray());
var maxPairs = GetPairs(arrayOfMax.ToArray());
// Рекурсивно вычисляем минимаксы от уже имеющихся
GetMinMax(minPairs, maxPairs);
}
static void Main()
{
var n = 0;
Console.Write("N = ");
int.TryParse(Console.ReadLine(), out n);
N = n;
var weights = new int[AmountOfRocks];
Console.WriteLine("Число камней = {0}", AmountOfRocks);
Console.WriteLine("Число взвешиваний = {0}", AmountOfWeighings);
Console.WriteLine();
if (AmountOfWeighings > 0)
{
string[] splittedData;
// Ввод данных осуществляется через пробел
while (true)
{
Console.Write("Введите веса камней: ");
var inputData = Console.ReadLine();
if (inputData != null)
{
splittedData = inputData.Split(' ');
if (splittedData.Length == AmountOfRocks)
break;
}
}
// Формируем массив весов
for (var i = 0; i < AmountOfRocks; i++)
{
int.TryParse(splittedData[i], out n);
weights[i] = n > 0 ? n : 1;
}
// Запоминаем последний элемент списка
var lastElement = weights[weights.Length - 1];
Console.WriteLine();
// Первый проход: массив общий, посему второй параметр = null.
// Предварительно разбиваем массив весов на пары.
// В результате рекурсивного выполнения данной функции, мы получим глобальный минимакс без последних
// двух итераций (когда происходит сравнение с последним элементом).
GetMinMax(GetPairs(weights), null);
// Подготовка последних двух взвешиваний: найденный ранее минимакс сравнивается с поледним элементом
var lastMin = new[] { GlobalMin, lastElement };
var lastMax = new[] { GlobalMax, lastElement };
var minPair = GetPairs(lastMin);
var maxPair = GetPairs(lastMax);
GetMinMax(minPair, maxPair);
Console.WriteLine();
Console.WriteLine("Минимальный вес камня = {0}", GlobalMin);
Console.WriteLine("Максимальный вес камня = {0}", GlobalMax);
Console.WriteLine("Число взвешиваний = {0}", Stages);
}
else
Console.WriteLine("Число взвешиваний должно быть величиной положительной!");
}
}
} |