Abbiamo una sequenza crescente in cui ogni elemento è composto solo da cifre pari (0, 2, 4, 6, 8). Come possiamo find the nth number in this sequenceTrova l'ennesimo numero nella sequenza crescente formato da 0,2,4,6,8?
E 'possibile trovare n numero in questa sequenza in O (1) tempo.
Sequenza: 0, 2, 4, 6, 8, 20, 22, 24, 26, 28, 40, 42, 44, 46, 48, 60, 62, 64, 66, 68, 80, 82, 84, 86, 88, 200, 202 and so on.
Il numero esimo in questa sequenza è n in base 5, con le cifre raddoppiati.
def base5(n):
if n == 0: return
for x in base5(n // 5): yield x
yield n % 5
def seq(n):
return int(''.join(str(2 * x) for x in base5(n)) or '0')
for i in xrange(100):
print i, seq(i)
Questo funziona nel tempo O (log n). Non credo sia possibile farlo nel tempo O (1).
Può essere semplificato un po combinando il raddoppio delle cifre con la generazione della base 5 cifre di n:
def seq(n):
return 10 * seq(n // 5) + (n % 5) * 2 if n else 0
grazie Paul, O (logn) è anche buono :) – Godfather
@Paul Hankin: Signore, potresti aiutarmi per favore come hai risolto questa sequenza? –
@Ram non ti è di grande aiuto, ma ho visto subito la relazione con i numeri in base 5, e da lì, scrivere il codice è relativamente semplice. Lasse nei commenti sopra suggeriva di controllare la sequenza in OEIS - sarebbe un buon modo per trovare il modello se non lo vedessi. –
int Code()
{
k=0;
for(i=0;i<=10000;i++)
{
count=0;
n=i;
while(n!=0)
{
c=n%10;
n=n/10;
if(c%2!=0)
{
count=1;
}
}
if(count==0)
{ a[k]=i;
k++;}
}
}
dove n è iniziare forma zero o uno? –
Sto votando per chiudere questa domanda come off-topic perché è una discarica di un compito a casa che mostra lo sforzo ZERO dall'OP. –
La prima sosta sul Web quando si esamina questo esatto * tipo * problema è la [Enciclopedia online di Integer Sequences (OEIS)] (https://oeis.org), che ha [questo da dire per la sequenza 0 , 2, 4, 6, 8, 20, 22, 24, 26, 28, 40, 42] (https://oeis.org/search?q=0%2C+2%2C+4%2C+6% 2C + 8% 2C + 20% 2C + 22% 2C + 24% 2C + 26% 2C + 28% 2C + 40% 2C + 42 & language = inglese & go = Ricerca). –