Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ]

000
25.07.2002, 18:20 Uhr
NemoEimi

Hi,

da ich jetzt ein paar Tage weg sein werde, und weil die Rätsler unter uns bis Sonntag voraussichtlich sonst in dieser Hinsicht nichts zu tun haben werden, möchte ich dem Forum bis dahin auch noch eine kleine Aufgabe vermachen

.
Hier ist sie:

Zitat:

Man entwickle ein Programm, das feststellt, ob für ein gegebenes n die Gleichung x_1+...+x_n=x_1*...*x_n, alle x_i ganzzahlig und größer als Null, bis auf Umordnen der x_i nur genau eine Lösung hat. Gewonnen hat das Programm, das am schnellsten alle n < 1000 mit eindeutig bestimmter Lösung dieser Gleichung findet.

Grüße,
NemoEimi.

Profil || Private Message || Suche

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

001
25.07.2002, 21:44 Uhr
~PacMan
Gast

Also, ...wenn ich die Aufgabenstellung richtig verstanden habe, dann sollte unterer Code das Problem lösen. Scheinbar gibt es keine ganzzahlige Lösung.

#include <stdio.h>
#include <math.h>

int main()
{
int n = 1;
int i = 0;
double a;
double x;

for(; n < 1000; n++)
{
a = 0;
x = 0;

for(i = 1; i <= n; i++)
a += (double) i;

x = 1/(a - 1) * log(a);

x = exp(x);

if((x * a) == (exp(a * log(x))))
printf("n:%d x:%lf ", n, x);
}
return 0;
}

Profil || Private Message || Suche

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

002
25.07.2002, 21:51 Uhr
virtual
Sexiest Bit alive
(Operator)

Doch: Für jdes n>1 gibt es mind. eine Lösung, und zwar derart, daß sowohl summe alsauch produkt 2*n ergeben:

Code:

2*n = 1 + 1 +1 ...(n-2 mal) ... +1 +2 +n

Die Frage ist, ob es Zahlen mit mehr als einer Lösung gibt

--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

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

003
26.07.2002, 08:11 Uhr
virtual
Sexiest Bit alive
(Operator)

Ich hab nochmal drüber nachgedacht. Ich glaube es gilt folgendes: es kommen nur die Zahlen in Frage, deren primfaktorzerlegung aus genau zwei Zahlen besteht wobei die Summe der beiden Faktoren kleiner oder gleich N sein muß.
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

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

004
26.07.2002, 09:51 Uhr
Bruder Leif
dances with systems
(Operator)

Hab ich schon erwähnt, daß ich mich gerade auf die Matheklausur vorbereite und noch knapp 1800 Seiten Papula vor mir hab? AAAAARGH! *durchdreh* *hüpf* *spring* ;-)
--
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

005
26.07.2002, 10:39 Uhr
virtual
Sexiest Bit alive
(Operator)

Hm, da brauchen wir aber langsame Rechner, um die Geschwindigkeiten zu vergleichen (user Time liegt bei 0.01 Sekunden!). Das Programm gibt nur die X_i aus, die !=1 sind. Insesamt gibt es fuer n = 1000 299 eindeutige Kombinationen.
Kann natuerlich auch sein, dass ich mich vertan habe...

C++:

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

#define INC_SIZE 10

unsigned* squares = NULL;
unsigned* primes = NULL;
unsigned max_primes = 0;
unsigned current_primes = 0;

void
realloc_primes()
{
    unsigned new_len = max_primes+INC_SIZE;
    unsigned* tmpp = realloc(primes, new_len*sizeof(unsigned));
    unsigned* tmps = realloc(squares, new_len*sizeof(unsigned));

    if (NULL == tmpp || NULL == tmps)
    {
        if(NULL!=primes) free(primes);
        if(NULL!=tmpp) free(tmpp);
        if(NULL!=tmps) free(tmps);
        fprintf(stderr, "*** ERROR: no memory\n");
        exit(EXIT_FAILURE);
    }
    primes = tmpp;
    squares = tmps;
    max_primes = new_len;
}

void
init()
{
    realloc_primes();
    squares[current_primes] = 4;
    primes[current_primes++] = 2;
    squares[current_primes] = 9;
    primes[current_primes++] = 3;
}

void
get_primes(
    unsigned limit)
{
    unsigned n;
    unsigned k;
    int noprime = 0;
    for(n=5; n<limit; n+=2)
    {
        if(1>max_primes-current_primes) realloc_primes();
        for(k=1; squares[k]<=n; ++k)
        {
            if (n%primes[k]==0)
            {
                noprime = 1;
                break;
            }
        }
        if (!noprime)
        {
            squares[current_primes] = n*n;
            primes[current_primes++] = n;
        }else
        {
            noprime = 0;
        }
    }
}

void
print_solutions(
    unsigned limit)
{
    unsigned j;
    unsigned k;
    unsigned l;

    for(j=0; j<current_primes; ++j)
        for(k=0; k<=j; ++k)
            if (primes[k]*primes[j]<=limit)
            {
                printf("%8u = %u*%u\n", primes[k]*primes[j], primes[k], primes[j]);
            }
}

int main(
    int argc,
    char** argv)
{
    unsigned n = atoi(argv[1]);
    init();
    get_primes(n);
    print_solutions(n);
}

--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Dieser Post wurde am 26.07.2002 um 11:11 Uhr von virtual editiert.

Profil || Private Message || Suche

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

006
26.07.2002, 16:37 Uhr
~Johannes
Gast

Nach print_solutions fehlt natuerlich noch ein

C++:

free(primes);

Profil || Private Message || Suche

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

007
27.07.2002, 17:16 Uhr
~NemoEimi
Gast

Hi,

Zitat:

virtual postete
Ich hab nochmal drüber nachgedacht. Ich glaube es gilt folgendes: es kommen nur die Zahlen in Frage, deren primfaktorzerlegung aus genau zwei Zahlen besteht (...).

Ich weiss zwar nicht, wie Du das beweisen willst, aber imho ist 2*2*3*37=444 ein Gegenbeispiel.

Grüße,
NemoEimi.

Profil || Private Message || Suche

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

008
27.07.2002, 17:34 Uhr
virtual
Sexiest Bit alive
(Operator)

Zitat:

~NemoEimi postete
Hi,

[quote]virtual postete
[i]Ich hab nochmal drüber nachgedacht. Ich glaube es gilt folgendes: es kommen nur die Zahlen in Frage, deren primfaktorzerlegung aus genau zwei Zahlen besteht (...).

Ich weiss zwar nicht, wie Du das beweisen willst, aber imho ist 2*2*3*37=444 ein Gegenbeispiel.

Grüße,
NemoEimi.[/i][/quote]

Hm. Dann habe ich die Aufgabenstellung nicht kapiert:
Also bei

Code:

2*2*3*37=444

Scheint mit das vorgegebene N=404 zu sein, wobei X_1=37, X_2=3, X_3=2 , X_4=2 und alle übrigen X_i = 1.
Dann ist neben Deiner Loesung aber auch

Code:

2*404 = 808

Für N=404 eine Lösung, mit X_1=404, X_2=2, und allen übrigen X_i = 1

Könntest Du bitte die Aufgabenstellung so formulieren, daß sogar ich sie verstehe?

Vielleich genügt ja auch einfach mal die Aussage, warum die Gleichung oben eine der gesuchten Zahlen ist (also: wie groß ist das N Deiner Meinung nach und warum gibt es Deiner Meinung nach zu diesem N nur diese eine Lösung)

--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

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

009
27.07.2002, 17:55 Uhr
~NemoEimi
Gast

Zitat:

virtual postete
Hm, da brauchen wir aber langsame Rechner, um die Geschwindigkeiten zu vergleichen (user Time liegt bei 0.01 Sekunden!).

Schnell ist das Programm, aber im Fall n=9 finde ich beispielsweise die nichttriviale Lösung (1 1 1 1 1 1 1 3 5), und umgekehrt finde ich in Deiner Liste nicht alle Fälle, in denen die Lösung eindeutig bestimmt ist.

Grüße,
NemoEimi.

Profil || Private Message || Suche

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

Seiten: > 1 < [ 2 ] [ 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: