| Precedente :: Successivo |
| Autore |
Messaggio |
mdweb
Dio maturo
Registrato: 18/12/07 15:59
Messaggi: 4412
|
 Inviato: 21 Dic 2008 15:33 Oggetto: * Contest:Il numero palindromo successivo |
 |
|
Da qui.
Problema:
Dato un input trovare il numero palidromo più vicino che sia però maggiore del numero dato.
Esempio se l'input è 32 l'output dovrà essere 33.
Postate le vostre soluzioni con i linguaggi che preferite.Ecco la mia soluzione python:
| Codice: | def reverse(x):
i=-1
lunghezza=len(x)
rit=""
while i>= -lunghezza:
rit=rit+x[i]
i=i-1
return rit
def palindromo(x):
return x==reverse(x)
def programma(x):
if palindromo(x):
print x,"e' polindromo"
return
else:
programma(str(int(x)+1))
programma("119")
|
Vi consiglio di dare un'occhiata a questi siti
Lista di problemi classici
Altra lista |
|
| Top |
|
 |
mdweb
Dio maturo
Registrato: 18/12/07 15:59
Messaggi: 4412
|
| Inviato: 21 Dic 2008 15:40 Oggetto: |
|
|
C'era un return che non c'entrava niente:
| Codice: |
def reverse(x):
i=-1
lunghezza=len(x)
rit=""
while i>= -lunghezza:
rit=rit+x[i]
i=i-1
return rit
def palindromo(x):
return x==reverse(x)
def programma(x):
if palindromo(x):
print x,"e' polindromo"
else:
programma(str(int(x)+1))
programma("119")
|
|
|
| Top |
|
|
mdweb
Dio maturo
Registrato: 18/12/07 15:59
Messaggi: 4412
|
| Inviato: 21 Dic 2008 16:08 Oggetto: |
|
|
Risolto un bug:
| Codice: | X=raw_input("Inserisci un numero: ")
def reverse(x):
i=-1
lunghezza=len(x)
rit=""
while i>= -lunghezza:
rit=rit+x[i]
i=i-1
return rit
def palindromo(x):
return x==reverse(x)
def programma(x):
if palindromo(x):
print x,"e' polindromo"
else:
programma(str(int(x)+1))
programma(str(int(X)+1)) |
Come chiesto nell'esercizio questo programma trova il palindromo successivo anche se è un nuermo è già palindromo.
Ecco la schermata:
 |
|
| Top |
|
|
Mark89
Comune mortale
Registrato: 21/12/08 23:48
Messaggi: 2
|
| Inviato: 22 Dic 2008 00:00 Oggetto: |
|
|
Ciao, ecco la mia soluzione in C#
| Codice: |
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Palindromo
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("Questo programma trova il numero palindromo appena superiore al numero dato");
Console.Write("Scrivi un numero :");
string numero = Console.ReadLine();
string stringainvertita;
bool palindromo=false;
while (palindromo == false)
{
numero = Convert.ToString(Convert.ToInt32(numero) + 1);//aggiunge di uno alla stringa
char[] charArray = numero.ToCharArray();//trasforma in caratteri
Array.Reverse(charArray);//inverte i caratteri
stringainvertita = new string(charArray);//ritrasformata in stringa
if (string.Compare(numero, stringainvertita) == 0) palindromo = true;
}
Console.Write("Il numero palindromo più vicino è: ");
Console.WriteLine(numero);
Console.ReadKey();
}
}
}
|
 |
|
| Top |
|
|
mdweb
Dio maturo
Registrato: 18/12/07 15:59
Messaggi: 4412
|
| Inviato: 22 Dic 2008 00:06 Oggetto: |
|
|
Ciao Mark89 benvenuto nel forum.
E' bello vedere la semplicità di Python e soprattutto l'eleganza di python.
In poche righe (una 15ina) sono riuscito a fare quello che C# in 30 righe?
Comunque il programma funziona benissimo.Non so se si può migliorare qualcosa dal punto di vista della velocità.
P.S Se vuoi presentati qui |
|
| Top |
|
|
mdweb
Dio maturo
Registrato: 18/12/07 15:59
Messaggi: 4412
|
| Inviato: 22 Dic 2008 11:42 Oggetto: |
|
|
Come richiesto posto le indicazione.
Generare un palindromo è facile.Io ho trattato il numero come una stringa.
Poi con una funzione (reverse) l'ho confrontato restituendo un True o False.Ricorsione e ciclo while funzionano bene.
Ricordate però che se il numero è 808 l'output dovrà essere 818:Il numero palindromo successivo più piccolo,anche se l'input è già palindromo.
@freemind[OT]:
L'algortimo per genererare palindromo è:
| Codice: | 79 + 97 => 176 + 671 => 847 + 748 => 1595 + 5951 =>
=> 7546 + 6457 => 14003 + 30041 => 44044 |
Nel nostro caso non è utile però.
Puoi trovare qualcosa qua |
|
| Top |
|
|
freemind
Supervisor sezione Programmazione
Registrato: 04/04/07 20:28
Messaggi: 4643
Residenza: Internet
|
| Inviato: 22 Dic 2008 14:06 Oggetto: |
|
|
Ciao,
questo algoritmo lo conoscevo però come hai detto tu non è utili per il problema proposto.
Dato che la densità dei numeri palindromi è nota, sarebbe bello riuscire a sfruttarla per evitare dei cicli inutili su numeri che sicuramente non sono palindromi.
Ad esempio, supponiamo che dato x intero, il successivo palindromo sia dopo 3000 numeri ossia x+3000, se esistesse qualche proprietà che permettesse di restringere lo spazio di ricerca, si eviterebbero molte iterazioni comprese tra x+1 e x+2999. |
|
| Top |
|
|
mdweb
Dio maturo
Registrato: 18/12/07 15:59
Messaggi: 4412
|
| Inviato: 22 Dic 2008 14:45 Oggetto: |
|
|
| freemind ha scritto: | Ciao,
questo algoritmo lo conoscevo però come hai detto tu non è utili per il problema proposto.
Dato che la densità dei numeri palindromi è nota, sarebbe bello riuscire a sfruttarla per evitare dei cicli inutili su numeri che sicuramente non sono palindromi.
Ad esempio, supponiamo che dato x intero, il successivo palindromo sia dopo 3000 numeri ossia x+3000, se esistesse qualche proprietà che permettesse di restringere lo spazio di ricerca, si eviterebbero molte iterazioni comprese tra x+1 e x+2999. |
su internet non c'è niente ma comunque la cose che dici tu non capita mai..penso |
|
| Top |
|
|
chemicalbit
Dio maturo
Registrato: 01/04/05 17:59
Messaggi: 18597
Residenza: Milano
|
| Inviato: 22 Dic 2008 16:48 Oggetto: Re: Contest:Il numero palindromo successivo |
|
|
| mdweb ha scritto: | .Ecco la mia soluzione python:
[code]def reverse(x):
i=-1
lunghezza=len(x)
rit=""
while i>= -lunghezza:
rit=rit+x[i]
i=i-1
return rit |
Non conosco il pyton,
x[i] è un elemento di un vettore (array)?
In tal caso, visto che i è sempre negativo (parte da -1, e man mano viene sottratto 1), che elemento è x[i] ? |
|
| Top |
|
|
mdweb
Dio maturo
Registrato: 18/12/07 15:59
Messaggi: 4412
|
| Inviato: 22 Dic 2008 19:38 Oggetto: Re: Contest:Il numero palindromo successivo |
|
|
| chemicalbit ha scritto: | | mdweb ha scritto: | .Ecco la mia soluzione python:
[code]def reverse(x):
i=-1
lunghezza=len(x)
rit=""
while i>= -lunghezza:
rit=rit+x[i]
i=i-1
return rit |
Non conosco il pyton,
x[i] è un elemento di un vettore (array)?
In tal caso, visto che i è sempre negativo (parte da -1, e man mano viene sottratto 1), che elemento è x[i] ? |
In python se abbiamo :
[code]
s="stringa"
print s[-1]
[/code]
stampa l'ultima lettera "a" |
|
| Top |
|
|
chemicalbit
Dio maturo
Registrato: 01/04/05 17:59
Messaggi: 18597
Residenza: Milano
|
| Inviato: 22 Dic 2008 19:49 Oggetto: |
|
|
| Ah , capito, è un indice che parte dal fondo. ( -2 ad es. è la penultima lettera della stringa, giusto?) |
|
| Top |
|
|
mdweb
Dio maturo
Registrato: 18/12/07 15:59
Messaggi: 4412
|
| Inviato: 22 Dic 2008 20:00 Oggetto: |
|
|
| chemicalbit ha scritto: | | Ah , capito, è un indice che parte dal fondo. ( -2 ad es. è la penultima lettera della stringa, giusto?) |
si |
|
| Top |
|
|
mdweb
Dio maturo
Registrato: 18/12/07 15:59
Messaggi: 4412
|
| Inviato: 22 Dic 2008 20:21 Oggetto: |
|
|
Possiamo anche usare:
| Codice: |
x="ciao"
l=len(x)
print x[l-1]
|
Ovviamente la forma usata prima è più compatta e concisa. |
|
| Top |
|
|
dany88
Dio maturo
Registrato: 12/02/09 11:14
Messaggi: 1300
|
| Inviato: 12 Feb 2009 11:22 Oggetto: |
|
|
potreste migliorare notevolmente la velocità dell'algoritmo in questa maniera (ve lo scrivo in pseudocodice)
function palindromo(x):boolean
if x mod 11 <> 0 then return false
if x=reverse(x) return true else return false
end function
il reverse (che non ho scritto) può essere ulteriormente migliorato facendo ritornare false alla prima incongruenza e si può ottenere ancora qualcosa in più utilizzando per la gestione della stringa, algoritmi particolari od oggetti messi a disposizione dal linguaggio scelto.
Avete citato il python, ecco alcuni esempi di concatenazioni veloci
http://skymind.com/~ocrow/python_string/
e per il C# vi posto un interessante funzione di reverse veloce basata su XOR
http://weblogs.sqlteam.com/mladenp/archive/2006/03/19/9350.aspx |
|
| Top |
|
|
dameunfiasco
Comune mortale
Registrato: 12/02/09 19:28
Messaggi: 4
|
| Inviato: 12 Feb 2009 19:31 Oggetto: |
|
|
E perché non usare il caro Bash 
| Codice: |
#!/bin/bash
echo -n "Inserisci numero? "
read NUMERO
let NUMERO=$NUMERO+1
while : ; do
[[ $NUMERO == $(echo $NUMERO | rev) ]] && echo $NUMERO && exit
let NUMERO=$NUMERO+1
done
|
[/code] |
|
| Top |
|
|
mdweb
Dio maturo
Registrato: 18/12/07 15:59
Messaggi: 4412
|
| Inviato: 12 Feb 2009 19:49 Oggetto: |
|
|
Ciao dameunfiasco benvenuto nel forum.
| Citazione: | | E perché non usare il caro Bash |
Forse perchè non è il più usato.
Dacci tu le motivazioni per usarlo! |
|
| Top |
|
|
chemicalbit
Dio maturo
Registrato: 01/04/05 17:59
Messaggi: 18597
Residenza: Milano
|
| Inviato: 12 Feb 2009 19:53 Oggetto: |
|
|
| mdweb ha scritto: | Ciao dameunfiasco benvenuto nel forum.
| Citazione: | | E perché non usare il caro Bash |
Forse perchè non è il più usato.
Dacci tu le motivazioni per usarlo! |
Scusa mdweb, e le motivazioni per non usarlo?
Secondo te va usato solo il linguaggio di programmazione è "il più usato"?! |
|
| Top |
|
|
Scrigno
Semidio
Registrato: 26/07/09 04:32
Messaggi: 313
|
| Inviato: 16 Set 2009 00:31 Oggetto: L'Algoritmo Più Breve :-P |
|
|
| freemind ha scritto: | Ciao,
questo algoritmo lo conoscevo però come hai detto tu non è utili per il problema proposto.
Dato che la densità dei numeri palindromi è nota, sarebbe bello riuscire a sfruttarla per evitare dei cicli inutili su numeri che sicuramente non sono palindromi.
Ad esempio, supponiamo che dato x intero, il successivo palindromo sia dopo 3000 numeri ossia x+3000, se esistesse qualche proprietà che permettesse di restringere lo spazio di ricerca, si eviterebbero molte iterazioni comprese tra x+1 e x+2999. |
Lo scrivo in italiano perchè a programmazione sono ancora una schiappa ;-P
Analisi:
- i numeri sono formati da un certo numero di cifre (pari O dispari)
- se sono pari possono essere spezzati in due parti
- se dispari hanno la stessa peculiarità ma hanno una cifra solitaria al centro.
Esempio
- 12345 ha numero di cifre dispari quindi ha una cifra centrale (3) e partendo dal centro leggiamo prima (2) poi (1) e (4) (5) - 12345678 ha numero di cifre pari quindi al centro non troviamo cifre e da li leggiamo (4)(3)(2)(1) e (5)(6)(7)(8 )
Non c'ho ragionato molto sopra però sono pronto a scommettere che:
Definizioni:
Spezzando il numero come sopra otterremo:
Un appendice di destra
Un appendice di sinistra
Un eventuale centrale
Ad esempio: 13458 darà Appendice di Sx (31); Centrale (4); Appendice di Dx(58 )
Lo scelto a caso e mentre scrivo sono pronto a dire che il palindromo successivo dovrebbe essere 13|5|31
Algoritmo:
- Distinguere se un numero ha parte centrale o meno perchè bisognerà operare in modo leggermente differente.
- Caso con numero di cifre pari:
- Confrontare le cifre del lato Sx con le rispettive del lato Dx e procedere fino a che non si incontra che NON sono identiche.
- determinare quale appendice ha la cifra più alta fra quelle in esame.
- Se la cifra è parte di Sx allora il palindromo sara formato dall' appendice di Sx e di conseguenza l' appendice Dx sarà a lei speculare
- se la cifra più alta è parte di Dx allora aggiungere 1 alla cifra inmeno significativa di Sx considerando anche gli eventuali resti e costruire la Dx dalla Nuova Sx
-in caso di Dx = Sx il palindromo si ha sempre aggiungendo 1 alla meno significativa di Sx e dalla nuova Sx si crea Dx
ESEMPIO:
1993 --> 19 | 93 --> (3 ) è maggiore di 1 quindi:
Sx = Sx + 1 = 20 --> 20 | 02
il primo palindromo dopo 1993 è 2002
Altro esempio:
1423 -- > 14 | 23 --> 4 è maggiore di 2 quindi:
Sx = Sx = 14 --> 14 | 41
il primo palindromo dopo 1423 è 1441
Infine:
1441 --> 14 | 41 --> è palindromo quindi
Sx = Sx + 1 = 15 --> 15 | 51
il primo palindromo dopo 1441 è 1551
...
per quanto riguarda i formati da un numero di cifre dispari Bisogna tener conto della parte centrale nel senso che nella formula Sx + 1 Sx avra come cifr ameno significativa la parte centrale e nella costruzione della Dx questa parte centrale non dovrà esser ripetuta
Esempio:
123 --> 1 | 2 | 3
3 > 1 quindi
sx = sx + 1 = 12 + 1 = 13
sx sarà 1
Centro sarà 3
Dx sarà lo specchio di Sx e quindi 1
dopo 123 il primo palindromo è 131
Altro esempio:
14325 --> 14 | 3 | 25
4 > 2 quindi Sx = sx
14 | 3 | 41
dopo il 14325 il primo palindromo è 14341
8)
Spero possiate provare quanto ho appena trovato perchè gioisco al solo scriverlo 
Perdonatemi se mi gongolo
Anche se scommetto che avrò sicuramente cannato qualcosa |
|
| Top |
|
|
Scrigno
Semidio
Registrato: 26/07/09 04:32
Messaggi: 313
|
| Inviato: 19 Set 2009 01:16 Oggetto: |
|
|
| freemind ha scritto: | Ciao,
questo algoritmo lo conoscevo però come hai detto tu non è utili per il problema proposto.
Dato che la densità dei numeri palindromi è nota, sarebbe bello riuscire a sfruttarla per evitare dei cicli inutili su numeri che sicuramente non sono palindromi.
Ad esempio, supponiamo che dato x intero, il successivo palindromo sia dopo 3000 numeri ossia x+3000, se esistesse qualche proprietà che permettesse di restringere lo spazio di ricerca, si eviterebbero molte iterazioni comprese tra x+1 e x+2999. |
Raga spero di farvi cosa gradita nel postare il mio duro lavoro con PAIT  ... ho perso 4 anni di vita ma mi pare non ci siano errori.. però, come al solito gli errori li vedono sempre gli altri 
Comunque sia... eccovi lo schema a blocchi di quello che ho cercato di spiegare sopra...
 |
|
| Top |
|
|
freemind
Supervisor sezione Programmazione
Registrato: 04/04/07 20:28
Messaggi: 4643
Residenza: Internet
|
| Inviato: 20 Set 2009 16:32 Oggetto: |
 |
|
Ciao Scrigno,
cercherò con calma di guardare sia l'algoritmo da te proposto che anche il flow chart.
Solo un consiglio però: la prossima volta lo schema fallo con DIA, così non diventi matto a disegnare i blocchi! |
|
| Top |
|
|
|
FAQ
Cerca
Lista utenti
Gruppi
Registrati
Profilo
Messaggi privati
Log in
