from random import *
from math import *

def uniforme(n): ##simule une loi uniforme
    return randint(1,n)

def espiniforme(n,nb): #simule l'espérance
    s=0
    for k in range(nb):
        s=s+uniforme(n)
    return s/nb

###################################################

def protocole():
    U=['B','V']
    temps=1
    while True:
        n=len(U)
        #print(n,U)
        i=randint(0,n-1)
        if U[i]=='B':
            temps=temps+1
            U.append('B')
            U.append('B')
        else:
            return temps

def exempleDeTirage(nb): # renvoie l'exécutions de n fois la fonction "protocole"
    for i in range(nb):
        print(protocole(),end=' - ')



def espprtotocole(nb): #simule l'espérance
    s=0
    for j in range(nb):
        s=s+protocole()
    return(s/nb)


























#>>> espprtotocole(1000)
#274.456

#>>> espprtotocole(1000)
#464.704

#>>> espprtotocole(1000)
#3330.146

#>>> espprtotocole(1000)
#103.714









def protocoleBis(N):
    U=['B','V']
    temps=1
    while True:
        n=len(U)
        #print(n,U)
        i=randint(0,n-1)
        if U[i]=='B':
            temps=temps+1
            U.append('B')
            U.append('B')
            if temps>N:
                return 0
                #return 'fini' #print('grand',temps)
            #print(U)
        else:
            return temps

def exempleDeTirageBis(N,nb): # renvoie l'exécutions de n fois la fonction "protocole"
    for i in range(nb):
        print(protocoleBis(N),end=' *')

#>>> exempleDeTirageBis(50,100)
#9 *1 *1 *1 *36 *1 *2 *1 *1 *1 *1 *1 *1 *7 *1 *6 *1 *1 *1 *1 *1 *14 *45 *1 *0 *1 *1 *3 *0 *4 *1 *27 *16 *0 *1 *6 *1 *1 *1 *1 *0 *1 *1 *2 *0 *0 *4 *3 *1 *18 *2 *1 *1 *1 *25 *2 *4 *1 *1 *1 *1 *15 *0 *5 *2 *1 *1 *1 *1 *1 *1 *1 *2 *1 *4 *1 *1 *34 *33 *5 *7 *29 *10 *1 *3 *1 *1 *1 *3 *1 *1 *0 *2 *6 *3 *2 *1 *1 *1 *0 *


def probaBis0(N,nb):
    s=0
    for j in range(nb):
        tirage=protocoleBis(N)
        if tirage==0:
            s=s+1
    return(s/nb)

def espTheo(N):
    return  factorial(2*N*1.0)/factorial(N)/factorial(N-1)/4.**N


def espprtotocoleBis(N,nb):
    s=0
    for j in range(nb):
        s=s+protocoleBis(N)
    return(s/nb)

def espprtotocoleBis2(N,nb):
    s=0
    for j in range(nb):
        s=s+protocoleBis(N)**2
    return(s/nb)

def VarBis(N,nb):
    return espprtotocoleBis2(N,nb)-espprtotocoleBis(N,nb)**2

def T(p): # géo(p)
    essai=1
    tirage=random()
    while tirage>p:
        tirage=random()
        essai=essai+1
    return essai

def protocoleTer(p):
    U=['B','V']
    temps=1
    N=T(p)
    while True:
        n=len(U)
        #print(n,U)
        i=randint(0,n-1)
        if U[i]=='B':
            temps=temps+1
            U.append('B')
            U.append('B')
            if temps>N:
                return 0
                #return 'fini' #print('grand',temps)
            #print(U)
        else:
            return temps

def espprtotocoleTer(p,nb):
    s=0
    for j in range(nb):
        s=s+protocoleTer(p)
    return(s/nb)