У меня есть несколько вопросов по поводу некоторых кодирования питона. Я пытался решить эти три проблемы, но безрезультатно. я понятия не имею, как начать их решения. Это дополнительный курс, который я беру. У меня 2 выпускных экзаменов в школе завтра, и вся помощь будет высоко оценен.
Question 1:
One of the problems with our page ranking system is pages can collude with each other to improve their page ranks. We consider A->B a reciprocal link if there is a link path from B to A of length equal to or below the collusion level, k. The length of a link path is the number of links which are taken to travel from one page to the other.
If k = 0, then a link from A to A is a reciprocal link for node A, since no links needs to be taken to get from A to A.
If k=1, B->A would count as a reciprocal link if there is a link A->B, which includes one link and so is of length 1. (it requires two parties, A and B, to collude to increase each others page rank).
If k=2, B->A would count as a reciprocal link for node A if there is a path A->C->B, for some page C, (link path of length 2), or a direct link A-> B (link path of length 1).
The compute_ranks code must:
- take an extra input k, which is a non-negative integer, and
- exclude reciprocal links of length up to and including k from helping the page rank.
def compute_ranks(graph): d = 0.8 # damping factor numloops = 10 ranks = {} npages = len(graph) for page in graph: ranks[page] = 1.0 / npages for i in range(0, numloops): newranks = {} for page in graph: newrank = (1 - d) / npages for node in graph: if page in graph[node]: newrank = newrank + d * (ranks[node]/len(graph[node])) newranks[page] = newrank ranks = newranks return ranks
g = {'a': ['a', 'b', 'c'], 'b':['a'], 'c':['d'], 'd':['a']} #print compute_ranks(g, 0) # the a->a link is reciprocal #>>> {'a': 0.26676872354238684, 'c': 0.1216391112164609, # 'b': 0.1216391112164609, 'd': 0.1476647842238683} #print compute_ranks(g, 1) # a->a, a->b, b->a links are reciprocal #>>> {'a': 0.14761759762962962, 'c': 0.08936469270123457, # 'b': 0.04999999999999999, 'd': 0.12202199703703702} #print compute_ranks(g, 2) # a->a, a->b, b->a, a->c, c->d, d->a links are reciprocal # (so all pages end up with the same rank) #>>> {'a': 0.04999999999999999, 'c': 0.04999999999999999, # 'b': 0.04999999999999999, 'd': 0.04999999999999999}
Question 2:
A one-dimensional cellular automata takes in a string, which in our case, consists of the characters ‘.’ and ‘x’, and changes it according to some predetermined rules. The rules consider three characters, which are a character at position k and its two neighbours, and determine what the character at the corresponding position k will be in the new string.
For example, if the character at position k in the string is ‘.’ and its neighbours are ‘.’ and ‘x’, then the pattern is ‘..x’. We look up ‘..x’ in the table below. In the table, ‘..x’ corresponds to ‘x’ which means that in the new string, ‘x’ will be at position k.
Rules:
pattern in position k in contribution to
Value current string new string pattern number
is 0 if replaced by ‘.’ and value if replaced by ‘x’
# 1 ‘…’ ‘.’ 1 * 0
# 2 ‘..x’ ‘x’ 2 * 1
# 4 ‘.x.’ ‘x’ 4 * 1
# 8 ‘.xx’ ‘x’ 8 * 1
# 16 ‘x..’ ‘.’ 16 * 0
# 32 ‘x.x’ ‘.’ 32 * 0
# 64 ‘xx.’ ‘.’ 64 * 0
# 128 ‘xxx’ ‘x’ 128 * 1
# ———-
# 142
To calculate the patterns which will have the central character x, work out the values required to sum to the pattern number. For example, 32 = 32 so only pattern 32 which is x.x changes the central position to
an x. All the others have a . in the next line.
23 = 16 + 4 + 2 + 1 which means that ‘x..’, ‘.x.’, ‘..x’ and ‘…’ all
lead to an ‘x’ in the next line and the rest have a ‘.’
For pattern 142, and starting string
………..x………..
the new strings created will be
……….xx……….. (generations = 1)
………xx………… (generations = 2)
……..xx…………. (generations = 3)
…….xx………….. (generations = 4)
……xx…………… (generations = 5)
…..xx……………. (generations = 6)
….xx…………….. (generations = 7)
…xx……………… (generations = 8)
..xx………………. (generations = 9)
.xx……………….. (generations = 10)
Note that the first position of the string is next to the last position in the string.
Define a procedure, cellular_automaton, that takes three inputs:
a non-empty string,
a pattern number which is an integer between 0 and 255 that represents a set of rules, and
a positive integer, n, which is the number of generations.
The procedure should return a string which is the result of
applying the rules generated by the pattern to the string n times.
def cellular_automaton():
print cellular_automaton('.x.x.x.x.', 17, 2) #>>> xxxxxxx.. print cellular_automaton('.x.x.x.x.', 249, 3) #>>> .x..x.x.x print cellular_automaton('...x....', 125, 1) #>>> xx.xxxxx print cellular_automaton('...x....', 125, 2) #>>> .xxx.... print cellular_automaton('...x....', 125, 3) #>>> .x.xxxxx print cellular_automaton('...x....', 125, 4) #>>> xxxx...x print cellular_automaton('...x....', 125, 5) #>>> ...xxx.x print cellular_automaton('...x....', 125, 6) #>>> xx.x.xxx print cellular_automaton('...x....', 125, 7) #>>> .xxxxx.. print cellular_automaton('...x....', 125, 8) #>>> .x...xxx print cellular_automaton('...x....', 125, 9) #>>> xxxx.x.x print cellular_automaton('...x....', 125, 10) #>>> ...xxxxx