C Schleifenproblem

[datalukas]

Weiß auch nicht, was ich mir bei der Verdopplung gedacht habe. Ursprünglich wollte ich es auch so machen, bloß dann habe ich wohl bei diesem Punkt nicht ganz mitgedacht.

StringZuArray rufe ich so oft auf, da ich ja sonst die ganzen Array-Werte den Funktionen immer übergeben müsste, wenn ich das jetzt so richtig überblicke. Wenn du so fragst, muss ich das scheinbar nicht tun, aber ich weiß nicht, was ich machen muss, dass jede Funktion von vornherein die jeweiligen Werte des Arrays kennt.

Was die Benennung angeht:
Für mich sieht es ein bisschen komisch aus, ein Substantiv klein zu schreiben und dann alle darauffolgenden Wörter groß. Deswegen habe ich das so gemacht. Falls das ansonsten zu Unklarheiten führt, würde ich das aber auch so machen.

Zeichenweise wäre natürlich nicht nötig/sinnvoll, aber da ich nun mal so angefangen habe, wollte ich zunächst mal so weitermachen. Die anderen Möglichkeiten kann ich ja, wie gesagt, danach ausprobieren.

Mal eine Frage abseits:
Welche IDE ist eigentlich für C am besten? Oder ist auch ein Editor wie Notepad++ und die anschließende manuelle Kompilierung zu empfehlen?

 

[simpsonsfan]

Also die beste Umgebung gibt es wahrscheinlich nicht, alles hat Vor- und Nachteile und letztlich ist das auch Geschamckssache. Eclpise ist sicherlich nicht schlecht. Wenn du Zugriff auf Dreamspark hast, kannst du dort auch Visual Studio kostenlos beziehen. Zum Code schreiben ist eigentlich auch Notepad++ ausreichend (auch wenn einem dann vielleicht Funktionsdefintionen während der Eingabe fehlen), nur dann brauchst du halt noch einen extra Compiler und je nach dem ist es da halt mit Debuggen nicht immer so toll. Ist aber letztlich alles Geschmackssache, finde ich zumindest.

Und wegen dem String zu Array:

	//Umwandlung von String zu zweidimensionalem Array
for(int zeile=0;zeile<=19;zeile++)
{
for(int ziffer = 0; ziffer <= 58; ziffer++)
{
zahlenarray[ziffer][zeile] = zahl[(zeile*59)+ziffer] - '0';
}
}

Das zahlenarray bleibt doch nach einmaliger Ausführung in deinem Speicher erhalten, solange du nichts drüber schreibst, sind da auch immer noch die entsprechenden Werte drin.

 

[datalukas]

Ich hab grade mal zur Abwechslung was anderes gemacht, nämlich ein Programm, die Quadratwurzeln ziehen kann.

#include "stdafx.h"

double wurzelZiehen(double zahl, int genauigkeit)
{
	double teiler, mittelwert;
	teiler = 1;
	mittelwert = 5;
	for(int x=1; x<=genauigkeit; x++)
	{
		mittelwert = (mittelwert + teiler) / 2;
		teiler = zahl/mittelwert;
	}
	return teiler;
}

int main()
{
	double zahl;
	int genauigkeit, test;
	printf("\t Wurzel Ziehen \nWelche Zahl?");
	scanf("%f", &zahl);
	printf("\nWelche Genauigkeit?");
	scanf("%i", &genauigkeit);
	printf("\nDie Wurzel von %f bei %i facher Genauigkeit ist %f \n", zahl, genauigkeit, wurzelZiehen(zahl, genauigkeit));
	scanf("%i", &test);
	return 0;
}

Die Funktion scheint zu passen, aber ausgerechnet unten gibt es Probleme. Diese kann ich mir aber gar nicht erklären.
Wenn ich jetzt z.B. 5 als Zahl eingebe, kommt statt 5 im printf von Zeile 24 -92559604497122535000000000000000000000000000000000000000000000, obwohl ich bei scanf korrekt mit dem & und dem Formatierungszeichen gearbeitet habe. Auch bei printf ist eigentlich alles richtig. Noch komischer wird das Ganze, wenn ich jetzt das erste %f in Zeile 24 durch ein %i austausche. Dadurch ändern sich nämlich auch die anderen Werte.

Entweder ich hab einen totalen Anfängerfehler gemacht oder es stimmt etwas anderes nicht.

 

[Hancock]

http://www.cplusplus.com/reference/cstdio/scanf/
Wie siehts mit einem %fl aus?

 

[datalukas]

Das Gleiche. Sogar, wenn ich irgendeinen Buchstaben, z.B. %q nehme, kommt das raus.

 

[simpsonsfan]

Nicht %fl sonderm %lf für double.

 

[datalukas]

Jetzt gehts. Aber eigentlich müsste doch %f auch gehen, da dieser Platzhalter doch nur die Darstellung beeinflusst, oder?

 

[Hancock]

Nicht nur die Darstellung.
Ein double ist doppelt so groß wie ein float (meistens).
Wenn du printf sagst, dass du ein float übergibst, aber du ein double übergibst, dann macht printf was falsches, weil printf nicht riechen kannst, was du jetzt wirklich gemacht hast. Im Endeffekt nimmt printf die "vordere" Hälfte der double und interpretiert das dann als float, wenn du weitere Parameter übergibst, werden die dann auch alle falsch ausgelesen, weil du um ein float "verrutscht" bist.

 

[geisterfahrer]

Der technische Hintergrund: C ist nicht typsicher bei Funktionen mit variabler Länge der Parameter, geschweige denn kennt C das überladen von Funktionen für unterschiedliche Typen. printf nimmt alle Parameter quasi als void* entgegen und hat deswegen keine Ahnung, wie groß die ihm übergebenen Datentypen sind. Das leitet sich printf erst über die %-Parameter her, also wie bereits erwähnt nimmt der eben die Länge von float an, wenn du sagst es ist float, auch wenn's double ist. Erst mit C++11 wäre es möglich so eine Art von Funktion typsicher zu implementieren (Stichwort: Variadic Templates).

 

[datalukas]

Ich bin gerade bei Problem 12, aber dieser Ansatz würde ewig dauern:

#include "stdafx.h"
int anzahlTeiler(int zahl)
{
	int anzahlTeiler = 0;
	for(int x=zahl; x>0; x--)
	{
		if(zahl%x==0)
			anzahlTeiler++;
	}
	return anzahlTeiler;
}
int main()
{
	int tringular_number, test, zahl;
	zahl = 0;
	tringular_number = 1;
	do
	{
		tringular_number += zahl;
		printf("%i und %i\n", zahl, tringular_number);
		zahl++;
	}
	while(anzahlTeiler(tringular_number) <= 500 && zahl < 100000000); // zahl < 100000000 nur als Test, wie lange das Zählen dauert.
	printf("%i", tringular_number);
	scanf("%i", &test);
	return 0;
}

Nach ein paar Minuten (nachdem die Zahlen auch immer langsamer gestiegen sind, habe ich das Programm dann abgebrochen.

Die einzelnen Bestandteile habe ich stichprobenartig getestet und die funktionieren. Aber es muss doch schneller gehen!

 

[simpsonsfan]

Für die Teiler könntest du z.B. mit der Hälfte der Zahl anfangen, das darüber ist sicherlich keiner (abgesehen vobn der Zahl selbst).
Ausserdem sagt niemand, dass du alle Zahlen durchprüfen musst, wieviele Teiler sie haben. Nähere dich von unten und oben an.
Ausserdem könntest du da später noch Probleme mit der Zahlengröße und int bekommen.

 

[datalukas]

Mit von oben unten annähern meinst du das hier in der Art bei der Funktion anzahlTeiler, oder?:

#include "stdafx.h"
int anzahlTeiler(int zahl)
{
	int x, y;
	int anzahlTeiler = 0;
	for(x=zahl/2, y = 1; x > zahl/4, y <= zahl/4; y++, x--)
	{
		if(zahl%x==0 || zahl%y==0)
			anzahlTeiler++;
	}
	return anzahlTeiler;
}
int main()
{
	int tringular_number, test, zahl;
	zahl = 0;
	tringular_number = 1;
	do
	{
		tringular_number += zahl;
		printf("%i und %i\n", zahl, tringular_number);
		zahl++;
	}
	while(anzahlTeiler(tringular_number) <= 500);
	printf("%i", tringular_number);
	scanf("%i", &test);
	return 0;
}

Welche Zahlen ich nicht durchprüfen muss, wieviele Teiler sie haben, weiß ich jetzt aber nicht. Natürlich fallen Primzahlen raus, aber deren Prüfung würde ja auch ewig dauern. Und kleine Zahlen fallen auch raus, aber da lohnt es sich eh nicht, da v.a. die großen sehr ins Gewicht fallen.

Und ich habe jetzt mal das Programm durchlaufen lassen, bis es bei der Lösung war (76576500), aber die Schleife hat nicht gestoppt. Das kann ich mir nicht erklären, denn, wenn ich die Funktion anzahlTeiler mit diesem Wert aufrufe, wird ein Wert größer 500 ausgegeben (574).

EDIT:
Und bei Aufgabe 10 stehe ich vor einem Problem bzgl. Datentypen:

#include "stdafx.h"
bool ist_primzahl(double zahl)
{
  int teiler= (int) zahl/2;
  while((zahl%teiler!=0) && (teiler >=1))
    teiler--;
  if(teiler==1)
    return true;
  else
    return false;
}

int main(void)
{
	int test;
	double summe = 2;
	double i = 3;
	while(i < 200000)
	{
		if(ist_primzahl(i) == true)
			summe += i;
		i++;
		printf("%lf und %lf\n", i, summe);
	}
	scanf("%i", &test);
	return 0;
}

So bekomme ich immer den Fehler, dass Rest beim Teilen bei Double nicht geht. Hast du einen Tipp, wie ich das sonst lösen soll?
Int geht leider nicht mehr, da die Zahl irgendwann zu groß wird.

 

[Hancock]

Guck mal nach long long, das sollte normalerweise 64 bit sein und damit groß genug.

 

[7H3 N4C3R]

Pre-Inkrement ist schneller als post-inkrement.

++i; ++pal; etc.

Moin moin,

nur ne kurze Anmerkung dazu - das ist schon lange nicht mehr wahr, zumindest bei integrierten Datentypen.

Die zusätzliche Variable wird üblicherweise wegoptimiert, das ist egal. Der große Unterschied bei i++ ist aber, dass im Gegensatz zu ++i der Ausdruck nicht von dem Ergebnis des Inkrements abhängt.
Der Prozessor kann durch out of order execution den increment+store besser in der Pipeline dahin bewegen wo es ihm am besten passt, wenn es keine data dependency gibt. Selbst wenn man die Kosten für eine zusätzliche Variable bei i++ in Form eines Registers bezahlen muss, wiegt die freiere Gestaltung der Pipeline das üblicherweise auf.
Das ist allerdings so eine Mikroptimierung, dass sie in 99,99% aller Fälle keine Auswirkung hat.

Grüße

 

[antred]

nur ne kurze Anmerkung dazu - das ist schon lange nicht mehr wahr, zumindest bei integrierten Datentypen.

Stimmt, aber wie du schon angedeutet hast, kann es bei nicht-integrierten Typen durchaus einen sehr gewaltigen Unterschied machen (je nachdem, wie "teuer" der Kopierkonstruktor des Typs eben ist, bzw. ob es sich der jeweilige Compiler zutraut, die Kopie wegzuoptimieren.

Davon abgesehen, halte ich aber in Schleifenköpfen Präinkrement allein schon deshalb für die besser Wahl, weil es einfach treffender die Intention des Programmierers widerspiegelt. Präinkrement sagt ja schließlich: "Erhöhe x im eins." Postinkrement hingegen sagt aus: "Erhöhe x um eins und gib mir den alten Wert von x." ... in Schleifenköpfen interessiert mich der alte Wert aber meistens nicht die Bohne.

EDIT: Okay, da wir hier von C reden, sind Kopierkonstruktoren natürlich so wie so hinfällig. Hatte ich nicht dran gedacht.

 

[datalukas]

So melde mich mal wieder, nachdem ich nun eine Woche im Urlaub war.
Das Programm wollte ich in der Zwischenzeit etwas optimieren:

#include "stdafx.h"
int primzahlen[1000];
int anzahlPrimfelder = 1;
primzahlen[0] = 2;
bool ist_primzahl(long long zahl)
{
  long long haelfte= zahl/2;
  int potPrimzahl, teiler, x;
  int i = 0;
  teiler = 0;
  /*while((zahl%teiler!=0) && (teiler > 1))
    teiler--;
  if(teiler==1)
    return true;
  else
    return false;*/
  while(primzahlen[i]<haelfte && i<999)
  {
	 if(zahl%primzahlen[i]==0)
		 return false;
	 if(primzahlen[i+1]!=0)
		i++;
	 else
	 {
		x = 0;
		potPrimzahl=primzahlen[i];
		while(potPrimzahl%primzahlen[x]!=0)
		{
			x++;
			if(primzahlen[x] == 0)
			{	
				primzahlen[i+1] = potPrimzahl;
				break;
			}
		}
		i++;
	 }
  }
  if(i >= 999)
  {
	  teiler = primzahlen[i]+2;
	  while(zahl%teiler!=0	&&teiler < haelfte)
		  teiler += 2;
	  if(teiler == haelfte)
		  return true;
  }
  else
	  return true;
}

int main(void)
{
	int test;
	long long summe = 2;
	long long i = 3;
	while(i < 2000000)
	{
		if(ist_primzahl(i) == true)
			summe += i;
		i++;
		printf("%lld und %lld\n", i, summe);
	}
	scanf("%i", &test);
	return 0;
}

Ich habe nun ein array mit Primzahlen erstellt, da ich bei der Primzahlenprüfung ja eigentlich nur durch Primzahlen teilen lassen muss. Bei Bedarf werden neue Primzahlen ausgerechnet, nur wenn die Array-Größe überschritten ist, zähle ich von da an immer zwei rauf. Später will ich das dann mit malloc/realloc lösen.

Allerdings habe ich im Moment ein anderes Problem:
Die Deklarationen der globalen Variablen werden nicht vom Compiler akzeptiert. Die Fehlermeldungen erscheinen mir nicht logisch (alle bzgl. Zeile 4 im Quellcode):

• Zuordnung eines Arrays der konstanten Größe 0 nicht möglich.
• Fehlender Typspezifizierer - int wird angenommen. Hinweis: "default-int" wird von C++ nicht unterstützt (Zur Info: Ich verwende Visual C++ Express)
• 'int primzahlen[1000]': Neudefinition
• 'Initialisierung': 'int' kann nicht in 'int []' konvertiert werden

 

[Hancock]

Du darfst NUR Deklarationen/Definitionen im globalen Kontext schreiben, daher geht Zeile 4 so nicht.
Lösungen:
- int main(){
Primzahlen[0]=2;...
- int primzahlen[1000]={2};

 

[daemon777]

Es kann auch noch ein Probleme geben mit der Abfrage

if(primzahlen[i+1]!=0)

Das Feld Primzahlen wurde niemals mit 0 initialisiert. Das würde ich vorweg noch mit einer Hilfsfunktion machen.

Abgesehen davon halte ich den Ansatz aber nicht für besonders gut, da es wesentlich schneller geht einfach alle Zahlen zu prüfen als jedesmal alle gefundenen Primzahlen gegen die neue Zahl zu checken.

Weiterhin musst du nicht bis zur Hälfte der geprüften Zahl gehen sondern nur bis zur Wurzel. Ist x die gesuchte Zahl und a = Wurzel(x) und alle Zahlen (bzw. Primzahlen) von 2 bis a sind Teilerfremd zu x, dann ist x eine Primzahl, da es keine natürlichen Zahlen b und c gibt, für die gilt, dass b * c = x ergibt.
Oder in einfacher: wenn du alle natürlichen Zahlen bis a = Wurzel(x) gecheckt hast und x keine Quadratzahl ist, dann kann es keinen natürlichen Teiler für x mehr geben. Gäbe es den doch, dann müsste der andere Teiler nämlich kleiner als x sein. Da wir aber bereits alle Zahlen, die kleiner als x sind, bereits geprüft haben wissen wir: es gibt keinen Teiler.

Als ich mal ein bisschen mit dieser Greedy-Variante zum Primzahltest gespielt habe habe ich festgestellt, dass es ein Geschwindigkeitsvorteil sein kann immer die ersten paar Primzahlen fest zu testen und danach wirklich alle Zahlen durchzuprobieren also so etwas wie:

Wenn x%2 == 0
 return false
Wenn x%3 == 0
 return false
Wenn x%5 == 0
 return false

usw ...

Für alle i=7 bis Wurzel(x)+1
 if (x%i == 0 )
   return false

return true

Hier könnte man sich die erste Modulorechnung noch sparen, indem man von Anfang an nur ungerade Zahlen testet.

Primzahlen sind wirklich eine faszinierende Sache

EDIT: Man sollte natürlich bis Wurzel(x)+1 prüfen, da Programmiersprachen wie C hier standardmäßig abrunden.

 

[datalukas]

Hab jetzt mal nach deinem Versuch gearbeitet, nur leider bekomme ich da noch ein falsches Ergebnis (152426755493).

#include "stdafx.h"
#include <stdlib.h>
#include <math.h> 
//int *primzahlen;
//int anzahlPrimfelder = 1;
bool ist_primzahl(long long zahl)
{
  int potPrimzahl, x;
  int i = 0;
  /*while(primzahlen[i] <= sqrt((double)zahl) + 1)
  {
	 if(zahl%primzahlen[i]==0)
		 return false;
	 if(i<anzahlPrimfelder-1)
		i++;
	 else
	 {
		x = 0;
		potPrimzahl=primzahlen[i];
		while(potPrimzahl%primzahlen[x]!=0 && primzahlen[x] <= sqrt((double)primzahlen[x]))
		{
			x++;
		}
		anzahlPrimfelder++;
		i++;
	 }
  }*/
	if(zahl%2==0)
		return false;
	if(zahl%3==0)
		return false;
	if(zahl%5==0)
		return false;
	if(zahl%7==0)
		return false;
	if(zahl%11==0)
		return false;
	if(zahl%13==0)
		return false;
	if(zahl%17==0)
		return false;
	if(zahl%23==0)
		return false;
	for(int i = 23; i<=sqrt((double)zahl)+1;i++)
	{
		if(zahl%i==0)
			return false;
	}
	return true;
}

int main(void)
{
	int test;
	long long summe = 2;
	long long i = 3;
	//primzahlen[0] = 2;
	//primzahlen = (int *) malloc(1000000);
	while(i < 2000000)
	{
		if(ist_primzahl(i) == true)
			summe += i;
		i++;
		printf("%lld und %lld\n", i, summe);
	}
	scanf("%i", &test);
	return 0;
}

Das Auskommentierte enthält den Code für die alternative Lösung, jetzt mit malloc. Wenn ich statt deinem Vorschlag meinen verwende kommt eine Fehlermeldung. Das ist das erste Mal, dass ich mit der dynamischen Speicherverwaltung arbeite, ich habe damit also keine Erfahrung:

Unbehandelte Ausnahme bei 0x771015de in euler2.exe: 0xC0000005: Zugriffsverletzung beim Schreiben an Position 0x00000000.

So nebenbei:
Gibt es eigentlich in Visual C++ oder einer anderen IDE die Möglichkeit, einen Block, der zu weit links oder rechts ist, wie das hier oben im Code teilweise ist, zu verschieben? Wenn ich den Block ausschneide und an einer anderen Stelle wieder einfüge, ist nämlich höchstens die erste Zeile an der richtigen Position, d.h. ich muss alle Zeilen einzeln verschieben.

 

[omaliesschen]

Hi,

wie viele Monate hast Du fürs erstellen des Skripts eingeplant?