Учим питон (или пайтон)

[_Swetlana]

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

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

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)

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

[Hellerick]

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

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

[_Swetlana]

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

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

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

[_Swetlana]

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

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

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

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

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

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

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

[Vesle Anne]

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

[_Swetlana]

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

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

[Toman]

Какие ещё вложенные циклы. Рекурсией надо писать! 

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

[_Swetlana]

Какие ещё вложенные циклы. Рекурсией надо писать!

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

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

[_Swetlana]

Какие ещё вложенные циклы. Рекурсией надо писать!

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

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

[Hellerick]

Примечание 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('НЕТ')
Куда там запихивать циклы или рекурсии, ума не приложу.

[Hellerick]

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

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

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])])

[_Swetlana]

Примечание 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 году), одна девочка мне написала в комментарии: Как не стыдно давать такие заданья! 
С другой стороны, если у тебя нет глобальных переменных и управляющих операторов, а хочется хочется сохранить идею алгоритма, то без рекурсии и не напишешь. 

[Hellerick]

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

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

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('НЕТ')
Это считается вложенным циклом?

[Vesle Anne]

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

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

[_Swetlana]

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

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

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]

Ссылка на лекцию

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

[_Swetlana]

Ссылка на лекцию

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

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

[Vesle Anne]

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

[_Swetlana]

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

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

[Vesle Anne]

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

[_Swetlana]

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

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

Извините, вам запрещён просмотр содержимого спойлеров.

 
 

[_Swetlana]

Нет, это он в начале 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')

[_Swetlana]

Извините, вам запрещён просмотр содержимого спойлеров.

Постулат Бертрана
Постулат Бертрана (теорема Бертрана-Чебышева, теорема Чебышева) гласит, что для любого 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))


[_Swetlana]

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

[Vesle Anne]

Ну что ж так?