Home > Project Euler, python > Problem euler #40

Problem euler #40

An irrational decimal fraction is created by concatenating the positive
integers:

0.123456789101112131415161718192021...

It can be seen that the 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the value of
the following expression.

d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000

Analisi:

Si potrebbe erroneamente voler ciclare su 10**6 valori, dovendo
cercare anche il milionesimo decimale del valore in oggetto.
In raltà, come si nota partendo da un limite dato, si ottengono
molti più decimali del limite stesso.
Ad esempio, ciclando su 20 numeri, otteniamo 31 decimali

0.1234567891011121314151617181920

Quindi se il nostro massimo richiesto è di trovare la
20ma posizione della frazione irrazionale, possiamo ciclare solo
su 15 numeri, che mi danno origine a 21 decimali.
Per limitare quindi il campo di azione del codice e non ricadere
sul Brute Force totale, cerchiamo di capire quale numero ci dia
come risultato 10**6 decimali:

>>> res = ''
>>> for d in xrange(1, 10**6 + 1):
        res += str(d)
        if len(res) > 10**6:
		print d
		break

	
185185

ben lontano dal 10**6 iniziale!

quindi:

import time
ts = time.time()

def get_irrational(limit):
    res = ''
    for d in xrange(1, limit + 1):
        res += str(d)
    return res

num = get_irrational(185185) # previous limit

prod = 1
for pos in (10, 10**2, 10**3, 10**4, 10**5, 10**6):
    prod *= int(num[pos - 1])

print "euler 40: {} \nelapesd time: {}sec".format(prod, time.time() - ts)
Categorie:Project Euler, python
  1. Non c'è ancora nessun commento.
  1. No trackbacks yet.

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: