Salve a tutti, io avrei una soluzione algoritmica.
Pur non avendo trovato la formula che risponde al tuo quesito, con quest'approccio di forza bruta è possibile determinare - in tempo esponenziale rispetto l'input - la cardinalità dell'insieme delle soluzioni.
Intanto notiamo che n, pur se non esplicitamente richiesto come intero positivo, può essere il risultato della somma di tre interi non negativi sse è un intero non negativo, quindi restituiamo 0 nel caso in cui n sia decimale o negativo;
dopodiché parte la catena:
- per ogni n>0 esiste sempre la soluzione (n+0+0);
- per ogni n>1 esiste (n-1,1,0);
- per ogni n>2 esiste (n-2, 1, 1),(n-2,2,0);
- e così via..
Dopo aver testato tutte le combinazioni, eliminiamo le soluzioni equivalenti e contiamo quelle rimaste.
Ecco una possibile implementazione:
#!/usr/bin/python
import sys
import os
DEBUG = 0
class Terna:
terna = {}
def __init__(self, n1,n2,n3):
try:
values = [int(n1),int(n2),int(n3)]
values.sort()
if DEBUG > 0: print(str(values))
values_dict = {}
for i in xrange(0,3):
value = values[i]
if(not value in values_dict):
times = values.count(value)
values_dict[value] = times
self.terna = values_dict
except:
print("Error: worng Terna constructor!")
def equivalente(self, AltraTerna):
res = True
for val in self.terna:
try:
if self.terna[val] != AltraTerna.terna[val]:
res = False
except:
res = False
return res
class TreNumeri:
def __init__(self, number):
if(number==0):
print("Storing n=0!")
self.n = int(number)
self.getPermutations()
def getPermutations(self):
n = self.n
collection = [ ] #str(n)+"+0+0"
for x in xrange(0,n):
collection.append( (str(n-x)+"+"+str(x)+"+0") )
if DEBUG>0: print("x:"+str(x)+", y:0, appending:"+str()+(str(n-x)+"+"+str(x)+"+0"))
for y in xrange(1,x):
collection.append( str(n-x)+"+"+str(x-y)+"+"+str(y) )
if DEBUG>0: print("x:"+str(x)+", y:"+str(y)+", appending:"+( str(n-x)+"+"+str(x-y)+"+"+str(y) ))
if DEBUG>0: print(str(collection))
# Removing double solutions:
for coll in collection:
if DEBUG>0: print("\n- Evaluating "+coll+" doubles:")
values = coll.split("+",3)
values_dict = {} # value:occurences
for i in xrange(0,3):
value = values[i]
if(not value in values_dict):
times = values.count(value)
values_dict[value] = times
for coll2 in collection:
if DEBUG>0: print("-"+coll+"- is "+coll+" the same of "+coll2+"?")
if coll2 != coll:
if DEBUG>0: print("-"+coll+"- not exactly... let's find out if he has got the same digits...")
values2 = coll2.split("+",3)
values_dict2 = {} # value:occurences
for i in xrange(0,3):
value = values2[i]
if(not value in values_dict2):
times = values2.count(value)
values_dict2[value] = times
if DEBUG>0: print("-"+coll+"-is "+str(values_dict)+"=="+str(values_dict2)+"?")
are_equivalents = Terna(values[0],values[1],values[2]).equivalente(Terna(values2[0],values2[1],values2[2]))
if(are_equivalents):
if DEBUG>0: print("-"+coll+"- "+str(coll)+" is equal to "+str(coll2)+".. Removing the second!\n")
collection.pop(collection.index(coll2))
print("We've got "+str(len(collection))+" results:")
print(str(collection))
argLen = len(sys.argv)
if(argLen<2 ):
print("Error: excepting a second argument!")
exit()
try:
int(sys.argv[1])
except:
if(float(sys.argv[1])):
print("The result is 0.")
else:
print("Error: excepting a numbeer!")
exit()
if(argLen>2): DEBUG = 1
res = TreNumeri(int(sys.argv[1]))
Scusate se è disordinato e poco elegante ma è fatto di fretta!
Ciao, scusa se ci ho messo un po' ma sono stato impegnato e non volevo rispondere prima di avere un'altra soluzione da proporre.
L'errore dovrebbe essere nel punto in cui rimuovo le terne equivalenti (non uniche), ma direi che l'idea di base sia giusta, no?
In effetti mi hai ben indirizzato per trovare l'errore, non avevo notato che per $n=7$ si ha ['7+0+0', '6+1+0', '5+2+0', '5+1+1', '4+3+0', '4+2+1', '3+3+1', '2+2+3', '1+4+2'] con le tuple evidenziate equivalenti.
Ho dato una sistematina al codice, ed ecco una nuova lista di output:
# n = 0 --> 0
# n = 1 --> 1
# n = 2 --> 2
# n = 3 --> 3
# n = 4 --> 4
# n = 5 --> 5
# n = 6 --> 7
# n = 7 --> 8
# n = 8 --> 10
# n = 9 --> 12
# n = 10 --> 14
# n = 11 --> 16
# n = 12 --> 19
# n = 13 --> 21
# n = 14 --> 24
# n = 15 --> 27
# n = 16 --> 30
# n = 17 --> 33
# n = 18 --> 37
# n = 19 --> 40
# n = 21 --> 48
# n = 177 --> 2700
# n = 180 --> 2791
(se qualcuno fosse interessato anche alla lista dei risultati la chieda o esegua lo script con Python)
Ecco il codice, adesso sicuramente più comprensibile:
#!/usr/bin/python
import sys
import os
DEBUG = 0 # 0 = none, 1 = verbose, 2 = debug
class Terna:
terna = {}
string = ""
def __init__(self, n1,n2,n3):
try:
values = [int(n1),int(n2),int(n3)]
self.string = str(n1)+"+"+str(n2)+"+"+str(n3)
values.sort()
if DEBUG > 1: print(str(values))
values_dict = {}
for i in xrange(0,3):
value = values[i]
if(not value in values_dict):
times = values.count(value)
values_dict[value] = times
self.terna = values_dict
except:
print("Error: worng Terna constructor!")
exit(1)
def equivalentTo(self, AltraTerna):
res = True
for val in self.terna:
try:
if self.terna[val] != AltraTerna.terna[val]:
res = False
except:
res = False
return res
class TreNumeri:
permutations = { "cardinality":0, "set": [ Terna(0,0,0) ] }
unique_perms = { "cardinality":0, "set": [ Terna(0,0,0) ] }
n = 0
def __init__(self, number):
if(number==0):
print("Storing n=0!")
self.n = int(number)
self.permutations = self.getPermutations()
self.unique_perms = self.getDiffTernas()
self.printResponso()
def printResponso(self):
uniqueTernasOutput = ""
temp = 0
for uT in self.unique_perms["set"]:
temp += 1
uniqueTernasOutput += "["+uT.string+"] "
if temp == 5:
temp = 0
uniqueTernasOutput += "\n# "
if DEBUG>0: print("#########################################")
print("# \tn = "+str(self.n)+" --> "+str(self.unique_perms["cardinality"]))
if DEBUG>0:
print("#########################################")
print("# We've found "+str(self.unique_perms["cardinality"])+" unique sets of three positives")
print("# numbers such that their sum is "+str(self.n)+":")
print("#########################################")
print("# "+uniqueTernasOutput)
print("#######################################")
def getPermutations(self):
# Generating and storing all possible permutations of integers such that their sum is self.n
n = self.n
permutations = []
for x in xrange(0,n):
permutations.append( Terna(n-x,x,0) )
for y in xrange(0,x):
permutations.append( Terna(n-x, x-y, y) )
if DEBUG>0:
outPrint = ""
for te in permutations: outPrint += "["+te.string+"] "
print("We've "+str(len(permutations))+" permutations:\n"+outPrint)
return { "cardinality": len(permutations), "set" : permutations }
def getDiffTernas(self):
# Storing a new permutations set and cleaning it from equivalents ternas
res_set = list(self.permutations["set"])
for t1 in self.permutations["set"]:
t1_has_been_checked = False
for t2 in res_set:
if t1.string == t2.string or t1.equivalentTo(t2):
if t1_has_been_checked:
res_set.pop( res_set.index(t2) )
else:
t1_has_been_checked = True
if DEBUG>0:
outPrint = ""
for te in res_set: outPrint += "["+te.string+"] "
print("We've "+str(len(res_set))+" unique permutations:\n"+outPrint)
return { "cardinality": len(res_set), "set" : res_set }
class main:
name = ""
arguments = []
def __init__(self, argv):
self.executeOverUserInput(argv)
def executeOverUserInput(self,argv):
self.evaluateArguments(argv)
res = TreNumeri(self.arguments[0])
def testExecution(self):
for i in xrange(0,20): TreNumeri(i)
for i in xrange(1,3): TreNumeri(21**i)
def evaluateArguments(self,argv):
self.name = argv[0]
if(len(argv)<2):
print("Error: excepting a second argument!")
exit(1)
try:
int(argv[1])
except:
if(float(argv[1])): print("The result is 0.")
else: print("Error: excepting a number as argument!")
exit(1)
self.arguments = argv[1:]
if(len(argv)>2): DEBUG = 1
main(sys.argv)
Le due funzioni "cuore" sono TreNumeri.getPermutations() e TreNumeri.getDiffTernas():
(sono $80$ cifre, erano $100$ ma non me le scrive tutte )
Cordialmente, Alex
Be', diciamo che intanto dipende dalle risorse di calcolo che ho a disposizione; al momento il massimo di cui dispongo sono le circa (se non sbaglio) 25 milioni di operazioni binarie al secondo che mi concede il server dell'università.
Poi, provando ad azzardare un calcolo approssimativo:
a parte le relativamente poche operazioni di inizializzazione, assegnamento e simili, considerando che l'algoritmo prima calcola un numero di combinazioni compreso tra $n^2$ e $n^3$ (spendendo circa $3*n$ (da $3*2^log(n)$) operazioni per ogni terna generata) e dopodiché le confronta una ad una facendo un numero di confronti compreso tra $n^4$ ed $n^9$ (ogni confronto effettua circa $3*n$ (da $3*2^log(n)$) operazioni), per un totale di:
fissati $n^2
$r*3*n+s*3*n$
Quindi detto $C : [(n^3+n^5)*3] < C < [(n^4+n^10)*3]$ - i.e. C compreso tra caso pessimo e caso ottimo - con la possibilità di fare $25*10^6$ calcoli al secondo, e con $n=12345678901234567890123456789012345678901234567890123456789012345678901234567890$, il tempo che ci vorrebbe a calcolarlo, in secondi, è $T$ tale che:
$bot = [(1.88167*10^237)+(2.86797 * 10^395)]*3 = 8.60391 *10^395 [(operazioni)];$
$top = [(2.32305*10^316)+(8.22526 * 10^790)]*3 = 2.46758 *10^791 [(operazioni)];$
$bot
[€dit]: ho notato solo dopo che un modo più semplice per indicare il numero di operazioni necessarie C può essere: $C : [3*n^8 < C < 3*n^14]$
Questo in termini di operazioni nel tempo, significa che avendo la velocità $ lambda = 25*10^6 [(n.operazioni)/(secondi)] $ e dividendo $bot [n.operazioni]$ e $top [n.operazioni]$ per la velocità otteniamo (di tipo $[secondi]*([(operazioni)]/[(operazioni)])$):
$bot = (8.60391 *10^395) / (25*10^6) = 1.14718 * 10^388 [secondi]$
$top = (2.46758 *10^791) / (25*10^6) = 3.29010 * 10^783 [secondi]$
Passando da secondi ad ore:
$bot = (1.14718 * 10^388) / (60^2) = 3.18663 * 10^384$
$top = (3.29010 * 10^783) / (60^2) = 9.13918 * 10^779$
In termini di anni:
$bot = 1.21257 * 10^379$
$top = 3.47761 * 10^774$
$to [1.21257 * 10^379$[anni]$< T < 3.47761 * 10^774 $[anni]$]$
Va da se che, pure se avessi sbagliato qualche calcolo, non ci sarebbe nessun rischio di calcolarlo con questo algoritmo ed il potere di calcolo che ho a disposizione
Va detto però che l'algoritmo: uno non è stato rivisto né è stato progettato per funzionare velocemente, due non solo calcola la cardinalità dell'insieme, ma anche gli elementi che lo compongono
(Ho dovuto scriverlo su tre righe perché non lo prende come numero unico … ... e non dite che ho sparato numeri a caso perché tanto nessuno può controllare )
Comunque, la domanda era solo per avere un'idea di quanto potesse essere grande la differenza tra una formula diretta e un processo iterativo, non avevo altri scopi …
Un'ultima domanda (se posso permettermi): lo hai fatto per divertimento o anche come esercitazione?
"axpgn":Uellà che analisi! … ma sei già laureato o ancora studi?
Studio ancora, non saprei se purtroppo o per fortuna!
"axpgn":Un'ultima domanda (se posso permettermi): lo hai fatto per divertimento o anche come esercitazione?
Certo, direi in primis per divertimento; poi non avendo quasi mai occasione di lavorare con (il semplice) python è anche un modo per non dimenticarne la sintassi ed i vari trucchetti.
Comunque avrei anche un'approssimazione della formula da proporre: risolvendo il sistema tra la generica equazione di una parabola e tre dei punti del grafo della funzione ottenuti dall'algoritmo di cui sopra, ho ottenuto:
$y = (0.0838378279215)x^2 + (0.403228765364)x + 2.07319757843$
(approssimando il risultato all'intero più vicino)
"Erich":Studio ancora, non saprei se purtroppo o per fortuna!
Ho confrontato i risultati della tua funzione con i miei (usando le potenze di dieci da $10^1$ a $10^100$) e già da $10^9$ la differenza percentuale è costante: il rapporto tra la tua e la mia è $1.00605394$
Secondo te per ottenere un risultato più preciso devo scegliere i tre punti del grafo $(n,F(n))$ con $n$ più grandi? O c'è un altro modo per essere più precisi?
Magari non è che potresti inviarmi la soluzione esatta in privato?
Rispondi
Per rispondere a questa discussione devi prima effettuare il login.
Ciao! Sono il tuo Tutor AI, il compagno ideale per uno studio interattivo. Utilizzo il metodo maieutico per affinare il tuo ragionamento e la comprensione. Insieme possiamo:
Risolvere un problema di matematica
Riassumere un testo
Tradurre una frase
E molto altro ancora...
Cosa vuoi imparare oggi?
Il Tutor AI di Skuola.net usa un modello AI di Chat GPT.
Per termini, condizioni e privacy, visita la relativa pagina.
(qui la prima)
ho sbagliato qualcosa nei conti 
intanto ci ragiono ancora 
... ho pure fatto in tempo a notare che avevi scritto "per $n=6$" 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo