4. Verständnis Frage

Verständnis Frage

  • C
     

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

/* Uncomment the following line to use 'long long' integers */
#define HAS_LONG_LONG

#ifdef HAS_LONG_LONG
#define mul_mod(a,b,m) (( (long long) (a) * (long long) (b) ) % (m))
#else
#define mul_mod(a,b,m) fmod( (double) a * (double) b, m)
#endif

/* return the inverse of x mod y */
int inv_mod(int x,int y) {
    int q,u,v,a,c,t;
    u=x; v=y; c=1; a=0;
    do {
        q=v/u; t=c;
        c=a-q*c; a=t;
        t=u;
        u=v-q*u;
        v=t;
    } while (u!=0);
    a=a%y;
    if (a<0) a=y+a;
    return a;
}

/* return (a^b) mod m */
int pow_mod(int a,int b,int m) {
    int r,aa;
    r=1; aa=a;
    while (1) {
        if (b&1) r=mul_mod(r,aa,m);
        b=b>>1;
        if (b == 0) break;
        aa=mul_mod(aa,aa,m);
    }
    return r;
}

/* return true if n is prime */
int is_prime(int n) {
    int r,i;
    if ((n % 2) == 0) return 0;
    r=(int)(sqrt(n));
    for(i=3;i<=r;i+=2) if ((n % i) == 0) return 0;
    return 1;
}

/* return the prime number immediatly after n */
int next_prime(int n) {
    do {
        n++;
    } while (!is_prime(n));
    return n;
}

int main(int argc,char *argv[]) {
	int av,a,vmax,N,n,num,den,k,kq,kq2,t,v,s,i;
    double sum;

    if (argc<2 || (n=atoi(argv[1])) <= 0) {
        printf("Provide the number of digits!");
        exit(1);
    }
    N=(int)((n+20)*log(10)/log(2));
    sum=0;
    for(a=3;a<=(2*N);a=next_prime(a)) {
		vmax=(int)(log(2*N)/log(a));
		av=1;
		for(i=0;i<vmax;i++) av=av*a;
		s=0; num=1; den=1; v=0; kq=1; kq2=1;
		for(k=1;k<=N;k++) {
			t=k;
			if (kq >= a) {
				do {
					t=t/a; v--;
				} while ((t % a) == 0);
				kq=0;
			}
			kq++; num=mul_mod(num,t,av); t=(2*k-1);
			if (kq2 >= a) {
				if (kq2 == a) {
					do {
						t=t/a;
						v++;
					} while ((t % a) == 0);
				}
				kq2-=a;
			}
			den=mul_mod(den,t,av);
			kq2+=2;
			if (v > 0) {
				t=inv_mod(den,av);
				t=mul_mod(t,num,av);
				t=mul_mod(t,k,av);
				for(i=v;i<vmax;i++) t=mul_mod(t,a,av);
				s+=t;
				if (s>=av) s-=av;
			}
		}
		t=pow_mod(10,n-1,av);
		s=mul_mod(s,t,av);
		sum=fmod(sum+(double) s/ (double) av,1.0);
	}
	printf("Decimal digits at position %d: %09d\n",n,(int)(sum*1e9));
	return 0;

    }

    Hallo,

    ich versuche verwzeifelt das Programm zu verstehen.
    Ich muss das Programm in 2 Wochen vorstellen.
    Ich weiß, dass ich noch eine Zahl einlesen lass muss, aber da ich das Programm nicht versteh, weiß ich nicht wo ich die Zahl einlese und an was ich die Zahl binden muss.
    Kann jemand vllt erklärungen hinter den Zeilen schreiben oder mir versucht die verschiedenen Funktionen näher zu bringen?

    Vielen Dank

    0
  • S

    chin842 schrieb:

    Kann jemand vllt erklärungen hinter den Zeilen schreiben oder mir versucht die verschiedenen Funktionen näher zu bringen?

    geht's ja noch? Wenn du 5€ pro Zeile zahlst, dann würde ich es machen.

    Aber wie wäre es, wenn du es selber versuchst, Stück für Stück die Software zu analysieren? Du kannst sogar was dabei lernen 🙂 oder gehörst du zur Fraktion "bloß nicht denken/arbeiten"???

    Stell konkrete Fragen, zeig uns, dass du Eigeninitiative hast, sonst wirst du keine Hilfe bekommen.

    0
  • _

    Nutze den Debugger und gehe Schritt für Schritt durch!

    0
  • ?

    Hallo!

    chin842 schrieb:

    Ich weiß, dass ich noch eine Zahl einlesen lass muss, aber da ich das Programm nicht versteh, weiß ich nicht wo ich die Zahl einlese und an was ich die Zahl binden muss.

    Das Programm ist so geschrieben, das diese Zahl an der Eingabeaufforderung übergeben wird. Diese Zahl, ist eine ganze Zahl > 0 und wird der Variable n durch die Konvertierungsfunktion atoi zugewiesen.
    Zum Studieren der Funktionen kannst du die Zeilen 64 bis 67 auskommentieren und n = 1, n = 2, ... etc. setzen.

    int main(int argc,char *argv[]) { 
    int av,a,vmax,N,n,num,den,k,kq,kq2,t,v,s,i; 
    double sum; 

/*
	if (argc<2 || (n=atoi(argv[1])) <= 0) { 
        printf("Provide the number of digits!"); 
        exit(1); 
    } 
*/	
	n = 1; // Z.B. hier n = 2, n = ... durchtesten
...

    Gruß,
    B.B.

    0
  • ?

    chin842 schrieb:

    /* return true if n is prime */
int is_prime(int n) {
    int r,i;
    if ((n % 2) == 0) return 0;
    r=(int)(sqrt(n));
    for(i=3;i<=r;i+=2) if ((n % i) == 0) return 0;
    return 1;
}

    hab in der 6. klasse nicht gut aufgepasst aber du testest da unnötig häufig zahlen die es eh nie sein können z.b. 9,15... könnt natürlich auch sein das ich mich da täusch. es gibt auch absolut effiziente verfahren prims zu suchen und das native testen ist eines der einfachsten (langsamsten)

    int is_prime(int n) {
	int i=5;
	int r=(int)sqrt((double)n);

	if(n==2
	|| n==3)
	  return 1;

	if(n==1
	|| (n % 2) == 0
	|| (n % 3) == 0)
	  return 0;

	for(;i<=r;i+=6){
	  if((n % i) == 0) return 0;
	  if((n % (i+2)) == 0) return 0;
	}

	return 1;
}

    natürlich auch nativ und buggy 😞

    lg lolo

    0
  • C

    So, dann mal soweit ich weiß

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

/* Uncomment the following line to use 'long long' integers */
#define HAS_LONG_LONG

#ifdef HAS_LONG_LONG
#define mul_mod(a,b,m) (( (long long) (a) * (long long) (b) ) % (m))
#else
#define mul_mod(a,b,m) fmod( (double) a * (double) b, m)
#endif

    was ist Has_long_long ?

    /* return the inverse of x mod y */
int inv_mod(int x,int y) {
    int q,u,v,a,c,t;
    u=x; v=y; c=1; a=0;
    do {
        q=v/u; t=c;
        c=a-q*c; a=t;
        t=u;
        u=v-q*u;
        v=t;
    } while (u!=0);
    a=a%y;
    if (a<0) a=y+a;
    return a;
}

    Es werden 2 Zahlen übergeben x und y. x wird u und y wird v zugeordnet.c=1 und a=0. q=v/u ist klar. c(1)wird t zugeordnet, jetzt ist t=1. dann wieder ne rechensache, c neu definiert. t(1) wird a zugeordnet. u wird t zugeordnet. u wird neu definiert. t(altes U) wird v zugeordnet.
    das macht er solange wie u nicht 0 ist.
    a=a modulo y
    die if anweisung ist klar.
    die do while schleife... macht er nur, was zwischen do und while steht immer, oder auch das a=a&y jedes und überprüft a<0 ?

    /* return (a^b) mod m */
int pow_mod(int a,int b,int m) {
    int r,aa;
    r=1; aa=a;
    while (1) {
        if (b&1) r=mul_mod(r,aa,m);
        b=b>>1;
        if (b == 0) break;
        aa=mul_mod(aa,aa,m);
    }
    return r;
}

    Es werden 3 Zahlen übergeben, r=1 wert a wird aa zugeordnet.
    while (1) versteh ich nicht....
    if (b&1) versteh ich auch nicht..
    r=mul_mod wurde ja bei define definiert was es dann macht.
    dann wird b um 1 verschoben
    wenn b=0 wird pausiert
    mul_mod ist ja oben auch definiert
    aber was wird hier mit einer zahl gemacht?

    /* return true if n is prime */
int is_prime(int n) {
    int r,i;
    if ((n % 2) == 0) return 0;
    r=(int)(sqrt(n));
    for(i=3;i<=r;i+=2) if ((n % i) == 0) return 0;
    return 1;
}

    es wird eine Zahl übergeben und dann geteste ob sie durch 2 teilbar ist, wenn ja, wird ne 0 zurückgegeben.
    r=(int)(sqrt(n)); den ausdruck versteh ich nicht
    wird da einfach das interger quadrat von der übergeben zahl gebildet?
    dann wird i in i+2 schritten immer geschaut ob die zahl teilbar ist, wenn ja 0, wenn sie ne prim ist ne 1

    /* return the prime number immediatly after n */
int next_prime(int n) {
    do {
        n++;
    } while (!is_prime(n));
    return n;
}

    hier versteh ich nicht was gemacht wird.
    es wir ne zahl übergeben und sie wird erhöht um 1, solang n ne primzahl ist???

    int main(int argc,char *argv[]) {
    int av,a,vmax,N,n,num,den,k,kq,kq2,t,v,s,i;
    double sum;

    ist klar.

    if (argc<2 || (n=atoi(argv[1])) <= 0) {
        printf("Provide the number of digits!");
        exit(1);
    }

    den ausdruck kapier ich nicht, hab die funktion atoi hier schon nachgelesen aber nicht wirklich verstanden.
    argc<2 aber argc ist doch gar nicht vergeben?

    N=(int)((n+20)*log(10)/log(2));
    sum=0;

    N=(int) bedeutet es, dass das ergebniss von ((n+20)*log(10)/log(2)); als INT zahl dargestellt wird, oder was bedeutet das (int)?

    for(a=3;a<=(2*N);a=next_prime(a)) {
        vmax=(int)(log(2*N)/log(a));

    geht von 3 los bis 2*n und schrittgröße sind primzahlen von n???

    av=1;
        for(i=0;i<vmax;i++) av=av*a;
        s=0; num=1; den=1; v=0; kq=1; kq2=1;
        for(k=1;k<=N;k++) {
            t=k;
            if (kq >= a) {
                do {
                    t=t/a; v--;
                } while ((t % a) == 0);
                kq=0;
            }
            kq++; num=mul_mod(num,t,av); t=(2*k-1);
            if (kq2 >= a) {
                if (kq2 == a) {
                    do {
                        t=t/a;
                        v++;
                    } while ((t % a) == 0);
                }
                kq2-=a;
            }
            den=mul_mod(den,t,av);
            kq2+=2;
            if (v > 0) {

    kapier ich teilweise, aber sind ja eigentlich nur schleifen

    t=inv_mod(den,av);
                t=mul_mod(t,num,av);
                t=mul_mod(t,k,av);
                for(i=v;i<vmax;i++) t=mul_mod(t,a,av);
                s+=t;
                if (s>=av) s-=av;
            }
        }
        t=pow_mod(10,n-1,av);
        s=mul_mod(s,t,av);
        sum=fmod(sum+(double) s/ (double) av,1.0);
    }
    printf("Decimal digits at position %d: %09d\n",n,(int)(sum*1e9));
    return 0;

    verstehe nicht, warum t lauter verschiedene sachen zugeordnet werden, verfallen die nicht alle, bis auf das letzte?

    Vielen Dank für Hilfe!!!!

    0
  • ?

    chin842 schrieb:

    while (1) versteh ich nicht....

    das wiederholt endlos

    chin842 schrieb:

    if (b&1)

    ist sowas wie if(b%2) und testet auf gerade/ungerade

    chin842 schrieb:

    int next_prime(int n) {
    do {
    n++;
    } while (!is_prime(n));
    return n;
    }

    sucht die nächste primzahl... die funktion kannst auch in die tonne kloppen da auf eine prim nie noch eine prim folgt die einzige ausnahme bildet 2,3.

    chin842 schrieb:

    int next_prime(int n) {
    if(n==2)
    return 3;

    do {
    n+=2;
    } while (!is_prime(n));
    return n;
    }

    wenn die verwendeten funktionen schon müll sind wirst sicher verstehen das ich mir das gewurstle in der main nicht eingeb 😉

    lg lolo

    0
  • ?
     

    int next_prime(int n){
  if(n>2){
    if(n&1==0)
      n--;
    do{
      n+=2;
    }while(!is_prime(n));
  }
  else if(n<2)
    n = 2;
  else
    n = 3;
  return n;
}

    machen wir den müllberg noch ein bischen größer 😉

    btw. wo wir schon dabei sind was geht eigentlich mit negativen primzahlen 😃

    0
  • C
     

    if (argc<2 || (n=atoi(argv[1])) <= 0) {
        printf("Provide the number of digits!");
        exit(1);

    was genau macht die funktion.
    wenn ich das nicht ausklammer und z.b
    n=5; passiert trotzdem nix

    wenn ich das ausklammer, dann n=5; funktioniert die ganze Funktion.
    was genau macht des atoi?

    0
  • ?

    atoi() konvertiert ein string in ein int

    int n = atoi("123");
if(n==123)
  printf("alles klar?");

    🙂

    lg lolo

    0
  • _

    chin842 schrieb:

    was genau macht des atoi?

    Wenn du nicht weißt, was eine Funktion macht: einfach in die Doku schauen, die verrät's dir.

    http://cplusplus.com/reference/clibrary/cstdlib/atoi/

    0
  • ?

    Irgend wie habe ich den Verdacht der Beitragsersteller möchte auch folgendes wissen:
    http://www.c-plusplus.net/forum/viewtopic-var-t-is-197811.html

    MfG f.-th.

    0
  • C

    also muss ich ein n über scanf einlesen und dann

    atoi("n"); machen?

    0
  • ?

    chin842 schrieb:

    also muss ich ein n über scanf einlesen und dann

    atoi("n"); machen?

    omg 🙄

    am besten du suchst dir ne andere beschäftigung 😞

    0
  • ?

    chin842 schrieb:

    if (argc<2 || (n=atoi(argv[1])) <= 0) {
        printf("Provide the number of digits!");
        exit(1);

    was genau macht die funktion.
    wenn ich das nicht ausklammer und z.b
    n=5; passiert trotzdem nix

    wenn ich das ausklammer, dann n=5; funktioniert die ganze Funktion.
    was genau macht des atoi?

    Das ist eine if Abfrage mit zwei Bedingungen. Da die beiden Bedingungen oderverknüpft sind, wird die if Anweisung ausgeführt, wenn eine der beiden Bedingungen wahr ist.
    Wenn du also n = 5 setzt, ist argc < 2 ( wenn du keinen Parameter an der Eingabeaufforderung übergibst ), somit ist eine Bedingung wahr und das Programm wird mit der Ausgabe "Provide the number of digits!" beendet.

    0
  • ?

    chin842 schrieb:

    argc<2 aber argc ist doch gar nicht vergeben?

    Doch, das ist ein Parameter der main Funktion.

    0
  • _

    chin842 schrieb:

    also muss ich ein n über scanf einlesen und dann

    atoi("n"); machen?

    Hier übergibst du atoi einen String mit dem Inhalt 'n' (und '\0'). Das hat nix mit der eventuell in deinem Code vorhandenen Variable n zu tun...

    0
  • C

    ah okay 🙂
    aber wenn ich jetzt ne zahl einlesen lasse, muss ich des dann an n binden und dann die zahl atoi zuordnen lassen oder direkt an atoi einlesen lassen?

    0
  • _

    chin842 schrieb:

    ah okay 🙂
    aber wenn ich jetzt ne zahl einlesen lasse, muss ich des dann an n binden und dann die zahl atoi zuordnen lassen oder direkt an atoi einlesen lassen?

    Du sprichst in Rätseln! Formulier die Frage mal so, dass man wenigstens erahnen kann, was du wissen willst. 😃

    0
  • C

    okay.

    das Programm muss ja noch so ergänzt werden, dass eine Zahl eingelesen werden kann bzw. im Dos fenster eingegeben werden kann.
    an was binde ich diese Zahl und an welche stelle gehört diese Funktion hin?
    an n binden?

    0
Anmelden zum Antworten