M3.1011 PyGame[4]

Eh, già …

Un numero palindromo è identico se letto in entrambi i sensi. Il più grande palindromo che sia prodotto di 2 numeri di due cifre è : 9009=91 \times 99

Trovare il più grande palindromo che sia prodotto di 2 numeri di 3 cifre.

 

valore: 3 crediti

ottimizzato: 3 crediti

Questa voce è stata pubblicata in Algoritmi, Informatica, M3, M3.1011, Programmazione e contrassegnata con , , , . Contrassegna il permalink.

16 risposte a M3.1011 PyGame[4]

  1. bobcarr ha detto:

    il programma più corto che sono riuscito a trovare (che risolve il problema)

    >([:{: ]#~ (=|.&.>)) :/**/)~(i.100)-.~i.1000

    il linguaggio di programmazione si chiama J e si può trovare quì:

    http://www.jsoftware.com/

  2. bobcarr ha detto:

    ok il problema è risolto da Magoga

    alcune osservazioni:

    1) sia magoga che mattiuzzo hanno usato istruzioni misteriose (::-1) che sembrano emoticons sbalestrati; non sarebbe valido, visto il livello di apprendimento cui siamo arrivati; conclusione: dal prossimo problema usare solo le istruzioni che sono state svolte in laboratorio (spiacente per magoga)
    2) interessante la soluzione di magoga sia per la generalizzazione che per il tentativo (non raggiunto) di maggiore efficienza: l’idea è quella di scegliere cicli che vanno all’indietro (da 999 a 1) e questo dovrebbe consentire di trovare la soluzione prima. Buona idea: purtroppo non funziona perchè il ciclo viene percorso interamente lo stesso. Qualche idea per farlo funzionare?

    • Alessandro Magoga ha detto:

      si, il mio codice (ultima revisione NON ancora postata) lo risolve tranquillamente. Ora posto il tutto. Arriva a calcolare palindromi 7×7 poi va in overflow (poveretto :D)

      • Alessandro Magoga ha detto:

        codice velocizzato, senza scorrere tutte le combinazioni di numeri.


        def Pal33():
        for U in xrange(999,899,-1):
        for D in xrange(999,899,-1):
        if (str(U*D)[::-1] == str(U*D)): return [U,D,U*D]

        def PalGen(esp1,esp2):
        for U in xrange(pow(10,esp1),pow(10,esp1-1),-1):
        for D in xrange(pow(10,esp2),pow(10,esp2-1),-1):
        if (str(U*D)[::-1] == str(U*D)): return [U,D,U*D]

        xrange viene usata in quanto risulta molto più veloce di range.

        • roberto carrer ha detto:

          usare i numeri 999 e 899 implica conoscerli in anticipo e questo non vale
          il problema resta aperto

  3. Davide Mattiuzzo ha detto:

    Risultato = 906609 (913,993)
    Il sorgente è su dropbox..

  4. Alessandro Magoga ha detto:

    Preso dalla foga ho voluto generalizzare l’ algoritmo permettendo di passare come parametri il numero di cifre che devono avere i due numeri. (ES: richiamando la funzione con PalGen(2,4) verrà calcolato il palindromo più alto formato dalla coppia di numeri uno di 2 cifre e uno di 4)


    def PalGen(esp1,esp2):
    Pal = 0
    P1 = 0
    P2 = 0
    for U in range(pow(10,esp1),pow(10,esp1-1),-1):
    for D in range(pow(10,esp2),pow(10,esp2-1),-1):
    if (str(U*D)[::-1] == str(U*D) and (U*D > Pal):
    Pal = U*D
    P1 = U
    P2 = D
    return [P1,P2,Pal]

    print PalGen(x,y)

    PS: passando parametri alti (> 3 o > 4) risulta ovviamente rallentata l’ esecuzione data la mole di dati da elaborare.

    • bobcarr ha detto:

      @magoga

      il programma (dopo la sistemazione tabulazioni) contiene un errore (manca una parantesi).
      Apprezzabile generalizzazione.
      Un pò lentino

      • Alessandro Magoga ha detto:

        A me entrambe le soluzioni funzionano (Risultato di Pal33() = 906609, Risultato PalGen(3,3) = 906609).

        Gli eventuali errori di parentesi ecc sono dovuti dal fatto che compilo tutto su una macchina virtuale linux che (per oscure ragioni, ci sto lavorando) non va in rete. Perciò mi tocca fare un copia-incolla manuale e capita l’ errore di battitura. Se mi spiega il discorso di dropbox le faccio avere direttamente il sorgente.

      • Alessandro Magoga ha detto:

        OK, programma velocizzato di un bel pò togliendo un inutile controllo che avevo già eliminato in partenza nell’ analisi ma che poi sono andato comunque ad implementare. Attendo istruzioni per dropbox

        • Alessandro Magoga ha detto:

          Passare da “Qualche ora” ad “Circa un minuto” per calcolare un palindromo 7×7 mi pare un buon risultato 😀

  5. Alessandro Magoga ha detto:

    [SOURCE]

    def Pal33():
    for U in range(999,600,-1):
    for D in range(999,600,-1):
    if (str(U*D)[::-1] == str(U*D)):
    return [U,D,U*D]

    print Pal33

    [/SOURCE]

    (purtroppo, ahimè, credo perda la formattazione ordinata che ho dato al programma)
    l’ uso della funzione è stato necessario per fornire una sola terna di numeri, altrimenti si avrebbe avuto una lista di terne con tutti i palindromi formati da coppie di numeri di 3 cifre (potrebbe essere interessante lo stesso), a noi interessava la coppia di numeri che mi dava il palindromo più grande e quindi la prima coppia trovata.
    Non ho ben capito se devo dare anche il risultato finale (numerico), non ho letto tutto il regolamento in questione, quindi evito di metterla adesso (vabbè che uno basta che faccia girare il programma e salta fuori, però evito).

    La questione che dicevo del “si vede ad occhio” la spiego dopo aver avuto il permesso di scrivere il risultato altrimenti sarebbe troppo palese 🙂

  6. Alessandro Magoga ha detto:

    Si, più o meno ad occhio, ora non le spiego, prima posto il codice poi la spiegazione 🙂

  7. Alessandro Magoga ha detto:

    Posso partecipare prof? 😀

    la soluzione si vede ad occhio comunque.

I commenti sono chiusi.