Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиПоискОблакоComboВсе проекты

Помогите решите задачку на python

Kuro Nag Ученик (131), закрыт 1 месяц назад
В городском зоопарке содержатся животные n разных видов. Для участия в международной выставке «Три твари» зоопарк должен представить трех животных различных видов.

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

Например, если в зоопарке два медведя, тигр, лев и пингвин, то есть семь способов выбрать трех животных:

первый медведь, тигр и лев;
первый медведь, тигр и пингвин;
первый медведь, лев и пингвин;
второй медведь, тигр и лев;
второй медведь, тигр и пингвин;
второй медведь, лев и пингвин;
тигр, лев и пингвин.
Входные данные

Содержит в первой строке натуральное число n – количество видов животных в городском зоопарке (1 ≤ n ≤ 1000). Во второй строке через пробел записаны n натуральных чисел – количество животных соответствующего вида. Число животных каждого вида не превышает 1000.

Выходные данные

Должен содержать одно число – количество способов выбрать трех животных для международной выставки.
Лучший ответ
аноним аноним Гуру (2542) 1 месяц назад
matburo.ru/tvart_sub.php?p=calc_C
формула комбинаций

код-однострочник: from math import factorial as F;a=int(input());b=sum([int(i)for i in input().split(' ')]);print(F(b)/(F(3)*F(b-3))
УлугбекПрофи (815) 1 месяц назад
как-то не так работает твой код, хотя ты прав, комбинаторика нужна
аноним аноним Гуру (2542) Улугбек, да, странно... кстати, там еще скобка не закрыта в конце
Остальные ответы
Улугбек Профи (815) 1 месяц назад
Пока я готовил продукты на завтра (я ж продавец шаурмы, а не прогер), размышлял над комбинациями. Итоговое число комбинаций будет состоять из следующего:
кол-во сочетаний 1-го вида И кол-во сочетаний 2-го вида И кол-во сочетаний 3-го вида
ИЛИ
кол-во сочетаний 1-го вида И кол-во сочетаний 2-го вида И кол-во сочетаний 4-го вида
ИЛИ
...
Т. к. мы берем 1 любое животное из общего количества вида, то количество сочетаний будет равно количеству животных данного вида, т. е. нам не надо считать факториалы.
в комбинаторике И - произведение, ИЛИ - сумма.
Дальше идет ужасного вида код, который грамотные люди приведут в порядок (лямбда-функции, однострочники и т. д.) ибо я всех возможностей питона не знаю.

def multip(*args):
 m=1
 for i in args:
  m*=i
 return m

def calc_comb(comb):
 ans=0
 for s in comb:
  ans += multip(*s)
 return ans

def make_comb(arr, num_anim4show=3):
 res = []
 for i in range(0,len(arr)):
  if i+num_anim4show > len(arr):
   res.append(arr[:i+num_anim4show-len(arr)]+arr[i:])
  else:
   res.append(arr[i:i+num_anim4show])
 return res

n = int(input('Кол-во видов животных: '))
arr_ca = list(map(int, input('Кол-во животных каждого вида (через пробел): ').split(' ')))
print(calc_comb(make_comb(arr_ca)))

тут заложен потенцивал - можно задавать количество животных для выставки, НО этот потенцивал несет и ответственность - необходимо проверять входные данные, например, чтобы не требовалось собрать видов животных больше, чем всего видов ...
УлугбекПрофи (815) 1 месяц назад
Я тут еще немного подумал, пока крутил шаурму. В моём варианте кода совсем не нужно значение переменной n. Ведь кол-во видов животных определяется длинной массива с данными о кол-ве животных каждого вида. Возможно, данная переменная нужна для проверки входных данных. Что-то типа, если количество видов меньше длины массива, то берем первые n значений для рассчета:

n = int(input('Кол-во видов животных: '))
arr_ca = list(map(int, input('Кол-во животных каждого вида (через пробел): ').split(' ')))
if n <= len(arr_ca):
 print(calc_comb(make_comb(arr_ca[:n])))
else:
 print('Массив с кол-вом животных каждого вида не соответствует кол-ву видов животных.')
УлугбекПрофи (815) 1 месяц назад
А можно расширить решение для случая когда n меньше длины массива с данными о кол-ве животных каждого вида. Всё так же, по правилам комбинаторики, но задача тогда будет звучать по другому, что-то типа "Вычислить число способов выбрать трёх животных из n различных видов из m доступных видов". Задача на комбинации без повторений. В таком случае можно написать так:

n = int(input('Кол-во видов животных: '))
arr_ca = list(map(int, input('Кол-во животных каждого вида (через пробел): ').split(' ')))
if n < len(arr_ca):
 print(sum(calc_comb(make_comb(c)) for c in make_comb(arr_ca, n)))
elif n == len(arr_ca):
 print(calc_comb(make_comb(arr_ca)))
else:
 print(0) #'Трёх животных из {n} различных видов из {len(arr_ca)} доступных видов можно выбрать 0 способами'
УлугбекПрофи (815) 1 месяц назад
функцию calc_comb() можно записать проще:

def calc_comb(comb):
 return sum(multip(*s) for s in comb)
Похожие вопросы
Также спрашивают