Насчёт необходимости остановки в первом способе на 750км слукавил)) если заправка на 550км и проехать на одной заправке можно 400 и конечная точка 950 то нет необходимости в остановке на 750-м километре. Тогда первый способ получится на столько же эффективен как и первый). А вот если конечную точку сдвинуть немного вперёд, тогда да. Спасибо, интересно.
А если по пути пришлось выжидать в пробках, плюс и за жары включил кондиционер. Так от точки 550 не доехать до 950. Есть самый безопасный вариант: почаще останавливаться. А вдруг одна закрыта на ремонт, нет топлива или программа не работает. Большое спасибо Алишев за обучение. Мир и здоровье тебе!
@@VadimC5917 В условии сказано, что 400 км можно проехать на полном баке. Значит уже в эти 400 км включены предполагаемые расходы. Если это не так, то задачу нужно формировать заново. Это уже другое ТЗ.
надо заметить что задачу с числами эффективнее решать не с помощью выбора-удаления элемента так как очевидно что ассимптотика квадратичная у такого решения, а с помощью обратной сортировки (например быстрой или слиянием) за nlogn
@@user-tk7nh1jw3y дело не в том какой объем памяти а в том что далеко не все яп способны выделять память в статике, а значит это лишняя аллокация -> системный вызов под капотом, и как следствие жуткий оверхед по времени. Можно успеть 100500 раз отсортировать массив за O(nlogn) чем ожидать сис.колл
@@molotok1726 Так мы же про асимптоматику говорим, причем тут лишний сис колл? Если брать те же быструю сортировку и сортировку слиянием, то быстрая не использует дополнительную память, а слиянием постоянно создаёт дополнительные массивы. Тем не менее считается что обе работают в среднем за O(nlogn), а в худшем случае слиянием даже быстрее.
Отличный урок. Поставила на паузу, попробовала расписать код сама, а потом послушать тебя. Мой код, конечно, это одноглазый Джо: my_list = [3, 1, 7, 9, 9, 5] my_list.sort() new_list = [] for i in my_list: new_list.append(i) new_list.reverse() print(new_list)
Но ведь первая задача настолько очевидно проще решается сортировкой в порядке убывания, которую можно было бы осуществить более эффективными алгоритмами, чем предложенное решение O(n^2)
В задаче про монеты. Оно то, конечно, можно разменять по 20 центов, но где взять еще 1 монету номиналом 20 тогда? Или в условии забыли указать, что таких монет (20 центов) две?
Вопрос автору. Вы показали примеры жадных алгоритмов, а мой вопрос по динамическому программированию, нужно ли использовать динамическое программирование, чтобы найти кратчайший путь из точки A в точку Z с учетом, что путь из A в Z имеет много различных ответвлений и пересечений? В Google Map или в приложении Uber, когда мы задаем начальную точку и конечную точку - приложение нам строит кратчайшую траекторию, используется ли алгоритм динамического программирования там? Означает ли это, что динамическое программирование - это рекурсивный перебор всех возможных вариантов и выбор самого оптимального?
С чего это в первой задаче получается глобальный оптимальный результат? Сложность алгоритма будет O(n^2). Можно сделать O(n): public class MaxNumber { public static void main(String[] args) { int[] arr = new int[] {3,1,7,9,9,5}; int[] temp = new int[10]; long res = 0; for(int i = 0; i=0;i--) for (int j = 0; j
@@kanaagaat5194 для примера из 6 чисел - да, усложнил. Просто сортировать будет стоить дороже для больших n - O(nlogn). Чем асимптотика этого года отличается от прошлогодней?)
@@user-fr2dw3qd4v почему переписывать? Просто нужно прописать условие, которое проверяет, чтобы километраж не был более 400 км и остановка была на последней точке на этом отрезке. Тогда и будет работать на любых точках, только массивы меняй - программа будет выбирать наиболее удачные точки остановок. Смысл то решать с помощью костыля применимого только к одной ситуации?
package day21.AnyTest; import java.util.Arrays; public class MasSort { // Дан неупорядоченный список цифр от 0 до 9. Составить из этих числел наибольшее число //in: 317995 out: 997531 public static void main(String[] args) { int[] input = {3, 1, 7, 9, 9, 5}; int[] output = new int[input.length]; int max = 0; int count = 0; int c = 0; for (int j=0; j < input.length; j++) { for (int i = 0; i < input.length; i++) { if (input[i] < 0) { continue; } if (input[i] > max) { max = input[i]; c = i; } } input[c] = -9; output[count] = max; max = 0; count++; } System.out.println(Arrays.toString(output)); } }
Решение первой задачи просто рак, у нас сложность выходить O(n^2), причем автор использует фразу "удаляем из массива" и у меня вопрос, как мы это делаем, ибо нулл вместо инта поставить будет не всегда возможно, а удалять ячейку это ооочень дорого. Крч у меня много вопросов, первый задача оптимальной всего решается бакет сортом.
![Eminem - Houdini [Official Music Video]](http://i.ytimg.com/vi/22tVWwmTie8/mqdefault.jpg)
КУРС ПО GIT: www.udemy.com/course/git-alishev/?referralCode=71994763964B8E2E6A4E
Хорошая и четко поставленная речь, без всяких "ааа....", "ммм..." и "эээ...". Респект автору.
знаешь что такое монтаж?)))
@@indigolight6007 ну так про это и речь, некоторые авторы даже не вырезают подобное на этапе монтажа.
Самый крутой чувак который не лениться поделиться со своими знаниями
Насчёт необходимости остановки в первом способе на 750км слукавил)) если заправка на 550км и проехать на одной заправке можно 400 и конечная точка 950 то нет необходимости в остановке на 750-м километре. Тогда первый способ получится на столько же эффективен как и первый). А вот если конечную точку сдвинуть немного вперёд, тогда да.
Спасибо, интересно.
Да! Вы правы :)
А если по пути пришлось выжидать в пробках, плюс и за жары включил кондиционер. Так от точки 550 не доехать до 950.
Есть самый безопасный вариант: почаще останавливаться. А вдруг одна закрыта на ремонт, нет топлива или программа не работает.
Большое спасибо Алишев за обучение. Мир и здоровье тебе!
@@VadimC5917 В условии сказано, что 400 км можно проехать на полном баке. Значит уже в эти 400 км включены предполагаемые расходы. Если это не так, то задачу нужно формировать заново. Это уже другое ТЗ.
@@VadimC5917 вам даны четкие условия. Зачем вы придумываете себе всякие другие условия которых даже невозможно реализовать на голом коде
у этого канала великое будущее!
Спасибо большое за ваш труд!
Спасибо за урок!
Молодец, продолжай в том же духе, не глохни! Слушать тебя интересно, у тебя есть на ютубе будущее)))
Завтра зачёт, вовремя выложил)
Спасибо огромнейшее!
Спасибо за материал! Еще бы ссылки на презентации - было бы совсем здорово!
Пожалуйста!
drive.google.com/open?id=1Hx06zrR_e89vYJa7K3VLtSA33I1xqRZ_
Просто крутой чел, кстати спасибо за курс по python
надо заметить что задачу с числами эффективнее решать не с помощью выбора-удаления элемента так как очевидно что ассимптотика квадратичная у такого решения, а с помощью обратной сортировки (например быстрой или слиянием) за nlogn
Эта задача решается за O(n) без сортировки при помощи вспомогательного массива на 10 элементов.
@@user-tk7nh1jw3y вспомогательный массив это уже доп. память, лучше O(nlogn) зато in-place
@@molotok1726 ну если лишних 48 байт жалко, тогда да
@@user-tk7nh1jw3y дело не в том какой объем памяти а в том что далеко не все яп способны выделять память в статике, а значит это лишняя аллокация -> системный вызов под капотом, и как следствие жуткий оверхед по времени. Можно успеть 100500 раз отсортировать массив за O(nlogn) чем ожидать сис.колл
@@molotok1726 Так мы же про асимптоматику говорим, причем тут лишний сис колл? Если брать те же быструю сортировку и сортировку слиянием, то быстрая не использует дополнительную память, а слиянием постоянно создаёт дополнительные массивы. Тем не менее считается что обе работают в среднем за O(nlogn), а в худшем случае слиянием даже быстрее.
Отличный урок. Поставила на паузу, попробовала расписать код сама, а потом послушать тебя. Мой код, конечно, это одноглазый Джо:
my_list = [3, 1, 7, 9, 9, 5]
my_list.sort()
new_list = []
for i in my_list:
new_list.append(i)
new_list.reverse()
print(new_list)
my_list = [3, 1, 7, 9, 9, 5]
print(''.join([str(x) for x in sorted(my_list, reverse=True)]))
Добрый день) а будет продолжение?
Но ведь первая задача настолько очевидно проще решается сортировкой в порядке убывания, которую можно было бы осуществить более эффективными алгоритмами, чем предложенное решение O(n^2)
Так автор и использует сортировку выбором. Просто её понять проще, чем quick/mergesort
Мне кажется, в случае с заправками не всегда жадный алгоритм будет работать оптимально.
Ой как часто у меня бывают "ага!" моменты))
Задача 1
Lk = [1,3,7,5,9,9)
Print(sorted(Lk, reverse=Trur))
В задаче про монеты. Оно то, конечно, можно разменять по 20 центов, но где взять еще 1 монету номиналом 20 тогда? Или в условии забыли указать, что таких монет (20 центов) две?
Можно отсортировать массив по убыванию, и склеить все элементы
Вопрос автору. Вы показали примеры жадных алгоритмов, а мой вопрос по динамическому программированию, нужно ли использовать динамическое программирование, чтобы найти кратчайший путь из точки A в точку Z с учетом, что путь из A в Z имеет много различных ответвлений и пересечений? В Google Map или в приложении Uber, когда мы задаем начальную точку и конечную точку - приложение нам строит кратчайшую траекторию, используется ли алгоритм динамического программирования там? Означает ли это, что динамическое программирование - это рекурсивный перебор всех возможных вариантов и выбор самого оптимального?
Обычно для нахождения кратчайшего пути используются графы и алгоритм A*
Это же творческий переосмысленный курс San Diego University на Coursera)
С чего это в первой задаче получается глобальный оптимальный результат? Сложность алгоритма будет O(n^2). Можно сделать O(n):
public class MaxNumber {
public static void main(String[] args) {
int[] arr = new int[] {3,1,7,9,9,5};
int[] temp = new int[10];
long res = 0;
for(int i = 0; i=0;i--)
for (int j = 0; j
мне кажется ты все усложнил , можно же просто сортировать по убыванию ) (за асимптотику этого года хз)
@@kanaagaat5194 для примера из 6 чисел - да, усложнил. Просто сортировать будет стоить дороже для больших n - O(nlogn). Чем асимптотика этого года отличается от прошлогодней?)
Во второй задаче на одной жадности не уедешь. Если АЗС на 750 километре переместить на 775+1 километр, то произойдет облом)
Зачем что-то перемещать, если есть четкие условия задачи?
@@SplashDmg2011 не зачем конечно. Но если переместится, то код придется переписывать.
@@SplashDmg2011по тому что в олимпиадках четкие условия не дают никогда
@@user-fr2dw3qd4v почему переписывать? Просто нужно прописать условие, которое проверяет, чтобы километраж не был более 400 км и остановка была на последней точке на этом отрезке. Тогда и будет работать на любых точках, только массивы меняй - программа будет выбирать наиболее удачные точки остановок. Смысл то решать с помощью костыля применимого только к одной ситуации?
package day21.AnyTest;
import java.util.Arrays;
public class MasSort {
// Дан неупорядоченный список цифр от 0 до 9. Составить из этих числел наибольшее число
//in: 317995 out: 997531
public static void main(String[] args) {
int[] input = {3, 1, 7, 9, 9, 5};
int[] output = new int[input.length];
int max = 0;
int count = 0;
int c = 0;
for (int j=0; j < input.length; j++) {
for (int i = 0; i < input.length; i++) {
if (input[i] < 0) {
continue;
}
if (input[i] > max) {
max = input[i];
c = i;
}
}
input[c] = -9;
output[count] = max;
max = 0;
count++;
}
System.out.println(Arrays.toString(output));
}
}
Если топливо на 400км то 550+400 =950 остановка на 750 не нужна
Решение первой задачи просто рак, у нас сложность выходить O(n^2), причем автор использует фразу "удаляем из массива" и у меня вопрос, как мы это делаем, ибо нулл вместо инта поставить будет не всегда возможно, а удалять ячейку это ооочень дорого. Крч у меня много вопросов, первый задача оптимальной всего решается бакет сортом.