прикреплённый файл:gravec.py к странице LecturesVMSH/Python/2012-12-21

   1 #!/usr/bin/python
   2 '''
   3 Гравицаппу можно изготовить из нескольких деталей по прилагающейся инструкции.
   4 Если соответствующей детали нет, её, в свою очередь, можно изготовить из других
   5 деталей по другому разделу той же инструкции. Если деталей Написать программу,
   6 которая проверяет, можно ли из имеющегося набора деталей изготовить гравицаппу.
   7 
   8 Ввод: Первая строка "--- набор имеющихся деталей (разделённые
   9 пробелом натуральные числа, необязательно различные, в диапазоне от 1 до
  10 999 числом не более 10000). Вторая и последующие строки содержат правила из
  11 инструкции вида <<ЦелеваяДеталь Деталь1 Деталь2 ...>>, задающие
  12 способ сборки ЦелевойДетали. Последняя строка определяет правило
  13 сборки самой гравицаппы в виде <<0 Деталь1 Деталь2 ...>> (ноль
  14 вместо номера детали). Каждая составная деталь собирается единственным
  15 способом.
  16 '''
  17 
  18 List=raw_input().split()        # Набор имеющихся деталей
  19 Rules={}                        # Словарь вида R[ЦелеваяДеталь]=[Деталь1 Деталь2 ...]
  20 while True:                     # Строим словарь
  21     Rule=raw_input().split()    # Список слов
  22     Rules[Rule[0]]=Rule[1:]     # Первое слово - ЦелеваяДеталь
  23     if Rule[0] == "0": break    # Последняя строка: сборка гравицаппы
  24 print Rules
  25 
  26 Work=Rules["0"]                 # Каких деталей не хватает для гравицаппы?
  27 while Work:                     # Гравицаппа всё ещё не собрана
  28     Detail=Work.pop()           # Забираем нужную деталь из списка
  29     if Detail in List:          # ...есть в наборе?
  30         List.remove(Detail)     #    используем её
  31         continue                #    перейдём к другой детали
  32     if Detail not in Rules:     # ...нет в наборе и нельзя сделать из других?
  33         print "No"              #    cобрать гравицаппу нельзя
  34         break                   #    дальше можно не пробовать
  35     Work.extend(Rules[Detail])  # Добавим составляющие снятой детали в список
  36 else:                           # (выход из whilе не с помощью break)
  37     print "Yes"                 # Все детали или их составляющие оказались в наборе