Описание алгоритма: задан список А и число M, n = len(A). для того чтобы найти все возможные варианты выборки из А необходимо построить множество двоичных чисел от 1 до 2^n-1 и складывать только те индексы разряд которого которого в двоичном числе равен 1, т.е. для двоичного числа 1100 это будут индексы 2 и 3. Если сумма будет равна М вывести последовательность индексов, иначе идем далее Язык Python A=[21,4,5,4,32] #Задание массива А M = 9 #Задание М for i in range(1, 2**len(A)-1): # для всех i от 1 до 2^n-1 ind = [] # список индексов используемых в данной итерации cnt = 0 # сумма элементов А for j in range(len(A)): # для всех j от 0 до n if i&2**j: # Если индекс есть в бинарной записи i, то cnt += A[j] # прибавить к сумме A[j] ind.append(str(j)) # запомнить индекс if cnt > M: break # если сумма больше M выходим из цикла if cnt == M: # если сумма равна M print ', '.join(ind) # печатаем список эффективных индексов
для данной программы будет выдано две строки 1,2 2,3
Если Павел лжет в первый день, значит на самом деле он говорит правду либо в понедельник, либо во вторник. Если лжет в третий день - значит говорит правду либо в среду, либо в пятницу.Поскольку он говорит правду лишь в один день, то он не может лгать и в первый день, и в третий. Значит, в какой-то из этих дней он говорит правду. Значит, во второй день он точно лжет, следовательно второй день - это либо понедельник, либо вторник, либо среда либо пятница.Осталось выяснить, в какой из дней он говорит лжет, в первый или третий. Пусть это третий. Значит он говорит правду в среду или в пятницу - и первый день это среда или пятница. Но тогда второй день - четверг или суббота, а мы знаем что это невозможно. Противоречие.Следовательно, в первый день Павел солгал, а правду он говорит по понедельникам либо по вторникам. Тогда третий день - понедельник или вторник. Поскольку второй день не может быть воскресеньем, значит третий день (правдивый) - вторник.
Обозначу КД = множество результатов поиска по запросу Конан Дойль, БС = Г. Бичер-Стоу, ДД = Джером К. Джером. Кроме того, пересечение множеств обозначим *, объединение +.
A. КД * БС * ДД Б. КД + БС + ДД В. КД + БС * ДД Г. БС * ДД
Сравнивать количества элементов множеств можно, используя трюк: количества элементов соотносятся точно также, как и записанные мною выше выражения, в которых вместо КД, БС, ДД записаны какие-то числа между нулем и единицей. Можно даже просто подставить, например, КД = БС = ДД = 0,1 и посмотреть, что получится.
А. 0,1 * 0,1 * 0,1 = 0,001 Б. 0,1 + 0,1 + 0,1 = 0,3 В. 0,1 + 0,1 * 0,1 = 0,11 Г. 0,1 * 0,1 = 0,01
Б > В > Г > А
Для справедливости всего, что написано, в каждом выражении каждая переменная должна встречаться не более, чем по одному разу. Трюком можно пользоваться, если известно, что при любых значениях переменных порядок не будет меняться (это условие эквивалентно тому , что задача при любых количествах элементов и любых соотношениях будет разрешима, и ответ не меняется) Например, рассмотрим пример, который явно не определен однозначно: сравним количество результатов по запросу (A. Конан Дойл & Г. Бичер-Стоу) и (Г. Бичер-Стоу & Джером К. Джером). Следуя методу, надо сравнить при всех возможных 0 < КД, БС, ДД < 1 выражения: КД * БС и БС * ДД При разных выборах значений результат будет разным, например: - КД = БС = 0,1; ДД = 0,2: 0,01 < 0.02 - КД = БС = ДД = 0,1: 0,01 = 0,01 - КД = 0,2; БС = ДД = 0,1: 0,02 > 0.01 Это означает, что без дополнительных условий задача не разрешима.
Если сумма будет равна М вывести последовательность индексов, иначе идем далее
Язык Python
A=[21,4,5,4,32] #Задание массива А
M = 9 #Задание М
for i in range(1, 2**len(A)-1): # для всех i от 1 до 2^n-1
ind = [] # список индексов используемых в данной итерации
cnt = 0 # сумма элементов А
for j in range(len(A)): # для всех j от 0 до n
if i&2**j: # Если индекс есть в бинарной записи i, то
cnt += A[j] # прибавить к сумме A[j]
ind.append(str(j)) # запомнить индекс
if cnt > M: break # если сумма больше M выходим из цикла
if cnt == M: # если сумма равна M
print ', '.join(ind) # печатаем список эффективных индексов
для данной программы будет выдано две строки
1,2
2,3