Visualizzazione risultati 1 fino 7 di 7
Like Tree3Likes
  • 2 Post By mzanella
  • 1 Post By

Discussione: Trovare fattori di numero n con ciclo

  1. #1
    Guest

    Predefinito Trovare fattori di numero n con ciclo

    Salve, dovrei fare una cosa apparentemente molto semplice ma con la quale non riesco a venire a capo, almeno in PHP.

    Facciamo un esempio... Ho un valore N = 50880....

    Ora, tramite questa formula esatta (X * 10) + (Y * 199) vorrei trovare (ammettendo che X abbia un range minimo di 1000 per esempio, e Y un range massimo di 200) quei valori di X e Y per i quali appunto, quella formula, restituisce 50880..... Sono sicuro che è una stupidata, ma non riesco proprio a buttare giù le righe, il concetto proprio... Una mano?

  2. #2
    L'avatar di alemoppo
    alemoppo è connesso ora Staff AV
    Data registrazione
    24-08-2008
    Residenza
    PU / BO
    Messaggi
    22,067

    Predefinito

    ammettendo che X abbia un range minimo di 1000
    Vorresti dire valore massimo?


    Codice PHP:
    $N = 50880;

    $X = array();
    $Y = array();
    for (
    $y=1;$y<200;$y++)
    {
    for (
    $x=1;$x<1000;$x++)
    {
    if(
    10*$x+199*$y == $N)
    {
    $X[] = $x;
    $Y[] = $y;
    }
    }
    }

    var_dump($X,$Y);
    Tieni presente che può capitare, come nel tuo esempio, che non esistano tali numeri in quel ristretto range di x e y. Prova con N=5088 e vedrai che funzionerà, oppure aumentare il range dei possibili valori.

    Ciao!
    Ultima modifica di alemoppo : 20-04-2017 alle ore 18.48.02

  3. #3
    Guest

    Predefinito

    Ciao, intanto grazie per la riposta. :)

    Ho provato il tuo esempio e funziona perfettamente, facendo qualche correzione... Come range minimo intendevo proprio come valore minimo 1000 in sù, e per questo avevo preso come riferimento proprio 50.880, i cui X e Y che conoscevo erano 2700 e 120 (27000 + 23880)... Ad ogni modo anche se l'output non è chiarissimo come lo intendevo io, il tuo codice fa esattamente il suo dovere, per cui grazie. :)

  4. #4
    L'avatar di alemoppo
    alemoppo è connesso ora Staff AV
    Data registrazione
    24-08-2008
    Residenza
    PU / BO
    Messaggi
    22,067

    Predefinito

    In che modo avresti voluto l'output?

    Ciao!

  5. #5
    Guest

    Predefinito

    In realtà qualcosa tipo X (+Y) (tipo 2700 (+120)), ma va bene così, ho sostituito var_dump con print_r e già risulta meglio

    EDIT: risolto, piazzando semplicemente

    echo $x." (".$y.")<br>";
    ad ogni ciclo di if.... Grazie ancora alemoppo, numero uno!
    Ultima modifica di smackdownpsx : 20-04-2017 alle ore 19.00.57

  6. #6
    mzanella non è connesso AlterGuru
    Data registrazione
    29-12-2015
    Messaggi
    1,954

    Predefinito

    Modalità matematica on
    L'algoritmo proposto ha una complessità quadratica, ma le soluzioni si possono calcolare in maniera più efficiente in tempo lineare!

    La formula data è questa: x * 10 + y * 199 = 50880 (x e y naturali), che può essere riscritta come x = (50880 - y * 199) / 10 e quindi come: x = 5088 - y / 10 * 199.
    Poiché siamo interessati solo a numeri naturali, ha senso considerare solo i valori di y per i quali y / 10 è un numero naturale, ovvero valori come 0, 10, 20..., quindi nella forma 10 * n, n in Nat.

    Uno dei vincoli dati è x >= 1000 che, riscritto in termini di y, diventa (50880 - y * 199) / 10 >= 1000 o, equivalentemente 50880 - y * 199 >= 10000, disequazione lineare semplice da risolvere. La soluzione è y <= 40880 / 199 =~ 205.43. Poiché y è un numero naturale, tale vincolo può essere espresso come y <= 205.

    L'altro vincolo dato, y <= 200 rende ridondante il vincolo appena esaminato. In parole povere, uno dei vincoli che ti è stato dato, x >= 1000 era inutile!

    Mettendo tutto insieme arriviamo finalmente al codice:
    Codice PHP:
    for ($y = 0; $y < 200; $y += 10) {
    $x = 5088 - $y / 10 * 199;
    echo
    "Soluzione: ($x, $y)\n";
    }
    La differenza è (oltre che nella logica), nella complessità computazione. L'algoritmo di alemoppo "prova tutti i valori di x e y, e si salva quelli che soddisfano le proprietà", dovendo quindi effettuare tante prove quante sono le possibili coppie di x e y (quindi circa 800000 iterazioni), mentre quello proposto qui va a calcolare solo ed unicamente i valori necessari (circa una 20ina di iterazioni) .
    Modalità matematica off
    alemoppo and smackdownpsx like this.

  7. #7
    Guest

    Predefinito

    Ciao, scusa il ritardo ma l'ho visto solo adesso...Anche questa soluzione è davvero ottima e funzionale, per cui grazie mille anche a te mzanella :)
    mzanella likes this.

Regole di scrittura

  • Non puoi creare nuove discussioni
  • Non puoi rispondere ai messaggi
  • Non puoi inserire allegati.
  • Non puoi modificare i tuoi messaggi
  •