Насчёт необходимости остановки в первом способе на 750км слукавил)) если заправка на 550км и проехать на одной заправке можно 400 и конечная точка 950 то нет необходимости в остановке на 750-м километре. Тогда первый способ получится на столько же эффективен как и первый). А вот если конечную точку сдвинуть немного вперёд, тогда да. Спасибо, интересно.
А если по пути пришлось выжидать в пробках, плюс и за жары включил кондиционер. Так от точки 550 не доехать до 950. Есть самый безопасный вариант: почаще останавливаться. А вдруг одна закрыта на ремонт, нет топлива или программа не работает. Большое спасибо Алишев за обучение. Мир и здоровье тебе!
@@VadimC5917 В условии сказано, что 400 км можно проехать на полном баке. Значит уже в эти 400 км включены предполагаемые расходы. Если это не так, то задачу нужно формировать заново. Это уже другое ТЗ.
надо заметить что задачу с числами эффективнее решать не с помощью выбора-удаления элемента так как очевидно что ассимптотика квадратичная у такого решения, а с помощью обратной сортировки (например быстрой или слиянием) за nlogn
@@ДмитрийЧебанов-ю1м дело не в том какой объем памяти а в том что далеко не все яп способны выделять память в статике, а значит это лишняя аллокация -> системный вызов под капотом, и как следствие жуткий оверхед по времени. Можно успеть 100500 раз отсортировать массив за O(nlogn) чем ожидать сис.колл
@@molotok1726 Так мы же про асимптоматику говорим, причем тут лишний сис колл? Если брать те же быструю сортировку и сортировку слиянием, то быстрая не использует дополнительную память, а слиянием постоянно создаёт дополнительные массивы. Тем не менее считается что обе работают в среднем за O(nlogn), а в худшем случае слиянием даже быстрее.
В задаче про монеты. Оно то, конечно, можно разменять по 20 центов, но где взять еще 1 монету номиналом 20 тогда? Или в условии забыли указать, что таких монет (20 центов) две?
Отличный урок. Поставила на паузу, попробовала расписать код сама, а потом послушать тебя. Мой код, конечно, это одноглазый Джо: 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)
С чего это в первой задаче получается глобальный оптимальный результат? Сложность алгоритма будет 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). Чем асимптотика этого года отличается от прошлогодней?)
Вопрос автору. Вы показали примеры жадных алгоритмов, а мой вопрос по динамическому программированию, нужно ли использовать динамическое программирование, чтобы найти кратчайший путь из точки A в точку Z с учетом, что путь из A в Z имеет много различных ответвлений и пересечений? В Google Map или в приложении Uber, когда мы задаем начальную точку и конечную точку - приложение нам строит кратчайшую траекторию, используется ли алгоритм динамического программирования там? Означает ли это, что динамическое программирование - это рекурсивный перебор всех возможных вариантов и выбор самого оптимального?
@@Дмитрий-ю9к3г почему переписывать? Просто нужно прописать условие, которое проверяет, чтобы километраж не был более 400 км и остановка была на последней точке на этом отрезке. Тогда и будет работать на любых точках, только массивы меняй - программа будет выбирать наиболее удачные точки остановок. Смысл то решать с помощью костыля применимого только к одной ситуации?
Решение первой задачи просто рак, у нас сложность выходить O(n^2), причем автор использует фразу "удаляем из массива" и у меня вопрос, как мы это делаем, ибо нулл вместо инта поставить будет не всегда возможно, а удалять ячейку это ооочень дорого. Крч у меня много вопросов, первый задача оптимальной всего решается бакет сортом.
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)); } }
КУРС ПО 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_
надо заметить что задачу с числами эффективнее решать не с помощью выбора-удаления элемента так как очевидно что ассимптотика квадратичная у такого решения, а с помощью обратной сортировки (например быстрой или слиянием) за nlogn
Эта задача решается за O(n) без сортировки при помощи вспомогательного массива на 10 элементов.
@@ДмитрийЧебанов-ю1м вспомогательный массив это уже доп. память, лучше O(nlogn) зато in-place
@@molotok1726 ну если лишних 48 байт жалко, тогда да
@@ДмитрийЧебанов-ю1м дело не в том какой объем памяти а в том что далеко не все яп способны выделять память в статике, а значит это лишняя аллокация -> системный вызов под капотом, и как следствие жуткий оверхед по времени. Можно успеть 100500 раз отсортировать массив за O(nlogn) чем ожидать сис.колл
@@molotok1726 Так мы же про асимптоматику говорим, причем тут лишний сис колл? Если брать те же быструю сортировку и сортировку слиянием, то быстрая не использует дополнительную память, а слиянием постоянно создаёт дополнительные массивы. Тем не менее считается что обе работают в среднем за O(nlogn), а в худшем случае слиянием даже быстрее.
В задаче про монеты. Оно то, конечно, можно разменять по 20 центов, но где взять еще 1 монету номиналом 20 тогда? Или в условии забыли указать, что таких монет (20 центов) две?
Просто крутой чел, кстати спасибо за курс по python
Отличный урок. Поставила на паузу, попробовала расписать код сама, а потом послушать тебя. Мой код, конечно, это одноглазый Джо:
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
С чего это в первой задаче получается глобальный оптимальный результат? Сложность алгоритма будет 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). Чем асимптотика этого года отличается от прошлогодней?)
Мне кажется, в случае с заправками не всегда жадный алгоритм будет работать оптимально.
Можно отсортировать массив по убыванию, и склеить все элементы
Добрый день) а будет продолжение?
Вопрос автору. Вы показали примеры жадных алгоритмов, а мой вопрос по динамическому программированию, нужно ли использовать динамическое программирование, чтобы найти кратчайший путь из точки A в точку Z с учетом, что путь из A в Z имеет много различных ответвлений и пересечений? В Google Map или в приложении Uber, когда мы задаем начальную точку и конечную точку - приложение нам строит кратчайшую траекторию, используется ли алгоритм динамического программирования там? Означает ли это, что динамическое программирование - это рекурсивный перебор всех возможных вариантов и выбор самого оптимального?
Обычно для нахождения кратчайшего пути используются графы и алгоритм A*
Задача 1
Lk = [1,3,7,5,9,9)
Print(sorted(Lk, reverse=Trur))
Это же творческий переосмысленный курс San Diego University на Coursera)
Во второй задаче на одной жадности не уедешь. Если АЗС на 750 километре переместить на 775+1 километр, то произойдет облом)
Зачем что-то перемещать, если есть четкие условия задачи?
@@SplashDmg2011 не зачем конечно. Но если переместится, то код придется переписывать.
@@SplashDmg2011по тому что в олимпиадках четкие условия не дают никогда
@@Дмитрий-ю9к3г почему переписывать? Просто нужно прописать условие, которое проверяет, чтобы километраж не был более 400 км и остановка была на последней точке на этом отрезке. Тогда и будет работать на любых точках, только массивы меняй - программа будет выбирать наиболее удачные точки остановок. Смысл то решать с помощью костыля применимого только к одной ситуации?
Если топливо на 400км то 550+400 =950 остановка на 750 не нужна
Решение первой задачи просто рак, у нас сложность выходить O(n^2), причем автор использует фразу "удаляем из массива" и у меня вопрос, как мы это делаем, ибо нулл вместо инта поставить будет не всегда возможно, а удалять ячейку это ооочень дорого. Крч у меня много вопросов, первый задача оптимальной всего решается бакет сортом.
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));
}
}