C Schleifenproblem

[simpsonsfan]

Ja schon. Auf jeden Fall lässt es sich auch elegant mit For-Schleifen lösen. Und dann noch eins, Alternative zu zahl = zahl - 1 ist zahl -= 1 - ist kürzer.

 

[Dese]

--zahl

ist noch kürzer

 

[datalukas]

So sieht main() jetzt aus:

int main()
{
	int test;
	int zahl1, zahl2;
	int palindrome[999*999];
	int x, max;
	x = 0;
	max = 0;
	zahl1 = zahl2 = 999;
	for(zahl1 = 999; zahl1 <=100; zahl1--)
	{
		if(funktion(zahl1 * zahl2 == 0))
		{
			palindrome[x] = zahl1 * zahl2;
			x++;
		}	
		for(zahl2 =999; zahl2 <=100; zahl2--)
		{
			if(funktion(zahl1 * zahl2 == 0))
			{
				palindrome[x] = zahl1 * zahl2;
                                x++;
			}	
		}
	}
	for(int i = 1; i >= x; i++)
	{
		if(palindrome[i] > max)
		{
			max = palindrome[i];
		}
	}
	printf("Das groesste Palindrom ist %i", max);
	scanf("%i",&test);
	return 0;
}

Allerdings kommt immer die Fehlermeldung:

Unbehandelte Ausnahme bei 0x776915de in euler.exe: 0xC00000FD: Stack overflow.

 

[Darlis]

Die erste for-Schleife wird nie ausgeführt, schau' dir die Bedingung nochmal genau an.
Die zweite Schleife wird damit zur Endlos-Schleife, da x = 0.

 

[Dese]

du meinst die dritte wird zur entlosschleife. die zweite wird ebenfalls nie ausgefüht

bin mir aber noch nicht klar, warum er nen stackoverflow bekommt. muss grad mal genauer schaun.

Ergänzung (26. April 2013)

mal paar verbesserung:
1. zeile 9 kannst du löschen.
2. zeilen 12-16 ebenfalls.
3. die bedingungen in den forschleifen müssen bei allen drei umgedreht werden.
4. bennen deine variable "x" so, dass man versteht wofür sie ist. soll sie die anzahl der gefundenen palindrome darstellen?
5.

if(funktion(zahl1 * zahl2 == 0))

ich weiß zwar nicht was "funktion" machen soll (wähle sinnvolle namen!!!), aber ich glaube du meinst das:

if(funktion(zahl1 * zahl2) == 0)

das andere macht null sinn, da zahl1 * zahl2 NIE 0 ergibt (in deinem fall).

Ergänzung (26. April 2013)

generell: da du offenbar wirklich noch ein blutiger anfänger bist, schreibe dir in worten, aber präzise auf, was du da machen willst (quasi als pseudo code). und dann gieß das in programmcode. dann fällt dir sowas vieleicht von alleine auf.

 

[antred]

int palindrome[999*999]; ist vielleicht einfach ein wenig groß für ein auf dem Stack liegendes Array.

 

[Dese]

hmm, in der tat könnte das sein

hab darüber gar nicht mehr nachgedacht, als ich über den ganzen anderen kram gestolpert bin.

edit: wenn ich mich nicht irre, ist nicht die standardgröße meist bei 2 MB (pro funktionsaufruf) ?

 

[simpsonsfan]

Ok, der Tipp von wegen das Array so groß zu machen, das auf jeden Fall alles reinpasst, war vllt. ein bisschen unglücklich. Wenn du dir jetzt die Häufigkeit von den Palindromen mal anschaust, dann merkst du, dass es da so viele gar nicht gibt. Und mit der Abschätzung von kuddlmuddl

3*9 < 4*8 < 5*7 < 6*6 obwohl 3+9 = 4+8 = 5+7 = 6+6.

merkst du, dass du längst nicht bis 100 runter musst. Ich sage dir jetzt aber auch einfach mal, ohne was vom Code zu verraten, dass du hier tatsächlich die größte Zahl als erste erhälst, beim Runterzählen.

 

[datalukas]

So jetzt hats geklappt.

#include "stdafx.h"

int istPalindrom(int zahl)
{
	unsigned char stelle[6];
	stelle[5] = zahl % 1000000 / 100000;
	stelle[4] = zahl % 100000 / 10000;
	stelle[3] = zahl % 10000 / 1000;
	stelle[2] = zahl % 1000 / 100;
	stelle[1] = zahl % 100 / 10;
	stelle[0] = zahl % 10;
	if(stelle[5] == stelle[0] && stelle[4] == stelle[1] && stelle[3] == stelle[2])
		return 1;
	else
		return 0;
}
int main()
{
	int test;
	int zahl1, zahl2;
	int palindrome[10000];
	int palindromanzahl, max;
	palindromanzahl = 0;
	max = 0; 
	for(zahl1 = 999; zahl1 >=100; zahl1--)
	{
		for(zahl2 =999; zahl2 >=100; zahl2--)
		{
			if(istPalindrom(zahl1 * zahl2) == 1)
			{
				palindrome[palindromanzahl] = zahl1 * zahl2;
				palindromanzahl++;
			}	
		}
	}
	for(int i = 1; i < palindromanzahl; i++)
	{
		if(palindrome[i] > max)
		{
			max = palindrome[i];
		}
	}
	printf("Das groesste Palindrom ist %i", max);
	scanf("%i",&test);
	return 0;
}

Damit ihr zufrieden seit, hab ich jetzt auch allem eindeutige Namen gegeben. Nur bei der Funktion habe ich jetzt keine Schleife eingefügt.
@simpsonfan Wenn die erste das Größte wäre, dann hätte aber bei mir eigentlich auch der erste Anlauf mit den while-Schleifen funktionieren müssen, der hat aber nicht die Größe geliefert.

Mal ne Frage aus Interesse:

Wenn beim Programmieren von Speicher und Register die Rede ist, ist dann damit der RAM oder der Cache der CPU gemeint. Hier liest man da nur was vom Code-Speicher:
http://openbook.galileocomputing.de...ng_001.htm#mj8d062301d2449b13710f1484d499cd9b

Insgesamt kann man beim Programmieren halt so viele Fehler machen und Sachen übersehen und vergessen, dass sowas mir nunmal passiert, da ich auch leichter etwas mal vergesse.
Ich hoffe mal, das wird mit der Zeit besser (ich hab mit C erst vor kurzem wieder angefangen und es eigentlich noch nie wirklich intensiv behandelt, wie ich schon sagte).

 

[simpsonsfan]

Das kommt natürlich drauf an, wie man runterzählt.Mit deinem jetztigen Code mit den zwei For-Schleifen, müsste 993 * 913 als erstes auftauchen.
In deinen while Schleifen gehst du die für zahl2 die zahlen 998, 997, 996, 995 durch und dann findest du das erste Palindrom. Das ist da anders. PS: Der Vollständigkeit halber: 999 gehst du dort gar nicht durch, das hätte gefehlt.
Edit: Ok, da du auch hier bis auf die 100 runter gehst, kommt es wohl doch auch so raus wie beim ersten mal.

 

[Hancock]

Zu deiner Speicherfrage:

Dein Rechner hat einfach gesagt erstmal einfach RAM, also Speicher.
Diesen organisiert man oft in einer Struktur, die ähnlich! ist wie in deinem Link angegeben (Windows kennt z.B. gut Drölfzillionen Möglichkeiten, Heapspeicher anzufordern).
Register ist eine ganz andere Baustelle, die dich in deinem aktuellen Lern-Stadium nicht zu interessieren hat (Register werden von der Rechenarchitektur vorgegeben).

Zur Einteilung:
Code-Speicher: Ausführen und Lesen, alles andere ist ein Fehler, normalerweise muss man nicht direkt drauf zugreifen (also für dich unwichtig)
Daten-Speicher: globale Variablen
Stack: Darauf sind alle lokalen Variablen (wenn du eine Funktion aufrufst, dann reserviert sie sich neuen Speicher auf dem Stack, daher führt ein "zu oft Aufrufen" von Funktionen zum Stack-Overflow (oder wenn eine einzige Funktion zu viel will (z.B. mit int Array[1024][1024] sind gleich mal 4 MB belegt))).
Heap: Alles was nicht auf den Stack passt oder dessen Größe erst zur Ausführungszeit bekannt ist (das sind z.B. die 2 GB freien Speicher unter 32 bit).

Zu deinem Programm:
Dir ist bewusst, dass du direkt bei deinem ersten Fund die Ausgabe machen könntest und dann return aufrufen könntest

for(...){
for(...){
if(Palindrom){
printf("Palindrom ist ",x);
return 0;
}
}
}

Wenn du deine Schleife beibehalten willst:
Z. 36: Wäre besser du beginnst bei 0 (Jedes Array geht von 0 bis length-1).

 

[Dese]

@simpsonsfan:
der tip war nicht das problem, sondern dass er das array auf den stack anlegt statt im heap (mit new bei c++ oder malloc bei c).

Ergänzung (27. April 2013)

@datalukas:
deine funktion "istPalindrom" soll also einfach sagen ob palindrom oder nicht. dann lass sie doch bool zurückgeben statt int. dann brauchst du auch keinen vergleich mit einer zahl und macht alles noch verständlicher

 

[kuddlmuddl]

Ihr müsst ihn mal auf die einfachsten Grundlagen hinweisen und nicht komplizierte Details diskutieren:

- Das speichern der Palindrome ist überflüssig! Es interessiert einzig das größte. Dh man generiert eins nach dem anderen und guckt, ob dieses aktuelle größer ist als das bisher größte gefundene. Wenns besser ist merkt man sich statt dem alten das aktuelle.
Dh man muss sich nur ein einziges Palindrom merken und eins generieren.

- int palindrome[10000];
Das mag nun funktionieren aber ist extrem riskant. Woher weißt du 100%, dass es nur maximal 10.000 Palindrome gibt für 3 stellige Zahlen? Dein Programm würde gnadenlos abstürzen, wenn das 10.001 Palindrom gefunden wird da du dann auf den Index 10.000 zugreifst aber eigtl nur index 9999 erlaubt wäre.

- Wieso gehst du nur von 999 bis 100? Es könnte doch sein, dass 999*99 das größte Palindrom ist? 999*99 (was du nicht untersuchst) ist immerhin fast 10 mal so viel wie 100*100 (was du noch untersuchst).

- Es ist nicht nötig 999*999 Möglichkeiten durchzuprobieren, denn bei Multiplikationen gilt das Kommutativgesetz. 3*5 = 5*3. Es würde also reichen zahl1 von 999 bis 1 zu durchlaufen aber zahl2 immer größergleich zahl1 zu halten.
Stell dir die Möglichkeiten am besten wie ein x,y-Koordinatensystem vor. Nach rechts wächst Zahl1 und nach oben Zahl2. Dann hast du für 1-999 ein Quadrat. Da aber jede Kombination (bis auf die Diagonale) von dir doppelt geprüft wird reicht ein Dreieck dieser Fläche. Die Funktion f(x)=x teilt das Quadrat in "muss man ausrechnen" und "Ergebnis ist schon bekannt.

 

[omaliesschen]

Pre-Inkrement ist schneller als post-inkrement.

++i; ++pal; etc.

 

[datalukas]

Okay, Danke für alle Tipps!

@omaliesschen Danke, aber warum macht das denn einen solchen Unterschied?

Ich habe übrigens gerade die zweite Aufgabe fertig:

bool multiple20(int zahl)
{
	int zaehler;
	zaehler = 0;
	for(int x = 1; x <= 20; x++)
	{
		if(zahl%x==0)
			++zaehler;
	}
	if(zaehler == 20)
		return true;
	else 
		return false;
}
			
int main()
{
	int vielfaches, test;
	vielfaches = 1;
	while(multiple20(vielfaches) == false)
	{
		++vielfaches;
	}
	printf("Die gesuchte Zahl lautet %i", vielfaches);
	scanf("%i", &test);
}

Ist soweit kein Problem, nur dauert das Rechnen sehr lange. Die Zahl ist zwar sehr groß, aber ich bezweifle, dass die verbrauchte CPU-Leistung (25%) effizient gebraucht wird. Außerdem könnte sie ja auch höher ausgelastet werden. Allerdings wären wir dann wohl beim Multithreading.
Aber wenn ich mir die Kern-Leistung anschaue, ist Kern 3 auch nur teilweise voll ausgelastet. Muss das so sein oder kann man die Leistung effizienter nutzen?

 

[omaliesschen]

http://stackoverflow.com/questions/1546981/post-increment-vs-pre-increment-javascript-optimization

Da findest du auch ne kleine Anmerkung zu bitshifts.

 

[Darlis]

Aber wenn ich mir die Kern-Leistung anschaue, ist Kern 3 auch nur teilweise voll ausgelastet. Muss das so sein oder kann man die Leistung effizienter nutzen?

Windows verteilt die Last meist auf verschiedene Kerne. Du kannst deinem Programm im Taskmanager auch einen Kern zuweisen, der dann auf 100% arbeitet aber das dürfte performancemäßig nichts bringen, da auch andere Prozesse diesen Kern benutzten werden.
Im Endeffekt bekommt jeder Prozess nur ein paar Nanosekunden CPU-Zeit zugeteilt, dann ist ein anderer dran.

 

[Hancock]

Zur Aufgabe: Es ist doch effizienter, nicht alle Zahlen zu testen
Also
20,19,18,17,16,15,14,13,12,11 also nur die obere Hälfte, weil die kleineren sind ja Teiler von diesen und damit automatisch drin
und: du kannst ein short-circuit machen: Beim ersten Missmatch passt es nicht.
Und: Es gibt ein Trick, mit dem kannst du das ganze ca. 20x schneller machen.

 

[datalukas]

Das ist mir auch noch aufgefallen, dass man ja nur bis zum ersten Nichtfunktionieren testen muss:

#include "stdafx.h"
		
bool multiple20(int zahl)
{
	int x;
	x = 20;
	while((zahl%x == 0) && (x >= 10))
		--x;
	if(x == 9)
		return true;
	else 
		return false;
}
int main()
{
	int vielfaches, test;
	vielfaches = 1;
	while(multiple20(vielfaches) == false)
	{
		++vielfaches;
	}
	printf("Die gesuchte Zahl lautet %i", vielfaches);
	scanf("%i", &test);
}

Nun mit allen Verbesserungsvorschlägen.

Und: Es gibt ein Trick, mit dem kannst du das ganze ca. 20x schneller machen.

Klär mich auf. ;D

 

[Hancock]

Du machst immer noch kein frühes Beenden:

for(int x=20;x>=11;--x)
  if(zahl%x!=0)
    return false;
return true;

Das mit 20x war mein erster Gedanke, dann hab ich's auf 24 aufrufe für multiple20 bis zur Lösung gebracht.
Tipp: Du kannst die Zahlen, die passen könnten, sehr weit einschränken.