Qual è la sum delle cifre del numero 2 ^ 1000?

Questo è un problema di Project Euler , e questa domanda include qualche codice sorgente, quindi considera questo tuo avviso spoiler, nel caso tu sia interessato a risolverlo da solo. È scoraggiato distribuire soluzioni ai problemi, e non è quello che voglio. Ho solo bisogno di una piccola spinta e di una guida nella giusta direzione, in buona fede.

Il problema si legge come segue:

2 ^ 15 = 32768 e la sum delle sue cifre è 3 + 2 + 7 + 6 + 8 = 26.

Qual è la sum delle cifre del numero 2 ^ 1000?

Capisco la premessa e la matematica del problema, ma ho iniziato a praticare C # solo una settimana fa, quindi la mia programmazione è al limite.

So che int, long e double sono irrimediabilmente inadeguati per contenere precisamente le cifre 300+ (base 10) di 2 ^ 1000, quindi è necessaria una strategia. La mia strategia era quella di impostare un calcolo che ottenesse le cifre una per una, e sperare che il compilatore potesse capire come calcolare ogni cifra senza qualche errore come l’overflow:

using System; using System.IO; using System.Windows.Forms; namespace euler016 { class DigitSum { // sum all the (base 10) digits of 2^powerOfTwo [STAThread] static void Main(string[] args) { int powerOfTwo = 1000; int sum = 0; // iterate through each (base 10) digit of 2^powerOfTwo, from right to left for (int digit = 0; Math.Pow(10, digit) < Math.Pow(2, powerOfTwo); digit++) { // add next rightmost digit to sum sum += (int)((Math.Pow(2, powerOfTwo) / Math.Pow(10, digit) % 10)); } // write output to console, and save solution to clipboard Console.Write("Power of two: {0} Sum of digits: {1}\n", powerOfTwo, sum); Clipboard.SetText(sum.ToString()); Console.WriteLine("Answer copied to clipboard. Press any key to exit."); Console.ReadKey(); } } } 

Sembra funzionare perfettamente per powerOfTwo <34. La mia calcolatrice ha esaurito le cifre significative al di sopra di quella, quindi non ho potuto testare potenze più alte. Ma tracciando il programma, sembra che non si stia verificando un overflow: il numero di cifre calcolato aumenta gradualmente con l'aumentare di powerOfTwo = 1000 e anche la somma delle cifre aumenta (in media) con l'aumento di powerOfTwo.

Per il calcolo effettivo che dovrei eseguire, ottengo l’output:

Potenza di due: 1000 Somma di cifre: 1189

Ma 1189 non è la risposta giusta. Cosa c’è di sbagliato nel mio programma? Sono aperto a qualsiasi critica costruttiva.

Normale int non può aiutarti con un numero così grande. Neanche a long . Non sono mai progettati per gestire numeri così grandi. int può memorizzare circa 10 cifre (max esatto: 2,147,483,647 ) e long per circa 19 cifre (max esatto: 9,223,372,036,854,775,807 ). Tuttavia, un rapido calcolo dalla calcolatrice integrata di Windows mi dice che 2^1000 è un numero di oltre 300 cifre.

(nota a int.MAX_VALUE : il valore esatto può essere ottenuto rispettivamente da int.MAX_VALUE e long.MAX_VALUE )

Come vuoi una sum precisa di cifre, anche i tipi float o double non funzioneranno perché memorizzano solo cifre significative per poche decine di cifre. ( 7 cifre per float, 15-16 cifre per doppio). Leggi qui per maggiori informazioni sulla rappresentazione in virgola mobile, doppia precisione

Tuttavia, C # fornisce un BigInteger aritmetico BigInteger per precisione arbitraria, che dovrebbe soddisfare i tuoi bisogni (di test). cioè può fare aritmetica in un numero qualsiasi di cifre (teoricamente, ovviamente, in pratica è limitato dalla memoria della macchina fisica e richiede tempo anche in base alla potenza della CPU)


Tornando al tuo codice, penso che il problema sia qui

Math.Pow(2, powerOfTwo)

Ciò trabocca il calcolo. Beh, non proprio, ma è la double precisione che non rappresenta precisamente il valore reale del risultato, come ho detto.

Per calcolare i valori di numeri così grandi non solo devi essere un buon programmatore ma anche un buon matematico. Ecco un suggerimento per te, c’è una formula familiare a x = e x ln a , o se preferisci, a x = 10 x log a .

Più specifico al tuo problema 2 1000 Trova il log comune (base 10) di 2 e moltiplicalo per 1000; questa è la potenza di 10. Se ottieni qualcosa come 10 53.142 (53.142 = log 2 value * 1000) – che molto probabilmente lo farai – allora questo è 10 53 x 10 0.142 ; basta valutare 10 0.142 e otterrete un numero compreso tra 1 e 10; e moltiplica quello per 10 53 , ma questo 10 53 non sarà utile in quanto 53 sum zero sarà zero solo.

Per il calcolo del registro in C #

 Math.Log(num, base); 

Per una maggiore precisione è ansible utilizzare la funzione Log e Pow di Big Integer.

Ora resto a programmare, credo che tu possa avere dalla tua parte.

Una soluzione senza utilizzare la class BigInteger è quella di memorizzare ogni cifra nel proprio int e quindi eseguire la moltiplicazione manualmente.

 static void Problem16() { int[] digits = new int[350]; //we're doing multiplication so start with a value of 1 digits[0] = 1; //2^1000 so we'll be multiplying 1000 times for (int i = 0; i < 1000; i++) { //run down the entire array multiplying each digit by 2 for (int j = digits.Length - 2; j >= 0; j--) { //multiply digits[j] *= 2; //carry digits[j + 1] += digits[j] / 10; //reduce digits[j] %= 10; } } //now just collect the result long result = 0; for (int i = 0; i < digits.Length; i++) { result += digits[i]; } Console.WriteLine(result); Console.ReadKey(); } 

Ho usato lo spostamento bit a bit verso sinistra. Quindi convertire in array e sumre i suoi elementi. Il mio risultato finale è 1366, Non dimenticare di aggiungere un riferimento a System.Numerics;

 BigInteger i = 1; i = i < < 1000; char[] myBigInt = i.ToString().ToCharArray(); long sum = long.Parse(myBigInt[0].ToString()); for (int a = 0; a < myBigInt.Length - 1; a++) { sum += long.Parse(myBigInt[a + 1].ToString()); } Console.WriteLine(sum); 

dal momento che la domanda è c # specifica utilizzando un bigInt potrebbe fare il lavoro. anche in java e python funziona ma in linguaggi come c e c ++ dove la funzione non è disponibile devi prendere una matrice e fare moltiplicazione. prendere una grande cifra in serie e moltiplicarla con 2. che sarebbe semplice e aiuterà a migliorare la tua abilità logica. e venendo a progettare Eulero. c’è un problema in cui devi trovare 100! potresti voler applicare la stessa logica anche per questo.

Prova ad usare il type BigInteger, 2 ^ 100 finirà per avere un numero molto grande anche per il doppio da gestire.

 BigInteger bi= new BigInteger("2"); bi=bi.pow(1000); // System.out.println("Val:"+bi.toString()); String stringArr[]=bi.toString().split(""); int sum=0; for (String string : stringArr) { if(!string.isEmpty()) sum+=Integer.parseInt(string); } System.out.println("Sum:"+sum); ------------------------------------------------------------------------ output :=> Sum:1366 

Questa non è una risposta seria, solo un’osservazione.

Sebbene sia una buona sfida cercare di battere Project Euler usando un solo linguaggio di programmazione, credo che il sito miri a promuovere gli orizzonti di tutti i programmatori che lo tentano. In altre parole, considera l’utilizzo di un linguaggio di programmazione diverso.

Una soluzione Lisp comune al problema potrebbe essere semplice come

 (defun sum_digits (x) (if (= x 0) 0 (+ (mod x 10) (sum_digits (truncate (/ x 10)))))) (print (sum_digits (expt 2 1000))) 
  main() { char c[60]; int k=0; while(k< =59) { c[k]='0'; k++; } c[59]='2'; int n=1; while(n<=999) { k=0; while(k<=59) { c[k]=(c[k]*2)-48; k++; } k=0; while(k<=59) { if(c[k]>57){ c[k-1]+=1;c[k]-=10; } k++; } if(c[0]>57) { k=0; while(k< =59) { c[k]=c[k]/2; k++; } printf("%s",c); exit(0); } n++; } printf("%s",c); } 

Python rende molto semplice calcolare questo con un oneliner:

 print sum(int(digit) for digit in str(2**1000)) 

o in alternativa con la mappa:

 print sum(map(int,str(2**1000)))