Прикреплённый файл «2013-01-25.koleso.py»
Загрузка 1 #!/usr/bin/env python
2 # coding: utf
3 '''
4 Колесо разделено на K секторов, в каждом из которых находится число P0, P1, … , PK. Вначале стрелка указывает на P1, после поворота колеса — на P2 и так далее по кругу (…,Pk-1,PK, P1, P2,…). Вводится число A, На i-м шаге выбирается произвольная арифметическая операция среди «+», «-» и «*» и применяется к A и Pi (более точно Ai=Ai-1 +/-/* Pi%K ), после чего колесо поворачивается. Написать программу, которая определяет минимальное количество действий, которые нужно проделать для получения числа B из числа A (A<B)
5
6 В случае, когда {Pi}={1…K}
7
8 В случае, когда {Pi} — произвольное, но гарантируется достижимость B из A
9 В случае, когда достижимость не гарантируется (возможен ответ "B нельзя получить из A")
10 … + вывести формулу
11
12 Для четырёх операций: «+», «-», «*» и «//», где // — это целочисленное деление (соответственно, X/Y*Y может быть не равно X)
13
14 Ввод: K чисел через пробел, на следующей строке — A и B
15
16 Вывод: количество операций (или формула, если это требуется), НЕТ при недостижимости
17 '''
18
19 import sys, random
20
21 if len(sys.argv)>1:
22 N=int(sys.argv[1])
23 A=len(sys.argv)>2 and int(sys.argv[2]) or random.randint(1,30)
24 B=len(sys.argv)>3 and int(sys.argv[3]) or random.randint(A+1,A*A)
25 m=len(sys.argv)>4 and int(sys.argv[4]) or A/10+1
26 M=len(sys.argv)>5 and int(sys.argv[5]) or B*N
27 Nums=list(set((random.randint(m,M) for i in xrange(N))))
28 #print "###", A, B, Nums
29 else:
30 Nums=[int(c) for c in raw_input("Введите колесо: ").split()]
31 A,B=(int(c) for c in raw_input("Введите A и B: ").split())
32 def Add(a,b): return a+b
33 def Sub(a,b): return a-b
34 def Mul(a,b): return a*b
35 def Div(a,b): return a/b
36 Funs=Add, Sub, Mul, Div
37 SFun="+-*/"
38
39 def Granted():
40 '''Решение задачи при гарантированной достижимости B из A'''
41 Step,Field,Front=0,set(),set([A])
42 while B not in Field:
43 OldFront,Front=Front,set()
44 b=Nums[Step%len(Nums)]
45 for a in OldFront:
46 for f in Funs:
47 if f(a,b) not in Field:
48 Front.add(f(a,b))
49 Field|=Front
50 Step+=1
51 return Step
52
53 def Restricted(Count=1000):
54 '''Решение задачи с органичением на количество шагов'''
55 Step,Field,Front=0,set(),set([A])
56 while B not in Field:
57 OldFront,Front=Front,set()
58 b=Nums[Step%len(Nums)]
59 for a in OldFront:
60 for f in Funs:
61 try:
62 if f(a,b) not in Field:
63 Front.add(f(a,b))
64 except:
65 print "@@@",a,b
66 sys.exit(1)
67 Field|=Front
68 Step+=1
69 if Step>Count:
70 print Field
71 return 0
72 return Step
73
74 def Limited(m,M):
75 '''Решение задачи при условии невыхода значений за границы (m…M)'''
76 Step,Field,Front=0,set(),set([A])
77 while B not in Field:
78 OldFront,Front=Front,set()
79 b=Nums[Step%len(Nums)]
80 Front=set((f(a,b) for a in OldFront for f in Funs if f(a,b) not in Field and m<=f(a,b)<=M))
81 Field|=Front
82 Step+=1
83 return Step
84
85 #print Granted()
86 print Restricted()
Прикреплённые файлы
Для ссылки на прикреплённый файл в тексте страницы напишите attachment:имяфайла, как показано ниже в списке файлов. Не используйте URL из ссылки «[получить]», так как он чисто внутренний и может измениться.- [получить | показать] (2013-02-08 11:22:13, 3.9 KB) [[attachment:2013-01-25.koleso.py]]
- [получить | показать] (2013-02-08 11:21:37, 0.1 KB) [[attachment:2013-02-01.dumb_solver.py]]
- [получить | показать] (2013-02-08 11:25:57, 1.2 KB) [[attachment:2013-02-01.lab_shell.py]]
- [получить | показать] (2013-02-01 17:42:41, 0.5 KB) [[attachment:2013-02-01.pyexec.py]]
- [получить | показать] (2013-02-08 11:21:15, 1.7 KB) [[attachment:2013-02-01.univ_shell.py]]
Вам нельзя прикреплять файлы к этой странице.