Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 <

000
25.02.2004, 11:16 Uhr
NemoEimi

Huhu,

da in letzter Zeit nicht viel passiert hier in der Rätselecke, stelle ich mal wieder eins ein

:

Wir definieren eine Folge a_n natürlicher Zahlen iterativ durch folgende Vorschrift:

a_0 := a,
a_{n+1} := a_n / 2, falls a_n gerade ist,
a_{n+1} := 3*a_n - 1, falls a_n ungerade,

wobei a eine natürliche Zahl ist. Diese Folge nennen wir 3n-1 - Folge zum Startwert a.
Die 3n-1 - Folge zum Startwert 5 beispielsweise fängt also so an:

5, 14, 7, 20, 10, 5, 14, ......

Offenbar ist 20 der größte Wert, der von der 3n-1 - Folge zum Startwert 5 angenommen wird. Falls die 3n-1 - Folge zum Startwert a einen größten Wert hat, nennen wir den Mx(a) oder auch den Rekord von a; es gilt also hier Mx(5) = 20. Nimmt die 3n-1 - Folge zum Startwert a keinen größten Wert an, dann setzen wir Mx(a) = 0.
Besitzt eine natürliche Zahl n die Eigenschaft, daß Mx(n) > Mx(m) ist für alle natürlichen Zahlen m mit m < n, dann heisst n ein Rekordhalter .
Zu schreiben ist nun ein Programm, das alle Rekordhalter zwischen 1 und einer vom Benutzer vorzugebenden Zahl < 2^32 ermittelt und zusammen mit den dazugehörigen Rekorden ausgibt.
Es gewinnt das schnellste Programm. Ein Lob für besondere Leistungen beim Golfen gibt es zusätzlich für die kürzeste korrekte Lösung

.

Grüße,
Nemo

Dieser Post wurde am 25.02.2004 um 11:18 Uhr von NemoEimi editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
25.02.2004, 12:14 Uhr
Bruder Leif
dances with systems
(Operator)

Collatz-Folgen? So was hatten wir mal irgendwann in Mathe 3... damals sollten wir den Startwert (bis max. 10000) ermitteln, bei dem die Folge möglichst lang wird, bis sie periodisch wird

Wäre eine nette Erweiterung...
--
Mit 40 Fieber sitzt man nicht mehr vor dem PC.
Man liegt im Bett.
Mit dem Notebook.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
25.02.2004, 14:21 Uhr
~Der_Grosse_Unbekannte
Gast

C++:

#include <stdio.h>
#include <stdlib.h>

#define max(a,b) ((a)<(b)? (b):(a))

int main()
{
    unsigned N = 0;
    unsigned* rekordhalter = NULL;
    unsigned i = 0;

    printf("Bitte N eigeben: ");
    fflush(stdout);
    if (1 != scanf("%u", &N) || N<1)
    {
        fprintf(stderr, "N muß >= 1 sein!\n");
        return 1;
    }

    rekordhalter = malloc((1+N)*sizeof(unsigned));
    if (NULL == rekordhalter)
    {
        fprintf(stderr, "Nicht genug Speicher!\n");
        return 2;
    }

    rekordhalter[++i] = 2;

    while(i++<N)
    {
        unsigned n = rekordhalter[i] = i;

        if (n%2)
        {
            do
            {
                rekordhalter[i] = n = 3*n-1;
                while(!(n%2)) n/=2;
            } while(n>i);
        }else
        {
            while(!(n%2)) n/=2;
            rekordhalter[i] = max(rekordhalter[i], rekordhalter[n]);
        }
    }

    for(i=1; i<=N; ++i)
    {
        printf("Recordhalter[%10u] = %10u\n", i, rekordhalter[i]);
    }

    free(rekordhalter);
}

Dieser Post wurde am 25.02.2004 um 16:49 Uhr von Pablo editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
25.02.2004, 14:31 Uhr
Windalf
Der wo fast so viele Posts wie FloSoft...
(Operator)

hmm ohne jetzt ohne das ich die zeit dazu habe, vielleicht folgenden gedanken weiterzuspinnen

man könnte versuchen das in etwa so zu machen
a(n,a0)=(x*a0 +y)/z -s/t

wobei x dann pow(3,(n+1)/2) wäre
y=x/3
z=pow(2,n/2);
t=z/2
s.... hab ich mir noch nicht weiter den kopf zerbrochen

mit der explizieten formel die man dann bekommt könnte man vielleicht sowas wie limes sup oder so machen und versuchen das ergebnis expliziet vom startwert a0 herauszubekommen.
In dem Fall wäre dann die implementierung äussert performant und beim golfen vermutlich nicht zu schlagen...
--
...fleißig wie zwei Weißbrote

Dieser Post wurde am 25.02.2004 um 14:32 Uhr von Windalf editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ Rätselecke ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: