Explication algorithme vampire

Description

Soit n un nombre pair de digits. Soit l’ensemble n n1 2 2 2E =f10 ;:::; 10 1gn 2Par exemple E =f10; 11; 12;:::; 99g .

Informations

• Publié par: Nicolas-
• Publié le: 19 octobre 2013
• Nombre de lectures: 84
• Langue: English

Extrait

Soitnun nombre pair de digits. Soit l’ensemble

En={10n2−1, ...,102n−1}2

Par exempleE4={10,11,12, ...,99}2.
Onconsid`erelesousensemble

Cn={(i, j)∈En, i≥j}

On munitCnde la relation d’ordre lexicographique, ie :
i < kou (i=ketj < l).
Soit (Ukesd)ssiorce´detiusalntme´eels´deteanCn.
On peut construire (Uk) avec l’algorithme suivant :

Algorithm 1ParcourirCnecnasseoicr´end
k←0
fori= 10n2−1;i >= 10n2−1;i=i−1do
forj=i;j >= 102n−1;j=j−1do
Uk= (i, j)
k=k+ 1
end for
end for

(i, j)<(k, l) ssi

On notef:Cn−→Nl’application qui pour un couple (i, j) donne l’indice
kcorrespondant tel queUk= (i, j).
On noteVkebloulduiteprolee´ed´sdscuemtnUk, ie :Uk= (i, j)⇒Vk=ij.
On noteDkle premier digit deVk, ex :Vk= 4321⇒Dk= 4.
On remarque que pour tout couple de type (i, i), on a :
Pour toutktel quek > f(i, i), alorsi2> Vk.
Cela implique :
Pour toutktel quek > f(i, i), alorsDf(i,i)≥Dk
Cetteconstatationnouspermetd’am´eliorerl’algorithmebruteforcepour
trouver les nombres vampires :
Il suffit de monitorer les digitsDf(i, i) et d’exclure les couples (k, l)<(i, i) si
ketlrieuup´eentsctemtsirostnigstseidtlouttonsdrembnosedtnosa`srDf(i,i),
cetestpeutˆetrefaitdemani`ereefficace(O(1)) en monitorant la position dans
le couple du digit de poids le plus fort qui permet de ne pas exclure ce couple.
Par ailleurs, siDf(i,i)seneattnnolerslo,a=0´rpertigidederbmVf(i, i) est
inf´erieur`ana’ltroglmhtia’seˆerr.tee

Cidessouslesnombresd’ite´rationspourlebruteforcecompare´aunombre
d’ite´rationsenexcluantlescouplesselonnotrecrit`ere:

notre algo
brute force
rapport

n= 4
3426
4005
85.5%

n= 6
365140
404550
90.2%

n= 8
37285158
40495500
92.0%

1

n= 10
3766116479
4049955000
92.9%