MrKanister
Anmeldungsdatum: 13. Oktober 2007
Beiträge: 2105
|
Und hier noch mal ne verbesserte C++ Variante...ebenfalls mit 20 Iterationen. Wenn man sich aber nen eigenen Datentyp für Zahlen bastelt, dann ist auch noch mehr drin. 😉 #include <iostream>
#include <sstream>
using namespace std;
unsigned long long int revers(unsigned long long int zahl);
bool is_palin(unsigned long long int zahl);
int main(int argc, char** argv) {
unsigned long long int zahl;
for (int i = 1; i <= 100000; i++) {
zahl = i;
for (int j = 1; j <= 20; j++) {
zahl += revers(zahl);
if (is_palin(zahl)) {
break;
}
if (j == 20) {
cout << i << " könnte eine Lychrel-Zahl sein\n";
}
}
}
return EXIT_SUCCESS;
}
unsigned long long int revers(unsigned long long int zahl) {
stringstream buf;
while (zahl != 0) {
buf << zahl % 10;
zahl /= 10;
}
buf >> zahl;
return zahl;
}
bool is_palin(unsigned long long int zahl) {
if (zahl == revers(zahl)) {
return true;
} else {
return false;
}
} ...
99979 könnte eine Lychrel-Zahl sein
99990 könnte eine Lychrel-Zahl sein
99999 könnte eine Lychrel-Zahl sein
real 0m2.887s
user 0m2.076s
sys 0m0.032s
|
Marc_BlackJack_Rintsch
Ehemalige
Anmeldungsdatum: 16. Juni 2006
Beiträge: 4650
Wohnort: Berlin
|
Und eine C-Lösung. Ist nicht besonders hübsch, da auf Geschwindigkeit getrimmt: Test der Zahlen 1 bis 10000 dauert auf dem C64 damit nur 14 Minuten. ☺ #include <stdio.h>
#include <string.h>
#define FROM 1
#define TO 100000
#define TO_DIGITS 10
#define ITERATIONS 100
#define MAX_DIGITS (TO_DIGITS + ITERATIONS)
static unsigned int n_length, length;
static char n[TO_DIGITS], a[MAX_DIGITS], b[MAX_DIGITS];
static void reverse_add(void)
{
unsigned int i, carry, tmp;
for (i = 0, carry = 0; i < length; i++) {
tmp = a[i] + a[length - 1 - i] + carry;
if (tmp >= 10) {
tmp = tmp - 10;
carry = 1;
} else {
carry = 0;
}
b[i] = tmp;
}
if (carry) {
b[i] = carry;
length++;
}
}
static int is_palindrome(void)
{
char *x, *y;
x = b;
y = b + length - 1;
while (x < y) {
if (*x++ != *y--) return 0;
}
return 1;
}
static int is_lychrel()
{
unsigned int i;
memcpy(a, n, n_length);
length = n_length;
for (i = 0; i < ITERATIONS; i++) {
reverse_add();
if (is_palindrome()) return 0;
memcpy(a, b, length);
}
return 1;
}
static void print_n(void)
{
int i;
for (i = n_length - 1; i >= 0; i--) {
printf("%c", n[i] + '0');
}
printf("\n");
}
static void increase_n(void)
{
char *x = n;
while ((*x)++ == 9) {
*x++ = 0;
}
if (x - n == n_length) n_length++;
}
int main(void)
{
unsigned int i;
n_length = sprintf(a, "%d", FROM);
for (i = 0; i < n_length; i++) {
n[i] = a[n_length - 1 - i] - '0';
}
for (i = FROM; i <= TO; i ++) {
if (is_lychrel()) {
print_n();
}
increase_n();
}
return 0;
} real 0m0.386s
user 0m0.384s
sys 0m0.000s
|
BadBoy
Anmeldungsdatum: 25. Oktober 2007
Beiträge: 479
|
wahahahaha..... ich hab das ganze ma in ruby gemacht (orientiert an der c++ lösung von BlackJack)
def reverse(zahl)
zahl.to_s.reverse.to_i
end
def is_palin zahl
zahl == zahl.to_s.reverse.to_i
end
1.upto(100000) { |i|
zahl = i
1.upto(20) { |j|
zahl += reverse(zahl)
break if is_palin(zahl)
#endzahl << i
print i, " könnte eine Lychrel-Zahl sein\n" if j = 20
}
} ich hab auch ma weiter versucht es ruby-like zu machen mit:
class Integer
def palin?
self == self.to_s.reverse.to_i
end
def reverse
self.to_s.reverse.to_i
end
end aber das war langsamer...
naja...deshalb hab auch ma das ganze bissel weiter getestet, hier meine ergebnisse: (1. C++ Variante, 2. ruby1.9, 3. ruby1.8 )
$ time ./clychrel >/dev/null real 0m3.733s user 0m3.472s sys 0m0.012s $ time ruby1.9 lychrel > /dev/null real 0m3.331s user 0m2.148s sys 0m0.040s $ time ruby1.8 lychrel > /dev/null real 0m5.123s user 0m4.412s sys 0m0.200s
yeha! 😀
|
radoe2
Anmeldungsdatum: 30. November 2006
Beiträge: 243
|
Ok, dann erhöhe ich den Counter der funktionalen Ansätze um eine Lösung in Erlang. Ich habs mal übersichtlich gehalten, man kann das noch etwas eindampfen wenn man will. Kommt hier auf ~7 Sekunden Laufzeit, wobei der Shutdown des Laufzeitsystems wie üblich mit ca. 1,5 Sekunden mitgezählt wird. -module(lychrel).
-export( [is_palindrom/1, inversion/1, lychrel/3, start/0]).
%-- is_palindrom
is_palindrom(AnInteger) ->
L = integer_to_list(AnInteger),
R = lists:reverse(L),
ZipWithFun = fun( E1, E2 ) -> E1 == E2 end,
Zipped = lists:zipwith(ZipWithFun, L, R),
%% lists:any here returns true if L is *not* a palindrom, so negate it.
false == lists:any( fun(X) -> X == false end, Zipped);
%-- inversion
inversion(AnInteger) ->
list_to_integer (lists:reverse( integer_to_list(AnInteger))).
%-- find_lychrel
find_lychrel(OriginalStart, Current, 0) ->
case is_palindrom(Current) of
true -> ok;
false -> io:format("~w~n", [OriginalStart])
end;
find_lychrel(OriginalStart, Current, CurrentIter) ->
case is_palindrom(Current) of
true -> ok;
false -> find_lychrel(OriginalStart, Current + inversion(Current), CurrentIter -1 )
end.
%-- lychrel
lychrel(End,End,_) ->
ok;
lychrel(Start,End,MaxIter) ->
find_lychrel(Start, Start, MaxIter),
lychrel(Start+1, End, MaxIter).
%for convenience, assume Start=1,End=N,MaxIter=100
lychrel(N) ->
lychrel(1,N,100).
%-- for calling this as "erl -noshell lychrel start"
start() ->
lychrel(100000),
init:stop().
|
kart0ffelsack
(Themenstarter)
Anmeldungsdatum: 16. Oktober 2007
Beiträge: 102
Wohnort: Kaiserslautern
|
Ich hab mal Code_Gala aktualisiert. Is es möglich das eine Codebox neben den Inhaltsverzeichnis erscheint und nicht erst darunter? So wie es jetzt aussieht ist da ne hässliche Lücke 😢 Und dann nochmal eine Frage an die Mods: Könnte man die Threads hierzu nich in etwas wiedererkennbares umbennen? Z.b. Anstatt "Zeigt her eure Codes" "Code Gala: Fibonacci" und diesen Thread in "Code Gala: Lychrel" und alle zukünftigen dann nach den gleichen Schema.
|
audax
Anmeldungsdatum: 15. September 2006
Beiträge: 1253
|
from itertools import ifilter, imap
def mirror(n):
return int(
str(n)[::-1])
def is_lychrel(n, tries=100):
rev = mirror(n)
for dummy in xrange(tries):
n += rev
rev = mirror(n)
if n == rev:
return False
return True
def main():
print '\n'.join(imap(str, ifilter(is_lychrel, xrange(100000))))
if __name__ == '__main__':
main() An mirror() geht natürlich alle Rechenzeit verloren, das ist einfach viel zu langsam... Aber das Problem ist ja bekannt 😀
|
rocco_storm
Anmeldungsdatum: 3. November 2005
Beiträge: 1811
Wohnort: Ruhrpott
|
noch mal eine andere Bash-Lösung:
#!/bin/bash
i=1
last=1000
iterations=100
x=0
isPalindrom ()
{
if [[ "$x" == "$(echo $x | rev)" ]]
then
return 0
else
return 1
fi
}
isLychrel ()
{
j=0
x=$i
while [ "$j" -lt "$iterations" ]
do
x=$(echo "$x + $(echo $x | rev)" | bc)
if isPalindrom
then
return 1
fi
(( j += 1 ))
done
return 0
}
while [ "$i" -lt "$last" ]
do
if isLychrel
then
echo "-------------> Found Lychrel: $i"
fi
(( i += 1 ))
done
echo
exit 0
|
Marc_BlackJack_Rintsch
Ehemalige
Anmeldungsdatum: 16. Juni 2006
Beiträge: 4650
Wohnort: Berlin
|
Eine Lösung in D. Basiert auf meiner C-Lösung, implementiert die Integer-Klasse aber als Wert-Typ, es wird also viel "unnötig" umher kopiert. Dafür ist es wesentlich sauberer und wohl auch nachvollziehbarer. import std.stdio;
import std.string;
static const uint ITERATIONS = 100;
class Integer
{
ubyte[] digits;
invariant {
foreach (ubyte d; digits) {
assert(0 <= d && d < 10);
}
}
this(uint n)
out { assert(this.toInt == n); }
body
{
char[] d = std.string.toString(n);
this.digits = new ubyte[d.length];
foreach (uint i, char c; d) {
this.digits[$-1-i] = c - '0';
}
}
this(Integer i)
out { assert(this.digits !is i.digits); }
body
{
this.digits = new ubyte[i.length];
this.digits[] = i.digits;
}
Integer opAdd(Integer other)
{
auto result = new Integer(this);
uint carry = 0;
foreach (uint i, inout ubyte b; result.digits) {
b = b + other.digits[i] + carry;
if (b >= 10) {
b -= 10;
carry = 1;
} else {
carry = 0;
}
}
if (carry) {
result.digits.length = result.digits.length + 1;
result.digits[$-1] = carry;
}
return result;
}
uint length() { return this.digits.length; }
bool isPalindrome()
{
for (uint i = 0; i < this.length / 2; i++) {
if (this.digits[i] != this.digits[$-1-i]) return false;
}
return true;
}
Integer reversed()
{
auto result = new Integer(this);
for (uint i = 0; i < result.length / 2; i++) {
auto tmp = result.digits[i];
result.digits[i] = result.digits[$-1-i];
result.digits[$-1-i] = tmp;
}
return result;
}
char[] toString()
{
auto result = new char[this.length];
foreach (uint i, ubyte b; this.digits) {
result[i] = this.digits[$-1-i] + '0';
}
return result;
}
uint toInt()
{
uint result = 0;
foreach_reverse (ubyte b; this.digits) {
result = result * 10 + b;
}
return result;
}
}
bool isLychrel(Integer n, uint iterations = ITERATIONS)
{
for (uint i = 0; i < iterations; i++) {
n = n + n.reversed;
if (n.isPalindrome) return false;
}
return true;
}
void main()
{
for (uint n = 1; n <= 100_000; n++) {
auto i = new Integer(n);
if (isLychrel(i)) writef("%s\n", i);
}
}
|
rocco_storm
Anmeldungsdatum: 3. November 2005
Beiträge: 1811
Wohnort: Ruhrpott
|
Hm, ich habe gerade versucht das in php (shame on me) um zu setzten (frei nach der Bash-Verision von Mr. Kanister), aber irgendwie findet der Zahlen die nicht gefunden gehören, ich habe jetzt aber auch keine Zeit bzw. Lust mehr, vielleicht findet ja jemand den Fehler:
<?php
$last = 100000;
$iter = 100;
$anz = 0;
$start = time();
for ( $i=1; $i<=$last; $i++ ) {
$z = $i;
for ( $j=1; $j<=$iter; $j++ ) {
$z += intval(strrev($z));
if ( $z == intval(strrev($z)) ) break;
if ( $j == $iter ) {$anz++;echo $i . ' ';}
}
}
echo '<br/>anz: ' . $anz . '<br/>time: ' . (time()-$start);
?> 89 98 177 187 196 276
...
99988 99990 99995 99997 99998 99999
anz: 13620
time: 8 😲
|
rocco_storm
Anmeldungsdatum: 3. November 2005
Beiträge: 1811
Wohnort: Ruhrpott
|
Na gut, der Vollständigkeit halber hier noch mal der gleiche Algorithmus in Java:
import java.math.BigInteger;
public class lychrel3 {
public static void main(String[] args) {
int anz = 0;
int last = 100000;
int iter = 100;
long start = System.currentTimeMillis();
for(int i = 1;i <= last;i++) {
BigInteger z = new BigInteger(String.valueOf(i));
for (int j=1;j<=iter;j++) {
z=z.add(new BigInteger(String.valueOf(new StringBuffer(z.toString()).reverse().toString())));
if(new BigInteger(String.valueOf(new StringBuffer(z.toString()).reverse().toString())).compareTo(z) == 0) break;
if (j==iter) {
System.out.println(i);
anz++;
}
}
}
long stop = System.currentTimeMillis();
System.out.println("anz: " + anz);
System.out.println("time: " + (stop - start) + "ms");
}
}
|
Hello_World
Anmeldungsdatum: 13. Juni 2006
Beiträge: 3620
|
In C++, ohne Beschränkung auf 20 Iterationen. Benötigt libgmpxx4ldbl und den Compilerswitch -lgmpxx
#include <gmpxx.h>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
bool is_palindrome(const mpz_class& x) {
stringstream ss;
ss << x;
string s = ss.str();
int i1 = s.length()-1, i2=0;
while (i1 >= i2) {
if (s[i1] != s[i2])
return false;
i1--;
i2++;
}
return true;
}
mpz_class reverse(const mpz_class& x) {
stringstream ss;
mpz_class rv;
ss << x;
string s = ss.str();
reverse(s.begin(),s.end());
ss.str(s);
ss >> rv;
return rv;
}
bool is_lychrel(const mpz_class& x, int iterations) {
mpz_class y = x;
for (int i=0;i<iterations;++i) {
y+=reverse(y);
if (is_palindrome(y))
return false;
}
return true;
}
int main() {
cout.sync_with_stdio(false);
for (int i=0;i<100000;++i) {
if (is_lychrel(i,100))
cout << i << '\n';
}
}
|
sxfreak
Anmeldungsdatum: 27. Juni 2006
Beiträge: 436
|
So ich hab dann auch mal schnell etwas gebastelt: Die Ergebnisse sind noch etwas komisch, liegt das vielleicht an der Anzahl der Itterationen oder hab ich was falsch gemacht? 😀 unsigned long invertNumber(unsigned long number, unsigned int base)
{
unsigned long invertedNumber = 0;
// Die aktuelle Stelle der invertieren Zahl
unsigned int currentNumPos = 0;
unsigned int lastNumPos;
{
unsigned long temp = number;
// Anzahl Stellen herausfinden
while (temp != 0)
{
currentNumPos++;
temp /= base;
}
}
while (number != 0)
{
currentNumPos--;
lastNumPos = (number - ((number / base) * base));
invertedNumber += lastNumPos * pow(base, currentNumPos);
number /= base;
}
return invertedNumber;
};
bool isPalindrom(unsigned long number, unsigned int base = 10)
{
return invertNumber(number, base) == number;
};
int main(int arg_count, char **arg_list)
{
if (arg_count == 1 || arg_count > 4)
{
return 1;
}
unsigned int start = (unsigned int)atoi(arg_list[1]);
unsigned int end = (unsigned int)atoi(arg_list[2]);
unsigned int base = (unsigned int)atoi(arg_list[3]);
if (start > end)
{
unsigned int temp = start;
start = end;
end = start;
}
unsigned int count = 0;
clock_t start_time, end_time;
start_time = clock();
for (unsigned int run = start; run < end; run++)
{
unsigned int currentNum = run;
for (int iter = 1; iter < 21; iter++)
{
if (isPalindrom(currentNum, base))
{
break;
}
currentNum += invertNumber(currentNum, base);
if (iter == 20)
{
std::cout << run << " könnte eine Lychrel-Zahl sein." << std::endl;
count++;
}
}
}
end_time = clock();
std::cout.precision(10);
std::cout << count << " mögliche Lychrel-Zahlen in " << (double)(end_time - start_time) / (double)CLOCKS_PER_SEC << " Sekunden gefunden." << std::endl;
return 0;
}; Ach ja: 😉
11669 mögliche Lychrel-Zahlen in 0.62 Sekunden gefunden.
|
e1bart0
Anmeldungsdatum: 12. Mai 2007
Beiträge: 927
Wohnort: München
|
Dann werfe ich auch mal meine Lösung in die Runde: http://paste.pocoo.org/show/31710
|
Hello_World
Anmeldungsdatum: 13. Juni 2006
Beiträge: 3620
|
e1bart0 hat geschrieben: Dann werfe ich auch mal meine Lösung in die Runde: http://paste.pocoo.org/show/31710
Diese Lösung ist aber IMHO nicht korrekt. Meine Lösung, die Java-Lösung und audax' Python-Lösung spucken 6091 Zahlen aus, Deine dagegen 7444. Hier die Zahlen, die bei Dir zu viel sind: http://paste.pocoo.org/show/31787/ Und außerdem finde ich es ungerecht, dass sowohl die Python-Lösung schneller ist als C++. Zumal ich nicht so recht weiß, wie ich es optimieren soll. Der Profiler sagt, dass satte 54% der Laufzeit in std::reverse verbracht werden. Eine selbst geschriebene Reverse-Funktion für die Strings ist aber nur wenig schneller :/. Bei Java seh ich ja noch ein, dass da mittels Laufzeitoptimierung noch einiges herausgeholt werden kann. Da kann man schön erkennen, wie der JIT so optimiert ☺
|
coxran
Anmeldungsdatum: 4. März 2008
Beiträge: 11
|
Meine C++ Version, die ich momentan aber leider nicht posten kann (evtl. heut Abend), findet meiner Ansicht nach auch zuviele Zahlen. Zum Beispiel die 89 und die 98, obwohl laut Wikipedia (Lychrel-Zahl) 196 die kleinste Lychrel Zahl ist. Oder sind 100 Iterationen einfach noch nicht genug? Was sind eure ersten Lychrel Zahlen?
|