NovaLingua - форум любителей лингвистики

Делюсь моим опытом.
Изучать начали одновременно с внуком на бесплатных курсах для школьников в одной широко разрекламированной онлайн-школе. Занятия 3 раза в неделю по 1,5 часа + перерыв, итого почти 2 часа. Курсы начались где-то в конце октября. И сразу после этого я серьёзно заболела (реактивный синовит колена), 3 недели почти не ставала, нужно было себя чем-то занять.
(В скобках замечу, что летом, наконец, купила смартфоны себе и мужу, изучила весь рынок и выбрала Cubot P60. Шикарный телефон за 8 т.р., неплохая камера, много памяти, андроид 12. На чем они сэкономили - монозвук. Впрочем, для нас это некритично. Отсутствие музыкального слуха - это у нас семейное.)
Ну вот я лежу на диване с распухшим коленом, в руках - новая игрушка. На онлайн-курсах дали ссылку на Sololearn (армяно-американская обучающая платформа, получившая тучу грантов, наград и т. д.) - захожу туда через свой гугл-аккаунт, создаю там свой аккаунт и записываюсь на курс Питон для начинающих, русифицированный. Там какая-то теория, после теории небольшие и очень простые задания, курс сделан хорошо, подробно. К каждому заданию люди из разных стран пишут комментарии, ощущение, что все побежали, и я побежала  ;D прохожу эту курс за один день. Получаю сертификат. Тут же записываюсь на курс Питон для продолжающих - сделан совершенно халтурно, ничему научиться невозможно. Дошла до середины, бросила, стала осматриваться. На сайте какая-то движуха, какие-то поединки, все что-то пишут. Главное хорошее, что там есть - тренажеры кода. Условие задачи обычно большое, приближенное к реальной жизни, на английском (заодно и английский освежить). Пишешь программу, запускаешь, она или проходит ряд тестов, и пишет ошибку.
Там я перерешала (на питоне) все задачи средней трудности и все сложные, кроме двух. Одна - парсер арифметических выражений, хочу сделать её с помощью классов. Вторая - вывести любой заданный знак числа π. Неохота разбираться с математикой, какой там ряд удобнее суммировать.
1. Первая моя рекомендация - если есть возможность пользоваться Sololearn, то воспользуйтесь их тренажерами.
Приложение чисто мобильное, но я зашла с десктопа в почту, попыталась подтвердить регистрацию, что-то пошло не так. В результате бесплатный 14-дневный период у меня давно закончился, подписки на них у меня нет, а приложение и аккаунт есть.

Потом я стала искать ещё курсы и нашла бесплатные курсы Code Basics от компании ООО «Хекслет Рус», 432071, г. Ульяновск, пр-т Нариманова, дом 1Г, оф. 23, Russian Federation. Курсы по языкам с самыми начальными сведениями бесплатно, продолжение с новогодней скидкой 120 т.р.
Курс по питону для начинающих сделан хорошо, есть тренажеры кода, все очень подробно и обстоятельно, на середине обрывается. Его тоже прошла очень быстро. Можно проходить и на десктопе, и на мобилке, но результаты не переносятся. Есть обсуждение, есть дежурные модераторы, от которых можно получить какую-то обратную связь.
https://code-basics.com/ru
2. Вторая моя рекомендация: если вы очень начинающий можно и там пройти курс.

Затем я нашла курсы на codebra, там с меня взяли 999 р. Тренажеры сделаны плохо. Собственно, нужно самому в чем-то написать программу, затем загрузить файл к ним на сайт, и ещё ждать, когда прострекочет. Где=то на середине курса, с началом функций, тренажеры вообще исчезли, остались одни тесты. Создают видимость каких-то заданий.
3. Но всё же рекомендую и этот курс: автор курса очень хорошо пишет про функции, про области видимости, про локальные и глобальные переменные, с примерами программ. Вот именно эта сложная тема очень хорошо разобрана.
 
Дальше функций я пока не читала, т.к. в поисках практики и тренажеров нашла другую платформу: Stepik.

     

Это Stepik
https://stepik.org/learn

Там много чего, или бесплатно, или за небольшие деньги.
Я выбрала линейку "Поколение Пайтон" из трёх курсов: для начинающих, для продолжающих, для профессионалов. Первые два бесплатные, второй с новогодней скидкой около четырех тысяч.
Первый курс я полностью прошла, сегодня получила сертификат.
Огоромное количество задач и тренажеров кода!
Задачи советско-школьного типа, т.е. академические. Хотя явно делали под Sololearn.
Но для школьника и для начинающего - очень хорошо, натренироваться, руку набить на стандартных алгоритмических конструкциях. Есть, конечно, что мне не очень понравилось... С другой стороны, я уже и не совсем начинающий.
Так что всем рекомендую, а сама перехожу на второй курс - питон для продолжающих.

Теперь о курсах той самой онлайн-школы. Пока я два месяца била по клавишам на всех тренажерах кода, внук смотрел на вебинарах, как преподаватель (хороший, кстати) самозабвенно пишет программы. Никаких тренажеров кода, никаких дз написать программу. Да и кто ее будет проверять, если у препода 3 группы, в каждой 50 человек и цель не научить программировать, а сохранить контингент. Т.е. довести максимальное количество бездельников до выпуска, давая им несложные заданья. Собственно, как и везде с подушевым финансированием.
Отправила его на степик, уже что-то пишет.

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

Вот самое сложное заданье из первого курса - запрограммировать шифровку/дешифровку кода Цезаря для русского и английского языков. Вчера полдня писала. С английским программа заработала - с русским не работает. С русским языком чего только не узнаешь.  Например, что буква ё не находится среди букв русского алфавита.
Вот моё решение

# шифр Цезаря
# ввод языка
def input_lang():
    lang = input('Укажите язык ru/en ').lower()
    while lang != 'ru' and lang != 'en':
        lang = input('Укажите язык ru/en ').lower()
    return lang   

# ввод ключа шифрования
def input_key(lan):
# lan - язык, en или ru
    s = input('Укажите ненулевое целое число k ключ шифровки/дешифровки k/-k ')
    if len(s) >= 2 and s

• == '-' and s[1:].isdigit():

        k = -1*int(s[1:])
    elif s.isdigit():
        k = int(s)
    else:
        print("Ошибка ввода!")
        return input_key(lan)
   
    if lan == "ru":
        len_lan = 32 # мощность русского алфавита
        return k % len_lan 
    elif lan == "en":
        len_lan = 26 # мощность английского алфавита
        return k % len_lan
   
# ввод текста
def input_text():
    return input("Укажите строку ")

# замена одного символа
def replace_up_and_low(lang, k, i, text, f):
# lang - язык, k - ключ шифрования/дешифровки, text - строка, i - позиция символа в строке, f - регистр, up или low 
    if f == 'up' and lang == "en":
        len_lan = 26
        num = ord("A")
    elif f == 'low' and lang == "en":
        len_lan = 26
        num = ord("a")
    elif f == 'up' and lang == "ru":
        len_lan = 32
        num = ord("А")
    elif f == 'low' and lang == "ru":
        len_lan = 32
        num = ord("а")       
    p = (ord(text) - num + k) % len_lan
    p = p + num
    return text[:i] + text[i:].replace(text, chr(p), 1)

# шифрование
def encryption(lan, k, text):
    for j in range(len(text)):
        if text[j].islower():
            text = replace_up_and_low(lan, k, j, text, "low")
        elif text[j].isupper():
            text = replace_up_and_low(lan, k, j, text, "up")
    return text       

# main
language = input_lang()
key = input_key(language)
user_text = input_text()
print(encryption(language, key, user_text))

Цитата: Vesle Anne от 08 января 2024, 21:51Есть еще литкод - там много разных задачек. Также рекомендую Хирьянова (правда, это внуку, наверное, еще рано - в открытом доступе вроде только его университетский курс есть, а фоксфордовский, для школьников, за денежку, насколько мне известно).

С Хирьяновым? Там разные преподы есть вроде.

@_Swetlana
пользуйтесь тэгом [code], пожалуйста, он специально для этого и придуман. А то движок форума ваш код гробит.
Что до шифра Цезаря, то зачем пользователю выбирать между русским и английским алфавитом? Пусть программа работает сразу с обоими.

А сколько лет внуку?

Написал свой вариант.
Любую введенную строку программа пытается и зашифровать, и расшифровать.
Так что можно побаловаться, посмотреть, как происходит преобразование.

alphabets = (
        'ABCDEFGHIJKLMNOPQRSTUVWXYZ',
        'abcdefghijklmnopqrstuvwxyz',
        'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ',
        'абвгдеёжзийклмнопрстуфхцчшщъыьэюя',
    )

key = int(input('Enter the key: '))
print()

go_on = True

while go_on:
    text = input('Enter text: ')
    if text == '':
        go_on = False
    if go_on:
        encrypted = text
        decrypted = text
        for i in range(len(text)):
            for alphabet in alphabets:
                if text[i] in alphabet:
                    pos = [j for j in range(len(alphabet)) if alphabet[j] == text[i]][0]
                    encrypted = encrypted[:i]+alphabet[(pos+key)%len(alphabet)]+encrypted[i+1:]
                    decrypted = decrypted[:i]+alphabet[(pos-key)%len(alphabet)]+decrypted[i+1:]
        print('Encrypted: ', encrypted)
        print('Decrypted: ', decrypted)
        print()

Образец исполнения:

Enter the key: 10

Enter text: Куда идём мы с Пятачком is a very big secret.
Encrypted:  Фэнй тнпц це ы Щиьйбфшц sc k fobi lsq combod.
Decrypted:  Бйъц яъьг гс з Ёхицнбег yi q luho ryw iushuj.

Enter text: Фэнй тнпц це ы Щиьйбфшц sc k fobi lsq combod.
Encrypted:  Южчу ьчща ао е Гтёукюва cm u pyls vca mywlyn.
Decrypted:  Куда идём мы с Пятачком is a very big secret.

Enter text:

Зато проблем с Ё нет.

Можно находить номер буквы в алфавите и покороче: через метод find, но я об этом методе не знал, и ребенок, наверное, тоже знать не должен. Такие вещи нагугливаются по мере необходимости.
А вот без list comprehensions в питоне делать нечего.

alphabets = (
        'ABCDEFGHIJKLMNOPQRSTUVWXYZ',
        'abcdefghijklmnopqrstuvwxyz',
        'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ',
        'абвгдеёжзийклмнопрстуфхцчшщъыьэюя',
    )

key = int(input('Enter the key: '))
print()

go_on = True

while go_on:
    text = input('Enter text: ')
    if text == '':
        go_on = False
    if go_on:
        encrypted = text
        decrypted = text
        for i in range(len(text)):
            for alphabet in alphabets:
                if text[i] in alphabet:
                    pos = alphabet.find(text[i])
                    encrypted = encrypted[:i]+alphabet[(pos+key)%len(alphabet)]+encrypted[i+1:]
                    decrypted = decrypted[:i]+alphabet[(pos-key)%len(alphabet)]+decrypted[i+1:]
        print('Encrypted: ', encrypted)
        print('Decrypted: ', decrypted)
        print()


Спасибо, Hellerick!
Сейчас буду изучать ваш код))

Цитата: lammik от 09 января 2024, 06:02А сколько лет внуку?

Внук в 10 классе, в след. году будем готовиться к сдаче ЕГЭ по информатике на питоне.
Соответственно, план такой. В этом году изучаем питон, а в след. году бессмысленное и беспощадное натаскивание на решение егэшных задач.
Интересно, что каждый год в егэ добавляют какой-нибудь самый простой вариант из тех задач, что я читала второкурсникам. То на графе найти центр или медиану, только граф такого вида, что матрицу расстояний можно вручную сделать, без алгоритма Флойда, то что-нибудь из динамического программирования. 

Цитата: Vesle Anne от 08 января 2024, 22:03С Хирьяновым? Там разные преподы есть вроде.

Нет, Хирьянова на этих курсах нет.

Самая страшная строка моего скрипта выглядет особенно страшной из-за использования там слайсинга: разрезания строки выражениями типа word[:1].
Мне пришлось прибегнуть к нему из-за того, что формат данных строковых переменных в питоне не позволяет их значения изменять, он позволяет их значения только заменять.
Нельзя написать

word = "мама"
word[0] = "р"
и надеяться, что теперь word равно "рама". Интерпретатор выдаст TypeError.
Вот и приходится строку разрезать, заменять кусок и обратно соединять.
Зато в списках отдельные их элементы заменять можно.
К счастью, строки и списки можно легко преобразовывать друг в друга.

word = list("мама")
word[0] = "р"
word = ''.join(word)
Получается "рама". Пустое место между кавычками -- это знак, который будет вставлен между соединяемыми буквами.
С использованием этого приема в моем скрипте можно избавиться от слайсинга:

alphabets = (
        'ABCDEFGHIJKLMNOPQRSTUVWXYZ',
        'abcdefghijklmnopqrstuvwxyz',
        'АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ',
        'абвгдеёжзийклмнопрстуфхцчшщъыьэюя',
    )

key = int(input('Enter the key: '))
print()

go_on = True

while go_on:
    text = input('Enter text: ')
    if text == '':
        go_on = False
    if go_on:
        encrypted = list(text)
        decrypted = list(text)
        for i in range(len(text)):
            for alphabet in alphabets:
                if text[i] in alphabet:
                    pos = alphabet.find(text[i])
                    encrypted[i] = alphabet[(pos+key)%len(alphabet)]
                    decrypted[i] = alphabet[(pos-key)%len(alphabet)]
        print('Encrypted: ', ''.join(encrypted))
        print('Decrypted: ', ''.join(decrypted))
        print()


Цитата: Hellerick от 09 января 2024, 17:24Самая страшная строка моего скрипта выглядет особенно страшной из-за использования там слайсинга: разрезания строки выражениями типа word[:1].

Вспомнился американский лингвистический анекдот:
Вам сыр послайсить, или целым писом возьмёте?

Подоспело новое заданье из курса для продвинутых.

Задача Иосифа Флавия
В 67 году н.э. во время иудейско-римской войны Иосиф Флавий и сорок мятежников оказались в ловушке в пещере. Предпочтя самоубийство плену, они решили встать в круг и убивать каждого третьего из оставшихся в живых. Иосиф Флавий хотел остаться в живых и понял, где он должен стоять в кругу, чтобы остаться в живых в череде казней. Так он выжил, чтобы рассказать эту легенду.

Хорошие картинки вот здесь
https://habr.com/ru/articles/709540/
В обсуждении ссылка на библиотеку алгоритмов, там собраны все алгоритмы решения.

Вначале, конечно, пыталась вывести аналитическую формулу, тихо сетовала, что совсем дура стала. Потом погуглила и выяснила, что формулы нет. Что, в общем, не противоречит предыдущему высказыванию.
Рекурсивное соотношение тоже не сразу вывела. Но вывела  :)

# задача Иосифа Флавия, нумерация с 0
n = int(input()) # количество игроков, нумерация начинается с 0
k = int(input()) # вычеркиваем каждого k-го

# граничное условие рекурсии:
    # при одном игроке он же оставшийся: flavius(1, _) = 0
# рекуррентное соотношение для n игроков:
    # flavius(n, k) = (flavius(n-1, k) + k) mod n

def flavius(nn, kk):
    if nn == 1: return 0
    elif nn == 2:
        if kk % 2 == 0: return 0
        else: return 1
    else:
        return (flavius(nn-1, kk) + kk) % nn

res_rek = flavius(n, k)

f0 = 0 # n = 1, номер оставшегося - 0
for i in range(2, n + 1):
    f1 = (f0 + k) % i # n = i, f1 - номер оставшегося при нумерации с 0
    f0 = f1

res_vector = f1   

if res_rek == res_vector:
    print(res_vector + 1) # номер при нумерации с 1


Потом открыла правильное решение.
Нужно было так делать
res = 0
for i in range(1, n+1):
    res = (res + k) % i


Честно говоря, ничего в этих алгоритмах не понимаю.
Нельзя было просто так сделать?
n = int(input('Number of people: '))
k = int(input('Count for execution: '))
people = [i+1 for i in range(n)]
while len(people)>=k:
    people = people[3:]+people[:2]
print('Survivors:', people)

Почему у вас вообще один человек остается? Разве их не двое должно быть? Кто третий среди двоих?
Кстати, на эту тему был неплохой сериал. https://www.kinopoisk.ru/series/405546/

Среди двоих третьим станет первый по счёту.

Так что в конце останется только один.

Цитата: Vesle Anne от 08 января 2024, 21:51а фоксфордовский, для школьников, за денежку, насколько мне известно).

Лежит на Рутрекере.

Цитата: lammik от 11 января 2024, 09:59Среди двоих третьим станет первый по счёту.

Не убивал Иосиф первого.

Цитата: Иудейская война (Иосиф Флавий; Черток)/Книга третьяПо счастливой ли случайности, а быть может по божественному предопределению, остался последним именно Иосиф ещё с одним. А так как он не хотел ни самому быть убитым по жребию, ни запятнать свои руки кровью соотечественника, то он убедил и последнего сдаться римлянам и сохранить себе жизнь.

А в Англовики первого вообще называют его сообщником.

Цитата: lammik от 11 января 2024, 10:01

Цитата: Vesle Anne от 08 января 2024, 21:51а фоксфордовский, для школьников, за денежку, насколько мне известно).

Лежит на Рутрекере.

БПЧ! (большое человеческое спасибо)

Цитата: _Swetlana от 11 января 2024, 16:27БПЧ! (большое человеческое спасибо)

Да не за что, я всегда там изначально ищу что угодно. Но связи "БПЧ" и "большого человеческого спасибо" не уловил. :)

Цитата: lammik от 11 января 2024, 17:51

Цитата: _Swetlana от 11 января 2024, 16:27БПЧ! (большое человеческое спасибо)

Да не за что, я всегда там изначально ищу что-угодно. Но связи "БПЧ" и "большого человеческого спасибо" не уловил. :)

Это я на смартфоне набирала. Куда палец попадёт, туда и ладно  ;D

Цитата: Hellerick от 11 января 2024, 04:37Честно говоря, ничего в этих алгоритмах не понимаю.
Нельзя было просто так сделать?

Код Выделить Развернуть

n = int(input('Number of people: '))
k = int(input('Count for execution: '))
people = [i+1 for i in range(n)]
while len(people)>=k:
    people = people[3:]+people[:2]
print('Survivors:', people)

А я не поняла, как это работает. Но элегантно выглядит, это да.

Цитата: _Swetlana от 11 января 2024, 20:04А я не поняла, как это работает. Но элегантно выглядит, это да.

Да элементарно: выставляем народ в очередь, третьего убиваем, а двоих, которые были перед ним, переставляем в конец очереди. Повторяем так, пока в очереди не осталось двое.
Ну, если хочется, можно конечно и переделать, чтобы только один оставался. Тогда там номер жертвы надо будет находить через остаток от деления на число оставшихся людей.
Тьфу, черт, у меня там ошибка: я числа 3 и 2 жестко указал. Надо было на их месте k и k-1 написать.

Цитата: Hellerick от 11 января 2024, 20:18

Цитата: _Swetlana от 11 января 2024, 20:04А я не поняла, как это работает. Но элегантно выглядит, это да.

... числа 3 и 2 жестко указал. Надо было на их месте k и k-1 написать.

То-то я смотрю, что от k внутри цикла ничего не зависит.
Выч. сложность получится порядка n^2 / 2.
А с помощью рекуррентного соотношения будет линейный алгоритм O(n).

Вот сейчас затупила.

ЦитироватьНапишите программу для определения, является ли число произведением двух чисел из данного набора. Программа должна выводить результат в виде ответа «ДА» или «НЕТ».

Формат входных данных
В первой строке подаётся число n(0<n<1000) – количество чисел в наборе. В последующих n строках вводятся целые числа, составляющие набор (могут повторяться). Затем следует целое число, которое является или не является произведением двух каких-то чисел из набора.

Формат выходных данных
Программа должна вывести «ДА» или «НЕТ» в соответствии с условием задачи.

Примечание 1. Само на себя число из набора умножиться не может. Другими словами, два множителя должны иметь разные индексы в наборе.

Примечание 2. Для решения задачи используйте вложенные циклы.

Какие ещё вложенные циклы. Рекурсией надо писать! 
Посмотрела: в питоне нет оптимизации хвостовой рекурсии. Видимо, надо про рекурсию забыть. Всё-таки после пролога питон тяжеловато идет.

Не, ну рекурсия-то тоже временами используется, но лучше без нее.

Цитата: Vesle Anne от 11 января 2024, 21:41Не, ну рекурсия-то тоже временами используется, но лучше без нее.

Ну вот я не представляю, как эту задачу можно сделать вложенными циклами. Смена т.н. парадигмы - тяжёлое дело. Это я ещё до классов не дошла.

Цитата: _Swetlana от 11 января 2024, 21:32Какие ещё вложенные циклы. Рекурсией надо писать! 

А потом народ удивляется, что это программам памяти не хватает :) Ну хотя как раз рекурсией меньше всего риска забыть потом освободить память, но зато и занимается больше, и больше риска влететь - стек-то не резиновый.

Цитата: Toman от 11 января 2024, 22:50

Цитата: _Swetlana от 11 января 2024, 21:32Какие ещё вложенные циклы. Рекурсией надо писать!

А потом народ удивляется, что это программам памяти не хватает :) Ну хотя как раз рекурсией меньше всего риска забыть потом освободить память, но зато и занимается больше, и больше риска влететь - стек-то не резиновый.

Спокойствие, только спокойствие.
Догадалась перечитать условие. Произведение двух чисел. Двух.
А если не двух, то это NP-полная задача. Правда, ее можноделать не алгоритмом с возвратом, который как раз стандартно пишется рекурсивно, а динамическим программированием, заполняя табличку nXb, где n - число сомножителей, а b - набираемое произведение. То есть составляется рекуррентное соотношение, как в предыдущей задаче про Иосифа.

Цитата: Toman от 11 января 2024, 22:50

Цитата: _Swetlana от 11 января 2024, 21:32Какие ещё вложенные циклы. Рекурсией надо писать!

А потом народ удивляется, что это программам памяти не хватает :) Ну хотя как раз рекурсией меньше всего риска забыть потом освободить память, но зато и занимается больше, и больше риска влететь - стек-то не резиновый.

Есть такой предмет - рекурсивное программирование, есть языки, которые оптимизированы для работы с рекурсией. Увы, питон к ним не относится. Рекурсия очень экономит силы программиста и уменьшает время разработки.
Если вам интересно, могу показать примеры на прологе.

Цитата: _Swetlana от 11 января 2024, 21:32

ЦитироватьПримечание 2. Для решения задачи используйте вложенные циклы.

Если бы не это странное требование, то задача решалась бы очень просто:

multipliers = set()
for i in range(int(input('Количество множителей: '))):
    multipliers |= {int(input(f'Число №{i+1}: '))}
number = int(input('Проверяемое число: '))
if any([number/m in multipliers and number/m!=m for m in multipliers]):
    print('ДА')
else:
    print('НЕТ')
Куда там запихивать циклы или рекурсии, ума не приложу.

Прикола ради можно записать так:

multipliers = {int(input(f'Число №{i+1}: ')) for i in range(int(input('Количество множителей: ')))}
number = int(input('Проверяемое число: '))
print(('НЕТ', 'ДА')[any([number/m in multipliers and number/m!=m for m in multipliers])])

Цитата: Hellerick от 12 января 2024, 07:00

Цитата: _Swetlana от 11 января 2024, 21:32

ЦитироватьПримечание 2. Для решения задачи используйте вложенные циклы.

Если бы не это странное требование, то задача решалась бы очень просто:

Код Выделить Развернуть

multipliers = set()
for i in range(int(input('Количество множителей: '))):
    multipliers |= {int(input(f'Число №{i+1}: '))}
number = int(input('Проверяемое число: '))
if any([number/m in multipliers and number/m!=m for m in multipliers]):
    print('ДА')
else:
    print('НЕТ')
Куда там запихивать циклы или рекурсии, ума не приложу.

1. Ну они это любят делать. Решать задачу только так, чтобы что-то отработать. В начале курса для начинающих у них много заданий на печать. Когда я поинтересовалась, почему не дают f-строки, чтобы сразу приучить к правильной печати, меня строго отчитали, что уклонилась. Я уклонист.

2. Произведение из двух сомножителей. Подразумевалось, что первый цикл подбирает первый сомножитель, а вложенный второй - второй.

3. Труднее всего мне было запихивать рекурсию в сортировку пузырёк - уж очень она алгоритмична.
Когда предложила это заданье студентам (дистанционно, в 2020 году), одна девочка мне написала в комментарии: Как не стыдно давать такие заданья!  ;D
С другой стороны, если у тебя нет глобальных переменных и управляющих операторов, а хочется хочется сохранить идею алгоритма, то без рекурсии и не напишешь. 

Можно еще вот так написать:

multipliers = set()
for i in range(int(input('Количество множителей: '))):
    multipliers |= {int(input(f'Число №{i+1}: '))}
number = int(input('Проверяемое число: '))
found = any([a*b==number for a in multipliers for b in multipliers if a!=b])
if found:
    print('ДА')
else:
    print('НЕТ')
Это считается вложенным циклом?

ЦитироватьТруднее всего мне было запихивать рекурсию в сортировку пузырёк - уж очень она алгоритмична.

Вот это как раз у Хирьянова было, в курсе для студентов. Ща поищу ссылку

Цитата: Hellerick от 12 января 2024, 17:29Можно еще вот так написать:

Код Выделить Развернуть

multipliers = set()
for i in range(int(input('Количество множителей: '))):
    multipliers |= {int(input(f'Число №{i+1}: '))}
number = int(input('Проверяемое число: '))
found = any([a*b==number for a in multipliers for b in multipliers if a!=b])
if found:
    print('ДА')
else:
    print('НЕТ')
Это считается вложенным циклом?

Да, считается. Сразу не ответила, т.к. функцию any  не знала.

Ссылка на лекцию
Пузырьковая сортировка где-то в конце

Цитата: Vesle Anne от 13 января 2024, 21:52Ссылка на лекцию

Пузырьковая сортировка где-то в конце

Спасибо, Аня! Интересно вообще послушать умного молодого человека))

Всегда пожалуйста  :) мне очень нравится как он объясняет, прям буквально все разжевывает.

Цитата: Vesle Anne от 14 января 2024, 11:52Всегда пожалуйста  :) мне очень нравится как он объясняет, прям буквально все разжевывает.

Про рекурсию там следующая лекция, эта без рекурсии. Там он грит: рекурсия свойственна менталитету русского человека! Тут я, как говаривал WM,  немножко взоржала. Ну хороший лектор и должен быть немножко клоун)) Хорошо читает, но все-таки немножко косячит.
Дело в том, что при записи алгоритма (нуилисразу программы) всегда что-нибудь забудешь. Хочется, конечно, писать и тут же комментировать, повернувшись к доске передом, к студентам задом, но лучше не малодушествовать, а взять лист с предварительно написанным алгоритмом и со словами: щас я напишу, а потом мы все обсудим, - молча переписать этот текст на доску.

Мне нравится как он читает  :-[  потому и поделилась ссылкой

Цитата: Vesle Anne от 14 января 2024, 14:56Мне нравится как он читает  :-[  потому и поделилась ссылкой

Да мне тоже нравится. Он отлично читает! Так уже никто не читает - все картинки показывают и подписи под картинками читают. Новомодная манера. Ну подписи тоже можно с выражением читать)) Ну и детализировать.
Просто в лекции про рекурсию он в самом начале путается и немножко морочит студентам голову. Или у него конспекта нет, или он считает, что испортит впечатление о себе, если зайдет с конспектом)) Но ничего, они все как зайчики там сидят, терпеливо ждут.

 
 

Нет, это он в начале 8 лекции маненько запутался, а 7-я тоже про рекурсию. Надо мне их (7 и 8) спокойно посмотреть, без перематывания. А заодно и 9. Во вторник выделю на это время.

Щас решила задачку списковыми включениями. Ну и хитросделанный синтаксис.   

ЦитироватьНа вход программе подается число n. Напишите программу, которая создает и выводит построчно список, состоящий из n списков [[1, 2, ..., n], [1, 2, ..., n], ..., [1, 2, ..., n]].

m = int(input())
print(*[[int(i) for i in range(1, m+1)] for _ in range(m)], sep='\n')

ЦитироватьПостулат Бертрана
Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого n > 1 найдется простое число p в интервале n < p < 2n. Такая гипотеза была выдвинута в 1845 году французским математиком Джозефем Бертраном (проверившим ее до n=3000000) и доказана в 1850 году Пафнутием Чебышевым. Рамануджан в 1920 году нашел более простое доказательство, а Эрдеш в 1932 – еще более простое.

Ваша задача состоит в том, чтобы решить несколько более общую задачу – а именно по числу n найти количество простых чисел p из интервала n < p < 2n.

Напомним, что число называется простым, если оно делится только само на себя и на единицу.

from math import sqrt

# Функция формирует множество простых чисел, не превосходящих n,
# при условии, что мн-во pnums простых чисел, не превосходящих n0, уже сформировано.
# По умолчанию n0 = 2  и начальное множество простых чисел = {2}
def Eratosthen(n, n0=2, pnums={2}):
    if n == 1: return {}
   
    res = {i for i in range(n0 + 1, n+1)} # мн-во всех натуральных чисел в диапазоне [n0+1, n]
    maxp = int(sqrt(n)) + 1 # наибольший возможный простой делитель числа n
    maxp0 = max(pnums) # максимальное простое число из готового списка
    # для числа n формируем список его возможных делителей
    if maxp0 >= maxp:
        test = [i for i in pnums if i <= maxp] # выбираем из готового списка простых делителей
    else:
        test = list(pnums) + [i for i in range(maxp0+1, maxp + 1)] # к готовому списку добавляем числа в диапазоне [maxp0+1, maxp]
   
    for k in test:
        temp = {k*i for i in range(2, int(n/k) + 1)} # множество составных чисел, кратных k, в диапазоне [2k, n]
        res = res - temp # вычитаем множество составных чисел из целевого множества
    return res | pnums # добавляем исходное множество простых чисел к целевому

n1 = int(input())
set1 = Eratosthen(n1)
print(len(Eratosthen(2*n1 - 1, n1, set1)) - len(set1))


В фф окончательно отказались от намерения научить детей питону. Пришлось всё бросить и срочно записаться на степике на очень небольшой бесплатный курс HTML и CSS.

много_кроликов.png

Ну что ж так?

Знать базу, конечно, полезно, но, по-моему, последние лет двадцать странички так не делают.

Цитата: Vesle Anne от 10 марта 2024, 13:22Ну что ж так?

Негодяи. Теперь до конца мая будут html и css учить. Так и тому учить нормально не могут. Дети вроде загорелись, все хотят сайты делать, и уже после второго занятия стало непонятно, что к чему. Щас на степике читаю - все понятно.

Другое дело, насколько это все актуально для сайтостроения  :donno:

P.S. седни мне со степика пришло письмо-увещевание: что же вы записались на ООП и не заходите? Не надо отчаиваться! Занимайтесь, и у вас все получится!

Раз уж мы затронули frontend-разработку:
https://habr.com/ru/articles/800579/

Не, меня html интересует максимум в контексте парсинга сайтов. Не мое.

Цитата: Vesle Anne от 15 марта 2024, 21:40Не, меня html интересует максимум в контексте парсинга сайтов. Не мое.

Хочу сделать свой пет-проект,
онлайн- сервис для оптимального размещения обслуживающих центров (центров и медиан) с ограничениями (стандартные алгоритмы размещают без ограничений). М.б., и html пригодится  :)

Кстати, вчера, наконец, написала на питоне образцы восходящей и нисходящей рекурсии. Сегодня выложу с об'яснением. Оптимизация хвостовой рекурсии вообще важная вещь, жалко, что в питоне этого нет.

Цитата: _Swetlana от 16 марта 2024, 10:11онлайн- сервис для оптимального размещения обслуживающих центров (центров и медиан) с ограничениями (стандартные алгоритмы размещают без ограничений). М.б., и html пригодится  :)

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

Цитата: Hellerick от 16 марта 2024, 10:37

Цитата: _Swetlana от 16 марта 2024, 10:11онлайн- сервис для оптимального размещения обслуживающих центров (центров и медиан) с ограничениями (стандартные алгоритмы размещают без ограничений). М.б., и html пригодится  :)

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

Любопытно. Никогда не думала об этой задаче в таком ключе. А как вы сформулирует критерий оптимизации?

На степике 23 марта в 12.00 будет конкурс: питон + задачи на логику. Я записалась ;D

https://habr.com/ru/articles/799511/

Цитата: _Swetlana от 16 марта 2024, 10:39

Цитата: Hellerick от 16 марта 2024, 10:37

Цитата: _Swetlana от 16 марта 2024, 10:11онлайн- сервис для оптимального размещения обслуживающих центров (центров и медиан) с ограничениями (стандартные алгоритмы размещают без ограничений). М.б., и html пригодится  :)

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

Любопытно. Никогда не думала об этой задаче в таком ключе. А как вы сформулирует критерий оптимизации?

Необходимо придумать алгоритм постепенного заполнения заданной области центрами в количестве от 1 до N.
Критерий: составляем таблицу, в которой для числа центров от 2 до N указывается соответствующее отношение нагрузки наиболее загруженного центра к наименее загруженному. Идеальным алгоритмом является тот, при котором максимальное значение в этой таблице минимально.

Для начала можно потренироваться на одномерном пространстве. Условно говоря, мы разрабатываем однотипную продукцию в разных ценовых категориях. На какие именно ценовые категории нам надо ориентироваться, если мы каждый год выпускаем по новой модели и хотим избежать того, чтобы в каком-то ценовом диапазоне наши продукты слишком толпились, а в другом были мало представлены.

Цитата: Hellerick от 16 марта 2024, 10:57

Цитата: _Swetlana от 16 марта 2024, 10:39

Цитата: Hellerick от 16 марта 2024, 10:37

Цитата: _Swetlana от 16 марта 2024, 10:11онлайн- сервис для оптимального размещения обслуживающих центров (центров и медиан) с ограничениями (стандартные алгоритмы размещают без ограничений). М.б., и html пригодится  :)

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

Любопытно. Никогда не думала об этой задаче в таком ключе. А как вы сформулирует критерий оптимизации?

Необходимо придумать алгоритм постепенного заполнения заданной области центрами в количестве от 1 до N.
Критерий: составляем таблицу, в которой для числа центров от 2 до N указывается соответствующее отношение нагрузки наиболее загруженного центра к наименее загруженному. Идеальным алгоритмом является тот, при котором максимальное значение в этой таблице минимально.

Для начала можно потренироваться на одномерном пространстве. Условно говоря, мы разрабатываем однотипную продукцию в разных ценовых категориях. На какие именно ценовые категории нам ориентироваться, если мы каждый год выпускаем по новую модель и хотим избежать того, чтобы в каком-то ценовом диапазоне наши продукты слишком толпились, а в другом были мало прставлены.

Интересно, подумаю.

Суммируем числа от 1 до 7 восходящей и нисходящей рекурсией. Для определённости в обоих случаях идёт перебор слагаемых от 7 до 1. Можно было, конечно, наоборот.
 
# Задача о нахождении суммы первых n натуральных чисел

def ascending_recursion(n: int, partial_sum) -> int:
    # восходящая или хвостовая рекурсия
    # 1) Главный признак - нет отложенного действия, т.к. рекурсивный вызов является последней операцией перед возвратом из функции.
    # 2) В рекурсию в качестве параметра передается текущая частичная сумма, поэтому частичная сумма известна на каждом уровне рекурсии.
    # 3) Обнуление суммы происходит при вызове.
    # 4) Оптимизация хвостовой рекурсии (в некоторых языках программирования) снимает ограничения на глубину рекурсии.
   
    if n == 0: return partial_sum # граничное условие рекурсии
    return ascending_recursion(n - 1, partial_sum + n) # рекурсивный вызов

def descending_recursion(n: int) -> int:
    # нисходящая рекурсия
    # 1) Главный признак - есть отложенное действие: пока вызов рекурсивный вызов не вернул результат, слагаемое уходит в стек.
    # 2) При выполнении граничного условия рекурсии происходит обнуление суммы. К этому времени все члены последовательности находятся в стеке.
    # 3) В рекурсию передается только граничное значение члена последовательности, частичные суммы до останова рекурсии не известны.

    if n == 0: return 0 # граничное условие рекурсии
    return n + descending_recursion(n - 1) # рекурсивный вызов
 
print(f"восходящая рекурсия: S(7) = {ascending_recursion(7, 0)}")
print(f"нисходящая рекурсия: S(7) = {descending_recursion(7)}")

Цитата: _Swetlana от 16 марта 2024, 10:11

Цитата: Vesle Anne от 15 марта 2024, 21:40Не, меня html интересует максимум в контексте парсинга сайтов. Не мое.

Хочу сделать свой пет-проект,
онлайн- сервис для оптимального размещения обслуживающих центров (центров и медиан) с ограничениями (стандартные алгоритмы размещают без ограничений). М.б., и html пригодится  :)

я в качестве пет-проекта своего бота буду допиливать. В следующем месяце, в этом все ресурсы колаба закончились уже  :D

Цитата: Vesle Anne от 16 марта 2024, 11:42

Цитата: _Swetlana от 16 марта 2024, 10:11

Цитата: Vesle Anne от 15 марта 2024, 21:40Не, меня html интересует максимум в контексте парсинга сайтов. Не мое.

Хочу сделать свой пет-проект,
онлайн- сервис для оптимального размещения обслуживающих центров (центров и медиан) с ограничениями (стандартные алгоритмы размещают без ограничений). М.б., и html пригодится  :)

я в качестве пет-проекта своего бота буду допиливать. В следующем месяце, в этом все ресурсы колаба закончились уже  :D

А у колаба какие-то ограничения есть?

Цитата: _Swetlana от 16 марта 2024, 16:38А у колаба какие-то ограничения есть?

Есть  :)   Но с простыми программами вы их не увидите.
Я только на диффузионках сдалась и купила платный  :) ну и llm гонять тоже не просто.

Цитата: Hellerick от 16 марта 2024, 10:57

Цитата: _Swetlana от 16 марта 2024, 10:39

Цитата: Hellerick от 16 марта 2024, 10:37

Цитата: _Swetlana от 16 марта 2024, 10:11онлайн- сервис для оптимального размещения обслуживающих центров (центров и медиан) с ограничениями (стандартные алгоритмы размещают без ограничений). М.б., и html пригодится  :)

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

Любопытно. Никогда не думала об этой задаче в таком ключе. А как вы сформулирует критерий оптимизации?

Необходимо придумать алгоритм постепенного заполнения заданной области центрами в количестве от 1 до N.
Критерий: составляем таблицу, в которой для числа центров от 2 до N указывается соответствующее отношение нагрузки наиболее загруженного центра к наименее загруженному. Идеальным алгоритмом является тот, при котором максимальное значение в этой таблице минимально.

Не поняла с критерием. Нагрузку делим равномерно на любое количество центров. Отношение всегда равно 1.

Цитата: _Swetlana от 16 марта 2024, 21:49Не поняла с критерием. Нагрузку делим равномерно на любое количество центров. Отношение всегда равно 1.

По моей логике, каждый центр обслуживает ту область, к которой он ближайший.

Цитата: Hellerick от 16 марта 2024, 21:52

Цитата: _Swetlana от 16 марта 2024, 21:49Не поняла с критерием. Нагрузку делим равномерно на любое количество центров. Отношение всегда равно 1.

По моей логике, каждый центр обслуживает ту область, к которой он ближайший.

Давайте тогда в терминах одномерной упаковки. Имеется n камней с целым положительным весом. Имеется m куч, вместимость кучи не ограничена. Для каждого камня известно множество допустимых куч (то есть в далёкие кучи камни не кладутся, только в соседние).
Вопрос. Разложить камни по кучам таким образом, чтобы вес максимальной кучи был минимален.

Такая у вас задача?

P.S. или можно ограничить вместимость кучи.

Но это не задача о расположении центров, т.к. принадлежность камней кучам закреплена.
А если у нас есть карта, к примеру, мы любым образом размещаем обсл. центры, и ставим условие, что клиент обслуживается ближайшим к нему центром и минимизируем загрузку самого загруженного центра, то это другая задача.
Вообще, если у вас какая-то реальная производственная задача, то расскажите, в чем она заключается, а я сделаю для нее математическую постановку. Вдруг за счёт каких-то ограничений удастся уйти от NP-hard  :)

Эту задачу можно описать через марковский процесс и скормить RL-алгоритму. Кажется

В первую очередь нужно разобраться с принадлежностью задачи или к классу P (решается эффективными алгоритмами, т.е. за полиномиальное время, отсюда название P), либо доказать, что она NP-полная (трудная), а дальше разбираться, к какому типу она относится, что для неё имеется. Пока это не сделали, и говорить не о чем.
Я еще не поняла, с какой именно задачей мы имеем дело, поэтому не тороплюсь что-то доказывать.

Вот, например, задача для эвклидовой плоскости. В русском переводе её назвали "Скопления", а на самом деле вот:
MINIMUM GEOMETRIC DISK COVER
https://www.csc.kth.se/~viggo/wwwcompendium/node150.html

Если нам нужно разместить заданное число p центров (минимизируем расстояние от центра до самого удалённого клиента) или p медиан (минимизируем суммарное расстояние, проходимое клиентами до центров), то они обе NP-hard. 

Участвовала в конкурсе от "Поколения Пайтон" на образовательной платформе степик, где я уже больше трёх месяцев учусь, не менее чем на двух курсах одновременно ;D
Задачка оказалась совсем не тем, что я думала математически корректной, интересной и с простым решением.
Попробуйте свои силы в решении этой задачи. Формулировку привожу в том виде, в каком она была на конкурсе.

Задача.
Имеется функция magic(), принимающая три целочисленных аргумента, в теле которой определены константы a, b, c, являющиеся натуральными числами. Требуется определить значения констант a, b и c не более, чем за два вызова данной функции.
(https://habrastorage.org/r/w1560/getpro/habr/upload_files/cc7/e21/846/cc7e2184687703ace020b23d8d45a79e.png)

Автор задачи Тимур Гуев опубликовал на хабре решение
ссылка (https://habr.com/ru/users/tguev/publications/articles/)

Готов определить вообще без вызова этой функции.
Я как-то писал программу, которая читала код самой себя.
(А потом в свой же код сваливала результаты вычислений.)

Цитата: Hellerick от 04 апреля 2024, 04:52Готов определить вообще без вызова этой функции.
Я как-то писал программу, которая читала код самой себя.
(А потом в свой же код сваливала результаты вычислений.)

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

Цитата: Hellerick от 04 апреля 2024, 04:52Готов определить вообще без вызова этой функции.
Я как-то писал программу, которая читала код самой себя.
(А потом в свой же код сваливала результаты вычислений.)

Задачу открыли. Вот она
https://stepik.org/lesson/1264319/step/15?unit=1278444
Покажите мне, как можно было её хакнуть.

А то весь день читаешь про всякие методы, пишешь что-то вроде
import dis
s = dis.Bytecode(magic).dis()
new_s = s.split('\n')
lst = []
for a in new_s:
    if 'LOAD_CONST' in a:
        ind1 = a.find('(')
        ind2 = a.find(')')
        lst.append(int(a[ind1+1:ind2]))
print(lst, sum(i*i for i in lst)) 

а в ответ:
В голосе Гвидо слышится разочарование:
—  А я почти в тебя поверил... Ладно уж, у тебя есть еще попытка.

Failed test #1 of 7. Runtime error

Error:
Traceback (most recent call last):
  File "/sandbox/main.py", line 5, in <module>
    s = dis.Bytecode(magic).dis()
  File "/usr/local/lib/python3.10/dis.py", line 475, in __init__
    self.codeobj = co = _get_code_object(x)
  File "/usr/local/lib/python3.10/dis.py", line 148, in _get_code_object
    raise TypeError("don't know how to disassemble %s objects" %
TypeError: don't know how to disassemble magic objects

Посмотрела чужие решения. Есть и довольно простые хакерские, через ООП. Осталось только узнать, что это за магические методы, я до них еще не дошла.

Цитата: _Swetlana от 07 апреля 2024, 16:24Задачу открыли. Вот она
https://stepik.org/lesson/1264319/step/15?unit=1278444

Видимо, только для своих открыли. Я ничего не вижу.

Цитата: Hellerick от 07 апреля 2024, 19:17

Цитата: _Swetlana от 07 апреля 2024, 16:24Задачу открыли. Вот она
https://stepik.org/lesson/1264319/step/15?unit=1278444

Видимо, только для своих открыли. Я ничего не вижу.

Ну прям с улицы туда не зайдешь, конечно.
1. Вам нужно завести аккаунт на степике. Это очень просто - можно зайти через гугл-аккаунт или соцсеть.
https://stepik.org/
Зайдите, там огромное количество бесплатных или почти бесплатных курсов и не только по программированию, м.б. что-то понравится.
2. Выбрать курс "Поколение Python": квесты, конкурсы, марафоны, тесты и задачи"
3. Зайти в "Квест на миллион".
4. 14 задача (или 18 шаг).

У меня, оказывается, пошёл 101-й день на степике.
Себя не похвалишь, никто не похвалит Надо подвести итоги, для поддержания собственного интереса.

101.png 

Задача из Поколения Пайтон. Чем-то она мне понравилась, решила сделать ее с помощью ООП.

Вам доступен текстовый файл files.txt, содержащий информацию о файлах. Каждая строка файла содержит три значения, разделенные символом пробела — имя файла, его размер (целое число) и единицы измерения:

cant-help-myself.mp3 7 MB
keep-yourself-alive.mp3 6 MB
bones.mp3 5 MB
...
Напишите программу, которая группирует данные файлы по расширению, определяя общий объем файлов каждой группы, и выводит полученные группы файлов, указывая для каждой ее общий объем. Группы должны быть расположены в лексикографическом порядке названий расширений, файлы в группах — в лексикографическом порядке их имен.

Примечание 1. Например, если бы файл files.txt имел вид:

input.txt 3000 B
scratch.zip 300 MB
output.txt 1 KB
temp.txt 4 KB
boy.bmp 2000 KB
mario.bmp 1 MB
data.zip 900 MB
то программа должна была бы вывести:

boy.bmp
mario.bmp
----------
Summary: 3 MB

input.txt
output.txt
temp.txt
----------
Summary: 8 KB

data.zip
scratch.zip
----------
Summary: 1 GB
где Summary — общий объем файлов группы.

Примечание 2. Гарантируется, что все имена файлов содержат расширение.

Примечание 3. Общий объем файлов группы записывается в самых крупных (максимально возможных) единицах измерения с округлением до целых. Другими словами, сначала следует определить суммарный объем всех файлов группы, скажем, в байтах, а затем перевести полученное значение в самые крупные (максимально возможные) единицы измерения. Примеры перевода:

1023 B -> 1023 B
1300 B -> 1 KB
1900 B -> 2 KB
Примечание 4. Значения единиц измерения такие же, какие приняты в информатике:

1 KB = 1024 B
1 MB = 1024 KB
1 GB = 1024 MB

Вот моя первая самостоятельная ООП-программа на питоне

class File:
    all_ext = [] # список всех встретившихся расширений

    def __init__(self, name: str, ext: str, size: int, unit: str):
        self.name = name # имя файла
        self.ext = ext # расширение
        ind = Group.all_units.index(unit) # размерность ед. измерения
        self.size = size * (1024 ** ind) # размер файла в байтах
   
    @classmethod
    def add_file(cls, f):
        if f.ext not in cls.all_ext:
            cls.all_ext.append(f.ext) # добавляем новое расширение в список расширений
            g = Group(f) # создаем новую группу
            Group.add_group(g) # добавляем ее в список всех групп
        else:
            # ищем подходящую группу и добавляем туда файл
            for g in Group.all_groups:
                if g.ext == f.ext:
                    g.add_file(f)
                    break

class Group:
    all_groups = [] # список всех групп
    all_units = ['B', 'KB', 'MB', 'GB'] # единицы измериния

    def __init__(self, f: File):
        self.ext = f.ext # групповое расширени
        self.flst = [f] # список файлов
        self.size = f.size # размер группы в байтах

    # добавление файла в уже существующую группу
    def add_file(self, f: File):
        self.flst.append(f) # добавляем файл в список файлов
        self.size += f.size # размер группы в байтах
       
    # добавление группы в список всех групп
    @classmethod
    def add_group(cls, g):
        cls.all_groups.append(g)

with open('files.txt', 'r', encoding='utf-8') as my_file:
    temp = my_file.readlines()
temp = [a.strip() for a in temp]

for t in temp:
    name_ext, size, unit = t.split()
    name, ext = name_ext.split('.')
    new_file = File(name, ext, int(size), unit) # создаем файл
    File.add_file(new_file) # добавляем файл куда надо

# все сортировки
Group.all_groups = sorted(Group.all_groups, key=lambda x: x.ext)
for g in Group.all_groups:
    g.flst = sorted(g.flst, key=lambda x: x.name)

for g in Group.all_groups:
    for f in g.flst:
        print(f.name+'.'+f.ext)
    print('----------') 
    sz = g.size
    i = 0
    while sz > 1024:
        sz = sz // 1024
        i += 1               
    print(f'Summary: {round(g.size / (1024 ** i))} {Group.all_units[i]}\n')


А вот как люди делали )) Посмотрела и подумала: чукча не читатель!

with open('files.txt', 'r', encoding='utf-8') as f:
    dfile, mem = {}, {}
    conv = {'B': 1, 'KB': 1024, 'MB': 1024 ** 2, 'GB': 1024 ** 3}
    for line in f:
        l = line.strip().split()
        dfile.setdefault(l[0].split('.')[1], []).append(l[0])
        mem[l[0].split('.')[1]] = mem.get(l[0].split('.')[1], 0) + int(l[1]) * conv[l[2]]
    for k in sorted(dfile):
        mems = [f'{round(mem[k] / conv[i])} {i}' for i in conv if 1 <= mem[k] / conv[i] < 1023.5]
        print(*sorted(dfile[k]), '-' * 10, f'Summary: {mems[0]}', sep='\n')
        print()

Цитата: _Swetlana от 18 апреля 2024, 21:55А вот как люди делали )) Посмотрела и подумала: чукча не читатель!

Ну так, даже если не брать трудночитаемые способы написания кода, ООП обычно не даёт выигрыша ни в размере, ни в трудоёмкости (а обычно даёт чистый проигрыш) в случае таких программ, размер которых позволяет их написать целиком силами одного человека или даже небольшого коллектива.

Поэтому реалистичные учебные примеры (для написания в одно лицо) на ООП, которые бы не требовали значительно больше трудозатрат для написания, чем то же самое в обычном процедурном стиле - это довольно экзотическая и малореальная штука, имхо.

Тут уместно вспомнить питоновский Дзен.

ЦитироватьBeautiful is better than ugly.
Explicit is better than implicit.
Simple is better than complex.
Complex is better than complicated.
Flat is better than nested.
Sparse is better than dense.
Readability counts.
Special cases aren't special enough to break the rules.
Although practicality beats purity.
Errors should never pass silently.
Unless explicitly silenced.
In the face of ambiguity, refuse the temptation to guess.
There should be one-- and preferably only one --obvious way to do it.
Although that way may not be obvious at first unless you're Dutch.
Now is better than never.
Although never is often better than *right* now.
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
Namespaces are one honking great idea -- let's do more of those!

Доберусь до компа, покажу, как изящно хакается задачка про функцию с константами a, b, c с помощью функции __rmul__.
ООП - сила  :green:

Вот оно! Переопределяем правостороннее умножение на экземпляр класса: заменяем экземпляр класса на то, что передаётся в __rmul__ в качестве сомножителя

class int(int):
    def __rmul__(self, other):
        return other * other

x = int(1)
print(magic(x, x, x))

Цитата: _Swetlana от 23 апреля 2024, 21:02Вот оно! Переопределяем правостороннее умножение на экземпляр класса: заменяем экземпляр класса на то, что передаётся в __rmul__ в качестве сомножителя

Код Выделить Развернуть

class int(int):
    def __rmul__(self, other):
        return other * other

x = int(1)
print(magic(x, x, x))

Класс int тоже переопределяем.

Ни слова не понял.

Цитата: Hellerick от 25 апреля 2024, 04:26Ни слова не понял.

По условиям задачи на вход функции magic мы должны подать три целых числа, три объекта класса int.
1. Определяем свой класс-наследник от int:
class имя_класса(int):
Но функция magic ждет на вход объект типа int, поэтому называем наш класс - int. То есть переопределяем стандартный тип. В языках с динамической типизацией такие фокусы проходят.
2. Далее, наши объекты умножаются справа на числа a, b, c. Поэтому у нашего класса переопределяем правостороннее умножение так, как нам надо.
Просто супер!
P.S. Программа не моя, другого участника конкурса.

За такое котел в аду полагается.

Цитата: Hellerick от 29 апреля 2024, 05:07За такое котел в аду полагается.

В академических исследованиях нет каких-либо этических критериев. Делаю, потому что могу  :) 

@_Swetlana
А вы не могли бы поразмыслить над практической задачей?
Я называю ее задачей линейного раскроя.
Вот нам даны, скажем 9 шестов длинной 6000 мм: `poles={6000:9}`
Их надо разрезать на палки, при этом даны длины палок и требуемые их количества: `sticks={1550:10, 1200:8, 600:12, 550:4, 300:20}`.
Требуется: Напечатать, как следует разрезать шесты на палки оптимальным образом. Примерно так: "Pole #1: 1550*3+1550*3+1200=5850".
Критерий оптимизации: список `remainders`, содержащий в себе неиспользуемые остатки каждого шеста, отсортированный в порядке убывания, должен быть как можно больше (в том смысле, в котором в питоне сравниваются два списка). То есть, надо использовать как можно меньше шестов, при этом от использованных шестов надо оставить как можно бо́льшие остатки.
Я догадываюсь, что это какая-то классическая задача на оптимизацию, но не в курсе, как такие принято решать.
Сейчас я решаю ее в полуавтоматическом режиме: скрипт на питоне подсказывает, как красиво избавляться самого большого числа самых длинных палок, а потом, комбинируя предложенные способы, я нахожу хороший общий раскрой.

Я эту задачу на лекциях рассказывала, с точным и приближенным решением. Прям лекцию сюда выложу, обсудим.
И один товарищ в интернете меня спрашивал, как для изготовления пластиковых окон заготовки нарезать, стали кроить приближенным алгоритмом - вроде остался доволен.
А другой товарищ на хабре написал, как он одномерный раскрой делает генетическим алгоритмом. Я из лучших побуждений написала, что ГА эту задачу делать не надо, а надо вот так, и просто, и отклонение приближенного от оптимального в худшем случае небольшое, а на реальных данных вообще практически как точный работает - меня там заминусовали, как ёжика))

Задача одномерной упаковки - классическая NP-трудная в сильном смысле задача. Что это значит.
1. NP-трудная - никто не знает, как решить её за полиномиальное время точным алгоритмом.
2. ... в сильном смысле - не решается за псевдополиномиальное время динамическим программированием.
На самом деле таких задач полно - и на производстве, и в науке. По факту на производстве чего ни коснись - конгломерат различных NP-трудных задач.
Как такие задачи решают.
а) Для малой размерности (n<= 20) лучше всего воспользоваться точным экспоненциальным алгоритмом, который называется "алгоритм с возвратом" или бэктрекинг. Алгоритмом с возвратом можно решить любую NP-трудную (полную) задачу за экспоненциальное время.
б) Если размерность средняя и задача псевдополиномиальная - то решают динамическим программированием.
в) Если задача оптимизационная (найти максимальное или минимальное решение), а размерность большая и/или задача трудная в сильном смысле - то можно действовать по-разному.
На крайних полюсах - приближенные и эвристические алгоритмы.

В чем разница между приближенным и эвристическим алгоритмом, если они оба решают задачу неточно?
I. У приближенного доказана оценка погрешности: знаем насколько наше решение может отклониться от оптимального в самом худшем случае. Найти такую оценку - доказать теорему. Тот алгоритм, которым мы будем решать задачу одномерной упаковки - FFD-алгоритм (First Fit Decreasing, первый подходящий в порядке убывания) - как раз относится к таким алгоритмам. Собственно, его можно применять к любой задаче на минимум, но именно для одномерной упаковки он поразительно хорошо работает! На очень сложных, специально сконструированных плохих примерах он отклоняется от оптимального решения не более чем на 22%. А на реальных наборах данных работает практически как точный. Для производства - самое то.
II. Эвристические алгоритмы - нам никто ничего не гарантирует. ХЗ, насколько эвристическое решение отклонится от оптимального. Пример - ГА, генетические алгоритмы - стильно, модно, молодёжно. Если соберётесь научную статью писать, в журнал посылать - берите ГА, не прогадаете  ;D
III. Ну и третий путь, которым я часто пользовалась - гибридные алгоритмы. Пример задачи. Госзакупки, на подразделение выделяется сумма денег, ее нужно выбрать. Есть список товаров, которые нужны, известна их стоимость. Только размерность очень большая: и сумма велика, и товаров много.
Как эта задача решается гибридным алгоритмом.
Товары сортируются по убыванию стоимости. Придумывается приближенный алгоритм, который выбирает большую часть суммы, в первую очередь забирая дорогие товары. А на втором этапе начинает работать точный алгоритм: остаток суммы набирается с точностью до нескольких рублей перебором не более 20 товаров.   

Наша задача, неформально. Имеется n одинаковых контейнеров. Вместимость может быть любая, в модельной задаче вместимость равна 1. Имеется n предметов размерами от 0 до 1, не включая 0.
Нужно упаковать предметы в минимальное число контейнеров таким образом, чтобы все предметы были упакованы, и сумма размеров предметов в одном контейнере не превосходила его вместимости, т.е. 1.

Как она решается точным алгоритмом с возвратом, когда предметов <= 20:
общее описание алгоритма с возвратом (https://disk.yandex.ru/i/ZBytRWp9h26FPg)
алгоритм с возвратом для одномерной упаковки (https://disk.yandex.ru/i/8EsHnh-MV9GEOw)

Ну и как задача одномерной упаковки решается FFD-алгоритмом двойным циклом за O(n²), где n - количество пакуемых предметов.
FFD-алгорит для задачи одномерной упаковки (https://disk.yandex.ru/i/_ciYkrSvvZ06Qg)

Цитата: Hellerick от 30 апреля 2024, 07:21@_Swetlana
А вы не могли бы поразмыслить над практической задачей?
Я называю ее задачей линейного раскроя.
Вот нам даны, скажем 9 шестов длинной 6000 мм: `poles={6000:9}`
Их надо разрезать на палки, при этом даны длины палок и требуемые их количества: `sticks={1550:10, 1200:8, 600:12, 550:4, 300:20}`.
Требуется: Напечатать, как следует разрезать шесты на палки оптимальным образом. Примерно так: "Pole #1: 1550*3+1550*3+1200=5850".
Критерий оптимизации: список `remainders`, содержащий в себе неиспользуемые остатки каждого шеста, отсортированный в порядке убывания, должен быть как можно больше (в том смысле, в котором в питоне сравниваются два списка). То есть, надо использовать как можно меньше шестов, при этом от использованных шестов надо оставить как можно бо́льшие остатки.
Я догадываюсь, что это какая-то классическая задача на оптимизацию, но не в курсе, как такие принято решать.
Сейчас я решаю ее в полуавтоматическом режиме: скрипт на питоне подсказывает, как красиво избавляться самого большого числа самых длинных палок, а потом, комбинируя предложенные способы, я нахожу хороший общий раскрой.

Немножко удалила, что с телефона отправляла  :)  Будут вопросы - пишите, обсудим. Страсть как люблю производственные оптимизационные NP-полные задачи решать  ;D 

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

Взял конкретный рабочий пример из своей практики: sticks = {2200: 40, 1429: 40, 680: 40, 496: 20, 450: 40, 170: 20}

Для простоты решил все шесты взять по 6000 мм: pole_length = 6000

Попросил ИИ написать мне алгоритм. Тот решил задачу напрямик:
pole_length = 6000
sticks = {2200: 40, 1429: 40, 680: 40, 496: 20, 450: 40, 170: 20}

def cut_poles(pole_length, sticks):
    stick_lengths = list(sticks.keys())
    stick_lengths.sort(reverse=True)

    cutting_plan = []
    poles_used = 0

    while any(count > 0 for count in sticks.values()):
        remaining_length = pole_length
        pole_cutting_plan = []

        for stick_length in stick_lengths:
            while remaining_length >= stick_length and sticks[stick_length] > 0:
                pole_cutting_plan.append(stick_length)
                remaining_length -= stick_length
                sticks[stick_length] -= 1

        if pole_cutting_plan:
            cutting_plan.append(pole_cutting_plan)
            poles_used += 1

    return cutting_plan, poles_used

cutting_plan, poles_used = cut_poles(pole_length, sticks)

print(f"Minimum number of poles needed: {poles_used}")
print("\nCutting Plan:")
for i, pole_plan in enumerate(cutting_plan, start=1):
    print(f"Pole {i}: {' + '.join(str(length) for length in pole_plan)} = {eval(' + '.join(str(length) for length in pole_plan))}")

Результат:
Minimum number of poles needed: 35

Cutting Plan:
Pole 1: 2200 + 2200 + 1429 + 170 = 5999
Pole 2: 2200 + 2200 + 1429 + 170 = 5999
Pole 3: 2200 + 2200 + 1429 + 170 = 5999
Pole 4: 2200 + 2200 + 1429 + 170 = 5999
Pole 5: 2200 + 2200 + 1429 + 170 = 5999
Pole 6: 2200 + 2200 + 1429 + 170 = 5999
Pole 7: 2200 + 2200 + 1429 + 170 = 5999
Pole 8: 2200 + 2200 + 1429 + 170 = 5999
Pole 9: 2200 + 2200 + 1429 + 170 = 5999
Pole 10: 2200 + 2200 + 1429 + 170 = 5999
Pole 11: 2200 + 2200 + 1429 + 170 = 5999
Pole 12: 2200 + 2200 + 1429 + 170 = 5999
Pole 13: 2200 + 2200 + 1429 + 170 = 5999
Pole 14: 2200 + 2200 + 1429 + 170 = 5999
Pole 15: 2200 + 2200 + 1429 + 170 = 5999
Pole 16: 2200 + 2200 + 1429 + 170 = 5999
Pole 17: 2200 + 2200 + 1429 + 170 = 5999
Pole 18: 2200 + 2200 + 1429 + 170 = 5999
Pole 19: 2200 + 2200 + 1429 + 170 = 5999
Pole 20: 2200 + 2200 + 1429 + 170 = 5999
Pole 21: 1429 + 1429 + 1429 + 1429 = 5716
Pole 22: 1429 + 1429 + 1429 + 1429 = 5716
Pole 23: 1429 + 1429 + 1429 + 1429 = 5716
Pole 24: 1429 + 1429 + 1429 + 1429 = 5716
Pole 25: 1429 + 1429 + 1429 + 1429 = 5716
Pole 26: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 27: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 28: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 29: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 30: 680 + 680 + 680 + 680 + 680 + 680 + 680 + 680 + 496 = 5936
Pole 31: 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 + 496 = 5952
Pole 32: 496 + 496 + 496 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 = 5988
Pole 33: 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 = 5850
Pole 34: 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 + 450 = 5850
Pole 35: 450 + 450 + 450 + 450 = 1800

Результат неплохой.

А вот решение, которое я некогда нашел вручную:
2200×2 + 680×1 + 450×2 = 5980 (20 poles)
1429×3 + 680×2 + 170×2 = 5987 (10 poles)
1429×2 + 496×6 = 5834 (3 poles)
1429×4 = 5716 (1 pole)
496×2 = 992 (1 pole)

И там, и там использовано по 35 шестов.
Разница в том, что от последнего шеста ИИ оставил 6000-1800=4200 мм, а я -- 6000-992=5008 мм.
То есть я оставил больший деловой отход, так что мое решение лучше ИИшного.
ИИ решил пять шестов разрезать по схеме 1429+1429+1429+1429=5716, оставляя 6000-5716=284 мм отхода.
На этой длине поместилась бы палка длиной 170 мм, вот только ИИ их все уже использовал в предыдущих раскроях.
Когда я кроил осмысленно, я таких ситуаций не допускаю. Я знаю, что короткие палки дают больше свободы для раскроя, и их надо беречь.

Ну что я могу сказать. Этой неглубокой мысли соответствует доказанная теорема, что в самом худшем специально сконструированном случае FFD ошибётся на 22%, что очень неплохо для NP-hard. Более глубоких мыслей у меня нет  :)
Сортируйте заготовки по убыванию длины и раскладывайте по принципу "в первый подходящий".

Остатки шестов мы не максимизируем! оптимизация по одному параметру - количеству использованных шестов. Видимо, в вашем примере 35 шестов и есть оптимальное решение.

P.S. Попробую написать FFD на питоне, для тренировки.
 

Цитата: Hellerick от 02 мая 2024, 18:09Попытался почитать материалы по предоставленным вами ссылкам, но, честно говоря, ничего кроме неглубокой мысли...

Еще одна неглубокая мысль. Оценка снизу: складываем длины всех заготовок и делим нацело 6000.
Это я сделала в питоне (вот питон и пригодился  ;D ), получила 33.
Т.е. 33 - оценка снизу, которой явно не хватит, а 35 дает приближенный алгоритм.
Вы думаете, что какая-то очень глубокая мысль даст 34?
Можно проверить, путем точного перебора и логических рассуждений (раскидываем 40 заготовок по 2200 на 34 шеста однозначно, затем заготовки по 1429 тоже без вариантов распределяются), что для этого примера 34 недостаточно.

Мой FFD дает такой же результат, как ИИ. Но у меня ООП, в отличии от.
Правда, класс "палка" я не стала создавать, чтобы не усложнять ввод данных. Создала только класс шест  :)

class Pole:
    pcount = 0
   
    def __init__(self):
        self.length = 6000
        self.stics = []

    def add_stic(self, lstick):
        if lstick <= self.length:
            if self.length == 6000: # начинаем новый контейнер
                Pole.pcount += 1
            self.length -= lstick
            self.stics.append(lstick)
            return True
        else:
            return False


stics = [2200]*40 + [1429]*40 + [680]*40 + [496]*20 + [450]*40 + [170]*20
poles = [Pole() for _ in range(40)]

for stic in stics:
    for p in poles:
        if p.add_stic(stic):
            break
print('Использованных контейнеров:', Pole.pcount)
for p in poles:
    print(6000 - p.length, end=' ')
Использованных контейнеров: 35
5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5999 5716 5716 5716 5716 5716 5936 5936 5936 5936 5936 5952 5988 5850 5850 1800 0 0 0 0 0

Для полуавтоматической раскладки я сделал себе такую перебиралку:

sticks = {
    2200: 40,
    1429: 40,
    680: 40,
    496: 20,
    450: 40,
    170: 20}

pole_length = 6000

stick_lengths = sorted([l for l in sticks], reverse=True)

def vary(inlayouts, depth):
    check_qty = min(
        pole_length//stick_lengths[depth],
        sticks[stick_lengths[depth]],
        )
    outlayouts = []
    if depth == len(stick_lengths)-1:
        for i in range(check_qty+1):
            outlayouts = outlayouts + [inlayouts + [i]]
    else:
        for i in range(check_qty+1):
            outlayouts = outlayouts + vary(inlayouts+[i], depth+1)
    return outlayouts

layouts = vary([], 0)

def layout_total_len(layout):
    return sum([layout[i]*stick_lengths[i] for i in range(len(layout))])

layouts = [l for l in layouts if layout_total_len(l) <= pole_length and sum(l)>0]

layouts.sort(key = layout_total_len, reverse = True)

print(f'Number of layouts found: {len(layouts)}')

print(f'For sticks with lengths\n{stick_lengths}\n')

print(f'Best layouts:')
for l in layouts[:400]:
    print(f'{l}, L={layout_total_len(l)}')

Она мне печатает наиболее удачные возможные раскладки:

Number of layouts found: 6350
For sticks with lengths
[2200, 1429, 680, 496, 450, 170]

Best layouts:
[0, 0, 3, 0, 2, 18], L=6000
[0, 0, 4, 0, 2, 14], L=6000
[0, 0, 5, 0, 2, 10], L=6000
[0, 0, 6, 0, 2, 6], L=6000
[0, 0, 7, 0, 2, 2], L=6000
[0, 2, 0, 2, 1, 10], L=6000
[0, 2, 1, 2, 1, 6], L=6000
[0, 2, 2, 2, 1, 2], L=6000
[0, 1, 0, 0, 6, 11], L=5999
[0, 1, 0, 5, 2, 7], L=5999
[0, 1, 1, 0, 6, 7], L=5999
[0, 1, 1, 5, 2, 3], L=5999
[0, 1, 2, 0, 6, 3], L=5999
[1, 1, 0, 0, 3, 6], L=5999
[1, 1, 1, 0, 3, 2], L=5999
[2, 1, 0, 0, 0, 1], L=5999
[0, 0, 0, 3, 7, 8], L=5998
[0, 0, 0, 8, 3, 4], L=5998
[0, 0, 1, 3, 7, 4], L=5998
[0, 0, 1, 8, 3, 0], L=5998
[0, 0, 2, 3, 7, 0], L=5998
[1, 0, 0, 3, 4, 3], L=5998
[0, 1, 0, 1, 3, 16], L=5995
[0, 1, 1, 1, 3, 12], L=5995
[0, 1, 2, 1, 3, 8], L=5995
[0, 1, 3, 1, 3, 4], L=5995
[0, 1, 4, 1, 3, 0], L=5995
[1, 1, 0, 1, 0, 11], L=5995
[1, 1, 1, 1, 0, 7], L=5995
[1, 1, 2, 1, 0, 3], L=5995
...

Среди найденных вариантов я выбираю те, которые кажутся перспективными.
Перспективные раскладки — те, которые можно многократно повторять, то есть рабочий может нарезать эту раскладку несколько раз, избавляя нас от наиболее длинных палок, но при этом оставляя разумное количество коротких палок для дальнейших раскладок. Наверное, перспективную "хорошесть" раскладки можно как-то оценить численно.
Выбрав одну раскладку, и "нарезав" по ней палки, я прогоняю скрипт повторно, уже с меньшим набором требуемых палок. Чем дальше, тем меньше остается выбор, и тем меньше "мощность" задачи по перебору вариантов.

Короче, при осознанном подходе, у задачи не такое уж великое ветвление, и разумные варианты там вполне посильно перебрать.

Цитата: Hellerick от 03 мая 2024, 05:21Среди найденных вариантов я выбираю те, которые кажутся перспективными.
Перспективные раскладки — те, которые можно многократно повторять, то есть рабочий может нарезать эту раскладку несколько раз.

Вот это правильно, повторяющиеся раскладки. Тем более, данные у вас уж очень регулярные - каждого вида по 40 штук.
Как-то решала задачу, там разрезалась стальная полоса на полосы определенной ширины, и вот эти ширины набирались с помощью втулок, которые на листе выставлялись. И нужно было не просто набрать нужные суммы (ширины), а набрать минимальным числом втулок, чтобы резчику не приходилось долго это всё выкладывать.
Ну та задача решалась динамическим программированием.
Потом я ее в свой учебник вставила, вот она:

ЦитироватьЗадание 3 (высокий уровень)
Линия продольной резки рулонного металла вырезает из рулона полосу определённой ширины. У резчика имеется набор втулок разной ширины. Набрать заданную ширину с помощью имеющихся втулок так, чтобы количество использованных втулок было минимально. Исходные данные придумать самому, набор должен содержать не менее 25 втулок, в наборе могут быть втулки одинаковой ширины.

Не программист я и не математик. Зацепила реплика Hellerick'а, что ИИ сработал хуже человека. Попробовал и сам поискать решение его задачи. Действовал тупым перебором вариантов. Тактика простая: поначалу компоновал крупняк. Удачно подошли 20 раскроек по 5999 мм. Далее по убыванию... Итог: влез в 35-ый шест на 450 мм. Остаток, соответственно, 5550 мм. Был и промежуточный — 5100, но я нашёл и лучший.

2200*2 + 1429*1 + 170*1 =               5999 (20 шт.)
1429*3 + 680*1 + 496*2 =                5959 (5 шт.)
1429*1 + 680*2 + 496*1 + 450*6 =        5985 (2 шт.)
1429*1 + 680*3 + 496*2 + 450*3 =    5811 (1 шт.)   
1429*1 + 450*10 =                   5929 (2 шт.)
680*6 + 496*2 + 450*2 =             5972 (2 шт.)
680*8 + 496*1 =                     5936 (2 шт.)
450*1 =                              450 (1 шт.)                         

Цитата: H_N от 05 мая 2024, 12:57Не программист я и не математик. Зацепила реплика Hellerick'а, что ИИ сработал хуже человека.

@Hellerick А что там за ИИ-то был? Не яндексовский, надеюсь?

Так ИИ просили использовать минимальное количество шестов. Что он и сделал.
Нужно как-то формализовать наши дальнейшие хотелки, иначе многокритериальная оптимизация получится, а это другая задача.
Из всех минимальных упаковок в 35 шестов выбрать ту самую ... Ну давайте подумаем, что мы тут максимизируем.
У каждого шеста вычисляем длину "огрызка". У меня она прямо в атрибуте экземпляра хранится, и вычислять не надо. Далее, среди всех шестов находим максимальный огрызок.
Вопрос к ИИ. При таких-то исходных данных среди всех упаковок в 35 шестов найти упаковку, у которой длина максимального огрызка максимальна.

Цитата: _Swetlana от 05 мая 2024, 16:10А что там за ИИ-то был?

Если не ошибаюсь, я использовал модель claude-3-haiku вот здесь:
https://labs.perplexity.ai/

Цитата: _Swetlana от 05 мая 2024, 16:10Нужно как-то формализовать наши дальнейшие хотелки

Ны дык:

Цитата: Hellerick от 30 апреля 2024, 07:21Критерий оптимизации: список `remainders`, содержащий в себе неиспользуемые остатки каждого шеста, отсортированный в порядке убывания, должен быть как можно больше (в том смысле, в котором в питоне сравниваются два списка). То есть, надо использовать как можно меньше шестов, при этом от использованных шестов надо оставить как можно бо́льшие остатки.

Для моего решения:

Цитировать2200×2 + 680×1 + 450×2 = 5980 (20 poles)
1429×3 + 680×2 + 170×2 = 5987 (10 poles)
1429×2 + 496×6 = 5834 (3 poles)
1429×4 = 5716 (1 pole)
496×2 = 992 (1 pole)

остатки будут равны:
remainders = [5008, 284, 166, 166, 166, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13]

Задача -- найти раскладку, для которого отсортированный массив остатков будет наибольшим.

Цитата: Hellerick от 05 мая 2024, 16:29(в том смысле, в котором в питоне сравниваются два списка).

понятно

Ну тут как можно. FFD сформировать начальное решение. В скобках замечу, что по числу использованных шестов оно будет минимальным. А потом методом локального поиска пытаться улучшить упаковку. Например, делать обмены. Выбирать пару шестов, пусть они обмениваются палками. Если целевая функция улучшилась, то делать обмен. Давно я такое делала для равномерного распределения работ между бригадами, но подробности плохо помню. 

Найти бы хотя бы просто "недетерминированный" алгоритм, который перебирает варианты, вместо того, чтобы выдавать единственный.
А уж выбрать из них хороший — не проблема.

Цитата: Hellerick от 06 мая 2024, 04:33Найти бы хотя бы просто "недетерминированный" алгоритм, который перебирает варианты, вместо того, чтобы выдавать единственный.
А уж выбрать из них хороший — не проблема.

Да запросто. Ещё одна неглубокая идея  ;D
В оптимальной упаковке не может быть двух контейнеров, заполненных не более чем наполовину. Иначе бы мы сложили их содержимое в один контейнер и уменьшили целевую функцию.
Что отсюда следует. А то, что n-1 контейнер заполнен более чем на половину и только один-единственный может быть заполнен менее чем на половину. Так какой смысл пытаться уплотнить упаковку сразу во всех контейнерах? За этот один и возьмёмся, будем максимизировать "огрызок" в одном контейнере. Делать это можно локальным поиском: найдём решение FFD-алгоритмом, затем будем искать лучшее решение в его окрестности. Допустимые операции: одна палка перекладывается из одного контейнера в другой; две палки из разных контейнеров меняются местами.