|
|
|
|
iBac = materialul ULTRACOMPLET de pregătire pentru bac la mate. Dacă vrei poţi.
|
|
 |
|
 |
[1]
| Autor |
Mesaj |
|
|
Sunt curios daca exista un algoritm pentru determinarea numarului de solu?ii naturale pentru o ecua?ie diofantica, presupunând c? to?i coeficien?ii sunt pozitivi? Concret - pentru ecua?ia a+2b+4c+10d+20e=42, respectiv a+2b+4c+10d+20e=12, se cere numarul de solu?ii. Problema era formulata astfel:"Avem la dispozi?ie bancnote de 5?, 10?, 20?, 50?, 100?.
a) În câte moduri putem pl?ti 210? ?
b) Dar 60? ?"
Banuiesc c? solu?iile se pot determina relativ u?or cu ajutorul unui calculator ?i un program informatic, îns? problema am gasit-o într-un concurs local ce se adresa elevilor clasei a III-a. Mentionez ca am incercat sa scriu in excel solutiile, am gasit vreo 226 dar ma tem ca am ratat din ele (pentru prima ecuatie).
|
|
|
[Citat]
Sunt curios daca exista un algoritm pentru determinarea numarului de solu?ii naturale pentru o ecua?ie diofantica, presupunând c? to?i coeficien?ii sunt pozitivi.
Concret - pentru ecua?ia
a + 2b + 4c + 10d + 20e = 42 , respectiv
a + 2b + 4c + 10d + 20e = 12 ,
se cere numarul de solu?ii
cu a,b,c,d,e numere naturale. (Neaparat nenule?)
Problema era formulata astfel:
"Avem la dispozi?ie bancnote de 5?, 10?, 20?, 50?, 100?.
a) În câte moduri putem pl?ti 210? ?
b) Dar 60? ?"
Banuiesc c? solu?iile se pot determina relativ u?or cu ajutorul unui calculator ?i un program informatic, îns? problema am gasit-o într-un concurs local ce se adresa elevilor clasei a III-a. Mentionez ca am incercat sa scriu in excel solutiile, am gasit vreo 226 dar ma tem ca am ratat din ele (pentru prima ecuatie). |
Nota: 0 nu este nici pozitiv, nici negativ in unele carti...
Este motivul pentru care s-au introdus numerele "nenegative".
Cel mai bine este sa se spuna explicit in cuvinte "numar natural" sau "numar intreg mai mare sau egal cu zero".
O sa-l consider si pe zero, deoarece cand platesc ceva nu trebuie sa am toate bancnotele la mine.
Da, un algoritm exista, deoarece
a,b,c,d,e se afla in multimile finite de numere naturale de la 0 la 1000 (ca sa fiu sigur), deci avem un numar finit de cazuri de inspectat. Inspectam si am terminat.
Programarea este usoara.
In python de exemplu: COD
# solutii ale ecuatiei a + 2b + 4c + 10d + 20e = 42
count = 0
for a in range(0,42+1):
for b in range(0,42/2+1):
for c in range(0,42/4+1):
for d in range(0,42/10+1):
for e in range(0,42/20+1):
if a + 2*b + 4*c + 10*d + 20*e == 42:
count += 1
print "Solutia %3d :: %d + 2*%d + 4*%d + 10*%d + 20*%d " % (count, a,b,c,d,e)
(In python conteaza spatiile goale, dar acest html mi le mananca, rog a se da un [Citeaza] pentru a avea acces la cod cu spatii cu tot...)
Rezultate...
Solutia 1 :: 0 + 2*0 + 4*3 + 10*1 + 20*1
Solutia 2 :: 0 + 2*0 + 4*3 + 10*3 + 20*0
Solutia 3 :: 0 + 2*0 + 4*8 + 10*1 + 20*0
Solutia 4 :: 0 + 2*1 + 4*0 + 10*0 + 20*2
Solutia 5 :: 0 + 2*1 + 4*0 + 10*2 + 20*1
Solutia 6 :: 0 + 2*1 + 4*0 + 10*4 + 20*0
Solutia 7 :: 0 + 2*1 + 4*5 + 10*0 + 20*1
Solutia 8 :: 0 + 2*1 + 4*5 + 10*2 + 20*0
Solutia 9 :: 0 + 2*1 + 4*10 + 10*0 + 20*0
Solutia 10 :: 0 + 2*2 + 4*2 + 10*1 + 20*1
Solutia 11 :: 0 + 2*2 + 4*2 + 10*3 + 20*0
Solutia 12 :: 0 + 2*2 + 4*7 + 10*1 + 20*0
Solutia 13 :: 0 + 2*3 + 4*4 + 10*0 + 20*1
Solutia 14 :: 0 + 2*3 + 4*4 + 10*2 + 20*0
Solutia 15 :: 0 + 2*3 + 4*9 + 10*0 + 20*0
Solutia 16 :: 0 + 2*4 + 4*1 + 10*1 + 20*1
Solutia 17 :: 0 + 2*4 + 4*1 + 10*3 + 20*0
Solutia 18 :: 0 + 2*4 + 4*6 + 10*1 + 20*0
Solutia 19 :: 0 + 2*5 + 4*3 + 10*0 + 20*1
Solutia 20 :: 0 + 2*5 + 4*3 + 10*2 + 20*0
Solutia 21 :: 0 + 2*5 + 4*8 + 10*0 + 20*0
Solutia 22 :: 0 + 2*6 + 4*0 + 10*1 + 20*1
Solutia 23 :: 0 + 2*6 + 4*0 + 10*3 + 20*0
Solutia 24 :: 0 + 2*6 + 4*5 + 10*1 + 20*0
Solutia 25 :: 0 + 2*7 + 4*2 + 10*0 + 20*1
Solutia 26 :: 0 + 2*7 + 4*2 + 10*2 + 20*0
Solutia 27 :: 0 + 2*7 + 4*7 + 10*0 + 20*0
Solutia 28 :: 0 + 2*8 + 4*4 + 10*1 + 20*0
Solutia 29 :: 0 + 2*9 + 4*1 + 10*0 + 20*1
Solutia 30 :: 0 + 2*9 + 4*1 + 10*2 + 20*0
Solutia 31 :: 0 + 2*9 + 4*6 + 10*0 + 20*0
Solutia 32 :: 0 + 2*10 + 4*3 + 10*1 + 20*0
Solutia 33 :: 0 + 2*11 + 4*0 + 10*0 + 20*1
Solutia 34 :: 0 + 2*11 + 4*0 + 10*2 + 20*0
Solutia 35 :: 0 + 2*11 + 4*5 + 10*0 + 20*0
Solutia 36 :: 0 + 2*12 + 4*2 + 10*1 + 20*0
Solutia 37 :: 0 + 2*13 + 4*4 + 10*0 + 20*0
Solutia 38 :: 0 + 2*14 + 4*1 + 10*1 + 20*0
Solutia 39 :: 0 + 2*15 + 4*3 + 10*0 + 20*0
Solutia 40 :: 0 + 2*16 + 4*0 + 10*1 + 20*0
Solutia 41 :: 0 + 2*17 + 4*2 + 10*0 + 20*0
Solutia 42 :: 0 + 2*19 + 4*1 + 10*0 + 20*0
Solutia 43 :: 0 + 2*21 + 4*0 + 10*0 + 20*0
Solutia 44 :: 2 + 2*0 + 4*0 + 10*0 + 20*2
Solutia 45 :: 2 + 2*0 + 4*0 + 10*2 + 20*1
Solutia 46 :: 2 + 2*0 + 4*0 + 10*4 + 20*0
Solutia 47 :: 2 + 2*0 + 4*5 + 10*0 + 20*1
Solutia 48 :: 2 + 2*0 + 4*5 + 10*2 + 20*0
Solutia 49 :: 2 + 2*0 + 4*10 + 10*0 + 20*0
Solutia 50 :: 2 + 2*1 + 4*2 + 10*1 + 20*1
Solutia 51 :: 2 + 2*1 + 4*2 + 10*3 + 20*0
Solutia 52 :: 2 + 2*1 + 4*7 + 10*1 + 20*0
Solutia 53 :: 2 + 2*2 + 4*4 + 10*0 + 20*1
Solutia 54 :: 2 + 2*2 + 4*4 + 10*2 + 20*0
Solutia 55 :: 2 + 2*2 + 4*9 + 10*0 + 20*0
Solutia 56 :: 2 + 2*3 + 4*1 + 10*1 + 20*1
Solutia 57 :: 2 + 2*3 + 4*1 + 10*3 + 20*0
Solutia 58 :: 2 + 2*3 + 4*6 + 10*1 + 20*0
Solutia 59 :: 2 + 2*4 + 4*3 + 10*0 + 20*1
Solutia 60 :: 2 + 2*4 + 4*3 + 10*2 + 20*0
Solutia 61 :: 2 + 2*4 + 4*8 + 10*0 + 20*0
Solutia 62 :: 2 + 2*5 + 4*0 + 10*1 + 20*1
Solutia 63 :: 2 + 2*5 + 4*0 + 10*3 + 20*0
Solutia 64 :: 2 + 2*5 + 4*5 + 10*1 + 20*0
Solutia 65 :: 2 + 2*6 + 4*2 + 10*0 + 20*1
Solutia 66 :: 2 + 2*6 + 4*2 + 10*2 + 20*0
Solutia 67 :: 2 + 2*6 + 4*7 + 10*0 + 20*0
Solutia 68 :: 2 + 2*7 + 4*4 + 10*1 + 20*0
Solutia 69 :: 2 + 2*8 + 4*1 + 10*0 + 20*1
Solutia 70 :: 2 + 2*8 + 4*1 + 10*2 + 20*0
Solutia 71 :: 2 + 2*8 + 4*6 + 10*0 + 20*0
Solutia 72 :: 2 + 2*9 + 4*3 + 10*1 + 20*0
Solutia 73 :: 2 + 2*10 + 4*0 + 10*0 + 20*1
Solutia 74 :: 2 + 2*10 + 4*0 + 10*2 + 20*0
Solutia 75 :: 2 + 2*10 + 4*5 + 10*0 + 20*0
Solutia 76 :: 2 + 2*11 + 4*2 + 10*1 + 20*0
Solutia 77 :: 2 + 2*12 + 4*4 + 10*0 + 20*0
Solutia 78 :: 2 + 2*13 + 4*1 + 10*1 + 20*0
Solutia 79 :: 2 + 2*14 + 4*3 + 10*0 + 20*0
Solutia 80 :: 2 + 2*15 + 4*0 + 10*1 + 20*0
Solutia 81 :: 2 + 2*16 + 4*2 + 10*0 + 20*0
Solutia 82 :: 2 + 2*18 + 4*1 + 10*0 + 20*0
Solutia 83 :: 2 + 2*20 + 4*0 + 10*0 + 20*0
Solutia 84 :: 4 + 2*0 + 4*2 + 10*1 + 20*1
Solutia 85 :: 4 + 2*0 + 4*2 + 10*3 + 20*0
Solutia 86 :: 4 + 2*0 + 4*7 + 10*1 + 20*0
Solutia 87 :: 4 + 2*1 + 4*4 + 10*0 + 20*1
Solutia 88 :: 4 + 2*1 + 4*4 + 10*2 + 20*0
Solutia 89 :: 4 + 2*1 + 4*9 + 10*0 + 20*0
Solutia 90 :: 4 + 2*2 + 4*1 + 10*1 + 20*1
Solutia 91 :: 4 + 2*2 + 4*1 + 10*3 + 20*0
Solutia 92 :: 4 + 2*2 + 4*6 + 10*1 + 20*0
Solutia 93 :: 4 + 2*3 + 4*3 + 10*0 + 20*1
Solutia 94 :: 4 + 2*3 + 4*3 + 10*2 + 20*0
Solutia 95 :: 4 + 2*3 + 4*8 + 10*0 + 20*0
Solutia 96 :: 4 + 2*4 + 4*0 + 10*1 + 20*1
Solutia 97 :: 4 + 2*4 + 4*0 + 10*3 + 20*0
Solutia 98 :: 4 + 2*4 + 4*5 + 10*1 + 20*0
Solutia 99 :: 4 + 2*5 + 4*2 + 10*0 + 20*1
Solutia 100 :: 4 + 2*5 + 4*2 + 10*2 + 20*0
Solutia 101 :: 4 + 2*5 + 4*7 + 10*0 + 20*0
Solutia 102 :: 4 + 2*6 + 4*4 + 10*1 + 20*0
Solutia 103 :: 4 + 2*7 + 4*1 + 10*0 + 20*1
Solutia 104 :: 4 + 2*7 + 4*1 + 10*2 + 20*0
Solutia 105 :: 4 + 2*7 + 4*6 + 10*0 + 20*0
Solutia 106 :: 4 + 2*8 + 4*3 + 10*1 + 20*0
Solutia 107 :: 4 + 2*9 + 4*0 + 10*0 + 20*1
Solutia 108 :: 4 + 2*9 + 4*0 + 10*2 + 20*0
Solutia 109 :: 4 + 2*9 + 4*5 + 10*0 + 20*0
Solutia 110 :: 4 + 2*10 + 4*2 + 10*1 + 20*0
Solutia 111 :: 4 + 2*11 + 4*4 + 10*0 + 20*0
Solutia 112 :: 4 + 2*12 + 4*1 + 10*1 + 20*0
Solutia 113 :: 4 + 2*13 + 4*3 + 10*0 + 20*0
Solutia 114 :: 4 + 2*14 + 4*0 + 10*1 + 20*0
Solutia 115 :: 4 + 2*15 + 4*2 + 10*0 + 20*0
Solutia 116 :: 4 + 2*17 + 4*1 + 10*0 + 20*0
Solutia 117 :: 4 + 2*19 + 4*0 + 10*0 + 20*0
Solutia 118 :: 6 + 2*0 + 4*4 + 10*0 + 20*1
Solutia 119 :: 6 + 2*0 + 4*4 + 10*2 + 20*0
Solutia 120 :: 6 + 2*0 + 4*9 + 10*0 + 20*0
Solutia 121 :: 6 + 2*1 + 4*1 + 10*1 + 20*1
Solutia 122 :: 6 + 2*1 + 4*1 + 10*3 + 20*0
Solutia 123 :: 6 + 2*1 + 4*6 + 10*1 + 20*0
Solutia 124 :: 6 + 2*2 + 4*3 + 10*0 + 20*1
Solutia 125 :: 6 + 2*2 + 4*3 + 10*2 + 20*0
Solutia 126 :: 6 + 2*2 + 4*8 + 10*0 + 20*0
Solutia 127 :: 6 + 2*3 + 4*0 + 10*1 + 20*1
Solutia 128 :: 6 + 2*3 + 4*0 + 10*3 + 20*0
Solutia 129 :: 6 + 2*3 + 4*5 + 10*1 + 20*0
Solutia 130 :: 6 + 2*4 + 4*2 + 10*0 + 20*1
Solutia 131 :: 6 + 2*4 + 4*2 + 10*2 + 20*0
Solutia 132 :: 6 + 2*4 + 4*7 + 10*0 + 20*0
Solutia 133 :: 6 + 2*5 + 4*4 + 10*1 + 20*0
Solutia 134 :: 6 + 2*6 + 4*1 + 10*0 + 20*1
Solutia 135 :: 6 + 2*6 + 4*1 + 10*2 + 20*0
Solutia 136 :: 6 + 2*6 + 4*6 + 10*0 + 20*0
Solutia 137 :: 6 + 2*7 + 4*3 + 10*1 + 20*0
Solutia 138 :: 6 + 2*8 + 4*0 + 10*0 + 20*1
Solutia 139 :: 6 + 2*8 + 4*0 + 10*2 + 20*0
Solutia 140 :: 6 + 2*8 + 4*5 + 10*0 + 20*0
Solutia 141 :: 6 + 2*9 + 4*2 + 10*1 + 20*0
Solutia 142 :: 6 + 2*10 + 4*4 + 10*0 + 20*0
Solutia 143 :: 6 + 2*11 + 4*1 + 10*1 + 20*0
Solutia 144 :: 6 + 2*12 + 4*3 + 10*0 + 20*0
Solutia 145 :: 6 + 2*13 + 4*0 + 10*1 + 20*0
Solutia 146 :: 6 + 2*14 + 4*2 + 10*0 + 20*0
Solutia 147 :: 6 + 2*16 + 4*1 + 10*0 + 20*0
Solutia 148 :: 6 + 2*18 + 4*0 + 10*0 + 20*0
Solutia 149 :: 8 + 2*0 + 4*1 + 10*1 + 20*1
Solutia 150 :: 8 + 2*0 + 4*1 + 10*3 + 20*0
Solutia 151 :: 8 + 2*0 + 4*6 + 10*1 + 20*0
Solutia 152 :: 8 + 2*1 + 4*3 + 10*0 + 20*1
Solutia 153 :: 8 + 2*1 + 4*3 + 10*2 + 20*0
Solutia 154 :: 8 + 2*1 + 4*8 + 10*0 + 20*0
Solutia 155 :: 8 + 2*2 + 4*0 + 10*1 + 20*1
Solutia 156 :: 8 + 2*2 + 4*0 + 10*3 + 20*0
Solutia 157 :: 8 + 2*2 + 4*5 + 10*1 + 20*0
Solutia 158 :: 8 + 2*3 + 4*2 + 10*0 + 20*1
Solutia 159 :: 8 + 2*3 + 4*2 + 10*2 + 20*0
Solutia 160 :: 8 + 2*3 + 4*7 + 10*0 + 20*0
Solutia 161 :: 8 + 2*4 + 4*4 + 10*1 + 20*0
Solutia 162 :: 8 + 2*5 + 4*1 + 10*0 + 20*1
Solutia 163 :: 8 + 2*5 + 4*1 + 10*2 + 20*0
Solutia 164 :: 8 + 2*5 + 4*6 + 10*0 + 20*0
Solutia 165 :: 8 + 2*6 + 4*3 + 10*1 + 20*0
Solutia 166 :: 8 + 2*7 + 4*0 + 10*0 + 20*1
Solutia 167 :: 8 + 2*7 + 4*0 + 10*2 + 20*0
Solutia 168 :: 8 + 2*7 + 4*5 + 10*0 + 20*0
Solutia 169 :: 8 + 2*8 + 4*2 + 10*1 + 20*0
Solutia 170 :: 8 + 2*9 + 4*4 + 10*0 + 20*0
Solutia 171 :: 8 + 2*10 + 4*1 + 10*1 + 20*0
Solutia 172 :: 8 + 2*11 + 4*3 + 10*0 + 20*0
Solutia 173 :: 8 + 2*12 + 4*0 + 10*1 + 20*0
Solutia 174 :: 8 + 2*13 + 4*2 + 10*0 + 20*0
Solutia 175 :: 8 + 2*15 + 4*1 + 10*0 + 20*0
Solutia 176 :: 8 + 2*17 + 4*0 + 10*0 + 20*0
Solutia 177 :: 10 + 2*0 + 4*3 + 10*0 + 20*1
Solutia 178 :: 10 + 2*0 + 4*3 + 10*2 + 20*0
Solutia 179 :: 10 + 2*0 + 4*8 + 10*0 + 20*0
Solutia 180 :: 10 + 2*1 + 4*0 + 10*1 + 20*1
Solutia 181 :: 10 + 2*1 + 4*0 + 10*3 + 20*0
Solutia 182 :: 10 + 2*1 + 4*5 + 10*1 + 20*0
Solutia 183 :: 10 + 2*2 + 4*2 + 10*0 + 20*1
Solutia 184 :: 10 + 2*2 + 4*2 + 10*2 + 20*0
Solutia 185 :: 10 + 2*2 + 4*7 + 10*0 + 20*0
Solutia 186 :: 10 + 2*3 + 4*4 + 10*1 + 20*0
Solutia 187 :: 10 + 2*4 + 4*1 + 10*0 + 20*1
Solutia 188 :: 10 + 2*4 + 4*1 + 10*2 + 20*0
Solutia 189 :: 10 + 2*4 + 4*6 + 10*0 + 20*0
Solutia 190 :: 10 + 2*5 + 4*3 + 10*1 + 20*0
Solutia 191 :: 10 + 2*6 + 4*0 + 10*0 + 20*1
Solutia 192 :: 10 + 2*6 + 4*0 + 10*2 + 20*0
Solutia 193 :: 10 + 2*6 + 4*5 + 10*0 + 20*0
Solutia 194 :: 10 + 2*7 + 4*2 + 10*1 + 20*0
Solutia 195 :: 10 + 2*8 + 4*4 + 10*0 + 20*0
Solutia 196 :: 10 + 2*9 + 4*1 + 10*1 + 20*0
Solutia 197 :: 10 + 2*10 + 4*3 + 10*0 + 20*0
Solutia 198 :: 10 + 2*11 + 4*0 + 10*1 + 20*0
Solutia 199 :: 10 + 2*12 + 4*2 + 10*0 + 20*0
Solutia 200 :: 10 + 2*14 + 4*1 + 10*0 + 20*0
Solutia 201 :: 10 + 2*16 + 4*0 + 10*0 + 20*0
Solutia 202 :: 12 + 2*0 + 4*0 + 10*1 + 20*1
Solutia 203 :: 12 + 2*0 + 4*0 + 10*3 + 20*0
Solutia 204 :: 12 + 2*0 + 4*5 + 10*1 + 20*0
Solutia 205 :: 12 + 2*1 + 4*2 + 10*0 + 20*1
Solutia 206 :: 12 + 2*1 + 4*2 + 10*2 + 20*0
Solutia 207 :: 12 + 2*1 + 4*7 + 10*0 + 20*0
Solutia 208 :: 12 + 2*2 + 4*4 + 10*1 + 20*0
Solutia 209 :: 12 + 2*3 + 4*1 + 10*0 + 20*1
Solutia 210 :: 12 + 2*3 + 4*1 + 10*2 + 20*0
Solutia 211 :: 12 + 2*3 + 4*6 + 10*0 + 20*0
Solutia 212 :: 12 + 2*4 + 4*3 + 10*1 + 20*0
Solutia 213 :: 12 + 2*5 + 4*0 + 10*0 + 20*1
Solutia 214 :: 12 + 2*5 + 4*0 + 10*2 + 20*0
Solutia 215 :: 12 + 2*5 + 4*5 + 10*0 + 20*0
Solutia 216 :: 12 + 2*6 + 4*2 + 10*1 + 20*0
Solutia 217 :: 12 + 2*7 + 4*4 + 10*0 + 20*0
Solutia 218 :: 12 + 2*8 + 4*1 + 10*1 + 20*0
Solutia 219 :: 12 + 2*9 + 4*3 + 10*0 + 20*0
Solutia 220 :: 12 + 2*10 + 4*0 + 10*1 + 20*0
Solutia 221 :: 12 + 2*11 + 4*2 + 10*0 + 20*0
Solutia 222 :: 12 + 2*13 + 4*1 + 10*0 + 20*0
Solutia 223 :: 12 + 2*15 + 4*0 + 10*0 + 20*0
Solutia 224 :: 14 + 2*0 + 4*2 + 10*0 + 20*1
Solutia 225 :: 14 + 2*0 + 4*2 + 10*2 + 20*0
Solutia 226 :: 14 + 2*0 + 4*7 + 10*0 + 20*0
Solutia 227 :: 14 + 2*1 + 4*4 + 10*1 + 20*0
Solutia 228 :: 14 + 2*2 + 4*1 + 10*0 + 20*1
Solutia 229 :: 14 + 2*2 + 4*1 + 10*2 + 20*0
Solutia 230 :: 14 + 2*2 + 4*6 + 10*0 + 20*0
Solutia 231 :: 14 + 2*3 + 4*3 + 10*1 + 20*0
Solutia 232 :: 14 + 2*4 + 4*0 + 10*0 + 20*1
Solutia 233 :: 14 + 2*4 + 4*0 + 10*2 + 20*0
Solutia 234 :: 14 + 2*4 + 4*5 + 10*0 + 20*0
Solutia 235 :: 14 + 2*5 + 4*2 + 10*1 + 20*0
Solutia 236 :: 14 + 2*6 + 4*4 + 10*0 + 20*0
Solutia 237 :: 14 + 2*7 + 4*1 + 10*1 + 20*0
Solutia 238 :: 14 + 2*8 + 4*3 + 10*0 + 20*0
Solutia 239 :: 14 + 2*9 + 4*0 + 10*1 + 20*0
Solutia 240 :: 14 + 2*10 + 4*2 + 10*0 + 20*0
Solutia 241 :: 14 + 2*12 + 4*1 + 10*0 + 20*0
Solutia 242 :: 14 + 2*14 + 4*0 + 10*0 + 20*0
Solutia 243 :: 16 + 2*0 + 4*4 + 10*1 + 20*0
Solutia 244 :: 16 + 2*1 + 4*1 + 10*0 + 20*1
Solutia 245 :: 16 + 2*1 + 4*1 + 10*2 + 20*0
Solutia 246 :: 16 + 2*1 + 4*6 + 10*0 + 20*0
Solutia 247 :: 16 + 2*2 + 4*3 + 10*1 + 20*0
Solutia 248 :: 16 + 2*3 + 4*0 + 10*0 + 20*1
Solutia 249 :: 16 + 2*3 + 4*0 + 10*2 + 20*0
Solutia 250 :: 16 + 2*3 + 4*5 + 10*0 + 20*0
Solutia 251 :: 16 + 2*4 + 4*2 + 10*1 + 20*0
Solutia 252 :: 16 + 2*5 + 4*4 + 10*0 + 20*0
Solutia 253 :: 16 + 2*6 + 4*1 + 10*1 + 20*0
Solutia 254 :: 16 + 2*7 + 4*3 + 10*0 + 20*0
Solutia 255 :: 16 + 2*8 + 4*0 + 10*1 + 20*0
Solutia 256 :: 16 + 2*9 + 4*2 + 10*0 + 20*0
Solutia 257 :: 16 + 2*11 + 4*1 + 10*0 + 20*0
Solutia 258 :: 16 + 2*13 + 4*0 + 10*0 + 20*0
Solutia 259 :: 18 + 2*0 + 4*1 + 10*0 + 20*1
Solutia 260 :: 18 + 2*0 + 4*1 + 10*2 + 20*0
Solutia 261 :: 18 + 2*0 + 4*6 + 10*0 + 20*0
Solutia 262 :: 18 + 2*1 + 4*3 + 10*1 + 20*0
Solutia 263 :: 18 + 2*2 + 4*0 + 10*0 + 20*1
Solutia 264 :: 18 + 2*2 + 4*0 + 10*2 + 20*0
Solutia 265 :: 18 + 2*2 + 4*5 + 10*0 + 20*0
Solutia 266 :: 18 + 2*3 + 4*2 + 10*1 + 20*0
Solutia 267 :: 18 + 2*4 + 4*4 + 10*0 + 20*0
Solutia 268 :: 18 + 2*5 + 4*1 + 10*1 + 20*0
Solutia 269 :: 18 + 2*6 + 4*3 + 10*0 + 20*0
Solutia 270 :: 18 + 2*7 + 4*0 + 10*1 + 20*0
Solutia 271 :: 18 + 2*8 + 4*2 + 10*0 + 20*0
Solutia 272 :: 18 + 2*10 + 4*1 + 10*0 + 20*0
Solutia 273 :: 18 + 2*12 + 4*0 + 10*0 + 20*0
Solutia 274 :: 20 + 2*0 + 4*3 + 10*1 + 20*0
Solutia 275 :: 20 + 2*1 + 4*0 + 10*0 + 20*1
Solutia 276 :: 20 + 2*1 + 4*0 + 10*2 + 20*0
Solutia 277 :: 20 + 2*1 + 4*5 + 10*0 + 20*0
Solutia 278 :: 20 + 2*2 + 4*2 + 10*1 + 20*0
Solutia 279 :: 20 + 2*3 + 4*4 + 10*0 + 20*0
Solutia 280 :: 20 + 2*4 + 4*1 + 10*1 + 20*0
Solutia 281 :: 20 + 2*5 + 4*3 + 10*0 + 20*0
Solutia 282 :: 20 + 2*6 + 4*0 + 10*1 + 20*0
Solutia 283 :: 20 + 2*7 + 4*2 + 10*0 + 20*0
Solutia 284 :: 20 + 2*9 + 4*1 + 10*0 + 20*0
Solutia 285 :: 20 + 2*11 + 4*0 + 10*0 + 20*0
Solutia 286 :: 22 + 2*0 + 4*0 + 10*0 + 20*1
Solutia 287 :: 22 + 2*0 + 4*0 + 10*2 + 20*0
Solutia 288 :: 22 + 2*0 + 4*5 + 10*0 + 20*0
Solutia 289 :: 22 + 2*1 + 4*2 + 10*1 + 20*0
Solutia 290 :: 22 + 2*2 + 4*4 + 10*0 + 20*0
Solutia 291 :: 22 + 2*3 + 4*1 + 10*1 + 20*0
Solutia 292 :: 22 + 2*4 + 4*3 + 10*0 + 20*0
Solutia 293 :: 22 + 2*5 + 4*0 + 10*1 + 20*0
Solutia 294 :: 22 + 2*6 + 4*2 + 10*0 + 20*0
Solutia 295 :: 22 + 2*8 + 4*1 + 10*0 + 20*0
Solutia 296 :: 22 + 2*10 + 4*0 + 10*0 + 20*0
Solutia 297 :: 24 + 2*0 + 4*2 + 10*1 + 20*0
Solutia 298 :: 24 + 2*1 + 4*4 + 10*0 + 20*0
Solutia 299 :: 24 + 2*2 + 4*1 + 10*1 + 20*0
Solutia 300 :: 24 + 2*3 + 4*3 + 10*0 + 20*0
Solutia 301 :: 24 + 2*4 + 4*0 + 10*1 + 20*0
Solutia 302 :: 24 + 2*5 + 4*2 + 10*0 + 20*0
Solutia 303 :: 24 + 2*7 + 4*1 + 10*0 + 20*0
Solutia 304 :: 24 + 2*9 + 4*0 + 10*0 + 20*0
Solutia 305 :: 26 + 2*0 + 4*4 + 10*0 + 20*0
Solutia 306 :: 26 + 2*1 + 4*1 + 10*1 + 20*0
Solutia 307 :: 26 + 2*2 + 4*3 + 10*0 + 20*0
Solutia 308 :: 26 + 2*3 + 4*0 + 10*1 + 20*0
Solutia 309 :: 26 + 2*4 + 4*2 + 10*0 + 20*0
Solutia 310 :: 26 + 2*6 + 4*1 + 10*0 + 20*0
Solutia 311 :: 26 + 2*8 + 4*0 + 10*0 + 20*0
Solutia 312 :: 28 + 2*0 + 4*1 + 10*1 + 20*0
Solutia 313 :: 28 + 2*1 + 4*3 + 10*0 + 20*0
Solutia 314 :: 28 + 2*2 + 4*0 + 10*1 + 20*0
Solutia 315 :: 28 + 2*3 + 4*2 + 10*0 + 20*0
Solutia 316 :: 28 + 2*5 + 4*1 + 10*0 + 20*0
Solutia 317 :: 28 + 2*7 + 4*0 + 10*0 + 20*0
Solutia 318 :: 30 + 2*0 + 4*3 + 10*0 + 20*0
Solutia 319 :: 30 + 2*1 + 4*0 + 10*1 + 20*0
Solutia 320 :: 30 + 2*2 + 4*2 + 10*0 + 20*0
Solutia 321 :: 30 + 2*4 + 4*1 + 10*0 + 20*0
Solutia 322 :: 30 + 2*6 + 4*0 + 10*0 + 20*0
Solutia 323 :: 32 + 2*0 + 4*0 + 10*1 + 20*0
Solutia 324 :: 32 + 2*1 + 4*2 + 10*0 + 20*0
Solutia 325 :: 32 + 2*3 + 4*1 + 10*0 + 20*0
Solutia 326 :: 32 + 2*5 + 4*0 + 10*0 + 20*0
Solutia 327 :: 34 + 2*0 + 4*2 + 10*0 + 20*0
Solutia 328 :: 34 + 2*2 + 4*1 + 10*0 + 20*0
Solutia 329 :: 34 + 2*4 + 4*0 + 10*0 + 20*0
Solutia 330 :: 36 + 2*1 + 4*1 + 10*0 + 20*0
Solutia 331 :: 36 + 2*3 + 4*0 + 10*0 + 20*0
Solutia 332 :: 38 + 2*0 + 4*1 + 10*0 + 20*0
Solutia 333 :: 38 + 2*2 + 4*0 + 10*0 + 20*0
Solutia 334 :: 40 + 2*1 + 4*0 + 10*0 + 20*0
Solutia 335 :: 42 + 2*0 + 4*0 + 10*0 + 20*0
Alternativ, folosind polinoame...
(19:16) gp > p(x,N) = sum(k=0,N, x^k)
(19:16) gp > pp(x,N,k) = p(x^k, N/k)
(19:16) gp > q = pp(x,42,1) * pp(x,42,2) * pp(x,42,4) * pp(x,42,10) * pp(x,42,20) q explicit...
%14 = x^204 + x^203 + 2*x^202 + 2*x^201 + 4*x^200 + 4*x^199 + 6*x^198 + 6*x^197 + 9*x^196 + 9*x^195 + 13*x^194 + 13*x^193 + 18*x^192 + 18*x^191 + 24*x^190 + 24*
50*x^183 + 62*x^182 + 62*x^181 + 77*x^180 + 77*x^179 + 93*x^178 + 93*x^177 + 112*x^176 + 112*x^175 + 134*x^174 + 134*x^173 + 159*x^172 + 159*x^171 + 187*x^170
292*x^164 + 292*x^163 + 335*x^162 + 334*x^161 + 381*x^160 + 380*x^159 + 430*x^158 + 428*x^157 + 482*x^156 + 480*x^155 + 539*x^154 + 536*x^153 + 599*x^152 + 595*
146 + 786*x^145 + 865*x^144 + 857*x^143 + 939*x^142 + 928*x^141 + 1012*x^140 + 1000*x^139 + 1087*x^138 + 1072*x^137 + 1161*x^136 + 1145*x^135 + 1238*x^134 + 121
1459*x^128 + 1431*x^127 + 1528*x^126 + 1497*x^125 + 1597*x^124 + 1563*x^123 + 1663*x^122 + 1623*x^121 + 1720*x^120 + 1677*x^119 + 1774*x^118 + 1727*x^117 + 1822
847*x^111 + 1936*x^110 + 1873*x^109 + 1960*x^108 + 1894*x^107 + 1978*x^106 + 1908*x^105 + 1990*x^104 + 1917*x^103 + 1996*x^102 + 1917*x^101 + 1990*x^100 + 1908*
94 + 1847*x^93 + 1906*x^92 + 1813*x^91 + 1867*x^90 + 1772*x^89 + 1822*x^88 + 1727*x^87 + 1774*x^86 + 1677*x^85 + 1720*x^84 + 1623*x^83 + 1663*x^82 + 1563*x^81 +
362*x^75 + 1387*x^74 + 1292*x^73 + 1314*x^72 + 1219*x^71 + 1238*x^70 + 1145*x^69 + 1161*x^68 + 1072*x^67 + 1087*x^66 + 1000*x^65 + 1012*x^64 + 928*x^63 + 939*x^
6*x^56 + 656*x^55 + 661*x^54 + 595*x^53 + 599*x^52 + 536*x^51 + 539*x^50 + 480*x^49 + 482*x^48 + 428*x^47 + 430*x^46 + 380*x^45 + 381*x^44 + 334*x^43 + 335*x^42
x^36 + 187*x^35 + 187*x^34 + 159*x^33 + 159*x^32 + 134*x^31 + 134*x^30 + 112*x^29 + 112*x^28 + 93*x^27 + 93*x^26 + 77*x^25 + 77*x^24 + 62*x^23 + 62*x^22 + 50*x^
+ 24*x^14 + 18*x^13 + 18*x^12 + 13*x^11 + 13*x^10 + 9*x^9 + 9*x^8 + 6*x^7 + 6*x^6 + 4*x^5 + 4*x^4 + 2*x^3 + 2*x^2 + x + 1
(19:16) gp > polcoeff( q, 42, x )
%15 = 335
(19:16) gp > polcoeff( q, 12, x )
%16 = 18
(19:18) gp >
---
df (gauss)
|
|
|
Problema nu este una de clasa a III-a, decat daca se incearca asiduu inca de pe clasa a III-a sa se departeze elevii de matematica.
Motivul este simplu. Un elev de clasa a III-a nu are maturitatea matematica, disciplina de cautare si instrumentele necesare sa rezolve asa ceva. Nici macar primul pas, acel de trecere de la 210 la 42 nu este de clasa a III-a.
Singurul lucru pe care l-as fi facut eu pe clasa a III-a ar fi fost sa iau un caiet cu inca zece foi libere de hartie si sa incerc, mai intai cu zero bancnote mari (de 20), apoi cu o bancnota mare, cu doua, ...
Nu as fi invatat nimic util in viata. Nici macar sa adun si sa inmultesc, deoarece nu ma pot concentra asupra adunarii si inmultirii.
---
df (gauss)
|
|
|
Foarte frumos codul in Python, parca ati zis. Scurt si la obiect, dar oare cat i-a luat pana la ultima iteratie, puteti sa-mi zicetzi? Vreau sa fac un fel de comparatie... sa vad daca ruleaza mai bine in Python sau nu!
|
|
|
Va multumesc mult.
|
|
|
[Citat]
... dar oare cat i-a luat pana la ultima iteratie, puteti sa-mi zicetzi? Vreau sa fac un fel de comparatie... sa vad daca ruleaza mai bine in Python sau nu! |
Nu sunt multe operatii, python se instaleaza in cateva minute, apoi in nici o secunda (daca dau la o parte printarile nenumarate...) COD
# solutii ale ecuatiei a + 2b + 4c + 10d + 20e = 42
import time
def now():
return time.ctime()
print "Inainte de toate: Stampila de timp: %s" % now()
count = 0
for a in range(0,42+1):
for b in range(0,42/2+1):
for c in range(0,42/4+1):
for d in range(0,42/10+1):
for e in range(0,42/20+1):
if a + 2*b + 4*c + 10*d + 20*e == 42:
count += 1
# print "Solutia %3d :: %d + 2*%d + 4*%d + 10*%d + 20*%d " % (count, a,b,c,d,e)
print " Dupa toate: Stampila de timp: %s" % now()
print "Numar de solutii: %d" % count
Inainte de toate: Stampila de timp: Mon Oct 08 20:03:56 2012
Dupa toate: Stampila de timp: Mon Oct 08 20:03:56 2012
Numar de solutii: 335
---
df (gauss)
|
|
|
Am si eu python pe calculator... dar nu m-am riscat in el inca. Am auzit ca e bun. Ma interesa timpii de fapt (de la milisecunde in sus) faptul ca a luat sub o secunda e normal. Vroiam sa fac o comparatie cu programul meu scris in C, ca asta e o problema clasica... dar tb s-o caut prin fisiere n-am dat nume sugestive la astea si-s o groaza... cred ca ma apuc si-l fac din nou  ). 42*(42/2)*(42/4)*(42/10)*(42/20) e putin ca nr de operatii deci tb sa fie ceva instantaneu. Cam 82000 de operatii... ar cam tb sa ia sub 0.01 secunde in mod normal in C iar in python ma astept la performante mai bune! Oricum problema se poate face mult mai rapid printr-un backtracking-recursiv (daca avem numere mari si multe de bancnote dar fiind numarul redus nu prea conteaza)
|
|
|
C++-ul este de 1.3 pana la 1.6 ori mai rapid decat Python.
Codul C++ se citeste (si administreaza) de 2 ori pana la 3 ori mai incet decat cel din Python.
Eu am luat decizia de a scrie in python,
cu atat mai mult cu cat tot ce vreau sau pot sa fac in matematica *azi* este deja implementat (liber) in sagemath, http://www.sagemath.org/
Acolo se gaseste si documentatie pdf libera,
dar eu prefer pentru scopurile liceelor (si facultatilor politehnice) din tara sa indic pentru inceput http://cannelle.lateralis.org/sagebook-1.0.pdf
Daca vreau neaparat sa castig aici acele milisecunde, atunci iau ceva scris in C la baza, gp/pari, si prefer liniile criptice: (21:27) gp > N=42; count = 0; forvec( w = [ [0,N], [0,N/2], [0,N/4], [0,N/10], [0,N/20] ], if( sum( k=1,5, v[k]*w[k] )-N , , count=count+1 ) )
time = 437 ms.
(21:27) gp > count
time = 0 ms.
%42 = 335
Ca sa mai castig ceva din timpul asta (pentru cazul cu N=200) pot sa explicitez for-urile, sa incep cu ciclul dupa bancnota cea mai mare si inainte de a ma afunda in ciclul urmator sa vad daca nu am trecut cumva de N...
Dar probabil ca voi programa din prima o inmultire de polinoame / serii luate modulo puterea apropiata a lui N. De exemplu, calculez
si ii iau coeficientul in grad N...
(Sigur ca am reusit la maxim sa influentez pe cei de clasa a III-a sa se apuce de matematica. Multumesc pentru ajutor! In acest mod ramanem in cel mult doi pe acest site... Rog pe viitor ca sa nu intram in dimensiuni noi cu nuante noi pentru o postare initiala la care ajutorul principal este cel didactic. Daca totusi, pe baza unei probleme de clasa a III-a se poate discuta, sa incepem un subiect nou...)
(21:47) gp > v = [1,2,4,10,20]
time = 0 ms.
%51 = [1, 2, 4, 10, 20]
(21:47) gp > f(N) = polcoeff( prod( k=1,5, 1/(1-x^v[k]) + O(x^(N+1)) ) , N )
time = 0 ms.
(21:48) gp > f(12)
time = 0 ms.
%52 = 18
(21:48) gp > f(42)
time = 0 ms.
%53 = 335
(21:48) gp > f(200)
time = 0 ms.
%54 = 59576
(21:48) gp > f(2000)
time = 125 ms.
%55 = 432699251
(21:48) gp > f(20000)
*** prod: the PARI stack overflows !
current stack size: 4000000 (3.815 Mbytes)
[hint] you can increase GP stack with allocatemem()
(21:48) gp > allocatemem(40000000)
time = 0 ms.
(21:49) gp > f(20000)
time = 5,960 ms.
%56 = 4182519842501
In programare se subestimeaza destul de mult faptul ca programatorul trebuie sa inteleaga domeniul in care programeaza.
Aceasta intelegere este mult mai importanta decat algoritmii de parcurgere, sortare si cautare...
Input-ul de structura trebuie sa vina de altundeva, de exemplu din matematica sau fizica.
---
df (gauss)
|
|
|
aaaa pai nu e bine asha... trisezi! Nici nu stiam ca C-ul e mai rapid. Daca nu ma insel python e si interpretat cred ca de la asta vine lentoarea... (sau ma insel). Incerc sa descarc acum soft-ul ... poate poate imi descopar o pasiune noua ! Mersi ptr raspuns, lamuriri etc. Cred ca ma apuc sa scriu la Metoda Lespezilor. Vad ca nimeni n-a zis nimic. Ori e boring ori e naspa ori nu intereseaza pe nimeni! )
| [1]
|
Legendă:
|
 Access general
|
 Conţine mesaje necitite
|
47559 membri,
58582 mesaje.
|
|
|
|
 |
|
 |
© 2007, 2008, 2009, 2010 Pro-Didactica.ρ
|
