Необходимо определить произведение элементов массива, расположенных между максимальным и центральным элементами массива (предполагается что число элементов — нечётное и максимальный единственный. Если по какой-либо причине вычислить произведение не удается, выдать об этом сообщение с указанием причины. Я написал небольшой код, но он находит произведение максимального и минимального.. как найти центральный элемент?
class smth2
{
public void Main2()
{
int[] array = new int[10];
Random rand = new Random();
// заполняем массив случайными значениями
for (int i = 0; i < array.Length; i++)
array[i] = rand.Next(0, 10);
//
int max = array[0], min = array[0];
int maxIndex = 0, minIndex = 0;
// Находим максимальный и минимальный элемент вместе с индекчом
for (int i = 0; i < array.Length; i++)
{
if (array[i] >= max) { max = array[i]; maxIndex = i; }
if (array[i] <= min) { min = array[i]; minIndex = i; }
}
int kol = 0;
foreach (var item in array)
{
Console.WriteLine("{0} Индекс: {1}", item.ToString(), kol);
kol++;
}
Console.WriteLine("nmax is {0} with index {1} and min is {2} with index {3}", max, maxIndex, min, minIndex);
// произведение
double value = 1;
for (int i = 0; i < array.Length; i++)
{
if (minIndex < maxIndex)
{
if (i > minIndex && i < maxIndex)
{
value = value * array[i];
}
}
else if (maxIndex < minIndex)
{
if (i < minIndex && i > maxIndex)
{
value = value * array[i];
}
}
}
Console.WriteLine("Произведение равно {0}", value);
Console.ReadLine();
}
}```
Эникейщик
25.1k7 золотых знаков30 серебряных знаков46 бронзовых знаков
задан 3 мар 2022 в 5:31
1
int[] arr = new int[5] { 1, 10, 4, 6, 11 };
if (arr.Length % 2 == 0)
throw new ArgumentException("Массав должен иметь нечётное количество элементов");
int averageValue = arr[arr.Length / 2];
int averageIndex = Array.IndexOf(arr, averageValue);
var maxValue = arr.Max();
int maxIndex = Array.IndexOf(arr, maxValue);
try
{
var result = averageIndex <= maxIndex
? arr.Skip(averageIndex).Take(maxIndex - averageIndex + 1).Aggregate((x, y) => x * y)
: arr.Skip(maxIndex).Take(averageIndex - maxIndex + 1).Aggregate((x, y) => x * y);
Console.WriteLine(result);
}
catch (Exception ex)
{
Console.WriteLine(ex.ToString());
}
Console.ReadKey();
ответ дан 4 мар 2022 в 8:01
FrehzyFrehzy
1,2906 серебряных знаков18 бронзовых знаков
3
Находим значение «центрального» элемента:
var mV = array.[int.Parse(Math.Ceiling(array.Length / 2))]
Находим значение максимального:
var maxV = array.Max();
Находим произведение центрального и минимального:
var resut = mV * maxV;
ответ дан 3 мар 2022 в 10:45
KunoichiKunoichi
2,30518 серебряных знаков60 бронзовых знаков
1
this is my question:
Given an int array of length=6, i’d would like to know which pair of numbers that belongs to the array, is the center of it. That means that if you divide the array into 3 smalls arrays of length==2, and if you put them as single pair of coordinates in a matrix, (where the first coordinate means the value of the i, and the second one means the value of the j), you would get something like an «L», on your matrix. So, the center is the small coordinate of length=2 that’s in the midle of the L. I know it’s pretty confusing, so here’s an image:
PD: the only pair of «small arrays» available are:
{array[0],array[1]}
{array[2],array[3]}
{array[4],array[5]}
Hope you can help me! I’m making the logic of a game! Sorry for my English!
asked Nov 8, 2013 at 21:54
6
Your example is wrong ! your array should be |0|0|0|1|1|0|
A simple way to check it would be :
|0|1|2| 3 | 4 |5|
|x|y|x|y(+/-)1|x(+/-)1|y|
or
|0|1| 2 |3|4| 5 |
|x|y|x(+/-)1|y|x|y(+/-)1|
To check if the center is c(x=0,y=1) :
check if same value of x (index 0) is in index 2 and equal to (value in index 4 (+/-)1) AND if same value of y (index 1) is in index 3 and equal to (value in index 5 (+/-)1)
OR check if same value of x (index 0) is in index 4 and equal to (value in index 2 (+/-)1) AND if same value of y (index 1) is in index 5 and equal to (value in index 3 (+/-)1)
PS. in the above case I fixed the L length to 1 you can change that and use another value 4, 5 etc.
answered Nov 8, 2013 at 22:18
Mehdi KaramoslyMehdi Karamosly
5,3682 gold badges30 silver badges49 bronze badges
3
When the given three co-ordinates of the cells form «L» shape, two cells will be opposite to each other. That is those two cells will have points like (a,b) and (b,a). So the point other than these two will become the center.
So simply find the two points which are like (a,b) and (b,a). The other point will be the center.
if First, second and three are three points of the form (a,b)
something like
if(first.a==second.b && first.b=second.a)
return three;
if(second.a==three.b && second.b==three.a)
return first;
else return second;
Tom Leese
19.2k12 gold badges43 silver badges69 bronze badges
answered Nov 11, 2013 at 10:54
1
I’m not sure if I understand your question, you are given an arbitrary array of length 6 that contains some L-Shape of unknown orientation, and you must return the slice in the array that is the center?
Well, how would we figure out where the center is? It’s going to be the x and y coordinate that is repeated twice. So just look for the x value that is repeated twice, then look for your y value that is repeated twice. You now have your center.
answered Nov 8, 2013 at 22:14
hankdhankd
6493 silver badges12 bronze badges
first i could not understand your question properly.If what i understood is right then here is soluton.eg:You have an int array of lenght 10.you wanna put every two element in separate array and find the midle array in that order.
So if length of your input array is even then just do (length of array)/2 ,which in our case is 5.Then obviously yur mid array will be the array containing 5 th and 6 th element in the original input array
if length of your input array is odd then just do (length of array+1)/2 ,which in our case is 6.Then obviously yur mid array will be the array containing 6 th and 7 th element in the original input array.But in this case last array wont have jth co-ordinate .
You havenot specified about the lenght of the array.
answered Mar 27, 2014 at 13:07
Renganathan VRenganathan V
4031 gold badge9 silver badges27 bronze badges
You can use an array of 3 Points. A Point is a Java class that holds an x and y value.
Your 3 Points shaded red in the illustration would be:
0, 1
0, 0
1, 0
Another L shaped set of points would be:
2, 2
3, 2
3, 1
answered Nov 8, 2013 at 22:10
Gilbert Le BlancGilbert Le Blanc
49.9k6 gold badges66 silver badges111 bronze badges
2
I believe you are just looking for an average:
i = (array[0] + array[2] + array[4])/3;
j = (array[1] + array[3] + array[5])/3;
answered Nov 8, 2013 at 22:07
JasonJason
13.3k14 gold badges73 silver badges123 bronze badges
2
все правильно, вот только видите какое «большое» время? это для одной звезды. первый метод для того же примера дает
| Matlab M | ||
|
Добавлено через 1 минуту
Сообщение от Nick07
Какой смысл, кроме академического, ускорять этот код?
на самом деле никакого смысла нет. просто хочется убыстрить. когда звезд сотни и больше, время становится уже существенным
Добавлено через 2 минуты
Сообщение от Centurio
Я предлагаю гораздо более короткий вариант:
вот это я и искал. я делал через циклы и это как то напрягало, и много лишнего было
Добавлено через 26 минут
теперь немножко усложняю задачку. теперь есть 2 звезды. есть координаты вершин прямоугольников, которые ограничивают звезды. Я выбираю каждый раз один прямоугольник со звездой и нахожу центр звезды.
| Matlab M | ||
|
Проблема состоит в следующем. Каждый раз как я выбираю очередной прямоугольник, программа все считает с 1! Например, было, ymin = 11, ymax = 19, стало ymin = 1, ymax = 9, т.е. программа не сохраняет исходные номера. И как результат выдает неправильные ответы.
TLDR
Бинарный поиск элемента в отсортированном массиве
Рассмотрим задачу: дан массив a[], состоящий из целых чисел, и требуется найти в нём элемент x. Если x присутствует в a, то нужно вернуть его индекс (если x встречается несколько раз, то можно вернуть любой из подходящих индексов), иначе, если x нет, — вернуть -1.
Простейший способ решить такую задачу — пройти по всем элементам массива и сравнить их с x:
int search(int a[], int size, int x) { // ищем x в массиве a размера size
for (int i = 0; i < size; i++) // перебираем все элементы массива
if (a[i] == x) // если элемент равен x,
return i; // возвращаем его индекс
return -1; // если не встретили x, возвращаем -1
}
Такое решение называют линейным поиском. Очевидно, что количество действий, которые данный алгоритм выполняет в худшем случае (когда x отсутствует в массиве), пропорционально размеру массива (поиск выполняется за O(N)).
Если массив отсортирован, то мы можем использовать более эффективную стратегию. Пусть массив упорядочен по возрастанию, тогда:
- Найдём центральный элемент массива и сравним его с x. Если он равен x, то ответ найден;
- Если центральный элемент меньше x, то искать ответ имеет смысл только в правой половине массива (так как слева все элементы тоже меньше x);
- Если центральный элемент больше x, то искать ответ имеет смысл только в левой половине массива (так как справа все элементы тоже больше x);
- При переходе в ту или иную половину мы снова определяем в ней средний элемент и сравниваем его с x, и так далее, пока ответ не будет найден или пока в рассматриваемой области не останется элементов.
Для того, чтобы отслеживать текущую область поиска, заведём индексы l и r. Будем считать, что поиск производится в отрезке от l до r включительно; таким образом, изначально l = 0, r = size — 1. Зная l и r, середину можно найти как (l + r) / 2 или l + (r — l) / 2.
int binarySearch(int a[], int size, int x) { // ищем x в отсортированном массиве a размера size
int l = 0, r = size - 1; // ищем в отрезке [l; r]. изначально это весь массив
while (l <= r) { // пока в отрезке поиска есть хотя бы один элемент,
int m = l + (r - l) / 2; // находим индекс среднего элемента отрезка
if (a[m] == x) // если средний элемент равен x,
return m; // возвращаем его индекс
else if (a[m] < x) // если средний элемент меньше x,
l = m + 1; // продолжаем искать в правой половине - [m + 1; r]
else // если средний элемент больше x,
r = m - 1; // продолжаем искать в левой половине - [l; m - 1]
}
return -1 // если не встретили x, возвращаем -1.
}
Такое решение называют бинарным поиском. Бинарный поиск гораздо быстрее линейного, так на каждой итерации он сокращает область поиска в два раза (поиск выполняется за O(logN)).
| Размер массива | Линейный поиск | Бинарный поиск |
| 10 | 10 | 4 |
| 100 | 100 | 7 |
| 1000 | 1000 | 10 |
| 106 | 106 | 20 |
| 109 | 109 | 30 |
Для бинарного поиска массив должен быть отсортирован, в общем случае сортировка требует времени O(NlogN).
- Если элемент ищется лишь один раз, а массив не отсортирован, то выгоднее использовать линейный поиск (O(N) выгоднее, чем O(NlogN) + O(logN));
- Если элементы ищутся много раз, то выгоднее отсортировать массив и использовать бинарный поиск (O(NlogN) + много O(logN) выгоднее, чем много O(N));
- Если элементы добавляются и удаляются, то вместо отсортированного массива следует использовать другую коллекцию — двоичное дерево поиска или хеш-таблицу;
- При помощи хеш-таблицы можно решать исходную задачу эффективнее, чем двоичным поиском, — за константное время (O(1)). Но идея двоичного поиска применима в существенно более широком наборе задач, как мы увидим далее.
Левый и правый бинарный поиск
Рассмотренная выше задача, в которой требуется найти любое вхождение заданного элемента в массив, встречается сравнительно редко и представляет мало интереса. Гораздо важнее другой вид задач: дан отсортированный массив a[] и требуется найти в нём индекс первого или последнего вхождения числа x (или индекс последнего элемента, меньшего x, или индекс первого элемента, большего x).
При решении данной задачи мы уже не можем сразу вернуть индекс, как только нашли элемент, равный x, и функцию поиска придётся усложнить.
Оказывается, что написание бинарного поиска первого или последнего вхождения — достаточно трудная задача. Программист вынужден держать в голове множество тонких моментов. Вот некоторые из них:
- Является ли диапазон от l до r отрезком или полуинтервалом, как он отсортирован, содержит ли он искомый элемент;
- Как следует проверять центральный элемент и как смещать границы: l = m или l = m + 1, r = m или r = m — 1;
- Будет ли поиск правильно работать на массивах из 0, 1, 2 элементов;
- Какой из индексов в итоге указывает на ответ, как проверить, что ответ отсутствует, и др.
Правила написания бинарного поиска без головной боли
- Диапазон от l до r — всегда отрезок (включительно, [l; r]), изначально l = 0, r = size — 1. Искомый элемент изначально может как быть в отрезке, так и не быть, это не важно;
- Поиск всегда осуществляется до двух элементов (while (l + 1 < r));
- После проверки среднего элемента границы всегда смещаются только на середину (l = m или r = m, никаких плюс-минус единиц);
- Смещение границ должно происходить так, чтобы не потерять искомый элемент (чтобы он не выпал из отрезка [l; r], если он там был).
- Пример: массив отсортирован по неубыванию, ищем первый элемент, равный x. Простые, очевидные случаи: если a[m] < x, то l = m; если a[m] > x, то r = m. Более важный и трудный случай: a[m] == x. Если мы сдвинем левую границу, то можем потерять первый x, а если сдвинем правую — не потеряем. Поэтому нужно двигать правую: r = m.
- Подобным же образом нужно рассуждать во всех аналогичных задачах. Запоминать условия не нужно.
- Когда цикл завершится, останутся два соседних элемента — a[l] и a[r]. Их нужно проверить по отдельности. При этом, если мы ищем первое вхождение чего-либо, то сначала проверяем a[l], затем a[r]; если ищем последнее вхождение — сначала a[r], затем a[l].
Следуя этим правилам, вы сможете практически единообразно писать различные виды левых и правых двоичных поисков. Сравните показанные ниже примеры: в них меняются только условие проверки среднего элемента (выделено красным) и порядок проверки последних двух элементов (выделено оранжевым).
// сорт. по неубыванию
// последний элемент < x
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] < x)
l = m;
else
r = m;
}
if (a[r] < x)
return r;
if (a[l] < x)
return l;
return -1;
|
// сорт. по неубыванию
// последний элемент <= x
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] <= x)
l = m;
else
r = m;
}
if (a[r] <= x)
return r;
if (a[l] <= x)
return l;
return -1;
|
// сорт. по неубыванию
// последний элемент == x
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] <= x)
l = m;
else
r = m;
}
if (a[r] == x)
return r;
if (a[l] == x)
return l;
return -1;
|
// сорт. по неубыванию
// первый элемент > x
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] <= x) // if (a[m] > x)
l = m; // r = m;
else // else
r = m; // l = m;
}
if (a[l] > x)
return l;
if (a[r] > x)
return r;
return -1;
|
// сорт. по неубыванию
// первый элемент >= x
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] < x) // if (a[m] >= x)
l = m; // r = m;
else // else
r = m; // l = m;
}
if (a[l] >= x)
return l;
if (a[r] >= x)
return r;
return -1;
|
// сорт. по неубыванию
// первый элемент == x
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] < x) // if (a[m] >= x)
l = m; // r = m;
else // else
r = m; // l = m;
}
if (a[l] == x)
return l;
if (a[r] == x)
return r;
return -1;
|
// сорт. по невозрастанию
// последний элемент > x
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] > x)
l = m;
else
r = m;
}
if (a[r] > x)
return r;
if (a[l] > x)
return l;
return -1;
|
// сорт. по невозрастанию
// последний элемент >= x
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] >= x)
l = m;
else
r = m;
}
if (a[r] >= x)
return r;
if (a[l] >= x)
return l;
return -1;
|
// сорт. по невозрастанию
// последний элемент == x
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] >= x)
l = m;
else
r = m;
}
if (a[r] == x)
return r;
if (a[l] == x)
return l;
return -1;
|
// сорт. по невозрастанию
// первый элемент < x
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] >= x) // if (a[m] < x)
l = m; // r = m;
else // else
r = m; // l = m;
}
if (a[l] < x)
return l;
if (a[r] < x)
return r;
return -1;
|
// сорт. по невозрастанию
// первый элемент <= x
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] > x) // if (a[m] <= x)
l = m; // r = m;
else // else
r = m; // l = m;
}
if (a[l] <= x)
return l;
if (a[r] <= x)
return r;
return -1;
|
// сорт. по невозрастанию
// первый элемент == x
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (a[m] > x) // if (a[m] <= x)
l = m; // r = m;
else // else
r = m; // l = m;
}
if (a[l] == x)
return l;
if (a[r] == x)
return r;
return -1;
|
// f() возвращает
// сначала true, потом false
// последний f() == true
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (f(a[m]))
l = m;
else
r = m;
}
if (f(a[r]))
return r;
if (f(a[l])
return l;
return -1;
|
// f() возвращает
// сначала false, потом true
// первый f() == true
int l = 0, r = size - 1;
while (l + 1 < r) {
int m = l + (r - l) / 2;
if (!f(a[m])) // if (f(a[m]))
l = m; // r = m;
else // else
r = m; // l = m;
}
if (f(a[l])
return l;
if (f(a[r]))
return r;
return -1;
|
При желании показанный алгоритм можно оптимизировать, сократив количество проверок в конце.
Ссылки
Теория:
- Codeforces EDU — Двоичный поиск
- neerc.ifmo.ru/wiki — Целочисленный двоичный поиск
- neerc.ifmo.ru/wiki — Вещественный двоичный поиск
- brestprog — Бинарный поиск
- algorithmica.org — Бинарный поиск
- Калинин П. — Бинарный поиск
- Brilliant.org — Binary Search
Код:
- CodeLibrary — Binary search
Задачи:
- informatics.mccme.ru — Курс «Поиск и сортировка» — часть 2
- Задачи: Бинарный поиск
Программа должна вывести средний по значению элементы.
На примере такого кода:
#include <stdio.h>
#include <Windows.h>
#define SIZE 10
main() {
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
int m[SIZE], i;
int min, max;
int arithmetic_mean;
static sum_m;
for (i = 0; i <= SIZE - 1; i++) {
printf("Введіть 10 цілочисленних елементів массиву %d: ", i);
scanf_s("%d", &m[i]);
}
min = m[0]; max = m[0];
for (i = 1; i < SIZE - 1; i++) {
if (min > m[i]) {
min = m[i];
}
if (max < m[i]) {
max = m[i];
}
}
for (i = 0; i <= SIZE - 1; i++) {
sum_m += m[i];
arithmetic_mean = sum_m / 10;
}
printf("nМінімальний елемент массиву: %d", min);
printf("nMaксимальний елемент массиву: %d", max);
printf("nСереднє арифметичне цілих чисел массиву: %dn", arithmetic_mean);
}