CodeLab

⚪️ Краткие тезисы прошлых постов

🔗 Класс P (Polynomial time):

0️⃣ У нас есть задачи, время выполнения которых зависит от количества входных данных, это означает, 🟰за полиноминальное время🟰.

1️⃣ Еще один момент, такие задачи решаются детерминированным алгоритмом, это означает, что есть всего один возможный путь развития событий. Все эти вышеописанные свойства характерны для класса P.

2️⃣ Задачи класса P эффективны на практике, поскольку время решения увеличивается относительно медленно с ростом размера входных данных.

⚪️ Если задача находится в классе P, значит, мы можем найти её решение относительно быстро, даже если размер входных данных огромен)

🔗 Класс NP (Non-deterministic Polynomial time):

3️⃣ Касаемо класса NP, к которому и относится наша задача о коммивояжере:
Этот класс включает задачи, которые можно проверить за полиноминальное время детерминированным алгоритмом (То есть, быстро и с определенным алгоритмом выполнения). Но, решение может занять куда больше времени, больше чем полиноминальное. Заметьте, что речь идет лишь о проверке уже найденного решения, а не о нахождении решения)

⚪️ Полиномиальное время — это мера того, насколько быстро алгоритм может решить задачу в зависимости от размера входных данных.

4️⃣ Если быть еще точнее, у класса NP есть подкласс NP - полные задачи. Это самые 🌶 сложные задачи этого класса. Туда как раз и относится наша задача о коммивояжере. Если мы найдем ее за полиноминальное время — каждая задача в классе NP могла бы быть решена за полиномиальное время (то есть очень быстро).

39 viewsedited 21:05

CodeLab

‼️Наконец, мы подошли к итогам (Самое важное)‼️

⭕️ Метод, который мы разбирали (брутфорс, перебор всех значений) является неэффективным, особенно для 66 городов) Вы просто прикиньте факториал из 66 перестановок! Только одни бл❌ть перестановки! А еще не забывайте, что нам нужно рассчитать маршруты между городами (или точками, как хотите), затем посчитать это все и сравнить и только потом, найти минимальный маршрут)

⭕️ Задача о коммивояжере считается NP полной (complete), это, чтобы вы просто понимали, эквивалентно по сложности всем задача класса NP)

Факториал 24 это уже 620448401733239439360000 перестановок, поэтому о 66 городах смысла говорить просто нет!

‼️На текущий момент не существует известного алгоритма, который бы мог решить задачу коммивояжера за полиномиальное время (то есть, эффективно) для всех возможных случаев. (Но при этом, есть алгоритмы покруче брутфорса, надеюсь, попозже мы их обязательно разберем)

🔗 P = NP:

Вопрос о равенстве двух классов до сих пор не решен, но многие склонны к не равенству, поскольку, вот уже более чем трех с половиной десятилетий не было найдено алгоритма с полиномиальным временем выполнения ни для одной из 3000 известных NP-complete задач.

🔗 Полезные ссылки:

https://en.wikipedia.org/wiki/List_of_NP-complete_problems (List of NP-complete problems)

https://habr.com/ru/articles/43224/ (Полезный материал)

https://ru.hexlet.io/courses/graphs/lessons/hamiltonian/theory_unit (Гамильтонов цикл и Путь)

https://skillbox.ru/media/code/big-o-notation-chto-eto-takoe-i-kak-eye-poschitat/ (Полезный материал)

46 viewsedited 21:30

CodeLab

Еще вам закину классную фотаче, где очень хорошо показано, как время выполнения различных алгоритмов изменяется в зависимости от размера входных данных n и сложности алгоритма Big(O).

🧑‍💻 Самый левый столбец — значения входных данных.

42 views21:41

CodeLab

🔗 Пол и потолок (6.3)

В общем гайс, ниче сложного, подается лишь одно число x, а вычисляет значение по двум функциям:

⬜️ Функция floor() из модуля math в Python используется для округления чисел с плавающей точкой в меньшую сторону.

⬜️ Функция math.ceil() из модуля math в Python позволяет округлить число до ближайшего целого числа в большую сторону.

🔗 Теперь код:

from math import*
x = float(input())
ans = floor(x) + ceil(x)
print(ans) #Я иду спать, всем сладких

43 viewsedited 22:24

CodeLab

🪰

42 views22:39

CodeLab

🌶🌶 Квадратное уравнение (6.3)

Думали, эти формулы вам не пригодятся?) ~~Хуй~~ бы не там, ща быстренько решим:

🔗 Я максимально расписывал код, но можно и намного короче:

from math import*
a = float(input())
b = float(input())
c = float(input())

D = pow(b, 2) - (4 * a * c)

if D > 0:
    x1 = ((-b + sqrt(D))/(2 * a))
    x2 = ((-b - sqrt(D))/(2 * a))
    print(min(x1, x2))
    print(max(x1, x2))
elif D == 0:
    print(-b/(2 * a))
else:
    print('Нет корней')

🔗🔗 Функция pow() возводит число в степень. Она принимает два параметра: какое число возводить и в какую степень возводить.

43 viewsedited 07:57

CodeLab

🔗А можно и вот так:

a=float(input())
b=float(input())
c=float(input())
d=b**2-4*a*c
if d < 0:
  print("Нет корней")

40 views07:59

CodeLab

🧑‍💻 Последнее задания данного раздела 'Правильный многоугольник (6.3)'

✅🔗Переписываем по формуле:

from math import*
n = float(input())
a = float(input())

S = (n * pow(a, 2)) / (4 * tan(pi/n))
print(S)

57 views08:00

CodeLab

🔗 Дальше по курсу у нас 🟰циклы🟰

О том, что такое циклы и зачем они нужны, мы уже разговаривали, ссылочку вам прикрепил, почитаете !

Чисто вкратце, сама структура цикла for, с чего мы и начнем:

for название_переменной_цикла in range(количество_повторений):
    блок кода

60 viewsedited 20:42

CodeLab

🔗 Python is awesome (7.1 )

💲 Код:

s = "Python is awesome!"
for i in range(10):
    print(s)

49 views20:47

CodeLab

🔗 Повторяй за мной 1 (7.1)

⭕️ Код:

s = input() #Для строки
rep= int(input()) #Количество повторений

for i in range(rep):
    print(s)

57 views20:51

CodeLab

⭕️ Последовательность символов (7.1)

🔗 Код:

for i in range(6):
    print("AAA")
    
for i in range(5):
    print("BBBB")
    
print("E")

for i in range(9):
    print("TTTTT")
    
print("G")

53 views20:54

CodeLab

⭐️ Звездный прямоугольник (7.1)

🔗 Код:

n = int(input())

for i in range(n):
    print("*" * 19)

47 views21:04

CodeLab

🧑‍💻 Повторяй за мной 2 (7.1)

🔗 Код:

n = input()

for i in range(10):
    print(i, n)

⚪️ Переменная цикла — это величина, изменяющаяся на каждой итерации цикла.

Первый аргумент функции print() это переменная цикла 🟰 i 🟰, вторая — значение переменной, в нашем случае, любая введенная строка.

48 views21:10

CodeLab

⚙️ Квадрат числа (7.1)

"Функция range возвращает последовательность чисел в заданном диапазоне." Дак вот, поскольку нам сказали, что диапазон заканчивается на число (включительно), поэтому прибавляем единицу:

for i in range(n + 1):

🔗 Код:

n = int(input())

for i in range(n + 1):
    print(f'Квадрат числа {i} равен {i ** 2} '

f' строки (если забыли)

60 viewsedited 21:17

CodeLab

🔗Всем доброй ночи гайс, знаю, вы спите. Это скорее вводный пост про Машинное обучение. Если Python я понимал хоть немного, когда начинал этот канал, то вот эту ху⚙️ню я не понимаю от слова совсем..
🔗Далеко я уходить не стал, решил взять книгу из той же серии, что и 'Грокаем Алгоритмы' (посоветовали).

Все остальное я, естественно, не забрасываю, будет все также в полном объеме!

61 views22:02

CodeLab

Начнем с простейших понятий и я пойду спать, уже завтра будем изучать дальше!

◽️ Здесь нам сразу говорят, что есть такая штука, как искусственный интеллект (это типа набор задач, в которых компьютер может
принимать решения.)

◽️ Машинное обучение, в свою очередь, является частью этой области (МО — это у нас — набор всех задач, в которых компьютер может принимать решения на основе данных).

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

◽️ И, наконец, глубокое изучения — это целая область исследований, которая относится к машинному обучению (Это и есть нейросетки).

Кароч, на днях запилю уже какой-нибудь крутой пост о машинке. Это, скорее, было мое вводное слово, всем спокойно ночи!

68 viewsedited 22:15

CodeLab

https://www.youtube.com/watch?v=jLx5_1M0gJc
🧑‍💻 А вот вам видос на ночь

YouTube

Веб Программирование для Чеченцев Урок 4

Первая часть "To-Do List" - списка заданий, стандартной проги которую должен знать любой веб программист для интервью.

🤡1

72 viewsedited 22:15

CodeLab

🧑‍💻 Вот так резко мы врываемся к языку C (можете не спрашивать причем тут вообще Си). Пока что запишем некоторый код, потом уже попробую сделать структура и навигацию ко всему этому.

⭕️Массив — это группа ячеек памяти одинакового типа, расположенных рядом и имеющих общее имя.
⭕️Каждая ячейка в группе имеет уникальный номер.

При работе с массивами необходимо решать три задачи:
1️⃣ Выделять память нужного размера под массив.
2️⃣ Записывать данные в нужную ячейку.
3️⃣ Читать данные из ячейки.

60 views20:45

CodeLab

‼️ Очень важно понимать вам одно ‼️Я пока что сам в нем ничего не знаю, не сказал бы что процесс вынужденный, но, мне самому придется это все понять, а вам это вполне может быть интересно. Ща разберем один код, уверяю, вы все поймете 🖤

#include <stdio.h>
const int N = 10; # Размер массива

int main() {
    int A[N]; # Объявление массива

    # Ввод массива с клавиатуры
    printf("Введите массив A:\n"); #Вывод вод
    for (int i = 0; i < N; ++i) { #Цикл по всем элементам
        printf("Введите A[%d]: ", i); #Ввод A[i]
        scanf("%d", &A[i]); #Ввод A[i]
    }

    #Умножение всех элементов на 2
    for (int i = 0; i < N; ++i) { #Цикл по всем элементам
        A[i] = A[i] * 2; #Умножить A[i] на 2
    }

    #Вывод массива на экран
    printf("Результат:\n");
    for (int i = 0; i < N; ++i) { #Цикл по всем элементам
        printf("%d ", A[i]); #Вывод A[i]
    }

    return 0;
}

В целом, код достаточно читаем, но, я постараюсь объяснить и вам и себе его так, как я хотел бы, чтобы объясняли мне, начинаем)

0️⃣ Подключаем библиотеку stdio.h для использования таких функций, как, например, printf ( Вывод данных на экран ) и scanf ( Ввод данных с клавиатуры ). 👇🏿

#include <stdio.h>

1️⃣ В 🟰C🟰 нужно явно объявлять тип переменных ( К примеру: int A[N] объявляет массив целых чисел размером 10 ). В Python: переменные и типы данных динамические, и не нужно указывать их типы явно, вот вам явное отличие. const int N = 10;

⭕️ В Python список ( А еще массивы заменяются списками в нашем любимом питоне ) объявляется как A = [], и его можно динамически расширять с помощью метода .append() (Позже мы обязательно это рассмотрим подробнее).

Дак вот, возвращаемся к коду:

🟰 const int N = 10; устанавливает константу N, равную 10 ( Строчкой ниже мы зададим размер нашего массива этой переменной)
🟰 int A[N]; создается массив A размером 10.

Кстати, еще вы можете заметить Int main () ( Главная управляющая функция main () )

2️⃣:

for (int i = 0; i < N; ++i) { #Цикл по всем элементам
    printf("Введите A[%d]: ", i); #Ввод A[i]
    scanf("%d", &A[i]); #Ввод A[i]

Конструкцию for вы уже знаете (цикл ), давайте что-нибудь новенькое:

Итак, int i = 0 является начальной позицией, переменную i мы сразу же объявляем как целое число (int) и сразу же получает значение 0 (Потому что оно начальное).

int i = 0

⭕️ Это уже, своего рода, условие внутри нашей конструкции цикла (Пока i меньше значения N), цикл будет выполняться.)

i < N

🧑‍💻 "Инкремент — это операция, в результате которой значение переменной увеличивается на единицу" — не стал ничего придумывать, все сказано очень хорошо (После каждого выполнения тела цикла переменная i увеличивается на 1, а выполняется после каждого блока кода).

⭕️ Еще есть Декремент — это операция, в результате которой значение переменной уменьшается на единицу (- - 1)

++i

3️⃣:

Я уже сказал че за printf и scanf, Что за d в кавычках?? %d — это спецификатор формата, который говорит printf, что на этом месте в строке нужно подставить целое число.

🟰%d, %i — для целых чисел;

🟰%f, %g — для вещественных чисел;

🟰%c — для символов.

"&" — вот эта херь нужна для определения адреса переменной.

🟰 Операция * (звездочка) — позволяет получить значение объекта по его адресу.
🟰 Операция & (амперсанд) — позволяет определить адрес переменной.

 printf("Введите A[%d]: ", i); #Ввод A[i]
        scanf("%d", &A[i]); #Ввод A[i]
    }

4️⃣ В следующем цикле for, программа проходит по всем элементам массива и каждый элемент умножается на 2:

for (int i = 0; i < N; ++i) {
        A[i] = A[i] * 2;

5️⃣ После умножения всех элементов, программа снова использует цикл для вывода всех значений массива и наша программа решена‼️ (Мы вводим 10 чисел и каждое умножается на 2)

for (int i = 0; i < N; ++i) { #Цикл по всем элементам
    printf("%d ", A[i]); #Вывод A[i]
}

Итак, давайте подведем итоги:

🟰 Первый цикл производил ввод значений (чисел в нашем случае ) в массив ( Код запрашивал ввод чисел и сохранял их в массив A по индексу i ).

🟰 Второй цикл умножал каждый элемент массива на 2 и выводил результат

Я спать

91 viewsedited 20:50

About

Blog

Apps

Platform