Delimitazione di questo programma per determinare la somma dei reciproci numeri interi non contiene zero
https://stackoverflow.com/questions/3847615
-
27-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Lasciate Un indicare l'insieme dei numeri interi positivi la cui rappresentazione decimale non contengono la cifra 0.La somma dei reciproci di elementi in Un è noto per essere 23.10345.
Ex.1,2,3,4,5,6,7,8,9,11-19,21-29,31-39,41-49,51-59,61-69,71-79,81-89,91-99,111-119, ...
Poi prendi il reciproco di ogni numero, e la somma totale.
Come può essere verificato numericamente?
Scrivere un programma per computer per verificare questo numero.
Qui è quello che ho scritto finora, ho bisogno di aiuto delimitazione questo problema come questo attualmente impiega troppo tempo per completare:
Codice in Java
import java.util.*;
public class recip
{
public static void main(String[] args)
{
int current = 0; double total = 0;
while(total < 23.10245)
{
if(Integer.toString(current).contains("0"))
{
current++;
}
else
{
total = total + (1/(double)current);
current++;
}
System.out.println("Total: " + total);
}
}
}
Soluzione
Questo non è così difficile quando si è avvicinato in modo corretto.
Si supponga ad esempio, che si desidera trovare la somma dei reciproci di tutti gli interi a partire (vale a dire i più a sinistra cifre) con 123 e termina con k non-zero cifre. Ovviamente ci sono 9 k tali numeri interi e il reciproco di ciascuno di questi numeri interi è nell'intervallo 1 / (124 * 10 k ) .. 1 / (123 * 10 < sup> k ). Quindi la somma dei reciproci di tutti questi numeri interi è delimitata da (9/10) k / 124 e (9/10) k / 123.
Per trovare limiti per somma di tutti i reciproci che iniziano con 123 si devono sommare i limiti di cui sopra per ogni k> = 0. Questa è una serie geometrica, quindi può essere derivato che la somma dei reciproci dei numeri interi che iniziano con 123 è delimitata da 10 * (9/10) k / 124 e 10 * (9/10) < sup> k / 123.
Lo stesso metodo può naturalmente essere applicato a qualsiasi combinazione di maggior-sinistra cifre. I più cifre che esaminiamo sulla sinistra, il più preciso il risultato diventa. Ecco un'implementazione di questo approccio in Python:
def approx(t,k):
"""Returns a lower bound and an upper bound on the sum of reciprocals of
positive integers starting with t not containing 0 in its decimal
representation.
k is the recursion depth of the search, i.e. we append k more digits
to t, before approximating the sum. A larger k gives more accurate
results, but takes longer."""
if k == 0:
return 10.0/(t+1), 10.0/t
else:
if t > 0:
low, up = 1.0/t, 1.0/t
else:
low, up = 0, 0
for i in range(10*t+1, 10*t+10):
l,u = approx(i, k-1)
low += l
up += u
return low, up
Calling circa (0, 8) per esempio dà l'inferiore e limite superiore: 23,103,447707 millions ... e 23,103,448107 millions .... che è vicino alla rivendicazione 23,10,345 mila in OP.
Ci sono metodi che convergono più veloce per la somma in questione, ma richiedono più matematica. Una migliore approssimazione della somma può essere trovato qui . Una generalizzazione del problema sono la Kempner serie .
Altri suggerimenti
Per tutti i valori superiori ad una soglia current N, 1.0/(double)current sarà sufficientemente piccola che total non aumenta come conseguenza di aggiunta 1.0/(double)current. Pertanto, il criterio di terminazione dovrebbe essere qualcosa del tipo
while(total != total + (1.0/(double)current))
invece di testare contro il limite che è noto a priori . Il tuo ciclo si interrompe quando current raggiunge questo valore speciale di N.
Ho il sospetto che il cast a string e quindi il controllo per il carattere '0' è il passo che richiede troppo tempo.Se si vuole evitare di tutti zeri, potrebbe contribuire ad aumentare current quindi:
(A cura -- grazie a Aaron McSmooth)
current++;
for( int i = 10000000; i >= 10; i = i / 10 )
{
if ( current % i ) == 0
{
current = current + ( i / 10 );
}
}
Questo non è testato, ma il concetto dovrebbe essere chiaro:ogni volta che si colpisce un multiplo di una potenza di dieci (es.300 o 20000), aggiungere la successiva potenza inferiore a 10 (nel nostro esempio 10 + 1 e 1000 + 100 + 10 + 1 rispettivamente) fino a quando non ci sono più zeri del numero.
Cambia il tuo while loop di conseguenza e vedere se questo non aiuta le prestazioni al punto fosse il problema diventa gestibile.
Oh, e si potrebbe desiderare di limitare il System.out uscita un po ' così.Ogni decimo, un hundreth o 10000th iterazione essere sufficiente?
Modificare la seconda:
Dopo un po 'di sonno, ho il sospetto che la mia risposta potrebbe essere un po' miope (colpa della tarda ora, se volete).Ho semplicemente sperava che, oh, un milione di iterazioni di current la soluzione e di sinistra che, invece di calcolare la correzione dei casi, l'uso log( current ) ecc.
Il secondo pensiero, vedo due problemi con questo complesso problema.Una è che il vostro numero di destinazione di 23.10345 è un leeeeettle a giro per i miei gusti.Dopo tutto, tu sei l'aggiunta di migliaia di elementi, come "1/17", "1/11111" e così via, con infinite rappresentazioni decimali, ed è altamente improbabile che si sommano esattamente 23.10345.Se qualche specialista per la matematica numerica dice così, va bene-ma poi mi piacerebbe vedere l'algoritmo con cui sono arrivati a questa conclusione.
L'altro problema è legato alla prima e riguarda la limitata memoria binario rappresentazione dei numeri razionali.Si potrebbe ottenere utilizzando BigDecimals, ma ho i miei dubbi.
Quindi, in sostanza, vi suggerisco di riprogrammare l'algoritmo numerico invece di andare per la soluzione di forza bruta.Mi dispiace.
Modificare il terzo: Per curiosità, ho scritto questo in C++ per testare le mie teorie.E ' gestito per 6 minuti e ora è a circa 14,5 (circa 550 milioni di euro.iterazioni).Staremo a vedere.
La versione attuale è
double total = 0;
long long current = 0, currPowerCeiling = 10, iteration = 0;
while( total < 23.01245 )
{
current++;
iteration++;
if( current >= currPowerCeiling )
currPowerCeiling *= 10;
for( long long power = currPowerCeiling; power >= 10; power = power / 10 )
{
if( ( current % power ) == 0 )
{
current = current + ( power / 10 );
}
}
total += ( 1.0 / current );
if( ! ( iteration % 1000000 ) )
std::cout << iteration / 1000000 << " Mio iterations: " << current << "\t -> " << total << std::endl;
}
std::cout << current << "\t" << total << std::endl;
Calcolo currPowerCeiling (o comunque la si potrebbe chiamare questa parte consente di risparmiare qualche log10 e pow i calcoli di ogni iterazione.Ogni po ' aiuta, ma è ancora dura per sempre...
Modifica il quarto: Lo stato è 66.000 mio iterazioni, il totale è fino a 16.2583, runtime è di circa 13 ore.Non guardando bene, Bobby S.-- Mi suggeriscono un più approccio matematico.
Come su come conservare il numero attuale come matrice di byte in cui ogni elemento dell'array è una cifra 0-9? In questo modo, si può rilevare zeri molto rapidamente (il confronto byte utilizzando == invece di String.contains).
Il rovescio della medaglia è che è necessario per l'attuazione del incrementare da soli invece di utilizzare ++. Avrete anche bisogno di escogitare un modo per marcare cifre "inesistenti", in modo che non li rileva come zeri. Memorizzazione -1 per le cifre suoni inesistenti come una soluzione ragionevole.
Per un intero a 32 bit con segno, questo programma non si fermerà mai. Sarà effettivamente convergere verso -2097156. Poiché il numero massimo armonica (la somma dei reciproci integrali da 1 a N) di un intero a 32 bit con segno è ~14.66, questo ciclo non terminerà mai, anche quando avvolge intorno correnti da 2^31 - 1 a -2^31. Poiché il reciproco del grande numero intero negativo a 32 bit è ~ -4.6566e-10, ogni volta ritorno della tensione di 0, la somma sarà negativo. Dato che il maggior numero rappresentabile da un double tale che number + + 1/2^31 == number è 2^52 / 2^31, si ottiene all'incirca -2097156 come valore convergenti.
Detto questo, e supponendo che non si dispone di un modo diretto di calcolare il numero armonica di un intero arbitrario, ci sono alcune cose che puoi fare per velocizzare il ciclo interno. In primo luogo, l'operazione più costosa sarà System.out.println; che deve interagire con la console, nel qual caso il programma alla fine dovranno svuotare il buffer alla console (se presente). Ci sono casi in cui questo non può realmente accadere, ma dal momento che si sta utilizzando per il debug non sono relative a questa domanda.
Tuttavia, è anche spendere un sacco di tempo per determinare se un numero ha uno zero. È possibile capovolgere quel test in giro per generare gamme di numeri interi tali che all'interno di tale intervallo si sono garantiti di non avere un numero intero con una cifra pari a zero. Questo è davvero semplice da fare in modo incrementale (in C ++, ma abbastanza banale da convertire in Java):
class c_advance_to_next_non_zero_decimal
{
public:
c_advance_to_next_non_zero_decimal(): next(0), max_set_digit_index(0)
{
std::fill_n(digits, digit_count, 0);
return;
}
int advance_to_next_non_zero_decimal()
{
assert((next % 10) == 0);
int offset= 1;
digits[0]+= 1;
for (int digit_index= 1, digit_value= 10; digit_index<=max_set_digit_index; ++digit_index, digit_value*= 10)
{
if (digits[digit_index]==0)
{
digits[digit_index]= 1;
offset+= digit_value;
}
}
next+= offset;
return next;
}
int advance_to_next_zero_decimal()
{
assert((next % 10)!=0);
assert(digits[0]==(next % 10));
int offset= 10 - digits[0];
digits[0]+= offset;
assert(digits[0]==10);
// propagate carries forward
for (int digit_index= 0; digits[digit_index]==10 && digit_index<digit_count; ++digit_index)
{
digits[digit_index]= 0;
digits[digit_index + 1]+= 1;
max_set_digit_index= max(digit_index + 1, max_set_digit_index);
}
next+= offset;
return next;
}
private:
int next;
static const size_t digit_count= 10; // log10(2**31)
int max_set_digit_index;
int digits[digit_count];
};
Quello che il codice di cui sopra non è quello di iterare su ogni intervallo di numeri tali che il campo contiene solo numeri senza zeri. Funziona determinando come andare da N000 ... N111 a ... e da N111 ... a (N + 1) 000 ..., portando (N + 1) in 1 (0) 000 ... se necessario.
Sul mio portatile, ho in grado di generare il numero armonica di 2 ^ 31 -. 1 in 8.73226 secondi
public class SumOfReciprocalWithoutZero {
public static void main(String[] args) {
int maxSize=Integer.MAX_VALUE/10;
long time=-System.currentTimeMillis();
BitSet b=new BitSet(maxSize);
setNumbersWithZeros(10,maxSize,b);
double sum=0.0;
for(int i=1;i<maxSize;i++)
{
if(!b.get(i))
{
sum+=1.0d/(double)i;
}
}
time+=System.currentTimeMillis();
System.out.println("Total: "+sum+"\nTimeTaken : "+time+" ms");
}
static void setNumbersWithZeros(int srt,int end,BitSet b)
{
for(int j=srt;j<end;j*=10)
{
for(int i=1;i<=10;i++)
{
int num=j*i;
b.set(num);
}
if(j>=100)
setInbetween(j, b);
}
}
static void setInbetween(int strt,BitSet b)
{
int bitToSet;
bitToSet=strt;
for(int i=1;i<=10;i++)
{
int nxtInt=-1;
while((nxtInt=b.nextSetBit(nxtInt+1))!=strt)
{
b.set(bitToSet+nxtInt);
}
nxtInt=-1;
int lim=strt/10;
while((nxtInt=b.nextClearBit(nxtInt+1))<lim)
{
b.set(bitToSet+nxtInt);
}
bitToSet=strt*i;
}
}
}
Questa è un'implementazione utilizzando BitSet.I calcolata la somma di di reciproci per tutti intero è nella gamma (1-Integer.MAX_VALUE/10).The somma arriva fino 13.722766931560747.This è il massimo che può essere calcolato usando BitSet in quanto la portata massima per BitSet è Integer.MAX_VALUE.I necessità di dividerlo per 10 e limitare il campo per evitare overflow.But v'è un significativo miglioramento nella speed.I'm proprio questo distacco di codice in-caso potrebbe darvi qualche nuova idea per migliorare il vostro codice. (Aumentare la memoria utilizzando il VM argomento -Xmx[Size>350]m)
Output:
Total: 13.722766931560747
TimeTaken : 60382 ms
UPDATE:
Java Porting di una precedente risposta, cancellato:
public static void main(String[] args) {
long current =11;
double tot=1 + 1.0/2 + 1.0/3 + 1.0/4 + 1.0/5 + 1.0/6 + 1.0/7 + 1.0/8 + 1.0/9;
long i=0;
while(true)
{
current=next_current(current);
if(i%10000!=0)
System.out.println(i+" "+current+" "+tot);
for(int j=0;j<9;j++)
{
tot+=(1.0/current + 1.0/(current + 1) + 1.0/(current + 2) + 1.0/(current + 3) + 1.0/(current + 4) +
1.0/(current + 5) + 1.0/(current + 6) + 1.0/(current + 7) + 1.0/(current + 8));
current += 10;
}
i++;
}
}
static long next_current(long n){
long m=(long)Math.pow(10,(int)Math.log10(n));
boolean found_zero=false;
while(m>=1)
{
if(found_zero)
n+=m;
else if((n/m)%10==0)
{
n=n-(n%m)+m;
found_zero=true;
}
m=m/10;
}
return n;
}
