Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

Ich hab mir mal ne Aufgabe ausgedacht. Sie ist auf jeden Fall lösbar und das mit einer überschaubaren Zahl an Codezeilen. Ziel ist es, eigenen Code einzufügen, sodass Gelöst auf der Console ausgegeben wird.

using System;
using System.Runtime.InteropServices;

class Program
{
    static void Main(string[] args)
    {
        string ShouldBe = "This String";
        string IsAtStart= "R4nd0om data or somthing nobody cares about....";
        IntPtr buffer = Marshal.StringToHGlobalUni(IsAtStart);
        int hash = ShouldBe.GetHashCode();//Doppelte Prüfung hält besser

        WriteToBuffer(buffer, ShouldBe);

        string newString = Marshal.PtrToStringUni(buffer);
        Marshal.FreeHGlobal(buffer);

        if (newString == ShouldBe && newString.GetHashCode() == hash)
            Console.WriteLine("Gelöst");
        else
            Console.WriteLine("Nicht gelöst, in \"buffer\" steht: "+newString);
        Console.ReadLine();
    }

    //Hinter dem Ende dieses Kommentars darf der Code geändert werden.
    //Der nachfolgende vorgegebene Code ist als Hinweis gedacht und darf gelöscht/bearbeitet werden.
    //Folgende Ausdrücke dürfen dabei NICHT verwendet werden:
    //unsafe, Marshal, DllImport, extern, Reflection, GetType, typeof, Type, Program, Console, Main

    [StructLayout(LayoutKind.Explicit)]
    struct SomeStruct
    {
        //TODO
    }

        //TODO

    private static void WriteToBuffer(IntPtr buffer, string ShouldBe)
    {
        //TODO
    }
}
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Hi Floste,

du hast zwar wahrscheinlich an etwas komplett anderes gedacht ;)
Aber hier meine Lösung, die statt Marshal.Copy einfach Bitmap und SetPixel nutzt:

    [StructLayout(LayoutKind.Explicit)]
    struct SomeStruct
    {
        //TODO
    }

    //TODO

    private static void WriteToBuffer(IntPtr buffer, string ShouldBe)
    {
        byte[] shouldBeBytes = System.Text.Encoding.Unicode.GetBytes(ShouldBe);
        int pixels = shouldBeBytes.Length / 4 + 1; // +1 for some trailing EndOfString-Zeroes
        int[] colorValues = new int[pixels];
        Buffer.BlockCopy(shouldBeBytes, 0, colorValues, 0, shouldBeBytes.Length);

        using (var b = new System.Drawing.Bitmap(pixels, 1, pixels * 4, System.Drawing.Imaging.PixelFormat.Format32bppArgb, buffer))
        {
            for (int i = 0; i < pixels; i++)
            {
                b.SetPixel(i, 0, System.Drawing.Color.FromArgb(colorValues[i]));
            }
        }
    }

beste Grüße
zommi
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Hi,

vollständigkeitshalber noch das, woran Flotse wohl eher dachte:

    [StructLayout(LayoutKind.Explicit)]
    struct SomeStruct
    {
        [FieldOffset(0)]
        public IntPtrContainer A;

        [FieldOffset(0)]
        public CharacterContainer B;
    }

    
    [StructLayout(LayoutKind.Sequential)]
    class IntPtrContainer
    {
        public IntPtr IntPtr;
    }
    
    [StructLayout(LayoutKind.Sequential)]
    class CharacterContainer
    {
        public SingleCharacter SingleCharacter; 
    }
    
    class SingleCharacter
    {
        public char Char;
    }

    private static void WriteToBuffer(IntPtr buffer, string ShouldBe)
    {
        for (int i = 0; i < ShouldBe.Length; i++)
        {
            WriteCharacter(buffer + i * sizeof(char), ShouldBe[i]);
        }
        WriteCharacter(buffer + ShouldBe.Length * sizeof(char), '\u0000');
    }

    private static void WriteCharacter(IntPtr buffer, char character)
    {
        SomeStruct s = new SomeStruct();
        s.A = new IntPtrContainer() {IntPtr = buffer - IntPtr.Size}; // skip SyncBlock of object
        s.B.SingleCharacter.Char = character;
    }

abermals beste Grüße
zommi
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

Das erste Snippet hat mich schmunzeln lassen. Aber gut, ich hatte solche Lösungen aber nicht ausgeschlossen^^
, Du bist dran...

Was mir grade noch auffällt: Da is nicht der Syncblock (der is ein IntPtr davor, sic), sondern die Typenangabe, aber das ist in diesem Falle egal^^
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo zusammen,

es gibt zwar keine neue Aufgabe von mir, aber einen Hinweis, dass sich auf http://pexforfun.com/ - einer Art "automatisiertem Programmierspiel" - viele interessante Aufgaben finden.

Dort bekommt man einen Quellcode-Rahmen angezeigt, den man entsprechend der Aufgabe ausfüllen muss, nur dass die Aufgabe nicht als Text vorgeben ist, sondern man den Code auf Verdacht ändert und sich nach jeder Code-Änderung anzeigen lassen kann, mit welchen Testdaten der White-Box-Testdatengenerator PEX das eigene Programm füttert und welche Ausgabe es daraus errechnet und was das jeweils erwünschte Ergebnis ist. Das Prinzip hat ein bisschen was von Mastermind, wo man auch eine mögliche Lösung ausprobiert und vom Gegenüber Hinweise bekommt, was schon stimmt und was noch nicht.

herbivore
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Ich habe wieder etwas ausgegraben:

Ein string-search Algorithmus á la Boyer-Moore: http://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus

Da in dem Artikel ein Beispielcode in C existiert könnte man sich auch die Zeit nehmen und diesen zu überarbeiten - doch würde ich eine eigene Implementation bevorzugen
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Daniel B. am .
private Nachricht | Beiträge des Benutzers
ProGamer
myCSharp.de - Member



Dabei seit:
Beiträge: 691
Herkunft: NRW

beantworten | zitieren | melden

Hallo zusammen,

Da hier seit langem nichts mehr los ist, würde ich gerne eine Aufgabe stellen.
Zitat
Erstelle einen Algorithmus welches den Ostersonntag eines Jahres ermittelt.

Wem das zu einfach war kann ja mal versuchen noch folgende Tage zu ermitteln:

KarFreitag
OsterMontag
ChristiHimmelfahrt
PfingstSonntag
PfingstMontag
Fronleichnam


Viel spaß beim lösen!
MfG
ProGamer
private Nachricht | Beiträge des Benutzers
ProGamer
myCSharp.de - Member



Dabei seit:
Beiträge: 691
Herkunft: NRW

Lösung der vorherigen Aufgabe

beantworten | zitieren | melden

Ich werde hier die Lösung meiner Aufgabe zeigen [SCNR]da es für die meisten hier zu schwer zu sein scheint[/SCNR] (Bitte nicht ernst nehmen ^^).

Der Code ist nicht Optimal aber dafür einige Jahre alt...


public class Feiertage
    {

        public const int GruenDonnerstag = -3;
        public const int KarFreitag = -2;
        public const int OsterMontag = 1;
        public const int ChristiHimmelfahrt = 39;
        public const int PfingstSonntag = 49;
        public const int PfingstMontag = 50;
        public const int Fronleichnam = 60;

        public string GetOsterSonntag(int Jahr)
        {
            float Saekularzahl = 0;
            float Mondschaltung = 0;
            float Sonnenschaltung = 0;
            float Mondparameter = 0;
            float ErsterVollmond = 0;
            float KorrekturGroeße = 0;
            float Ostergrenze = 0;
            float ErsterSonntag = 0;
            float Entfernung = 0;
            float Sonntag = 0;
            DateTime Date;
                        
            Saekularzahl = Jahr / 100;
            Mondschaltung = 15 + (3 * Saekularzahl + 3) / 4 - (8 * Saekularzahl + 13) / 25;
            Sonnenschaltung = 2 - (3 * Saekularzahl + 3) / 4;
            Mondparameter = Jahr % 19;
            ErsterVollmond = (19 * Mondparameter + Mondschaltung) % 30;
            KorrekturGroeße = ErsterVollmond / 29 + (ErsterVollmond / 28 - ErsterVollmond / 29) * (Mondparameter / 11);
            Ostergrenze = 22 + ErsterVollmond - KorrekturGroeße;
            ErsterSonntag = 7 - (Jahr + Jahr / 4 + Sonnenschaltung) % 7;
            Entfernung = 7 - (Ostergrenze - ErsterSonntag) % 7;
            Sonntag = Ostergrenze + Entfernung;

            Sonntag = Convert.ToInt32(Math.Floor(Sonntag));

            if (Sonntag > 31)
            {
                Sonntag -= 31;
                Date = Convert.ToDateTime(Sonntag + ".04." + Jahr);
            }
            else
            {
                Date = Convert.ToDateTime(Sonntag + ".03." + Jahr);
            }

            return Date.ToShortDateString();
        }
        
        public Dictionary<string, string> GetBeweglicheFeiertage(DateTime OsterSonntag)
        { 
            DateTime[] BewegFeier = new DateTime[7];

            Dictionary<string, string> Dic = new Dictionary<string, string>();

            //Dic.Add("GruenDonnerstag", OsterSonntag.AddDays(GruenDonnerstag));
            Dic.Add("KarFreitag", OsterSonntag.AddDays(KarFreitag).ToShortDateString());
            Dic.Add("OsterMontag", OsterSonntag.AddDays(OsterMontag).ToShortDateString());
            Dic.Add("ChristiHimmelfahrt", OsterSonntag.AddDays(ChristiHimmelfahrt).ToShortDateString());
            Dic.Add("PfingstSonntag", OsterSonntag.AddDays(PfingstSonntag).ToShortDateString());
            Dic.Add("PfingstMontag", OsterSonntag.AddDays(PfingstMontag).ToShortDateString());
            Dic.Add("Fronleichnam", OsterSonntag.AddDays(Fronleichnam).ToShortDateString());

            return Dic;

        }
		
		public Dictionary<string, string> GetBeweglicheFeiertage(string OsterSonntag)
		{
			return GetBeweglicheFeiertage( Convert.ToDateTime(OsterSonntag) );
		}
		
	}

Für mehr Infos einfach hier reinschauen --> OsterFormel (Wobei man das nicht als Formel bezeichnen kann...)
MfG
ProGamer
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo ProGamer,

vielen Dank, dass du eine Lösung gepostet hast. So bleibt das Programmierspiel nicht nur eine Aufgabensammlung, sondern eine mit Beispiellösungen.

Ich sinniere mal darüber, warum es keine Antwort von Seiten der Community gab. Versteht das bitte nicht als Kritik, sondern eher als Anregung - auch für anderer Aufgabensteller -, wie Aufgaben stattdessen aussehen sollten, also möglichst so, dass der Algorithmus selbst entwickelt werden kann und gleichzeitig fertige Lösungen schwer zu finden sind. Damit scheiden dann die gängigen Übungsaufgaben aus.

Die Hürde bei der Aufgabe (Osterberechnung) und auch bei der Aufgabe davor (Boyer-Moore) ist, dass man den eigentlichen Algorithmus kaum oder gar nicht selber entwickeln kann, sondern das dieser vorgegeben ist (bei Boyer-Moore ist das noch etwas eindeutiger als bei der Osterformel). Es geht also nur noch um die Umsetzung der Formel in Code bzw. die Implementierung des vorgegebenen Algorithmus. Das ist aus meiner Sicht relativ eintönige, teilweise mühsame Arbeit. Und außerdem gibt es im Netz schon viele fertige Implementierungen. Wenn ich einen (Feiertags-)Kalender programmieren wollte, würde ich einfach so eine fertige Implementierung suchen und verwenden.

Ob ich in jedem einzelnen Punkt recht habe oder nicht, sei mal dahingestellt und das müssen und sollten wir auch nicht diskutieren, weil es hier ja um das Spiel selbst gehen soll und nicht um die Meta-Ebene. Mein Ziel ist erreicht, wenn sich potenzielle Aufgabensteller das Gesagte durch den Kopf gehen lassen und sich das herausziehen, was sie für plausibel und nützlich halten.

herbivore
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Community,

nachdem die letzte Aufgabe ohne "Sieger" beantworte wurde, erlaube ich mir, eine neue Aufgabe zu stellen.
Schreibe eine Methode RemoveDuplicates, die ein String-Array als Parameter bekommt und eine List<String> zurückliefert, in der im Ergebnis alle doppelten/mehrfachen Zeilen entfernt sind. Es soll jeweils das erste Auftreten einer Zeile 1:1 übernommen und [I]alle[/I] späteren Wiederholungen der gleichen Zeile verworfen werden.

Damit es nicht zu einfach wird, soll die Methoden folgende Optionen verarbeiten können, die beliebig kombinierbar sind.

[csharp]
[Flags]
enum RemoveDuplicatesOptions
{
   IgnoreCase                  = 0x01,
   IgnoreLeadingTrailingSpace  = 0x02,
   IgnoreSpaceChange           = 0x04,
   IgnoreAllSpace              = 0x08,
   RemoveBlankLines            = 0x10,
   KeepBlankLines              = 0x20
}
[/csharp]

[B]IgnoreCase:[/B] Zwei Zeilen werden auch dann als gleich betrachtet, wenn sie sich nur in der Groß-Kleinschreibung unterscheiden. Beispiel:
[pre]
"Hallo World!"
"hAll0 worlD!"
"HALLO WORLD!"
[/pre]

[B]IgnoreLeadingTrailingSpace:[/B] Zwei Zeilen werden auch dann als gleich betrachtet, wenn sie sich nur darin unterscheiden, ob, welche oder wieviele Spaces am Anfang und am Ende vorhanden sind. Beispiel:
[pre]
"Hallo World!"
"Hallo World!   "
" Hallo World!"
"\t\tHallo World!\t"
[/pre]

[B]IgnoreSpaceChange:[/B] Zwei Zeilen werden auch dann als gleich betrachtet, wenn sie sich nur durch die Art oder Anzahl aufeinander folgender Spaces unterscheiden. Das gilt auch für Zeilenanfang und Ende. Egal, ob ein oder mehr Spaces. Beispiel:
[pre]
"Hallo World!"
"Hallo\tWorld!"
"Hallo    World!"
[/pre]

[B]IgnoreAllSpace:[/B] Zwei Zeilen werden auch dann als gleich betrachtet, wenn sie sich nur durch das Spacing unterscheiden. Egal, ob null, ein oder mehr Spaces. Beispiel:
[pre]
"HalloWorld!"
"Hallo World!"
"HalloW orld!"
" Hallo   World!\t\t"
[/pre]

[B]RemoveBlankLines[/B] bzw. [B]KeepBlankLines[/B] entfernen bzw. erhalten alle Leerzeilen. Werden beide gleichzeitig angegeben, wird nur RemoveBlankLines berücksichtigt. Was als Leerzeile angesehen wird, hängt von davon ab, ob mindestens eine von den Space-Optionen gesetzt ist (alle Zeilen, die gar keine Zeichen oder nur Spaces enthalten) oder keine davon gesetzt ist (alle Zeilen, die überhaupt keine Zeichen enthalten).

Die Signatur der Methode, sieht also so aus:

[csharp]public static List<String> RemoveDuplicates (String [] lines, RemoveDuplicatesOptions options)[/csharp]

Die Methode sollte auch bei einer Million Input Zeilen noch zügig arbeiten. Das wird vermutlich nur der Fall sein, wenn ihr es schafft, den Aufwand linear (also bei O(n)) zu halten.

Im PS gibts noch zwei Tipps. Tut euch den Gefallen und probiert es erstmal selber, ohne die Tipps zu lesen.

Viel Spaß und viel Erfolg!

herbivore


PS: Wie gesagt solltet ihr euch selbst den Gefallen tun und es erstmal selber versuchen, ohne gleich die Tipps zu lesen. Schluss jetzt. Stopp! Als Parametertyp kann man statt String [] besser IEnumerable<String> verwenden. Das wird hiermit ausdrücklich erlaubt und empfohlen. Es wird außerdem erlaubt, die Methode als Erweiterungsmethode von IEnumerable<String> zu definieren. Nochmal stopp! Zur Lösung der Aufgabe sind keine Indexzugriffe erforderlich. Nochmal stopp! Bei der Implementierung wird ein HashSet bzw. ein Dictionary gute Dienste leisten und kann bei richtiger Verwendung dafür sorgen, dass der Aufwand der Methode wie gewünscht im Schnitt linear ist.
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 631

beantworten | zitieren | melden

Hier meine Lösung zu herbivores Aufgabe:


public class RemoveDublicatesComparer : IEqualityComparer<string>
{
    RemoveDublicates.RemoveDuplicatesOptions options = new RemoveDublicates.RemoveDuplicatesOptions();

    public RemoveDublicatesComparer(RemoveDublicates.RemoveDuplicatesOptions options)
    {
        this.options = options;
    }

    public bool Equals(string x, string y)
    {
        string tempx = "";
        string tempy = "";
        bool isMatch = false;

        isMatch = Regex.IsMatch(x, y);

        if(options.HasFlag(RemoveDublicates.RemoveDuplicatesOptions.IgnoreCase) && !isMatch)
        {
            isMatch = Regex.IsMatch(x, y, RegexOptions.IgnoreCase);
        }
        if (options.HasFlag(RemoveDublicates.RemoveDuplicatesOptions.IgnoreLeadingTrailingSpace) && !isMatch)
        {
            tempx = Regex.Replace(x, "^[ \t]+|[ \t]+$", "");
            tempy = Regex.Replace(y, "^[ \t]+|[ \t]+$", "");
            isMatch = Regex.IsMatch(tempx, tempy);
        }
        if (options.HasFlag(RemoveDublicates.RemoveDuplicatesOptions.IgnoreSpaceChange) && !isMatch)
        {
            tempx = Regex.Replace(x, "[ \t]*", " ");
            tempy = Regex.Replace(y, "[ \t]*", " ");
            isMatch = Regex.IsMatch(tempx, tempy);
        }
        if (options.HasFlag(RemoveDublicates.RemoveDuplicatesOptions.IgnoreAllSpace) && !isMatch)
        {
            tempx = Regex.Replace(x, "[ \t]*", "");
            tempy = Regex.Replace(y, "[ \t]*", "");
            isMatch = Regex.IsMatch(tempx, tempy);
        }
        return isMatch;
    }

    public int GetHashCode(string obj)
    {
        throw new NotImplementedException();
    }
}

public class RemoveDublicates
{
    [Flags]
    public enum RemoveDuplicatesOptions
    {
        IgnoreCase = 0x01,
        IgnoreLeadingTrailingSpace = 0x02,
        IgnoreSpaceChange = 0x04,
        IgnoreAllSpace = 0x08,
        RemoveBlankLines = 0x10,
        KeepBlankLines = 0x20
    }

    public static List<String> RemoveDuplicates(String[] lines, RemoveDuplicatesOptions options)
    {
        List<String> resultStringList = new List<string>();
        RemoveDublicatesComparer comparer = new RemoveDublicatesComparer(options);

        foreach (string line in lines)
        {
            if (options.HasFlag(RemoveDublicates.RemoveDuplicatesOptions.RemoveBlankLines) && comparer.Equals("", line))
                continue;

            if (options.HasFlag(RemoveDublicates.RemoveDuplicatesOptions.KeepBlankLines) && comparer.Equals("", line))
            {
                resultStringList.Add(line);
                continue;
            }
            if (!resultStringList.Contains(line, comparer))
            {
                resultStringList.Add(line);
            }
        }

        return resultStringList;
    }
}

Sehr intressante Aufgabe. Habe viel dabei gelernt. Zerreisst mich bitte in der Luft, damit ich noch mehr lernen kann (Stichwort: Coding Horror)

Viele Grüße


PS: Das komplette Test-Programm gibts auf Anfrage

edit: Ok, Datei angehängt.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Alf Ator am .
Attachments

Moderationshinweis von gfoidl (08.07.2011 - 16:32:44):

Zitat
Zerreisst mich bitte in der Luft, damit ich noch mehr lernen kann (Stichwort: Coding Horror)
Bitte nicht hier in diesem Thread.

private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 3138

beantworten | zitieren | melden

Zitat von Alf Ator
PS: Das komplette Test-Programm gibts auf Anfrage
*Anfrag*. Hänge es doch einfach als Dateianhang an deinen Beitrag an.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Alf Ator,

die Richtung ist schon mal nicht schlecht. Gut gefällt mir, dass du durch den Comparer die Komplexität geschickt verteilt hast. Leider habe ich noch ein paar Fehler gefunden. Deshalb sehe ich die die Aufgabe noch nicht als gelöst an.

Bei Regex.IsMatch(x, y) wird x als Regex-Pattern interpretiert. Eine Eingabezeile muss aber kein gültiger Pattern sein. Dann knallt es. Aber selbst wenn die Zeile ein gültiger Pattern ist, sagt das matchen nicht, ob die Zeilen gleich sind. Wäre x z.B. ".*", dann würde das auf beliebige y passen. String.Compare wäre wohl eher, was du suchst.

Auch bei den Regex-Operationen danach, stimmt nicht alles. Regex.Replace(x, "[ \t]*", " ") geht zwar in die richtige Richtung, aber bei einem Pattern, der durch * auch die Länge null akzeptiert, muss man immer aufpassen, weil er an jeder Stelle passt, auch da, wo keine Leerzeichen sind. Dadurch wäre auch "Hallo World" und "HalloWorld" gleich.

Hast du es wirklich mal mit einer Million Zeilen probiert? Sowie ich das sehe, müsste das ziemlich lange dauern. Wenn es mit einer Million doch zügig geht, probier es mal mit 10 Millionen Zeilen. Ich vermute, dass wird nicht ca. 10 sondern ca. 100 Mal solange dauern. Das liegt daran, dass List.Contains eine O(n)-Operation ist, die jedes Mal innerhalb einer Schleife über n Elemente aufgerufen wird. Das ergibt am Ende O(n^2). Mit dem Tipp im PS kommt man an eine Contains-Operation, die einen Aufwand von nur O(1) hat. Damit erreicht man am Ende das gewünschte O(n).

Und leider rächt sich sogar der an sich elegante Comparer, weil er für jedes Zeilenpaar aufgerufen wird. Damit wird jede einzelne Zeile n-fach neu aufbereitet (also z.B. die Leerzeichen entfernt). Es wäre schöner, wenn jede Zeile nur einmal aufbereitet werden müsste (und das kann man tatsächlich realisieren). Den Comparer ersetzt mal also besser durch eine Zeilenaufbereitungsmethode.

Dass du fast überall Dublicates statt Duplicates geschrieben hast, wäre zu verschmerzen gewesen. :-)

Also auf zu einem weiteren oder neuen Versuch. Von dir oder von jemand anderem.

herbivore
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 631

beantworten | zitieren | melden

So, mein zweiter Versuch:


public class RemoveDuplicates
{
    [Flags]
    public enum RemoveDuplicatesOptions
    {
        IgnoreCase = 0x01,
        IgnoreLeadingTrailingSpace = 0x02,
        IgnoreSpaceChange = 0x04,
        IgnoreAllSpace = 0x08,
        RemoveBlankLines = 0x10,
        KeepBlankLines = 0x20
    }

    public static List<String> Remove(List<String> inputStringList, RemoveDuplicatesOptions removeDuplicatesOptions)
    {
        HashSet<String> hash = new HashSet<string>();
        foreach (string line in inputStringList)
        {
            // evt. sollen Blanklines entfernt werden
            if (removeDuplicatesOptions.HasFlag(RemoveDuplicatesOptions.RemoveBlankLines) && (ProcessString(line, removeDuplicatesOptions).Equals(""))) continue;

            // evt. sollen Blanklines erhalten werden
            if (removeDuplicatesOptions.HasFlag(RemoveDuplicatesOptions.KeepBlankLines) && (ProcessString(line, removeDuplicatesOptions).Equals("")))
            {
                hash.Add(line);
                continue;
            }
            hash.Add(ProcessString(line, removeDuplicatesOptions));
        }
        return hash.ToList<string>();
    }

    public static string ProcessString(string x, RemoveDuplicatesOptions options)
    {
        string tempx = x;

        if (options.HasFlag(RemoveDuplicatesOptions.IgnoreCase))
        {
            tempx = tempx.ToLower();
        }
        if (options.HasFlag(RemoveDuplicatesOptions.IgnoreLeadingTrailingSpace))
        {
            tempx = tempx.TrimStart(" \t".ToCharArray());
            tempx = tempx.TrimEnd(" \t".ToCharArray());
        }
        if (options.HasFlag(RemoveDuplicatesOptions.IgnoreSpaceChange))
        {
            tempx = System.Text.RegularExpressions.Regex.Replace(tempx, "[ \t]+", " ");
        }
        if (options.HasFlag(RemoveDuplicatesOptions.IgnoreAllSpace))
        {
            tempx = System.Text.RegularExpressions.Regex.Replace(tempx, "[ \t]+", "");
        }
        return tempx;
    }
}
Attachments
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Alf Ator,

du bist wieder näher dran. Und darüber, dass die Blankline-Abfragen in dem Fall, dass eine Leerzeile ein oder mehrere Spaces enthält und zusätzlich zu einem Blankline-Flag nur das Flag IgnoreSpaceChange gesetzt ist, nicht richtig funktionieren, weil ProcessString für diese Zeilen (in sich korrekt, aber für die Abfrage nunmal unpassend) " " und nicht "" liefert, hätte ich sogar hinweggesehen.

Doch was nützt KeepBlankLines, wenn du dabei HashSet.Add verwendest, welche doppelte Zeilen eben nicht doppelt hinzufügt? Hier bräuchtest du List.Add.

Die größten Auswirkungen hat aber der Fehler, dass du HashSet.ToList zurückgibst, denn darin sind ja (an sich korrekt, aber für die Rückgabe nunmal unpassend) die aufbereiteten Zeilen und nicht die Originalzeilen. Da wundert mich schon ein bisschen, dass das beim Testen nicht aufgefallen ist. Meiner Ansicht nach brauchst du eine Liste und ein Hashset.

Dass du eine Zeile immer noch bis zu dreimal aufbereitest, tut der Linearität zwar keinen Abbruch (konstanter Faktor). Schöner wärs aber, wenn du das vermeiden würdest. Und tempx kannst du dir eigentlich komplett sparen. Spätestens da sind wir aber endgültig bei den Stilfragen angekommen.

Im Sinne des Dazulernens sind solche Iterationen vermutlich nicht schlecht. Dadurch steigt allerdings die Gefahr, dass dir doch noch jemand zuvorkommt. Auf die Idee, dass man durch diese Aufgabe viel lernen kann, sind bestimmt schon andere gekommen. :-)

herbivore
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 631

beantworten | zitieren | melden

Hallo herbivore, du lässt mir ja kein gutes Haar
Zitat von herbivore
du bist wieder näher dran. Und darüber, dass die Blankline-Abfragen in dem Fall, dass eine Leerzeile ein oder mehrere Spaces enthält und zusätzlich zu einem Blankline-Flag nur das Flag IgnoreSpaceChange gesetzt ist, nicht richtig funktionieren, weil ProcessString für diese Zeilen (in sich korrekt, aber für die Abfrage nunmal unpassend) " " und nicht "" liefert, hätte ich sogar hinweggesehen.

Ist " " eine Blankline? Und wie schauts mit "\t" aus oder " \t \t"; Hier habe ich mich für den einfachsten Weg entschieden und definiert das nur "" = Blankline ist.
Zitat von herbivore
Doch was nützt KeepBlankLines, wenn du dabei HashSet.Add verwendest, welche doppelte Zeilen eben nicht doppelt hinzufügt? Hier bräuchtest du List.Add.
Da hast du mich eiskalt erwischt. Das war mir natürlich bewusst, aber ich hatte noch keine Lösung gefunden. Ich hätte eine Liste anlegen können und die Blanklines hinzufügen können und später dann das HashSet hinzufügen. Das würde aber die Reihenfolge durcheinander bringen. Oder ich füge jedesmal wenn ein String ins HashSet passt diesen String (oder dann das Original) in die List ein.
Zitat von herbivore
Die größten Auswirkungen hat aber der Fehler, dass du HashSet.ToList zurückgibst, denn darin sind ja (an sich korrekt, aber für die Rückgabe nunmal unpassend) die aufbereiteten Zeilen und nicht die Originalzeilen. Da wundert mich schon ein bisschen, dass das beim Testen nicht aufgefallen ist. Meiner Ansicht nach brauchst du eine Liste und ein Hashset.

Das ist mir natürlich aufgefallen. Die Frage ist halt, in welcher Form ein String zurückgegeben werden muss. In der Form, wie er als erstes aufgefunden wurde? Es gibt ja auch noch die Duplikate, die evt. andere Schreibweisen haben. Auch hier hab ich's mir einfach gemacht und angenommen, dass ein aufbereiteter String zurückgegeben werden kann.
Zitat von herbivore
Dass du eine Zeile immer noch bis zu dreimal aufbereitest, tut der Linearität zwar keinen Abbruch (konstanter Faktor). Schöner wärs aber, wenn du das vermeiden würdest. Und tempx kannst du dir eigentlich komplett sparen. Spätestens da sind wir aber endgültig bei den Stilfragen angekommen.

Find ich auch unschön so. X(
Zitat von herbivore
Im Sinne des Dazulernens sind solche Iterationen vermutlich nicht schlecht. Dadurch steigt allerdings die Gefahr, dass dir doch noch jemand zuvorkommt. Auf die Idee, dass man durch diese Aufgabe viel lernen kann, sind bestimmt schon andere gekommen. :-)

Einen habe ich hier schon in der Streckbank..
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Alf Ator,
Zitat
Ist " " eine Blankline? Und wie schauts mit "\t" aus oder " \t \t";
Sind alles Blanklines, wenn und nur wenn mindestens eine der Space-Optionen gesetzt ist. Was unter welchen Umständen als Blankline betrachtet werden soll, steht in der Aufgabe. :-)
Zitat
Hier habe ich mich für den einfachsten Weg entschieden und definiert das nur "" = Blankline ist.
Nö, da du vor dem Abfragen auf "" die Zeile aufbereitest (ProcessLine), wird auch bei dir (bis auf die von mir beschriebene Ausnahme vollkommen korrekt) viel mehr als nur "" als Blankline betrachtet.
Zitat
Das würde aber die Reihenfolge durcheinander bringen.
Wie schon gesagt, brauchst du wohl sowohl eine Liste als auch ein HashSet. Die Liste um die zu übernehmenden Zeilen zu sammeln und das HashSet für die Prüfung auf doppelte/mehrfache Zeilen.
Zitat
In der Form, wie er als erstes aufgefunden wurde?
Ja, und genau so steht es auch in der Aufgabe. :-)
Zitat
Das ist mir natürlich aufgefallen.
Du solltest eine Lösung nur dann posten, wenn du selber davon ausgehst, dass sie korrekt ist.

herbivore
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 631

beantworten | zitieren | melden

Zitat von herbivore
Du solltest eine Lösung nur dann posten, wenn du selber davon ausgehst, dass sie korrekt ist.

Sorry X(


public static List<String> Remove(List<String> inputStringList, RemoveDuplicatesOptions removeDuplicatesOptions)
{
    List<String> resultList = new List<string>();
    HashSet<String> hash = new HashSet<string>();
    string tmp = "";
    foreach (string line in inputStringList)
    {
        tmp = ProcessString(line, removeDuplicatesOptions);
        if (tmp.Equals("") || tmp.Equals(" "))
        {
            // evt. sollen Blanklines entfernt werden
            if (removeDuplicatesOptions.HasFlag(RemoveDuplicatesOptions.RemoveBlankLines))
                continue;
            // evt. sollen Blanklines erhalten werden
            if (removeDuplicatesOptions.HasFlag(RemoveDuplicatesOptions.KeepBlankLines))
            {
                resultList.Add(line);
                continue;
            }
        }
        if (hash.Add(tmp)) resultList.Add(line);
    }
    return resultList;
}

public static string ProcessString(string x, RemoveDuplicatesOptions options)
{
    if (options.HasFlag(RemoveDuplicatesOptions.IgnoreCase))
    {
        x = x.ToLower();
    }
    if (options.HasFlag(RemoveDuplicatesOptions.IgnoreLeadingTrailingSpace))
    {
        x = x.TrimStart(" \t".ToCharArray());
        x = x.TrimEnd(" \t".ToCharArray());
    }
    if (options.HasFlag(RemoveDuplicatesOptions.IgnoreSpaceChange))
    {
        x = System.Text.RegularExpressions.Regex.Replace(x, "[ \t]+", " ");
    }
    if (options.HasFlag(RemoveDuplicatesOptions.IgnoreAllSpace))
    {
        x = System.Text.RegularExpressions.Regex.Replace(x, "[ \t]+", "");
    }
    return x;
}

Ich hab jetzt versucht, alles bisherige zu beachten. Diesmal passt alles 8)
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Alf Ator,
Zitat
Diesmal passt alles
fast alles. :-) Die Behandlung von BlankLines stimmt immer noch nicht ganz. Wenn z.B. keine Space-Option gesetzt ist, wird eine Zeile, die von vornherein nur ein einzelnes Blank enthält, fälschlicherweise trotzdem als Leerzeile erkannt. Statt " " in der Abfrage zu berücksichtigen, wäre es aus meiner Sicht eine korrekte Lösung, wenn du in ProcessString am Ende des Then-Teil der Abfrage auf IgnoreSpaceChange abfragst, ob das Ergebnis ein einzelnes Leerzeichen ist und wenn ja, x auf den leeren String setzt. Also

if (x == " ") {
   x = "";
}

Ich akzeptiere die Lösung trotzdem als korrekt. Du bist dran, die nächste Aufgabe zu stellen.

herbivore
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 631

beantworten | zitieren | melden

Zitat von herbivore
fast alles. :-)

Arrrrghhh :tongue:
Zitat von herbivore
Ich akzeptiere die Lösung trotzdem als korrekt. Du bist dran, die nächste Aufgabe zu stellen.


Puh! Das war aber auch ne knackige Aufgabe.

Eine Frage hab ich noch dazu:
Zitat von herbivore
Als Parametertyp kann man statt String [] besser IEnumerable<String> verwenden. Das wird hiermit ausdrücklich erlaubt und empfohlen. Es wird außerdem erlaubt, die Methode als Erweiterungsmethode von IEnumerable<String> zu definieren.
Was hattest du dabei denn im Hinterkopf? Eine eigene Liste implementieren, die die Funktion RemoveDuplicates anbietet?

So, ich werde mir mal Gedanken über eine neue Aufgabe machen.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Alf Ator,
Zitat
Was hattest du dabei denn im Hinterkopf?
IEnumerable<String> ist die beste Wahl, weil die Methode damit am universellsten wird, egal in welcher konkreten Collection (Array, List, LinkedList, ...) die Eingabedaten vorliegen. Als Erweiterungsmethode von IEnumerable<String> kann man die Methode zudem (wiederum für beliebige Collections) sehr elegant aufrufen.

Der Grund, warum ich nicht gleich IEnumerable<String> vorgegeben habe, war, dass ich wollte, dass jeder möglichst von alleine darauf kommt, dass Indexzugriffe auf die Eingabedaten gar nicht erforderlich sind. Hätte ich statt String [], wo Indexzugriffe möglich sind, gleich IEnumerable<String> vorgegeben, wäre man gar nicht erst in die (trügerische) Versuchung gekommen, Indexzugriffe zu verwenden.

herbivore
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 631

beantworten | zitieren | melden

Neue Aufgabe:

- zwei MovingObjects erstellen (Ship & Asteroid)
- ein 3. MovingObject erstellen, dass vom Schiff aus, den Asteroiden trifft
- der vorgegebene Code darf beliebig verändert werden
- Viel Spaß!


public class MovingObject
{
    public int x, y;    // Position
    public int r;       // Radius
    public int dx, dy;  // Bewegungsrichtung

    public MovingObject(int x, int y, int r, int dx, int dy)
    {
        this.x = x;
        this.y = y;
        this.r = r;
        this.dx = dx;
        this.dy = dy;
    }

    public static MovingObject GenerateRandomObject()
    {
        System.Threading.Thread.Sleep(156);
        Random rnd = new Random(DateTime.Now.Millisecond);
        return new MovingObject(rnd.Next(0, 10), rnd.Next(0, 10),
                                rnd.Next(1, 4), rnd.Next(0, 10),
                                rnd.Next(0, 10));
    }
}
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Alf Ator am .
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Hallo,

ich verstehe deine Angabe leider noch nicht so ganz, aber eins weiß ich bestimmt:

Deklariere das Random Objekt irgendwo und erzeuge nur eine Instanz davon, da ansonsten ziemlich oft gleiche Werte als Ergebnis kommen ;)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Daniel B. am .
private Nachricht | Beiträge des Benutzers
gfoidl
myCSharp.de - Team

Avatar #avatar-2894.jpg


Dabei seit:
Beiträge: 7538
Herkunft: Waidring

beantworten | zitieren | melden

Hallo Alf Ator,

zusätzlich zu Daniel B.s Hinweis: wenn der Code beliebig verändert werden kann dann ersetzt ich GenerateRandomObject durch etwas was bekannte Positionen für die Objekte zurückgibt und die Aufgabe ist schon gelöst.
Selbst wenn das ein wenig strenger wäre würde ich beim Random ein bekanntes Seed übergeben und somit kann ich die Positionen auch errechnen.

Ich denke du solltest die Aufgabe nachbessern.
Ich könnte für die Aufgabe aber auch den Code posten - dann wärs gelöst, aber das soll ja nicht das Ziel der Übung sein.


mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.

"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Ich hab hier mal eine kleine Grafische darstellung gemacht, für die die es brauchen (so wie ich :P) :


  public partial class DrawBoard : Form
    {
        public MovingObject ship;
        public MovingObject ast;
        public MovingObject shot;

        public DrawBoard(MovingObject a, MovingObject b) : this(a, b, null)
        {
        }

        public DrawBoard(MovingObject a, MovingObject b, MovingObject c)
        {
            InitializeComponent();
            ship = a;
            ast = b;
            shot = c;
            Timer t = new Timer();
            t.Interval = 500;
            t.Tick += new EventHandler(t_Tick);
            t.Start();
        }

        void t_Tick(object sender, EventArgs e)
        {
            if (ship != null)
            {
                ship.Move();
            }
            if (ast != null)
            {
                ast.Move();
            }
            if (shot != null)
            {
                shot.Move();
            }
            this.Invalidate();
            if (shot.x == ast.x && shot.y == ast.y)
            {
                MessageBox.Show("TREFFER!");
            }
        }

        protected override void OnPaint(PaintEventArgs e)
        {
            Graphics draw = e.Graphics;
            {//DrawGraph
                    Pen gray = new Pen(Brushes.Gray, 1F);
                    int max = 200; // constant     |
                    int abstand = 50; // constant  > change for graphstyle
                    for (int i = 0; i < max; i++)
                    {
                        draw.DrawLine(gray, new Point(i * abstand, 0), new Point(i * abstand, max * abstand));
                        draw.DrawLine(gray, new Point(0, i * abstand), new Point(max * abstand, i * abstand));
                        draw.DrawString((i * abstand).ToString() + "px", new Font(FontFamily.GenericSansSerif, 7F), Brushes.Black, new PointF(abstand * i, 0));
                        draw.DrawString((i * abstand).ToString() + "px", new Font(FontFamily.GenericSansSerif, 7F), Brushes.Black, new PointF(0, abstand * i));
                    }
            } //End DrawGraph
            //Draw the Objects
            if (ship != null)
            {
                Pen black = new Pen(Brushes.Black, 2F);
                draw.DrawEllipse(black, ship.x * 40, ship.y * 40, ship.r * 10, ship.r * 10);
            }
            if (ast != null)
            {
                Pen blue = new Pen(Brushes.Blue, 2F);
                draw.DrawEllipse(blue, ast.x * 40, ast.y * 40, ast.r * 10, ast.r * 10);
            }
            if (shot != null)
            {
                Pen green = new Pen(Brushes.Green, 1.5F);
                draw.DrawEllipse(green, shot.x * 40, shot.y * 40, shot.r * 10, shot.r * 10);
            }
            //Draw line for movement
            Pen red = new Pen(Brushes.Red, 1F);
            draw.DrawLine(red, new Point(ship.x * 40, ship.y * 40), new Point(ship.dx * 40, ship.dy * 40));
            draw.DrawLine(red, new Point(ast.x * 40,ast.y * 40), new Point(ast.dx * 40, ast.dy * 40));
            draw.DrawLine(red, new Point(shot.x * 40, shot.y * 40), new Point(shot.dx * 40, shot.dy * 40));
        }
        

        /// <summary>
        /// Required designer variable.
        /// </summary>
        private System.ComponentModel.IContainer components = null;

        /// <summary>
        /// Clean up any resources being used.
        /// </summary>
        /// <param name="disposing">true if managed resources should be disposed; otherwise, false.</param>
        protected override void Dispose(bool disposing)
        {
            if (disposing && (components != null))
            {
                components.Dispose();
            }
            base.Dispose(disposing);
        }

        #region Windows Form Designer generated code

        /// <summary>
        /// Required method for Designer support - do not modify
        /// the contents of this method with the code editor.
        /// </summary>
        private void InitializeComponent()
        {
            this.SuspendLayout();
            // 
            // DrawBoard
            // 
            this.AutoScaleDimensions = new System.Drawing.SizeF(6F, 13F);
            this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font;
            this.ClientSize = new System.Drawing.Size(365, 262);
            this.Name = "DrawBoard";
            this.Text = "DrawBoard";
            this.ResumeLayout(false);

        }

        #endregion
    }

OK, hab das ganze denk ich jetzt mal verstanden, fehlt nur noch die Berechnung - aber das ist nur noch Kopfsache und wenn ich Zeit dafür finde ^^

[DrawBoard updated]
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Daniel B. am .
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

@Alf Ator
Ist es ausreichend wenn man sieht dass die Objekte kolidieren oder muss man auch eine Kollisionserkennung einbauen?
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Ich lade jetzt einfach mal meine derzeitige Lösung hoch.
Vielleicht ist es ja schon ausreichend :P (hab das als .rar hochgeladen da ich es irgendwie unnütz finde 4 .cs Dateien zu posten) [Programm update]
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Daniel B. am .
Attachments
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Zitat
Nachricht von Alf Ator vom 22.07.2011 15:03
RE: Programmier spiel

Da du jetzt grundsätzlich triffst, gilt die Aufgabe als gelöst, und du darfst dir eine neue Aufgabe ausdenken

Endlich 8)

OK-neue Aufgabe ...

ich hätte gerne eine Klasse die mit Binärzahlen rechnet (es sollen die 4 Grundrechnungsarten implementiert werden). (Einmal mit operator overloading und einmal als Methode [ebenfalls alle 4] um beispielsweise eine int-Zahl hinzu zu addieren [ binary.add(123) ])
Als Konstruktor kann man entweder die Binärzahl als string übergeben oder eine int-Zahl die dann in eine Binärzahl umgerechnet wird. Intern wird alles bitweise gerechnet!
Jedes Bit soll einzeln via Index gesetzt werden können bzw abgerufen werden (Die Zahl darf ebenfalls nicht als normale int-Zahl vorhanden sein sondern im Binär-Format).
Man soll ebenfalls die Zahl mit ToInt() als Integer Zahl bekommen können.
Viel Spaß!
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von Daniel B. am .
private Nachricht | Beiträge des Benutzers
stes
myCSharp.de - Member

Avatar #avatar-3381.png


Dabei seit:
Beiträge: 67

beantworten | zitieren | melden

Hallo zusammen,

hier meine Lösung der Aufgabe von Daniel:

Zunächst die Klasse zur Darstellung von Binärzahlen:
(Achtung: Die Klasse ist relativ lang geworden, daher habe ich sie zusätzlich als Anhang hinzugefügt; der eingefügte Code lässt sich ja zum Glück minimieren ^^)


using System;

namespace Binary
{
    public struct BinaryNumber
    {
        public const int BIT_QUANTITY = 8;

        public bool this[int i]
        {
            get { return Bits[i]; }
            set { Bits[i] = value; }
        }
        /// <summary>
        /// least significant bit
        /// </summary>
        public bool LSB
        {
            get { return Bits[0]; }
        }
        /// <summary>
        /// most significant bt
        /// </summary>
        public bool MSB
        {
            get { return Bits[Bits.Length - 1]; }
        }

        private bool[] bits;
        public bool[] Bits
        {
            get { return bits; }
            set { bits = value; }
        }

        #region constructors

        public BinaryNumber(int fromInt)
        {
            bits = new bool[BIT_QUANTITY];
            if (fromInt > pow2(BIT_QUANTITY-1)-1 || fromInt < -pow2(BIT_QUANTITY-1))
                throw new ArgumentOutOfRangeException();
            else
            {
                if (fromInt ≥ 0)
                    Bits = convertInt(fromInt);
                else if (fromInt < 0)
                {
                    Bits = convertInt(-fromInt);
                    Bits = this.Neg().Bits;
                }
            }

        }

        public BinaryNumber(string fromString)
        {
            bits = new bool[BIT_QUANTITY];
            if (fromString.Length != BIT_QUANTITY)
                throw new ArgumentException();
            for (int n = 0; n < BIT_QUANTITY; n++)
            {
                Bits[n] = (fromString[BIT_QUANTITY - 1 - n] == '1');
            }
        }

        #endregion

        private bool[] convertInt(int x)
        {
            bool[] buffer = new bool[BIT_QUANTITY];
            for (int i = 0; i < buffer.Length; i++)
            {
                int pot = (int)Math.Pow(2, i);
                buffer[i] = ((x & pot) == pot);
            }
            return buffer;
        }

        private int pow2(int e)
        {
            return (e == 0) ? 1 : (2 << e - 1);
        }

        #region calculations

        public BinaryNumber Neg()
        {
            BinaryNumber b = new BinaryNumber(0);
            for (int n = 0; n < Bits.Length; n++)
            {
                b.Bits[n] = !Bits[n];
            }
            return b.Add(1);
        }

        public BinaryNumber Abs()
        {
            return MSB ? this.Neg() : this;
        }

        public BinaryNumber Add(BinaryNumber b)
        {
            BinaryNumber newB = new BinaryNumber(0);
            bool carry = false;
            for (int i = 0; i < newB.Bits.Length; i++)
            {
                newB.Bits[i] = Bits[i] ^ b.Bits[i] ^ carry;
                carry = (Bits[i] & b.Bits[i]) | (Bits[i] & carry) | (b.Bits[i] & carry);
            }
            return newB;
        }

        public BinaryNumber Add(int i)
        {
            return this.Add(new BinaryNumber(i));
        }

        public BinaryNumber Subtract(int i)
        {
            return this.Subtract(new BinaryNumber(i));
        }

        public BinaryNumber Subtract(BinaryNumber b)
        {
            return this.Add(b.Neg());
        }

        public BinaryNumber Multiply(BinaryNumber b)
        {
            if (b == 1)
                return this;
            else
                return this + this.Multiply(b - 1);
        }

        public BinaryNumber Multiply(int b)
        {
            return this.Multiply(new BinaryNumber(b));
        }

        public BinaryNumber Divide(BinaryNumber b)
        {
            if (b == 0)
                throw new DivideByZeroException();
            if (!MSB && !b.MSB)
            {
                // positive number
                if (this < b)
                    return new BinaryNumber(0);
                else
                    return (this - b).Divide(b) + 1;
            }
            else if (MSB && b.MSB)
            {
                return this.Abs().Divide(b.Abs());
            }
            else
            {
                // negative number
                return this.Abs().Divide(b.Abs()).Neg();
            }
        }

        public BinaryNumber Divide(int i)
        {
            if (this < new BinaryNumber(i))
                return new BinaryNumber(0);
            else
                return new BinaryNumber(1) + (this - new BinaryNumber(i)).Divide(i);
        }
        
        #endregion

        #region operator overloads

        public static BinaryNumber operator +(BinaryNumber a, BinaryNumber b)
        {
            return a.Add(b);
        }

        public static BinaryNumber operator +(BinaryNumber a, int b)
        {
            return a.Add(b);
        }

        public static BinaryNumber operator -(BinaryNumber a, BinaryNumber b)
        {
            return a.Subtract(b);
        }

        public static BinaryNumber operator -(BinaryNumber a, int b)
        {
            return a.Subtract(b);
        }

        public static BinaryNumber operator *(BinaryNumber a, int b)
        {
            return a.Multiply(b);
        }

        public static BinaryNumber operator *(BinaryNumber a, BinaryNumber b)
        {
            return a.Multiply(b);
        }

        public static BinaryNumber operator /(BinaryNumber a, BinaryNumber b)
        {
            return a.Divide(b);
        }

        public static BinaryNumber operator /(BinaryNumber a, int b)
        {
            return a.Divide(new BinaryNumber(b));
        }

        public static bool operator ==(BinaryNumber a, BinaryNumber b)
        {
            return a.Equals(b);
        }

        public static bool operator !=(BinaryNumber a, BinaryNumber b)
        {
            return !a.Equals(b);
        }

        public static bool operator >(BinaryNumber a, BinaryNumber b)
        {
            return a.isBigger(b);
        }

        public static bool operator <(BinaryNumber a, BinaryNumber b)
        {
            return b.isBigger(a);
        }

        public static bool operator ==(BinaryNumber a, int b)
        {
            return a.Equals(b);
        }

        public static bool operator !=(BinaryNumber a, int b)
        {
            return !a.Equals(b);
        }

        public static bool operator >(BinaryNumber a, int b)
        {
            return a.isBigger(b);
        }

        public static bool operator <(BinaryNumber a, int b)
        {
            return !a.isBigger(b) && (a != b);
        }

        #endregion

        #region converting methods
        public override string ToString()
        {
            string buffer = "";
            for (int n = Bits.Length-1; n ≥ 0; n--)
            {
                buffer += Bits[n] ? "1" : "0";
            }
            return buffer;
        }

        public int ToInt()
        {
            int i = 0;
            bool[] bits = null;
            int sign = 0;
            if (Bits[Bits.Length - 1])
            {
                sign = -1;
                bits = this.Neg().Bits;
            }
            else
            {
                sign = 1;
                bits = this.Bits;
            }
            for (int n = 0; n < bits.Length; n++)
            {
                if (bits[n])
                    i += pow2(n);
            }
            return i*sign;
        }
        #endregion

        public override bool Equals(object obj)
        {
            if (obj is BinaryNumber)
            {
                BinaryNumber comp = (BinaryNumber)obj;
                for (int n = 0; n < Bits.Length; n++)
                {
                    if (Bits[n] != comp.Bits[n])
                    {
                        return false;
                    }
                }
                return true;
            }
            else if (obj is int)
            {
                return Equals(new BinaryNumber((int)obj));
            }
            else
            {
                return false;
            }
        }

        public bool isBigger(BinaryNumber b)
        {
            for (int n = Bits.Length - 1; n ≥ 0; n--)
            {
                if (Bits[n] == b.Bits[n])
                {
                    continue;
                }
                else if (Bits[n] && !b.Bits[n])
                {
                    return true;
                }
                else if (!Bits[n] && b.Bits[n])
                {
                    return false;
                }
            }
            // numbers are equal
            return false;
        }

        public bool isBigger(int b)
        {
            return isBigger(new BinaryNumber(b));
        }
    }
}

Zum Testen der drei Grundrechenarten hier ein kleines Hauptprogramm für die Konsole:


using System;

namespace Binary
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                // input
                Console.Write("Zahl 1: ");
                int a = Convert.ToInt32(Console.ReadLine());
                Console.Write("Zahl 2: ");
                int b = Convert.ToInt32(Console.ReadLine());

                // converting to binary numbers
                BinaryNumber bin1 = new BinaryNumber(a);
                BinaryNumber bin2 = new BinaryNumber(b);

                // output
                Console.WriteLine("Summe:\t\t{0}", (bin1 + bin2).ToInt());
                Console.WriteLine("Differenz:\t{0}", (bin1 - bin2).ToInt());
                Console.WriteLine("Produkt:\t{0}", (bin1 * bin2).ToInt());
                Console.WriteLine("Quotient:\t{0}", (bin1 / bin2).ToInt());

                Console.ReadLine();
                Console.Clear();
            }
        }
    }
}

Kleine Beschreibung:

Die Binärzahlen werden durch ein Array aus mehreren bools dargestellt. Mit der Konstanten BIT_QUANTITY wird festgelegt, aus wie vielen Bits die Binärzahl besteht. WICHTIG: Ich bin grundsätzlich von einer Zahl MIT Vorzeichen ausgegangen, daher führen z. B. 4 Bits zu einem Zahlenbereich von 1000 (- 8) bis 0111 (7).

Weitere Anmerkung: Die pow2-Methode, an einigen Stellen zur Berechnung von 2er-Potenzen genutzt, habe ich anstelle der Math.Pow-Funktion verwendet:


        private int pow2(int e)
        {
            return (e == 0) ? 1 : (2 << e - 1);
        }
ist gleichbedeutend mit

Math.Pow(2, e)

Habe das so implementiert da in der Aufgabenstellung stand man solle intern alles bitweise ausrechnen, bei höheren Werten für die BIT_QUANTITY führt das allerdings zu StackOverflowExceptions; im Zweifelsfall also ggf. durch die Pow-Funktion aus der Math-Klasse ersetzen ;)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von stes am .
Attachments
private Nachricht | Beiträge des Benutzers
Daniel B.
myCSharp.de - Member



Dabei seit:
Beiträge: 87
Herkunft: Linz

beantworten | zitieren | melden

Funktioniert - du bist drann
private Nachricht | Beiträge des Benutzers