from IPython.display import Javascript
Javascript('IPython.notebook.execute_cells_below()')
def next_alive(k):
k = k % N
while dead[k]: k = (k + 1) % N
return k
N = 6
dead = [False for _ in range(N)]
alive = 0
for i in range(N- 1):
alive = next_alive(next_alive(alive) + 1)
dead[alive] = True
dead
%matplotlib inline
from math import sin
import graphviz
from ipywidgets import interactive
from IPython.display import Image
import matplotlib.pylab as plt
soldati = lambda n: list(range(1, n + 1))
def gioca(soldati):
V = list(soldati)
M = []
m = 1
while len(V) > 1:
M.append(V[m])
del V[m]
m = m + 1
if m >= len(V): m = m - len(V)
return M
def giuseppe(N, size = 400):
G = graphviz.Digraph(engine = 'neato', format = 'png', graph_attr = {'size': '8!', 'ratio': 'compress', 'dpi': '75'})
for i in range(N):
G.node(str(i), label=str(i+1))
G.edge(str(i), str((i +1)%N))
seq = list(gioca(soldati(N)))
images = [Image(G.pipe(), width = size)]
for i in seq:
G.node(str(i-1), color = 'red', style = 'filled')
images.append(Image(G.pipe(), width = size))
def red(s = 0):
display(images[s])
iw = interactive(red, s = (0, len(images) - 1))
iw.children[-1].layout.height = f'{size + 60}px'
return iw
def disegna(N):
x = soldati(N)
y = [sopravvissuto(n) for n in x]
plt.subplots(figsize=(16, 8))
i = 1
while i <= x[-1]:
plt.axvline(i, color = 'r', lw = .5)
i *= 2
plt.plot(x,y, '.-')
DEBUG = False
from IPython.core.ultratb import AutoFormattedTB
itb = AutoFormattedTB(mode = 'Plain', tb_offset = 1)
def custom_exc(shell, etype, evalue, tb, tb_offset=None):
if DEBUG: shell.showtraceback((etype, evalue, tb), tb_offset=tb_offset)
stb = itb.structured_traceback(etype, evalue, tb)
print(itb.stb2text(stb[-1]))
get_ipython().set_custom_exc((Exception,), custom_exc)
3 + 4 * 2
11
4 < 2
False
5 == 5
True
sin(3)
0.1411200080598672
print(3 + 2)
5
x + 3
NameError: name 'x' is not defined
x = 3
x + 3
6
x = x + 1
x
4
v = [10, 30, 60, 50]
v
[10, 30, 60, 50]
$\vec{\mathbf{v}} = (v_0, v_1, \ldots, v_{n-1})$
v[2]
60
del v[3]
v
[10, 30, 60]
x = 3
y = 2
x + y
5
if y == 2:
x = 7
else:
x = 3
x
7
i = 1
while i <= 10:
print(3 * i)
i = i + 1
3 6 9 12 15 18 21 24 27 30
Citando Frederic Brooks, in The Mythical Man-Month (1975)…
giuseppe(11)
interactive(children=(IntSlider(value=0, description='s', max=10), Output(layout=Layout(height='460px'))), _do…
giuseppe(41, 600)
interactive(children=(IntSlider(value=0, description='s', max=40), Output(layout=Layout(height='660px'))), _do…
vivi = soldati(5)
vivi
[1, 2, 3, 4, 5]
del vivi[1]
vivi
[1, 3, 4, 5]
vivi = soldati(5)
i = 1
while i < 5:
del vivi[i]
i = i + 2
vivi
[1, 3, 4]
vivi = soldati(6)
i = 1
while i < 6:
del vivi[i]
i = i + 2
IndexError: list assignment index out of range
N = 6
vivi = soldati(N)
i = 1
while i < N:
print(i, vivi)
del vivi[i]
i = i + 2
1 [1, 2, 3, 4, 5, 6] 3 [1, 3, 4, 5, 6] 5 [1, 3, 4, 6] IndexError: list assignment index out of range
vivi = soldati(N)
i = 1
while i < N:
del vivi[i]
i = i + 1
IndexError: list assignment index out of range
vivi
[1, 3, 5]
vivi = soldati(N)
i = 1
while i < len(vivi):
del vivi[i]
i = i + 1
vivi
[1, 3, 5]
i
4
vivi + vivi
[1, 3, 5, 1, 3, 5]
vivi = soldati(N)
i = 1
while i < len(vivi):
del vivi[i]
i = i + 1
if i >= len(vivi): i = i - len(vivi)
vivi
[]
vivi = soldati(N)
i = 1
while len(vivi) > 1:
del vivi[i]
i = i + 1
if i >= len(vivi): i = i - len(vivi)
vivi
[5]
def sopravvissuto(N):
vivi = soldati(N)
i = 1
while len(vivi) > 1:
del vivi[i]
i = i + 1
if i >= len(vivi): i = i - len(vivi)
return vivi[0]
sopravvissuto(6)
5
N = 1
while N < 12:
print(N, sopravvissuto(N))
N = N + 1
1 1 2 1 3 3 4 1 5 3 6 5 7 7 8 1 9 3 10 5 11 7
giuseppe(16)
interactive(children=(IntSlider(value=0, description='s', max=15), Output(layout=Layout(height='460px'))), _do…
N = 1
while N <= 1024:
print(sopravvissuto(N))
N = N * 2
1 1 1 1 1 1 1 1 1 1 1
disegna(11)
disegna(130)
Se $n$ è il più grande intero tale che
$$N = 2^n + \ell$$(ossia $\ell < 2^n$), dal grafico formuliamo l'ipotesi che
$$\text{sopravvisuto}(N) = m \ell + q$$restano da determinare $m$ e $q$…
N = 1
due_alla_n = 1
while N <= 16:
l = N - due_alla_n
print(l, sopravvissuto(N))
N = N + 1
if 2 * due_alla_n <= N: due_alla_n = due_alla_n * 2
0 1 0 1 1 3 0 1 1 3 2 5 3 7 0 1 1 3 2 5 3 7 4 9 5 11 6 13 7 15 0 1
Possiamo concludere che $$\text{sopravvisuto}(2^n + \ell)= 2 \ell + 1.$$
Quando $N = 41 = 32 + 9 = 2^6 + 9$, per sopravvivere bisogna quindi essere al posto
$$2 \times 9 + 1 = 19$$