Bene, ho appena iniziato a fare i puzzle ed è così fastidioso vedere i puzzle facili da fare ma anche gestire numeri molto grandi. Questo è il problema.
Dire che devo occuparmi di numeri come 10 ^ 6/2147483647 / ecc. Devo fare operazioni aritmetiche!
Tuttavia, ritengo che questi non dovrebbero essere gestiti in modo brutale, ma i teoremi matematici / le affermazioni non mi fanno semplicemente clic a volte.
Come potrei gestire questi puzzle (non usare lib esterna)
I grandi numeri vengono utilizzati nelle sfide di codice perché sono difficili da gestire, è lo stesso motivo per cui vengono utilizzati per la crittografia. Esistono classi BigInt per la maggior parte delle lingue che possono renderle più gestibili. La maggior parte delle sfide legate al codice può essere risolta mentre si gestiscono in minima parte grandi quantità, tuttavia esistono soluzioni intelligenti che trovano il modo di evitare di dover lavorare con grandi numeri fino a quando non sono assolutamente necessari.
Mentre la soluzione esatta dipende dal problema reale, ci sono vari approcci che puoi provare a fare prima di calcolare semplicemente in forza bruta usando una libreria matematica di precisione arbitraria o multipla (BigInt, GMP, MPFR, ARPREC, ecc.).
Per prima cosa, usa un po 'di matematica. Le espressioni possono essere semplificate? Hai detto che la fonte di questi compiti riguarda i puzzle, quindi sarei molto propenso a considerare questo approccio per una soluzione, dato che questo potrebbe essere un fattore del puzzle aha momento. Le equazioni con fattoriali come le probabilità binomiali possono essere tipicamente semplificato o calcolato (indirettamente) usando tecniche matematiche piuttosto che forza bruta.
Factoring i numeri e la cancellazione di fattori comuni sarebbero una delle prime cose che proverei, a mano se necessario. Un calcolatore di precisione multiplo può essere utile.
Ri-inquadrando la domanda oi suoi valori in una base diversa (es. binario, esadecimale) o una scala di differenza (ad esempio base logaritmica 2, 10 o e - naturale ) rendere i valori più facili da gestire? Un esempio di scala logaritmica è decibel , utilizzato per RF e livelli audio.
Utilizzo di tecniche non comunemente insegnate oggigiorno, ma ben conosciute da programmatori, ingegneri, matematici che hanno familiarità con la regola di scorrimento può essere utile qualche volta.
A seconda della domanda, eseguire approssimazione prima può a volte ti conducono alla risposta corretta impedendo che le minuzie ti distolgano dall'attaccare il problema in modo creativo.
Per il tuo esempio; calcola un'equazione (approssimativa) correlata, ma semplificata.
cheèmoltovicinoallarispostacorrettaoesatta
Unaltro"trucco" è usare modulo ( mod , % , modulo , a \bmod n ) che è uno dei miei modi preferiti per ridurre i numeri, quindi se lo sai alcune algebre astratte di base a volte puoi lavorare con aritmetica modulare .
Questa è una guida pratica, molto approssimativa su come affrontare un'equazione di "puzzle" o un problema di programmazione che coinvolge grandi numeri.
Ogni linguaggio di programmazione supporta l'uso di grandi numeri: alcuni hanno questo supporto direttamente nella libreria standard, altri hanno librerie speciali scritte per questo scopo (anche molti altri).
Finché stai bene con i numeri interi dovresti cercare qualcosa come BigInteger che è presente in molte lingue. Se hai bisogno di numeri reali, allora dovresti cercare le aritmetica arbitraria di precisione .
Ecco alcuni esempi:
Se stai elaborando una sfida rompicapo e iniziano a comparire grandi numeri, la sfida non è tanto trovare la risposta (come altri hanno notato, esistono librerie per lavorare con grandi numeri), ma piuttosto la sfida è sviluppare la tua libreria per lavorare con grandi numeri. Questo può essere piuttosto impegnativo in quanto di solito dovresti dividere il numero in qualche modo su diversi spazi di memoria diversi. Per i numeri interi questo è abbastanza semplice, se richiede molto tempo da leggere e implementare; tuttavia, il supporto per i valori in virgola mobile migliorerà sicuramente le tue abilità matematiche!
Per iniziare, i seguenti siti hanno un codice open source che potresti voler leggere per vedere come funzionano con i numeri:
Inoltre, la pagina di Wikipedia su aritmetica con precisione arbitraria può inviarti anche in alcune direzioni interessanti.
Quelli in realtà non sono numeri particolarmente grandi. Il tuo esempio è ben all'interno dell'intervallo supportato da un C 'unsigned int' o 'long' su un tipico compilatore x86, e le configurazioni vanilla di python supporteranno automaticamente l'aritmetica di precisione arbitraria. Parte del problema potrebbe essere che in Python "^" non è l'operatore esponenziale, è l'operatore "XOR" bit a bit. Prova a utilizzare 10 ** 6 invece. Ovviamente, usando la divisione in interi la risposta sarà zero. Vuoi invece la divisione in virgola mobile?
Leggi altre domande sui tag programming-practices algorithms math numeric-precision