Schmetterlinge

N

Nornagest

0
Da ich nun Mod in diesem Forum bin will ich auch gleich mal eine Aufgabe stellen.

Ihr findet sie hier: http://www.soinf.ch/tasks/Butterflies/desc.de.html

Kurz zusammengefasst:
Es geht darum ein Programm zu schreiben, das ein Bild eines Schmetterlings dargestellt durch Einsen (1) und Nullen (0) aus einer Datei liest und feststellt, ob der Schmetterling symmetrisch ist.
Zu beachten ist, dass der Schmetterling nicht im Bild zentriert sein muss.

Sollte nicht allzu schwer sein, ich werde dann bei Gelegenheit auch meine Lösung posten.
mfg
Nornagest
 
Manno, jetz hab ich hier drei eigene Posts hintereinander... :)
aber hier ist mein Code:
Code: 
#include <iostream>
#include <fstream>
#include <string>
#include <vector>


using namespace std;

int main()
{
	ifstream in;
	in.open("in.txt",ios_base::in);
	vector<string> vec;
	vector<string>::iterator it;
	string buffer;
	int b, h,i;
	in>>b>>h;
	int left=b,
		right=0;
	cout<<b<<" "<<h<<"\n";

	while(in>>buffer)
	{
		vec.push_back(buffer);
		cout<<buffer;
		i=0;
		char tmp=buffer[i];
		bool info=false;
		while(tmp=='0' && i<b)
		{
			i++;
			tmp=buffer[i];
		}
		if(i<left)
			left=i;
		i=b-1;
		tmp=buffer[i];
		while(tmp=='0' && i>0)
		{
			i--;
			tmp=buffer[i];
		}
		if(i>right)
			right=i;
	}
	cout<<left<<" "<<right<<"\n";
	in.close();
	
	bool exit=false;
	it=vec.begin();
	while(it!=vec.end())
	{
		buffer=*it;
		it++;
		//cout<<buffer;
		int r=right, l=left;
		while(r>l && exit==false)
		{
			if(buffer[r] != buffer[l])
				exit=true;
			r--;
			l++;
		}
	}
	if(exit==true)
		cout<<"Der Schmetterling ist nicht symmetrisch!\n";
	else
		cout<<"Der Schmetterling ist symmetrisch!\n";
	return 0;
}

Ich vertraue natürlich darauf, dass hier trotzdem noch weitere Lösungen eintreffen.
mfg
Nornagest
 
Hm.
Und jetzt zeigst Du mir, wo das Lindenblatt ist, auf gut deutsch
Du kommentierst dein Listing mal:

1.) Den Algo, wie du das Bild bearbeitest
2.) Schritt für Schritt, wie Du das Problem gelöst hast.

Ich möchte nämlich herausbekommen, ob Du nur abgeschrieben hast
oder Du wirklich hinter deinem Proggy stehst.
In Ordnung?

Golgotha
 
Also erstmal, ohne anmaßend wirken zu wollen, bitte achte auf deinen Tonfall.
Und bitte unterstell mir nicht einfach irgendwo Code zu klauen, wenn ich fremden Code verwende weise ich ausdrücklich darauf hin.
Vorsicht, das kratzt an meinem Ehrgefühl! :)

aber ich tu dir natürlich den Gefallen, weil du so nett fragst...

Das Programm öffnet die Datei und liest zuerst Zeilenlänge und -anzahl aus.
Dann liest es die einzelnen Zeilen der Datei und schreibt sie in einen Vector.
Dabei wird gleich überprüft wieviele Spalten links und rechts weggelassen werden können (damit der Schmetterling dann zentriert ist) indem überprüft wird wo die erste Eins kommt (einmal von links und einmal von rechts).

Nachdem wir die Daten so aufbereitet haben überprüfen wir die einzelnen Elemente (Strings) des Vektor auf Symmetrie. Hierbei lassen wir natürlich die vorher rausgefundene Anzahl von Spalten außer acht.
Symmetrieprüfung:
äußerst linkes und äußerst rechtes Zeichen wird verglichen, wenn sie identisch sind, nehmen wir das jeweils nächste Zeichen, bis die Mitte erreicht ist, oder eine Asymetrie festgestellt wurde.


Ich hoffe du bist mit mir zu frieden. ;)
 
Hey, Nornagest,

Also erstmal, ohne anmaßend wirken zu wollen, bitte achte auf deinen Tonfall.
Und bitte unterstell mir nicht einfach irgendwo Code zu klauen, wenn ich fremden Code verwende weise ich ausdrücklich darauf hin.
Zum Vergrößern anklicken....

Hi, genau dies hab ich gemerkt, der Code ist nicht geklaut.
Deshalb frage ich ja nach. Deshalb hab' ich mir Deinen Code genau angesehen.
entschuldige bitte meinen Tonfall, aber es ist meine Absicht genau
Dich zu provozieren!

Vorsicht, das kratzt an meinem Ehrgefühl!
Zum Vergrößern anklicken....
Wie weit habe ich jetzt Dein Ehrgefühl verletzt?
Wie weit darf ich noch gehen? *gg*

Ich hoffe du bist mit mir zu frieden.
Zum Vergrößern anklicken....
Absolut.

Wie weit kannst Du den Code auf Geschwindigkeit optimieren?
Versuchst Du es bitte einmal?
Für mich?

Danke!
Golgotha
 
ARRRRRR
endlich hab ich meins fertig ;P
Nornagest kann ganz schön triezen wenn er will hrrhrr
trotzdem viiielen dank an ihn fürs motiviern & helfen.
ne gute lebende referenz isser :D



Code: 
/* checks a butterfly on symmetry
** written by Jobbe
** thx goes out to NORNAGEST
*/

#include <fstream>
#include <iostream>
#include <string>
using namespace std;

int StartSpaces(string strLine)
{
	for(int i = 0; i < (int)strLine.length()-1; i++)
	{
		if( strLine[i] != ' ')
			return i;
	}
	return 0;
}

// lose spaces at the beginning 
// and in the end of the string
string LoseSpaces(string strwSpaces)
{
	string strBuf, strNoSpace;
	bool noStart = true;
	
	// beginning
	for(int i = StartSpaces(strwSpaces); i<(int)(strwSpaces.length()); i++)
		strBuf += strwSpaces[i];

	// end 
	for(int i = (strBuf.length()-1); i >= 0; i--)
	{	
		if( strBuf[i] != (' ') )
			noStart = false;
		if(!noStart)
			strNoSpace += strBuf[i];
	}

	return strNoSpace;
}

int GetSymCenter(string strLine)
{
	string myLine;
	myLine = LoseSpaces(strLine);

	return StartSpaces(strLine) + (int)((myLine.length()+1)/2);
}
				
bool AnalyseLine(string strLine, int sCenter)
{
	string myLine;
	myLine = LoseSpaces(strLine);

	// compare the current center to sCenter
	int curCenter = StartSpaces(strLine) + (int)((myLine.length()+1)/2);
	if( curCenter != sCenter)
		return false;

	// check for odd charcount
	if( myLine.length()%2 == 0 )
		return false;

	// now check for symmetry
	for( int i = 0; i < sCenter-1; i++)
		if( myLine[i] != myLine[myLine.length()-i-1] )
			return false;

	return true;
}

int main(int argc, char *argv[])

{
	// variables
	char strcBuf[256];
	string strBuf;
	int sCenter = -1;
	bool bSym = true;
	ifstream myFile;
	
	// check commandline options
	if(argc < 2) 
		cout << "Syntax: Schmetterlinge <Datei>\n";
	else
	{	
		cout << "Versuche, '" << argv[1] << "' zu oeffnen...\n\n";
		myFile.open(argv[1]);	
		
		// check file
		if(!myFile.is_open())
			cout << "Oeffnen fehlgeschlagen.\n";
		else
		{
			// file output and analysis
			while( myFile.getline(strcBuf, 256))
			{
				// convert to string
				strBuf = strcBuf;

				// line output
				cout << strBuf;

				// get symmetry center
				if(sCenter == -1)
					sCenter = GetSymCenter(strBuf);
				
				// analyse line
				if(!AnalyseLine(strBuf, sCenter))
				{
					cout << " |=> keine Symmetrie";
					bSym = false;
				}
				
				// looks better :)
				cout << "\n";
			}
			
			// we need to clean up
			myFile.close();
			
			cout << "\n";

			if(bSym)
				cout << "Der Schmetterling ist symmetrisch!\n";	
			else
				cout << "Der Schmetterling ist asymmetrisch!\n";				
		}
	}
	return (0);
}


als testdateien kann man z.b. diese hier benutzen

symmetrisch:
Code: 
     1         1
   00000     00000  
  000 000 1 000 000
  00000001110000000
    0000011100000
     00001110000
    0000011100000
  0000000 1 0000000
000 0000     0000 000
00   00       00   00
 00 00         00 00
  000           000
   1             1

asymmetrisch:
Code: 
     1         1
   00000     00000  
  000 000 1 0001000
  00000001110000000
    0000011100000
      0001110000
    0000011100000
  0000000 1 0000000
 000 0000     0000 000
00   00       00   00
 00 00         00 00
  000           000
   1             1


;)
 
symmetrie bei diagonaler achse

hi leutz,

hab die aufgabe eben mal überflogen und fand sie ganz nett, doch würde mich interessieren ob auch jemand ne lösung fände für ne diagonale symmetrieachse?

sobald ich aus dem prüfungsstress raus bin, denk ich mal ne runde drüber nach. bis dahin geh ich mich nochmal mit endlichen automaten beschäftigen.

cu

ps: fällt jemandem ne tolle prüfungsaufgabe zu bäumen ein?
 
diagonal:
Also dann muss das ganze ja ein Quadrat sein (oder ein Drachenviereck...) und dann sollte das auch kein großes Problem sein, du zählst diagonal durch, die Überprüfung läuft im Grunde genauso.
Man ließt erst das ganze "Bild" ein (zweidimensionaler array/Vektor) und dann überprüft man.

zu Bäumen:
schau mal in die Labyrinth Aufgabe, wenn man das mit Bäumen löst kann das ne schöne Aufgabe sein ;)
Labyrinth

mfg
Nornagest
 
das mit dem laby klingt ganz spannend, ist aber wohl bis zur prüfung morgen als kleine übung nicht mehr zu schaffen ;-)

bezüglich des schmetterlings war ich wohl mal wieder mathematisch zu unpräzise. ich meinte natürlich keine exakte diagonale. die positionen wären reichlich einfach zu vergleichen. suchte eher nen algorhytmus für ne schiefe achse... das würde die sache sicher interessanter gestalten.

mfg
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben