Загрузка библиотек
для работы с текстовыми данными
import pandas as pd
import numpy as np
from collections import Counter
для обработки текстовых данных
import re
import nltk
from nltk.corpus import stopwords
from nltk.tokenize import word_tokenize
import pymorphy3
from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_similarity
для визуализации
from tqdm import tqdm
tqdm.pandas()
Открытие и предварительный просмотр данных
Для открытия и предварительного просмоотра были выбраны слудющие библиотеки:
pandas(для работы с табличными данными)
colections(для подсчета значений)
Указываем путь к файлу
file_path = "file.tskv"
Читаем файл построчно, так как TSKV имеет формат ключ=значение
with open(file_path, 'r', encoding='utf-8') as f:
lines = [line.strip().split('\t') for line in f if line.strip() and not line.startswith('#')]
Преобразуем строки в словари (ключ=значение)
data = [dict(item.split('=', 1) for item in line if '=' in item) for line in lines]
Создаем DataFrame
df = pd.DataFrame(data)
Вывод датафрейма
df
Вывод информации по датафрейму
df.info()
Приведение к целочисленному формату
df['col'] = df['col'].astype('float').astype('int')
df
Просмотр самых часто встречающихся категорий
Counter(df.col).most_common()
Фильтрация по категории объекта
df = df[df['col'] == 'Гостиница']
df
Удаление неинформативных колонок и реиндексация
df.drop(columns = ['col'], inplace=True)
df.reset_index(drop=True, inplace=True)
df
Предобработка текстов
Для предобработки текстов были выбраны следующие библиотеки:
pandas и numpy(для работы с таблицами и их колонками)
tqdm(для визуализадии прогресс баров)
re(для очистки данных)
nltk(для стоп-стов, токенизации и n-грамм)
pymorphy3(для лемматизации и выделения значимых частей речи)
Очистка текстовых данных
Загружаем стоп-слова для русского языка
nltk.download("stopwords")
sw = stopwords.words("russian")
Был выбран список стоп слов из библиотеки nltk, по следующим причинам:
Обширность – nltk включает наиболее распространённые предлоги, союзы и частицы, которые не несут смысловой нагрузки.
Простота использования – подключается одной строкой, легко расширяется или сокращается под нужды проекта.
создание функции очистки текстовых данных
def clean_text(text):
# Приведение текста к нижнему регистру
text = text.lower()
# Замена всех не-словесных символов на пробел (кроме букв и знаков препинания)
text = re.sub(r'\W+', ' ', text)
# Удаление URL-адресов
text = re.sub(r"http\S+", "", text)
# Создание шаблона для HTML-тегов
html = re.compile(r'<.*?>')
# Удаление HTML-тегов из текста
text = html.sub(r'', text)
# Список пунктуаций для удаления
punctuations = '@#!?+&*[]-%.:/();$=><|{}^' + "'`" + '_'
for p in punctuations:
text = text.replace(p, '') # Удаление пунктуации
# Удаление стоп-слов и приведение слов к нижнему регистру
text = [word.lower() for word in text.split() if word.lower() not in sw]
# Объединение слов обратно в текст
text = " ".join(text)
# Создание шаблона для поиска эмодзи
emoji_pattern = re.compile("["
u"\U0001F600-\U0001F64F" # эмоции
u"\U0001F300-\U0001F5FF" # символы и пиктограммы
u"\U0001F680-\U0001F6FF" # транспорт и карты
u"\U0001F1E0-\U0001F1FF" # флаги
u"\U00002702-\U000027B0"
u"\U000024C2-\U0001F251"
"]+", flags=re.UNICODE)
# Удаление эмодзи из текста
text = emoji_pattern.sub(r'', text)
return textФункция выполняет следующие действия:
Приведение к нижнему регистру
Удаление всех спецсимволов
Удаление URL адресов
Удаление HTML-тегов
Удаление пунктуации
Очистка от стоп-слов
Удаление эмодзи
Приведение к нижнему регистру стандартизирует текстовые данные и позволяет воспринимать разные формы слова как одну. Спецсимволы не несут никакой смысловой нагрузки и путают алгоритмы кластеризации. При рассмотрении жалоб, нам не приносят никакой информации URL адреса и HTML-теги. Убирая пунктуацию, мы убираем лишние шумы в данных и сокращаем размер словаря. Удаление стоп-слов для обучения модели помогает уменьшить объём текста и сосредоточиться на важных и значимых словах. Эмодзи создают шумы в данных и не несут смысловой нагрузки при рассмотрение нашей проблемы.
очистка текстовых данных
df['text'] = df['text'].progress_apply(lambda x: clean_text(x))
df
Токенизация
Загружаем необходимые ресурсы
nltk.download('punkt')
Токенизация необходима для разбиения на токены, которые вдальнейшем просто и удобно преобразовать в числовые значения. Также она приводит текстовые данные к формату, эффективному при обработке различными алгоритмами.
инициализация функции токенизации текстовых данных
def tokenize(text):
# применение метода word_tokenize из библиотеки nltk
tokenized_text = word_tokenize(text, language='russian')
return tokenized_text
Был выбран word_tokenize из библиотеки nltk, по следующим причинам:
Универсальность – поддерживает множество языков, включая русский.
Скорость и оптимизация – работает быстро даже на больших текстах.
токенизация текстовых данных
df['text'] = df['text'].progress_apply(lambda x: tokenize(x))
df
Лемматизация
Была выбрана лемматизации вместо стемминга, по следующим причинам:
Сохранение смысла – лемматизация приводит слово к его нормальной форме, тогда как стемминг может обрезать его до несуществующего корня.
Грамматическая корректность – учитывает часть речи и морфологию, в отличие от грубого усечения в стемминге.
Точность в обработке языка – особенно важна для языков со сложной морфологией, таких как русский.
Хотя стемминг быстрее, он менее точен, что делает лемматизацию лучшим выбором.
инициализация анализатора(лемматизатора)
morph = pymorphy3.MorphAnalyzer()
инициализация функции лемматизации текстовых данных
def lemmatize(text: list) -> list:
# создание списка лемматизированных слов
lemmas = [morph.parse(token)[0].normal_form for token in text]
return lemmas
Для лемматизации была выбрана библиотека pymorphy3, по следующим причинам:
Поддержка частей речи – определяет, к какой части речи относится слово, и приводит его к правильной лемме.
Высокая скорость работы.
лемматизация текстовых данных
df['text'] = df['text'].progress_apply(lambda x: lemmatize(x))
df
Выделение значимых частей речи
Для выделения значимых частей речи был выбран анализатор частей речи из библиотеки pymorphy3, благодаря его скорости работы и разнообразию токенов для работы с русским языком. В качестве значимых частей речи были выбраны:
Существительное(указывает на предмет недовольства граждан)
Глагол прилагательное(указывает совершенное действие или действие, которое стоит совершить для решения проблемы)
Прилагательное(описывает объект недовольства)
Остальные части речи не несут важной информации в контексте нашей задачи.
инициализация анализатора частей речи
morph = pymorphy3.MorphAnalyzer()
инициализация функции фильтрации слов по частям речи
def filter_words(words):
# инициализация итогового списка отфильтрованных
filtered_words = []
# фильтрация слов по частям речи
for word in words:
parsed_word = morph.parse(word)[0]
if parsed_word.tag.POS in {'NOUN', 'ADJF', 'ADJS', 'INFN', 'VERB'}: # если это существительное, прилагательное или глагол
filtered_words.append(word)
# объединение слов в текст
processed_text = " ".join(filtered_words)
return processed_text
Фильтрация текста по значимым частям речи необходима для удаления мусора, и дальнейщего ускорения работы и повышения точности алгоритмов машинного обучения. Для реализации фильтрации слов были использованы данные токены:
NOUN(имя существительное)
ADJF(имя прилагательное (полное))
ADJS(имя прилагательное (краткое))
VERB(глагол (личная форма))
INFN(глагол (инфинитив))
выделение значимых частей речи
df['text'] = df['text'].progress_apply(lambda x: filter_words(x))
df
Поиск ключевых слов/n-грамм
Для поиска ключевых слов был выбран алгоритм выбора самого часто встречающегося слова. Поскольку скорость работы данного алгоритма оптимальна, также данный алгоритм помогает находит слово которое максимально отражает контекст, так как если слово упоминается несколько раз, оно отражает основной смысл.
инициализация функции поиска ключевого слова
def extract_keywords(text, top_n=5):
# разбиение на токены
tokens = text.split()
keywords = [word for word, _ in Counter(tokens).most_common(top_n)]
# выбор самых часто встречающихся слов в зависимости от количества слов
if len(keywords) == 1: keyword = [keywords[0]]
else: keyword = keywords[:3]
return keyword
Выбор ключевых слов необходим для лучшего понимания моделью главной мысли текста. Данное действие повысит точность и поможет модели меньше путаться.
выделение ключевых слов
df['keywords'] = df['text'].progress_apply(lambda x: extract_keywords(x))
df
Для поиска и добавления биграмм в качестве признака воспользуемся встроеным в библиотеку nltk методом bigrams, это метод позволяет автоматизированно находить биграммы по каждому предложению. Данный способ обнаружения является быстрым и эффективным.
df['bigrams'] = np.array(df['text'].progress_apply(lambda x: list(nltk.bigrams(x.split()))))
df
Для поиска и добавления триграмм в качестве признака воспользуемся встроеным в библиотеку nltk методом trigrams, это метод позволяет автоматизированно находить триграммы по каждому предложению. Данный способ обнаружения является быстрым и эффективным.
df['trigrams'] = np.array(df['text'].progress_apply(lambda x: list(nltk.trigrams(x.split()))))
df
Векторизация
инициализация функции преобразования n-грамм
def process_ngrams(ngrams_list):
return ['_'.join(ngram) for ngram in ngrams_list]
инициализация функции преобразования текста
def process_text(text):
return text.split()
объединение в единый текст для векторизации
df['combined_text'] = (
df['text'].progress_apply(process_text) + # исходный текст
df['keywords'] + # ключевые слова
df['bigrams'].progress_apply(process_ngrams) + # биграммы
df['trigrams'].progress_apply(process_ngrams) # триграммы
)
df
Текст – это нечисловая информация, а модели оперируют числами. Векторизация переводит слова и документы в числовые представления, что позволяет использовать их для любого вида моделей.
инициализации векторайзера
vectorizer = TfidfVectorizer()
векторизация данных
X = vectorizer.fit_transform(df['combined_text'].progress_apply(lambda x: " ".join(x)))
X
В качестве векторайзера был выбран TF-IDF, по следующим причинам:
Выделяет значимые слова – снижает вес частых, но малозначимых.
Легко интерпретируется – присваивает каждому слову числовой вес.
Высокая скорость работы.
Разработка модели
Выбор алгоритма решения задачи
Для решения задачи было принято решение использовать: математическую модель, которая обеспечивает точность и воспроизводимость результатов, что снижает вероятность субъективных и случайных ошибок. Кроме того, использование математического подхода позволяет учитывать множество факторов одновременно, оптимизируя процесс подбора рекомендаций. Такой метод хорошо масштабируется, что делает его применимым как для небольших наборов данных, так и для более сложных сценариев анализа текста.
функция обработки текста
def text_prep(text):
text = clean_text(text)
text = tokenize(text)
text = lemmatize(text)
text = filter_words(text)
keywords = extract_keywords(text)
bigrams = list(nltk.bigrams(text.split()))
trigrams = list(nltk.trigrams(text.split()))
combined_text = (
process_text(text) + # исходный текст
keywords + # ключевые слова
process_ngrams(bigrams) + # биграммы
process_ngrams(trigrams) # триграммы
)
final_vector = vectorizer.transform(combined_text)
return final_vector
Функция для поиска наиболее подходящего варианта на основе косинусного расстояния
def find_best_hotel(user_query, hotels):
user_query = text_prep(user_query)
similarities = cosine_similarity(user_query, hotels)
best_match_index = similarities[0].argmax()
return best_match_index
Почему именно косинусное расстояние?
Эффективность для текстовых данных – косинусное сходство хорошо работает с TF-IDF, оценивая не абсолютное совпадение слов, а их относительную значимость.
Устойчивость к разной длине текста – сравнивает направление векторов, а не их величину, что важно при анализе коротких и длинных запросов.
Простота и быстродействие – в отличие от нейросетей, не требует долгого обучения и работает быстро даже на больших массивах данных.
Хорошо выявляет смысловую близость – подходит для поиска наиболее релевантного объекта среди текстовых описаний.
Резюмируя, косинусное расстояния является оптимальным вариантом для получения рекомендаций по тексту.
проверка работы
user_query = "Хочу отель у моря с бассейном"
find_best_hotel(user_query, X)
def metric(user_query, hotels):
user_query = text_prep(user_query)
similarities = cosine_similarity(user_query, hotels)
best_match_metric = similarities[0].max()
return best_match_metric
user_query = "Хочу отель у моря с бассейном"
metric(user_query, X)
import random
from pathlib import Path
import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import torch
import torch.optim as optim
import torchvision
import torchvision.transforms as tt
from torchvision.io import read_image
from sklearn.preprocessing import LabelEncoder
from PIL import Image
from sklearn.metrics import f1_score
from sklearn.model_selection import train_test_split
from torch import nn
from torch.utils.data import DataLoader, Dataset
from torchvision.models import ResNet18_Weights
from tqdm.notebook import tqdm
from torchvision import models as vision_models
import timm
from torchvision.utils import make_grid
from torchvision.io import decode_image
from pathlib import Path
import torchvision.transforms.functional as F
from torch.optim.lr_scheduler import StepLR
device = (
"cuda"
if torch.cuda.is_available()
else "cpu"
)
print(f"Using {device} device")
import os
import shutil
import pandas as pd
source_dir = r"journey-springfield\train"
target_dir = os.path.join(os.path.dirname(source_dir), "dataset", "images")
csv_path = os.path.join(os.path.dirname(source_dir), "dataset", "labels.csv")
# Создаем целевую директорию, если её нет
os.makedirs(target_dir, exist_ok=True)
# Массив для хранения данных
data = []
# Перебираем классы в исходной директории
for class_name in os.listdir(source_dir):
class_path = os.path.join(source_dir, class_name)
if not os.path.isdir(class_path):
continue
# Перебираем изображения в каждом классе
for img_name in os.listdir(class_path):
img_path = os.path.join(class_path, img_name)
new_img_path = os.path.join(target_dir, img_name)
# Проверяем, существует ли уже файл с таким именем
if os.path.exists(new_img_path):
base, ext = os.path.splitext(img_name)
new_img_name = f"{base}_{class_name}{ext}"
new_img_path = os.path.join(target_dir, new_img_name)
# Перемещаем изображение в целевую директорию
shutil.move(img_path, new_img_path)
# Добавляем путь к изображению и класс в список
rel_path = os.path.relpath(new_img_path, os.path.dirname(csv_path))
data.append([rel_path, class_name])
# Создаем DataFrame и сохраняем его в CSV
df = pd.DataFrame(data, columns=["image_path", "class"])
df.to_csv(csv_path, index=False)
print(f"Готово! Все изображения перемещены в {target_dir}, CSV создан по пути {csv_path}.")
le1 = LabelEncoder()
data = pd.read_csv(r'journey-springfield\dataset\labels.csv')
data['class_id'] = le1.fit_transform(data['class'])
data['class_id'] = data['class_id'].astype('int64')
train, val = train_test_split(data, test_size=0.15, random_state=1, stratify=data['class'])
train = train.reset_index(drop=True)
val = val.reset_index(drop=True)
print(train.shape, val.shape)
images_path = r'journey-springfield\dataset'
data['unified_class'] = data['class']
train['unified_class'] = train['class']
train = train.drop('class',axis = 1)
val['unified_class'] = val['class']
val = val.drop('class',axis = 1)
class EfficientNet(nn.Module):
def __init__(self, num_classes: int):
super().__init__()
self.model = vision_models.efficientnet_b1(vision_models.EfficientNet_B1_Weights.DEFAULT)
self.model.classifier[1] = torch.nn.Linear(self.model.classifier[1].in_features, num_classes)
def forward(self, batch):
inputs, _ = batch
return self.model(inputs)
class SimpDataset(Dataset):
def __init__(self, dataframe: pd.DataFrame, path_to_images: Path, transforms: tt.Compose) -> None:
self.df = dataframe
self.path_to_images = path_to_images
self.transforms = transforms
def __len__(self):
return len(self.df)
def __getitem__(self, idx):
row = self.df.iloc[idx]
# print(row)
image = Image.open(self.path_to_images + '\\' + row["image_path"]).convert('RGB')
# print(image)
if self.transforms is not None:
image = self.transforms(image)
return image, row["class_id"]
idx = 1
img = read_image(images_path +'\\'+ data.iloc[idx]["image_path"])
rescale_size = 244
# Imagenet mean and standard (are calculated from all of images)
imagenet_mean = np.array([0.485, 0.456, 0.406])
imagenet_std = np.array([0.229, 0.224, 0.225])
train_transform = tt.Compose([
tt.Resize((int(rescale_size * 1.25), int(rescale_size * 1.25))),
tt.RandomCrop(rescale_size),
tt.RandomHorizontalFlip(),
tt.ToTensor(),
tt.Normalize(imagenet_mean, imagenet_std)
])
val_transform = tt.Compose([
tt.Resize((int(rescale_size * 1.05), int(rescale_size * 1.05))),
tt.CenterCrop(rescale_size),
tt.ToTensor(),
tt.Normalize(imagenet_mean, imagenet_std)
])
train_dataset = SimpDataset(train, images_path, transforms=train_transform)
val_dataset = SimpDataset(val, images_path, transforms=val_transform)
train_dataloader = DataLoader(train_dataset, batch_size=64, num_workers=0, shuffle=True)
valid_dataloader = DataLoader(val_dataset, batch_size=64, num_workers=0, shuffle=False)
train_dataloader = DataLoader(train_dataset, batch_size=64, shuffle=True)
valid_dataloader = DataLoader(val_dataset, batch_size=128, shuffle=False)
next(iter(train_dataloader))[1]
model = EfficientNet(num_classes=data["unified_class"].nunique()).to(device)
# Инициализируем функцию потерь (loss/criterion), а так же оптимизатор, который будет регулировать обновление весов нашей модели
optimizer = optim.AdamW(model.parameters(), lr=3e-4)
criterion = nn.CrossEntropyLoss()
# Переменные для визуализации метрик и функции потерь
train_losses = []
val_losses = []
# Для удобства оценивать качество модели будем той же метрику, что на лидерборде - F1 score
train_f1_scores = []
val_f1_scores = []
best_val_f1 = 0.0
best_model_path = 'best_model.pth'
# Определим, сколько раз мы пройдёмся по всему датасету, прежде, чем закончим обучение модели и выберем лучшую версию
num_epochs = 25
# Шаговое уменьшение (StepLR)
scheduler = StepLR(optimizer, step_size=5, gamma=0.1) # Каждые 5 эпох уменьшать lr в 10 раз
# Напишем свой train_loop
for epoch in range(num_epochs):
model.train()
running_loss = 0.0
train_true = []
train_pred = []
for batch in tqdm(train_dataloader):
inputs, labels = batch
inputs, labels = inputs.to(device), labels.to(device)
optimizer.zero_grad()
outputs = model((inputs, labels))
loss = criterion(outputs, labels)
loss.backward()
optimizer.step()
running_loss += loss.item()
preds = torch.argmax(outputs, dim=1)
scheduler.step()
model.eval()
val_running_loss = 0.0
val_true = []
val_pred = []
# валидационный цикл, когда мы оцениваем качество работы модели на отложенной выборке
with torch.no_grad():
for batch in tqdm(valid_dataloader):
inputs, labels = batch
inputs, labels = inputs.to(device), labels.to(device)
outputs = model((inputs, labels))
loss = criterion(outputs, labels)
val_running_loss += loss.item()
preds = torch.argmax(outputs, dim=1)
val_true.extend(labels.cpu().numpy())
val_pred.extend(preds.cpu().numpy())
val_f1 = f1_score(val_true, val_pred, average='macro')
val_losses.append(val_running_loss / len(valid_dataloader))
val_f1_scores.append(val_f1)
# если получившаяся модель лучше предыдущей, сохраним чекпоинт
if val_f1 > best_val_f1:
best_val_f1 = val_f1
torch.save(model.state_dict(), best_model_path)
print(f'New best model saved with F1: {best_val_f1:.4f}')
# выведем в консоль получившиеся результаты на отдельной эпохе
print(f'Epoch [{epoch+1}/{num_epochs}], '
f'Val Loss: {val_losses[-1]:.4f}, Val F1: {val_f1:.4f}')
sample = pd.read_csv(r"journey-springfield\sample_submission.csv")
sample['image_name'] = r'journey-springfield/testset/'+sample['Id']
class InferenceDataset(Dataset):
def __init__(self, image_paths, transforms=None):
self.image_paths = image_paths
self.transforms = transforms
def __len__(self):
return len(self.image_paths)
def __getitem__(self, idx):
image_path = self.image_paths[idx]
image = Image.open(image_path).convert('RGB')
if self.transforms is not None:
image = self.transforms(image)
return image, image_path
# Тут важно не ошибиться и не использовать тренировочные трансформы
infer_transform = tt.Compose([
tt.RandomHorizontalFlip(),
tt.RandomRotation((-5, 5)),
tt.Resize((int(244 * 1.25), int(244 * 1.25))),
tt.ToTensor(),
tt.Normalize(mean=[0.485, 0.456, 0.406], std=[0.229, 0.224, 0.225]),
])
# Найдем все тестовые картинки
test_image_paths = sample.image_name.tolist()
infer_dataset = InferenceDataset(test_image_paths, transforms=infer_transform)
infer_dataloader = DataLoader(infer_dataset, batch_size=1, shuffle=False)
best_model_path = r'best_model.pth'
model.load_state_dict(torch.load(best_model_path))
# Не забудем перевести модель в режим предсказания, а не обучения.
model.eval()
# Для ускорения инференса будем подавать в модель картинки батчами (по несколько картинок за раз) и сохраним предсказанные метки классов.
results = []
for images, image_names in tqdm(infer_dataloader):
images = images.to(device)
with torch.no_grad():
outputs = model((images, None)) #для не хагина
preds = torch.argmax(outputs, dim=1).cpu().numpy()
results.append(preds[0])
# Для удобства объединим все пары "имя файла - предсказанный класс" в датафрейм (таблицу) с колонками image_name, predicted_class
sample['predicted_class'] = results
# Вывод DataFrame
sample
sample['Expected'] = le1.inverse_transform(sample['predicted_class'])
sample.drop(['image_name','predicted_class'],axis=1,inplace=True)
sample.to_csv('submit.csv',index = False)
Вот список базовых алгоритмов с примерами на Python:
1. Сортировка (Bubble Sort)
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
print(bubble_sort([5, 3, 8, 4, 2]))
2. Поиск (Бинарный поиск)
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
print(binary_search([1, 3, 5, 7, 9], 5)) # Вывод: 2
3. Поиск наибольшего общего делителя (алгоритм Евклида)
def gcd(a, b):
while b:
a, b = b, a % b
return a
print(gcd(48, 18)) # Вывод: 6
4. Числа Фибоначчи (рекурсия)
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(7)) # Вывод: 13
5. Быстрое возведение в степень
def power(x, y):
if y == 0:
return 1
half = power(x, y // 2)
return half * half if y % 2 == 0 else half * half * x
print(power(2, 10)) # Вывод: 1024
6. Обход графа (DFS)
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
print(node, end=" ")
for neighbor in graph.get(node, []):
if neighbor not in visited:
dfs(graph, neighbor, visited)
graph = {
1: [2, 3],
2: [4, 5],
3: [6],
4: [],
5: [],
6: []
}
dfs(graph, 1) # Вывод: 1 2 4 5 3 6
7. Обход графа (BFS)
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
node = queue.popleft()
if node not in visited:
print(node, end=" ")
visited.add(node)
queue.extend(graph.get(node, []))
bfs(graph, 1) # Вывод: 1 2 3 4 5 6
8. Проверка на простоту (метод пробного деления)
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
print(is_prime(29)) # Вывод: True
9. Жадный алгоритм (размен монет)
def coin_change(coins, amount):
coins.sort(reverse=True)
count = 0
for coin in coins:
while amount >= coin:
amount -= coin
count += 1
return count if amount == 0 else -1
print(coin_change([1, 5, 10, 25], 63)) # Вывод: 6 (25+25+10+1+1+1)
10. Алгоритм Дейкстры (поиск кратчайшего пути)
import heapq
def dijkstra(graph, start):
heap = [(0, start)]
shortest = {node: float('inf') for node in graph}
shortest[start] = 0
while heap:
(cost, node) = heapq.heappop(heap)
for neighbor, weight in graph[node]:
new_cost = cost + weight
if new_cost < shortest[neighbor]:
shortest[neighbor] = new_cost
heapq.heappush(heap, (new_cost, neighbor))
return shortest
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 5)],
'C': [('D', 1)],
'D': []
}
print(dijkstra(graph, 'A')) # Вывод: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
Эти алгоритмы покрывают основные задачи: сортировку, поиск, работу с графами, жадные алгоритмы и динамическое программирование. Если тебе нужно что-то еще, спрашивай! 🚀