Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Java [игнор отключен] [закрыт для гостей] / Есть ли проще способ найти 3 наименьших числа из некого перечня / 25 сообщений из 41, страница 1 из 2
25.02.2016, 20:41
    #39179303
arrt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Код: java
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.
public class Primer { 
static int [] arr={16,56,5,88,3,7,2,4};
static int small1, small2, small3;
public static void min3 () {
if ((arr[2]>arr[1])&&(arr[2]>arr[0])&&(arr[1]>arr[0])) {small1=arr[0];small2=arr[1];small3=arr[2];}
else if ((arr[2]<arr[1])&&(arr[2]<arr[0])&&(arr[1]>arr[0])) {small1=arr[2];small2=arr[0];small3=arr[1];}
else if (arr[2]<arr[1] && arr[2]>arr[0] && arr[1]>arr[0]) {small1=arr[0];small2=arr[2];small3=arr[1];}
else if ((arr[2]<arr[1])&&(arr[2]<arr[0])&&(arr[1]<arr[0])) {small1=arr[2];small2=arr[1];small3=arr[0];}
else if ((arr[2]>arr[1])&&(arr[2]<arr[0])&&(arr[1]<arr[0])) {small1=arr[1];small2=arr[2];small3=arr[0];}
else if ((arr[2]>arr[1])&&(arr[2]>arr[0])&&(arr[1]<arr[0])) {small1=arr[1];small2=arr[0];small3=arr[2];}
for(int i=3; i<arr.length;i++) {
//System.out.println(arr[i]);
//System.out.println(small1+" "+small2+" "+small3);
if ((arr[i]>small3)&&(arr[i]>small1)&&(arr[i]>small2))continue;
else if ((arr[i]<small3)&& (arr[i]>small2) && (arr[i]>small1)) small3=arr[i];
else if ((arr[i]<small3)&& (arr[i]<small2) && (arr[i]>small1)) {int temp=arr[i];small3=small2;small2=temp;}
else if ((arr[i]<small3)&& (arr[i]<small2) && (arr[i]<small1)) {int temp=arr[i]; int temp1=small1; small3=small2; small2=temp1; small1=temp;}  
//System.out.println(small1+" "+small2+" "+small3);
}
System.out.print("Res"+ small1+" "+small2+" "+small3);
}
public static void main(String[] args) { 
min3();
} 
}


//То есть сперва, упорядочиваем первых три числа (согласно 6-и возможным комбинациям их взаиморасположения) с которыми потом идет сравнение в одном цыкле (такое условие) for этого задания (может while имеет лутшую альтернативу?). Потом в этом цыкле, сперва заменяем третье наименьшее число без здвига, или второе - уже со сдвигом второго на место третьего, или первое - уже с двигом на единицу первых двух.
Упростить, что в общем не существенно для структуры, можно через замену последнего else if просто на else, ибо в начале цыкла есть условие проверки есть ли число больше всех текущех трех наименьших чисел
...
Рейтинг: 0 / 0
25.02.2016, 21:04
    #39179314
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Сортировка брат...
...
Рейтинг: 0 / 0
25.02.2016, 21:18
    #39179325
arrt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
mayton, один цыкл надо
...
Рейтинг: 0 / 0
25.02.2016, 21:25
    #39179330
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
arrtmayton, один цыкл надо
Тоже самое что поиск минимального значения, только вместо одной переменной храним три. По ним вложенный цикл будет
...
Рейтинг: 0 / 0
25.02.2016, 21:38
    #39179340
arrt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Blazkowicz, вложенный цикл - это уже два, а мне надо один (который у меня есть и работает)
Но на это у меня пошло несколько часов, чтобы сделать его полностью рабочем, а вроде предполагается на 10-15 минут.
Без упорядочивание первых трех элементов и соответсвуещого выталкивание или сдвига заменяющих ничего не получается, и только на перебор шести комбинаций сколько времени идет
...
Рейтинг: 0 / 0
25.02.2016, 23:14
    #39179386
ivanra
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Если задание допускает использование коллекций, то очень хорошо подойдет PriorityQueue
...
Рейтинг: 0 / 0
25.02.2016, 23:17
    #39179388
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
arrt,

Ещё один гуманитарий. Ну не пиши цикл для трёх. Напиши вместо него три условия.
...
Рейтинг: 0 / 0
25.02.2016, 23:43
    #39179402
Partisan M
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
б-р-р. Точнее, Б-Р-Р. Ещё точнее написать нельзя, т.к. более крупных букв нет. Делаю вывод, что программа была сделана в IDEA. Надо было в Eclipse. Сейчас продемонстрирую разницу между ними. Но сначала теория: выявлять наименьшее значение сортировкой - не лучший способ, поскольку его трудоёмкость (в общем случае) O(N log N), в то время как в цикле можно найти решение за O(N).
Демонстрирую поиск одного минимального значения в цикле:
Код: java
1.
2.
3.
4.
5.
6.
7.
                int [] arr={16,56,5,88,3,7,2,4};
		int m = arr[0];
		for (int i = 1; i < arr.length; i++)
			if (arr[i] < m)
				m = arr[i];
		
		System.out.println (m);



Здесь можно было бы сначала m (минимуму) присвоить произвольное значение меньше минимально возможного, а цикл начинать от 0;
Для демонстрации этого приёма поиска в цикле я и написал этот ответ, а вовсе не чтоб подсказать решение простого учебного примера. Этот приём используется часто.
Обобщаем программный пример на случай поиска 3 минимальных значений. Вот что получается в Eclipse:

Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
                int [] arr={16,56,5,88,3,7,2,4};
                int m1 = arr[0];
                int m2 = arr[0];
		int m3 = arr[0];
		for (int i = 1; i < arr.length; i++) {
			int x = arr [i];
			if (x < m1) {
				m3 = m2;
				m2 = m1;
				m1 = x;
			}
		}
		System.out.println (m1 + "," + m2 + "," + m3);



Отсюда видно, что Eclipse значительно лучше.
...
Рейтинг: 0 / 0
25.02.2016, 23:57
    #39179406
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
arrtmayton, один цыкл надо
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
int[] arr = { 16, 56, 5, 88, 3, 7, 2, 4 };

int i = 0;
int n = arr.length - 1;
int temp;
while (i < n) {
    if (arr[i+1] < arr[i]) {
        temp = arr[i + 1];
        arr[i + 1] = arr[i];
        arr[i] = temp;
        i = 0;
    } else {
        i++;
    }
}
System.out.println(java.util.Arrays.toString(arr));
...
Рейтинг: 0 / 0
25.02.2016, 23:59
    #39179407
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
maytonСортировка брат...+128

Реализация 18865228 взята отсюда: https://ru.wikipedia.org/wiki/Глупая_сортировка
...
Рейтинг: 0 / 0
26.02.2016, 00:01
    #39179408
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Usman https://ru.wikipedia.org/wiki/Глупая_сортировка Бубльсорт в один проход ?
...
Рейтинг: 0 / 0
26.02.2016, 00:04
    #39179409
Partisan M
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Хотя из-за позднего времени я допустил ошибку. Правильно:
[SRC java]int m1 = arr[0];
int m2 = arr[0];
int m3 = arr[0];
for (int i = 1; i < arr.length; i++) {
int x = arr [i];
if (x < m1) {
m3 = m2;
m2 = m1;
m1 = x;
} else if (x < m2) {
m3 = m2;
m2 = x;
} else if (x < m3)
m3 = x;
}
System.out.println (m1 + "," + m2 + "," + m3);
[/SRC]
Всё равно Eclipse получается лучше. Для выявления произвольного числа минимальных элементов можно вместо m1, m2, m3 ввести массив и заполнять его во вложенном цикле, что требует простой переделки этого примера.
...
Рейтинг: 0 / 0
26.02.2016, 00:15
    #39179411
Partisan M
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Usman+128

-100000
Хоть я и люблю объяснять, но не люблю, когда объяснение не доходит. А это вам должны были объяснить ещё в институте.
Поиск наименьшего элемента сортировкой неэффективен, т.к. требует O (N log N) операций, в то время как поиск его в цикле требует O (N) операций. Поиск 3 наименьших элементов в массиве, как легко догадаться, требует тоже O (N) операций, поэтому эффективнее, чем их поиск сортировкой.
Вот простое, но более подробное рассмотрение:
вот
...
Рейтинг: 0 / 0
26.02.2016, 00:43
    #39179418
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Есть еще такая интересная структура данных. Пирамида. Или heap.

Она не сортирует array но создает некую стуктуру данных, удобную
для быстрого буферизирования элементов с приоритетом. Тоесть наверху
всегда - топовый. Достоинства пирамиды - экономия памяти по сравнению
с деревьями.

По сути пирамида - это компромисс между сортировкой и просто поддержкой
структуры данных с max()/min() интерфейсом.
...
Рейтинг: 0 / 0
26.02.2016, 01:15
    #39179429
arrt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Интересное и простое решение от Partisan M, и Usman, особенно последнее с обнулением i. Есть ли такие пособие что учат решению мат. задач на таких примерах(?) именно в java, c++, а то если такое в институте учат - меня не учили никак, потому не знаю.
Хотя само задание было касательно вывода индексов этих трех значений - как вам найти такое? А то спросил сперва о значениях ибо не знал, что все так просто.
...
Рейтинг: 0 / 0
26.02.2016, 07:39
    #39179472
lor2
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
есть такая штука, называется лист. не?
1 коллекшн.сорт(...)
2 соут(лист.гет(лист.сизе-1) .... лист.гет(лист.сизе-3))

не? воще ни одного цикла. )
...
Рейтинг: 0 / 0
26.02.2016, 08:17
    #39179478
golovonometr
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
arrtИнтересное и простое решение от Partisan M, и Usman, особенно последнее с обнулением i. Есть ли такие пособие что учат решению мат. задач на таких примерах(?) именно в java, c++, а то если такое в институте учат - меня не учили никак, потому не знаю.
Хотя само задание было касательно вывода индексов этих трех значений - как вам найти такое? А то спросил сперва о значениях ибо не знал, что все так просто.
а почему теперь тебе самому не попытаться на этих готовых примерах записать куда нибудь индексы этих элементов и отобразить в конце? Вроде как все разжевали выше отписавшиеся, еще бы попросил переменные переименовать как тебе надо))

Почему если ты хочешь найти учебный материал, но не хочешь попробовать и запустить эти примеры у себя? Сохранить индексы этих элементов, даже на алгоритм не тянет, попробуй сделать сам а тут если что подправят;)
...
Рейтинг: 0 / 0
26.02.2016, 09:09
    #39179501
Zenia
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
А по моему в названии топика не вопрос, а утверждение.. Человек хотел поделиться своим многочасовым выс..трудом, а тут ему бульбосорт...
...
Рейтинг: 0 / 0
26.02.2016, 10:26
    #39179558
ivanra
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Решение выглядит просто, если использовать коллекции. Тут используется компаратор, позволяющий искать индексы, а если надо искать сами числа, то код будет еще проще:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
static Collection<Integer> findMin(final int[] arr, int cnt) {
  PriorityQueue<Integer> result = new PriorityQueue<Integer>(cnt, new Comparator<Integer>() {
    @Override
    public int compare(Integer i1, Integer i2) {
      return arr[i2]-arr[i1];
    }
  });
  for (int i=0;i<arr.length;i++) {
    if (i>=cnt) {
      if (result.comparator().compare(i,result.peek())<0) continue;
      result.poll();
    }
    result.offer(i);
  }
  return result;
}
...
Рейтинг: 0 / 0
26.02.2016, 12:22
    #39179691
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
arrtИнтересное и простое решение от Partisan M, и Usman, особенно последнее с обнулением i. Есть ли такие пособие что учат решению мат. задач на таких примерах(?) именно в java, c++, а то если такое в институте учат - меня не учили никак, потому не знаю.
Для быстрого старта - посмотри это видео.

Оно не претендует на теорию. А скорее моделируем процессы, просиходящие про сортировках.

YouTube Video
...
Рейтинг: 0 / 0
26.02.2016, 12:44
    #39179724
Valery Shiskin
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Partisan M,

Может я чего не понимаю, но причем здесь IDE?
...
Рейтинг: 0 / 0
26.02.2016, 12:47
    #39179727
chpasha
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Valery ShiskinPartisan M,

Может я чего не понимаю, но причем здесь IDE?
YouTube Video
...
Рейтинг: 0 / 0
26.02.2016, 12:52
    #39179733
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
chpasha, твоё видео заблокировано
...
Рейтинг: 0 / 0
26.02.2016, 13:11
    #39179756
chpasha
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
maytonchpasha, твоё видео заблокировано
его просто нужно на ютюбе смотреть перейдя по ссылке. жадный мосфильм не разрешает встраивание :(
...
Рейтинг: 0 / 0
24.05.2016, 13:17
    #39242160
arrt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Есть ли проще способ найти 3 наименьших числа из некого перечня
Вот снова у меня будет необходимость решать задачи на алгоритмы. Хотел бы спросить -- какую книгу или ресурс вы можете предложить? Это не обязательно должна быть джава (может быть с++, с#), но не рекомендуйте Кнута. То есть это должны быть краткие задачи на быстроту, типа этой. Среди примеров могут быть и соотвествующие разделы или ветки форума с примерами... А то если не имееш опыта решение таких задач, то и найти оптимальное и необходимое решение сложно если это нужно сделать быстро.
...
Рейтинг: 0 / 0
Форумы / Java [игнор отключен] [закрыт для гостей] / Есть ли проще способ найти 3 наименьших числа из некого перечня / 25 сообщений из 41, страница 1 из 2
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]