Кстати, теперь вы можете обращаться к тегам в закрепленном сообщении, чтобы найти нужное задание или статью(которые будут в будущем), закреп будет постоянно обновляться

Над тем, что вы дальше прочитаете, уже можно поразмыслить 🕐

Мы как то уже разбирали контент Адитьи Бхаргавы, я сообщение вам прикреплю. Будет лучше, если вы прочтете, что я там писал.

✅Там если что было про бинарный поиск, big(O) (это если че скорость выполнения алгоритмов, то насколько быстро возрастает время выполнения алгоритма с увеличением входных данных). Также мы с вами разобрали несколько основных разновидностей big(O), но будет лучше если вы это прочитаете сами.

Перед следующей главной идет разбор задачки о коммивояжере (TSP - traveling Salesman Problem) и конечно же блять мне стало интересно.⁉️ Это, наверное, самая известная задача о графах. В чем собственное суть⁉️

⭕️Вообще, в книге написано об этом не так много: у нас есть, допустим, чел👨‍💻, который решил посетить 5 городов (5 городов просто условность, пунктов может быть бесконечно много). Этот самый чел (коммивояжер) хочет заехать в каждый город, а некоторые источники трактуют, что он еще должен заехать обратно, но не суть. У нас известны длины дорог, которые соединяют города. Нам нужно найти кратчайший маршрут этого самого чела. Автор книги пишет, что одним из возможных решений будет являться перебор всех возможных комбинаций порядка объезда городов.

⭕️В нашем случае, поскольку городов - 5, количество перестановок будет 120, поскольку 5! = 120. ‼️Очень важный момент, 120 это не ответ, это именно количество перестановок, перестановки в данном случае это наши операции.

❗️Теперь вкратце: у нас из каждого города есть доступ в другой город, допустим от 1 города до второго - 150 км и так далее... (об этом тоже поговорим), также мы можем вычислить количество операций, в нашем случае городов 5, значит и перестановок будет 5! = 120. На этом этапе, я обратился к ChatGPT, отправил промт и он очень хорошо ответил. Ниже расписано, как бы мы считали длину маршрута.

- A -> B -> C -> D -> E -> A
- A -> B -> C -> E -> D -> A
- A -> B -> D -> C -> E -> A
- ......

‼️Это выглядело бы примерно вот так, только не 3 операции перебора, а 120). Хорошо, давайте решать,

0️⃣Допустим, городов также 5, у нас есть город А, начиная с которого, мы должны посетить все остальные города ровно один раз, вернувшись в исходный город. По сути, считать мы будем маршруты 4 городов (B, C, D, E).

1️⃣Помните, я вам выше писал, что нам нужно вычислить факториал количества городов? Дак вот в нашем случае будет 4!. Почему так? ‼️ Да потому что ебать город А у нас как начальный, так и заключительный, поэтому операции будут для 4 городов, а для 4 городов, количество операций будет 4! = 24. Дальше представлены точки, по которым мы можем определить расстояние между городами.

- Город A: (0, 0)
- Город B: (1, 2)
- Город C: (4, 3)
- Город D: (6, 1)
- Город E: (3, 5)

2️⃣Итак, точки есть, теперь рассчитываем расстояние (чекайте картинку).
👇🏿Внизу представлены длины между нашими городами.

- A -> B: 2.24
- A -> C: 5
- A -> D: 6.08
- A -> E: 5.83
- B -> C: 3.16
- B -> D: 5.10
- B -> E: 3.61
- C -> D: 2.83
- C -> E: 2.24
- D -> E: 5

3️⃣Теперь просто подставляем в маршруты, наши полученные ответы и складываем. Это все будет выглядеть дохуя объемным, но как по мне, очень хорошее
объяснение. ⚙️

- A -> B -> C -> D -> E -> A
- A -> B -> C -> E -> D -> A
- A -> B -> D -> C -> E -> A
- A -> B -> D -> E -> C -> A
- A -> B -> E -> C -> D -> A
- A -> B -> E -> D -> C -> A
- A -> C -> B -> D -> E -> A
- A -> C -> B -> E -> D -> A
- A -> C -> D -> B -> E -> A
- A -> C -> D -> E -> B -> A
- A -> C -> E -> B -> D -> A
- A -> C -> E -> D -> B -> A
- A -> D -> B -> C -> E -> A
- A -> D -> B -> E -> C -> A
- A -> D -> C -> B -> E -> A
- A -> D -> C -> E -> B -> A
- A -> D -> E -> B -> C -> A
- A -> D -> E -> C -> B -> A
- A -> E -> B -> C -> D -> A
- A -> E -> B -> D -> C -> A
- A -> E -> C -> B -> D -> A
- A -> E -> C -> D -> B -> A
- A -> E -> D -> B -> C -> A
- A -> E -> D -> C -> B -> A

#коммивояжер #TSP #Алгоритмы #bigO

✅ На этом этапе все становится понятно, наши ответы - расстояние между городами, подставляем в маршруты, ищем минимальный маршрут и вот вам ответ.

‼️Оптимальный маршрут для 5 городов это маршрут A -> B -> E -> C -> D -> A с общей длиной 16.62, потому что он наименьший.

😳Теперь представьте, если бы городов было хотя бы 15)). Это был самый 'тугой' способ - метод перебора, если мне хватит мозгов, то разберем еще пару методов позже.

🧑‍💻Чисто вам факт, если городов будет больше 66, то компьютеру понадобится несколько миллиардов лет, чтобы найти правильный ответ, потому что число, факториал из 66 это количество операций сложения) Да и к тому же, мы не знаем, какая там могла быть длина между городами. Вычисления ии ниже 👇🏿

Здесь применена формула для нахождения расстояния между двумя точками. Да и в целом, это все было расписано, чтобы показать, что нужно делать, чтобы решить задачу с самого начала, имея начальные координаты. #Алгоритмы #Книги

🔗А вот и самое задание #451_градус_по_Фаренгейту Решение выше 👆🏿

#Dog_age

🔗Тут нужно вычислить возраст кобеля в человеческих годах (ахуенно).
⭕️Первые два года равны 10.5 человеческим, значит умножаем на 2. Если возраст > 2, то каждый год будет равен 4 человеческим..

#Dog_age Если возраст меньше или равен 2, возраст умножаем на 10.5. Если возраст больше 2, то уже к 21 прибавляем (n-2) * 4 (n - 2, поскольку первые 2 года посчитали).

n = int(input())
  
if n <= 2:
    dog_age = n * 10.5
else:
    dog_age = 2 * 10.5 + (n - 2) * 4
    
print(dog_age)

🔗Итак, #Первая_цифра_после_точки. В задании указано, вывести первую цифру после десятичной точки, ну и хули там решаем

Самым обычным решением будет просто умножить наше число на 10, чтобы оно стало целым, а затем находим остаток от деления #Первая_цифра_после_точки

Код:

s = float(input())
print(int(s * 10) % 10)

Ебать я щас сидел разбирал другой пример решения, просто интересно ваше мнение: Как вы думаете, верно ли это решение или нет? Какой будет ответ, если ввести 19.9? #float

Код:

n = float(input())
print(int((n - int(n)) * 10))

Так, еще раз, представим, что с клавиатуры подается число 19.9, теперь подставляем и думаем

⭕️ Еще одно решение, которое я спиздил в комментариях к заданию (чуть позже опубликую причины, почему решение выше не является верным).

‼️ Итак, гений решил через метод split(), который я уже пытался объяснить (Сообщение я прикрепил). Итак, что тут происходит ❓

0️⃣ Input() запрашивает у нас ввод, вводим и он возвращает строку, тут все как обычно.

1️⃣ Дальше выводим s.split('.').

2️⃣ Мы разбиваем нашу строку s и в качестве разделителя используем точку, как раз, что нам и нужно.

3️⃣Допустим, было у нас число 111.234 - метод просто вернет список ['111', '234']. Дальше идет [-1]. Это значит что выбирается первый с конца элемент, как в нашем примере, это будет 234. Ну и собственно [0] выбирает первый символ '234', это будет просто 2, так как индекс [0] имеет первый символ. #split #Программирование