Finne ut om et nummer er palindromt (c++)

[kingkong]

Med et moderne programmeringsspråk kan man forsåvidt gjøre det elegant og begripelig samtidig, f.eks. i Ruby...

 

(1..10000).to_a.delete_if{|i| i.to_s!=i.to_s.reverse}

 

...som lager en array med alle palindrome tall mellom 1 og 10000.

[søppel]

Her er en i Common Lisp:

 

(defun palindrome (x)
 (let ((s (princ-to-string x)))
   (if (string-equal s (reverse s))
     t
     nil)))

 

(garantert bedre måter å gjøre dette på .. jeg lærer .. hadde det bare vært snakk om lister hadde noe annet vært raskere .. etc.)

 

(palindrome "abba")

T

(palindrome "abbaa")

NIL

(palindrome 123)

NIL

(palindrome 1221)

T

 

..og...

 

(dotimes (i 10000)
 (if (palindrome i)
   (format t "~A " i)
   nil))

0 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 111 121 131 141 151 161 171 181 191 202 212 222 232 242 252 262 272 282 292 303 313 323 333 343 353 363 373 383 393 404 414 424 434 444 454 464 474 484 494 505 515 525 535 545 555 565 575 585 595 606 616 626 636 646 656 666 676 686 696 707 717 727 737 747 757 767 777 787 797 808 818 828 838 848 858 868 878 888 898 909 919 929 939 949 959 969 979 989 999 1001 1111 1221 1331 1441 1551 1661 1771 1881 1991 2002 2112 2222 2332 2442 2552 2662 2772 2882 2992 3003 3113 3223 3333 3443 3553 3663 3773 3883 3993 4004 4114 4224 4334 4444 4554 4664 4774 4884 4994 5005 5115 5225 5335 5445 5555 5665 5775 5885 5995 6006 6116 6226 6336 6446 6556 6666 6776 6886 6996 7007 7117 7227 7337 7447 7557 7667 7777 7887 7997 8008 8118 8228 8338 8448 8558 8668 8778 8888 8998 9009 9119 9229 9339 9449 9559 9669 9779 9889 9999 

 

Sum-saken:

 

(let ((ans 0))
 (dotimes (i 10000)
   (if (palindrome i)
     (incf ans i)
     nil))
 ans)
545040

 

Edit:

eehh .. orginaloppgaven var jo ikke helt slik, men samme.

Endret 11. januar 2005 av søppel

[Zethyr]

Med et moderne programmeringsspråk kan man forsåvidt gjøre det elegant og begripelig samtidig, f.eks. i Ruby...

Jeg visste at ruby hadde støtte for noe som het 'reverse' etter å ha lest littegrann, men jeg er dessverre ikke noe særlig inne i dette, derfor ligger tråden under c++.

 

Hva kan jeg bruke under windows for å jobbe med ruby ?? (har ikke lest mer enn 2 min om det)

[JBlack]

Man kan gjøre det enkelt og lettlest i C++ også. (Om dette forumet hadde klart å formatere kode skikkelig da.

 

#include <iostream>
using namespace std;

int palindrome(int n){
int m=0;
for (int n2=n;n2>0;n2/=10) m=m*10+n2%10;
if (n==m) return 1;
return 0;
}

int main(){
for (int i=0;i<=1000;i++){
 if (palindrome(i)) cout << i << " ";
}
cout << endl;
return 0;
}

 

Edit: Forenklet og fikset bug. Nå er 0 lovlig palindrom.

Endret 17. januar 2005 av JBlack

[Neuro]

Kan man ikke bare lage en "reversert" string og så sammenligne med originalen? Jeg har ikke så mye greie på hva som er optimal kode, men koster det ikke mindre å bygge en ny string char for char og så teste til slutt, enn å teste for hver char?

 

Edit: oops, så ikke at det var 2 sider, noen hadde visst tenkt på det allerede :-)

Endret 17. januar 2005 av Neuro

[søppel]

Det som koster minst blir vel å finne midten av strengen, og så gå skritt for skritt "paralellt" begge veier til man møter to char'er som ikke er like (ikke palindromt). Hvis man ikke finner dette er strengen et palindrom.

 

123344321 gir:

 

4 4

3 3

2 2

1 1

 

...mens 12344331 ville gitt:

 

4 4

3 3

2 3 *bang* .. ikke palindromt.

 

 

Jeg er ikke sikker på dette -- bare første innfall .. :]

Endret 17. januar 2005 av søppel

[Legion]

O(n/2) er optimalt, hvor n er lengden på strengen/tallet som skal undersøkes.

 

en 'pen' måte å gjøre dette på er å sjekke første element mot siste, for så å rekursivt kalle samme metode uten første og siste element. returner true når det sjekkes mot tom streng/liste.

[saboi]

får vel slenge meg på bølgen over å skrive det i et fancy schmancy språk da, så her er en versjon i haskell..

palindrome                    :: Eq a => [a] -> Bool
palindrome []                 = True
palindrome (x:xs)           | n == 1 = True
                                    | x == xs!!n = palindrome (take m xs)
                                    | otherwise = False
                                    where n = length xs - 1; m = n - 1

Endret 18. januar 2005 av saboi