Laden...

Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch

Erstellt von abra_joe vor 14 Jahren Letzter Beitrag vor 3 Jahren 771.546 Views
49.485 Beiträge seit 2005
vor 11 Jahren

Hallo Ace86,

Schon im letzten Lösungsvorschlag wurde PadRight nur noch verwendet, wenn d = 0 ist.

das war mir zwar auch aufgefallen, aber erst jetzt, als ich nochmal genauer hingeschaut habe, ist mir aufgegangen, warum du in den meisten Fällen ohne PadRight auskommst. Dem ganzen liegt zu Grunde, dass es bei decimal für die meisten Zahlen mehrere unterschiedliche Repräsentationen mit demselben Zahlenwert gibt.

Klarer wird das, wenn man sich die Decimal.GetBits-Methode anschaut. Demzufolge besteht ein Decimal aus einer vorzeichenlosen 96bit Integer-Zahl (Mantisse), einem Bit für das Vorzeichen und einer Zahl zwischen 0 und 28, die bestimmt, um wieviele Stellen das Komma nach links verschoben werden soll.

Dadurch lässt sich z.B. die Zahl 10 auf verschiedene Arten repräsentieren, nämlich als Integer-Zahl 10 ohne Kommaverschiebung, als Integer-Zahl 100 mit einer Kommaverschiebung um eins nach links, als Integer-Zahl 1000 mit einer Kommaverschiebung um zwei nach links, usw.

Obwohl alle diese Repräsentationen den selben Zahlenwert haben, nämlich 10 und deshalb ein Vergleich mit == oder Equals auch bei unterschiedlichen Repräsentationen true liefert, werden die Zahlen doch unterschiedlich ausgegeben. Folgende Zeilen


Console.WriteLine (new Decimal (10, 0, 0, false, 0));
Console.WriteLine (new Decimal (100, 0, 0, false, 1));
Console.WriteLine (new Decimal (1000, 0, 0, false, 2));

produzieren die folgende Ausgabe:


10
10,0
10,00

Das machst du dir - ob nun bewusst oder unbewusst - in der Methode roundSignificant zu nutze. Wenn z.B. die Zahl 123 mit fünf signifikanten Stellen ausgegeben werden soll, ist dein scaleFactor 0.01m. Der folgende Code


decimal m = 123m;
Console.WriteLine (m);
m /= 0.01m;
Console.WriteLine (m);
m *= 0.01m;
Console.WriteLine (m);

produziert folgende Ausgabe:


123
12300
123,00

Obwohl die Ausgangszahl am Ende wieder den gleichen Zahlenwert hat, hat sich dennoch ihre Repräsentation und damit ihre Ausgabe geändert. Statt zu Anfang als 123 ohne Kommaverschiebung, wird sie am Ende als 12300 mit einer Kommaverschiebung um zwei Stellen nach links repräsentiert.


Interessanterweise würde das nicht passieren, wenn man Division und Multiplikation vertauschen und zum Ausgleich mit dem Kehrwert des scaleFactors rechen würde, also 100m statt 0.01m. Der folgende Code

[csharp]
decimal m = 123m;
Console.WriteLine (m);
m *= 100m;
Console.WriteLine (m);
m /= 100m;
Console.WriteLine (m);
[/csharp]

produziert folgende Ausgabe:

[FRAME]
123
12300
123

Hier hat die Zahl am Ende die gleiche Repräsentation wie am Anfang.

Ich habe allerdings nicht geschaut, ob dieses (unterschiedliche) Verhalten irgendwo verbindlich spezifiziert ist. Wenn das nicht der Fall ist, könnte sich das Verhalten bei einer neuen Framework und/oder Compiler-Version ändern, und wäre somit möglicherweise nicht zukunftssicher. Aber das nur am Rande.[/frame]

Kommen wir nach dieser Vorrede zu deiner Korrektur im aktuellen Lösungsvorschlag gegenüber dem vorherigen. Diese basiert darauf, die Overflow-Exception, die bei manchen Zahlen auftreten kann, wenn 29 signifikate Stellen gewünscht sind, abzufangen und mit einer signifikanten Stelle weniger zu runden. Das ist insofern nicht schlimm, als die Zahlen, bei denen die Overflow-Exception auftreten kann, ohnehin nur maximal 28 signifikante Stellen haben können. Es wird also trotzdem korrekt gerundet.

Allerdings verschiebt der scaleFactor dadurch die Mantisse auch um eine Stelle weniger und man bekommt entsprechend eine Repräsentation mit einer Stelle in der Mantisse weniger und entsprechend einer Kommaverschiebung um eine Stelle weniger. Im Ergebnis gibt ToString dadurch auch eine Stelle weniger aus.

Du sagst, dass man darüber streiten kann, ob in dem Fall zum Ausgleich eine Null angehängt werden müsste. Ich finde es allerdings eindeutig, dass das passieren müsste. Dazu zunächst folgende Test-Methode


private static void Test (decimal d)
{
   for (int i = 25; i <= 29; ++i) {
      Console.WriteLine ("{0,2} {1}", i, FormatSI (d, i, ""));
   }
   Console.WriteLine ();
}

und folgende Aufrufe:


Test (7.1234567890123456789012345678m);
Test (8.1234567890123456789012345678m); // Wie bekannt: die letzte 8 landet eh nicht im decimal

Test (7);
Test (8);

Die beiden ersten Zeilen produzieren folgende Ausgabe:


25 7,123456789012345678901235
26 7,1234567890123456789012346
27 7,12345678901234567890123457
28 7,123456789012345678901234568
29 7,1234567890123456789012345678

25 8,123456789012345678901235
26 8,1234567890123456789012346
27 8,12345678901234567890123457
28 8,123456789012345678901234568
29 8,123456789012345678901234568

Bis hierhin könnte man noch sagen, ok, die letzte Ziffer im zweiten Beispiel ist ja auch nicht im Decimal gelandet, also wird sie korrekterweise nicht mit ausgegeben, aber wenn man sich die Ausgabe der letzten beiden Test-Aufrufe ansieht


25 7,000000000000000000000000
26 7,0000000000000000000000000
27 7,00000000000000000000000000
28 7,000000000000000000000000000
29 7,0000000000000000000000000000

25 8,000000000000000000000000
26 8,0000000000000000000000000
27 8,00000000000000000000000000
28 8,000000000000000000000000000
29 8,000000000000000000000000000

dann sieht man, dass gewünschte signifikante Stellen, die in dem Wert gar nicht vorhanden sind, trotzdem immer als folgende Nullen ausgegeben werden, nur eben nicht in der allerletzten Zeile, die für den Benutzer der Methode nicht nachvollziehbar eine Null am Ende weniger enthält.

Allerdings stimmte ich dir darin zu, dass es kein Problem wäre, das Anfügen dieser letzten Null auch noch einzubauen.

Deshalb und da ich auch sonst keine Fehler mehr gefunden habe, erkläre ich die Aufgabe für gelöst. Ich hoffe, es hat dir und allen Mitleseren Spaß gemacht und einige neue Erkenntnisse beschert.

Du bist dran, die nächste Aufgabe zu stellen.

herbivore

A
15 Beiträge seit 2012
vor 11 Jahren

Das Ziel die Aufgabe besteht darin eine Morphing-Animation zweier geometrischer Figuren auf der Konsole zu erstellen. Dabei soll ein zeitgesteuerter gleichmäßiger Übergang von einem Quadrat zu einem Rhombus mit gleichlangen Diagonalen erzeugt werden. Die Länge der Diagonalen im Rhombus ist gleich der Seitenlänge des Quadrates. Um das zu verdeutlichen habe ich ein Bild angehangen.

Zu Beginn ist die blaue Form zu sehen, welche in die rote Form übergeht. Nachdem die Endform erreicht ist, soll die Animation rückwärts ablaufen, bis wieder die ursprüngliche Form erreicht ist. Die Animation läuft unendlich lange.

Zusätzlich ist zu beachten, dass die Animation für verschieden große Quadrate funktionieren soll und dass zu jeder Zeit der Animation eine vollständig umschlossene Form sichtbar ist, die zur x- und y- Achse symmetrisch ist. Die Farbe der Form ist beliebig.

Es empfiehlt sich in der Konsole Zeichen gleicher Höhe und Breite zu verwenden. Zum zeichnen einer Linie kann die untenstehende Methode verwendet werden.

public void drawLine(int x1, int y1, int x2, int y2, ConsoleColor bgColor)
{
    ConsoleColor BackgroundColorTemp = Console.BackgroundColor;
    int cursorLeftTemp = Console.CursorLeft;
    int cursorTopTemp = Console.CursorTop;

    Console.BackgroundColor = bgColor;

    int dx = Math.Abs(x2 - x1), sx = x2 < x1 ? -1 : 1;
    int dy = -Math.Abs(y2 - y1), sy = y2 < y1 ? -1 : 1;
    int err = dx + dy, e2;

    while(true)
    { 
        Console.CursorLeft = x1;
        Console.CursorTop = y1;
        Console.Write(" ");
        if(x1 == x2 && y1 == y2) break;
        e2 = 2 * err;
        if(e2 > dy) { err += dy; x1 += sx; }
        if(e2 < dx) { err += dx; y1 += sy; }
    }


    Console.BackgroundColor = BackgroundColorTemp;
    Console.CursorLeft = cursorLeftTemp;
    Console.CursorTop = cursorTopTemp;
}
A
764 Beiträge seit 2007
vor 11 Jahren

Ist aber ne ganze Menge geworden..

Ich hoffe, dass stört nicht, dass die 'Pixel' in der Console nicht quatratisch sind. Das kann man erreichen, in dem eine Verknüpfung an die kompilierte Exe erstellt und die Schriftgröße auf z.B. 8x8 einstellt. Andere Möglichkeit ist über die WinAPI. Ich finde aber, dass der Code schon umfangreich genug ist.


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Timers;

namespace RombusTest
{
    class Program
    {
        static void Main(string[] args)
        {
            CubeToRombusMorpher morpher = new CubeToRombusMorpher();
            morpher.Morph(3, 3, 60, 100);

            Console.ReadLine();
        }
    }
    
    public class CubeToRombusMorpher
    {
        private Timer timer;
        private List<Oktaeder> oktaeders;
        private IEnumerator<Oktaeder> enumerator;

        private class Point
        {
            public int X { get; set; }
            public int Y { get; set; }

            public Point(int x, int y)
            {
                X = x;
                Y = y;
            }
            public override string ToString()
            {
                return String.Format("({0}/{1})", X, Y);
            }
        }

        private class Oktaeder
        {
            public Point P1 { get; set; }
            public Point P2 { get; set; }
            public Point P3 { get; set; }
            public Point P4 { get; set; }
            public Point P5 { get; set; }
            public Point P6 { get; set; }
            public Point P7 { get; set; }
            public Point P8 { get; set; }

            public Oktaeder(int mx1, int my1, int mx2, int my2, int mx3, int my3, int mx4, int my4, int mx5, int my5, int mx6, int my6, int mx7, int my7, int mx8, int my8)
            {
                P1 = new Point(mx1, my1);
                P2 = new Point(mx2, my2);
                P3 = new Point(mx3, my3);
                P4 = new Point(mx4, my4);
                P5 = new Point(mx5, my5);
                P6 = new Point(mx6, my6);
                P7 = new Point(mx7, my7);
                P8 = new Point(mx8, my8);
            }

            public override string ToString()
            {
                return String.Join(", ", P1, P2, P3, P4, P5, P6, P7, P8);
            }
        }

        public void Morph(int x1, int y1, int length, int interval)
        {
            InitConsole(x1, y1, length);
            InitTimer(interval);
            InitOktaeders(x1, y1, length);
            DrawCube(x1, y1, x1 + length, y1 + length, ConsoleColor.Green);
            Console.ReadLine();
            timer.Start();
        }

        private void InitConsole(int x1, int y1, int length)
        {
            Console.SetWindowSize((x1 * 2) + length, (y1 * 2) + length);
            Console.SetBufferSize((x1 * 2) + length, (y1 * 2) + length);
        }

        private void InitOktaeders(int x1, int y1, int length)
        {
            oktaeders = new List<Oktaeder>();
            for (int i = 0; i <= (length / 2); i++)
            {
                int mx1 = x1,               my1 = y1 + i;
                int mx2 = x1 + i,           my2 = y1;
                int mx3 = x1 + length - i,  my3 = y1;
                int mx4 = x1 + length,      my4 = y1 + i;
                int mx5 = x1 + length,      my5 = y1 + length - i;
                int mx6 = x1 + length - i,  my6 = y1 + length;
                int mx7 = x1 + i,           my7 = y1 + length;
                int mx8 = x1,               my8 = y1 + length - i;
                oktaeders.Add(new Oktaeder(mx1, my1, mx2, my2, mx3, my3, mx4, my4, mx5, my5, mx6, my6, mx7, my7, mx8, my8));
            }
            enumerator = oktaeders.GetEnumerator();
        }

        private void InitTimer(int interval)
        {
            timer = new Timer();
            timer.Interval = interval;
            timer.Elapsed += new ElapsedEventHandler(timer_Elapsed);
        }

        private void timer_Elapsed(object sender, ElapsedEventArgs e)
        {
            timer.Stop();
            Console.Clear();

            if (enumerator.MoveNext())
            {
                DrawOktaeder(enumerator.Current, ConsoleColor.Magenta);
                Console.WriteLine();
                Console.WriteLine(enumerator.Current);
            }
            else
            {
                oktaeders.Reverse();
                enumerator = oktaeders.GetEnumerator();
                if (enumerator.MoveNext())
                {
                    DrawOktaeder(enumerator.Current, ConsoleColor.Magenta);
                    Console.WriteLine();
                    Console.WriteLine(enumerator.Current);
                }
            }
            
            timer.Start();
        }

        private void DrawOktaeder(Oktaeder oktaeder, ConsoleColor color)
        {
            DrawLine(oktaeder.P1.X, oktaeder.P1.Y, oktaeder.P2.X, oktaeder.P2.Y, color);
            DrawLine(oktaeder.P2.X, oktaeder.P2.Y, oktaeder.P3.X, oktaeder.P3.Y, color);
            DrawLine(oktaeder.P3.X, oktaeder.P3.Y, oktaeder.P4.X, oktaeder.P4.Y, color);
            DrawLine(oktaeder.P4.X, oktaeder.P4.Y, oktaeder.P5.X, oktaeder.P5.Y, color);
            DrawLine(oktaeder.P5.X, oktaeder.P5.Y, oktaeder.P6.X, oktaeder.P6.Y, color);
            DrawLine(oktaeder.P6.X, oktaeder.P6.Y, oktaeder.P7.X, oktaeder.P7.Y, color);
            DrawLine(oktaeder.P7.X, oktaeder.P7.Y, oktaeder.P8.X, oktaeder.P8.Y, color);
            DrawLine(oktaeder.P8.X, oktaeder.P8.Y, oktaeder.P1.X, oktaeder.P1.Y, color);
        }

        private void DrawRombus(int x1, int y1, int x2, int y2, ConsoleColor color)
        {
            DrawLine(x1, (y1 + y2) / 2, (x1 + x2) / 2, y1, color);
            DrawLine((x1 + x2) / 2, y1, x2, (y1 + y2) / 2, color);
            DrawLine(x1, (y1 + y2) / 2, (x1 + x2) / 2, y2, color);
            DrawLine((x1 + x2) / 2, y2, x2, (y1 + y2) / 2, color);
        }

        private void DrawCube(int x1, int y1, int x2, int y2, ConsoleColor color)
        {
            DrawLine(x1, y1, x2, y1, color);
            DrawLine(x1, y1, x1, y2, color);
            DrawLine(x1, y2, x2, y2, color);
            DrawLine(x2, y1, x2, y2, color);
        }

        private void DrawLine(Point p1, Point p2, ConsoleColor color)
        {
            DrawLine(p1.X, p1.Y, p2.X, p2.Y, color);
        }
        private void DrawLine(int x1, int y1, int x2, int y2, ConsoleColor color)
        {
            ConsoleColor BackgroundColorTemp = Console.BackgroundColor;
            int cursorLeftTemp = Console.CursorLeft;
            int cursorTopTemp = Console.CursorTop;

            Console.BackgroundColor = color;

            int dx = Math.Abs(x2 - x1), sx = x2 < x1 ? -1 : 1;
            int dy = -Math.Abs(y2 - y1), sy = y2 < y1 ? -1 : 1;
            int err = dx + dy, e2;

            while (true)
            {
                Console.CursorLeft = x1;
                Console.CursorTop = y1;
                Console.Write(" ");
                if (x1 == x2 && y1 == y2) break;
                e2 = 2 * err;
                if (e2 > dy) { err += dy; x1 += sx; }
                if (e2 < dx) { err += dx; y1 += sy; }
            }

            Console.BackgroundColor = BackgroundColorTemp;
            Console.CursorLeft = cursorLeftTemp;
            Console.CursorTop = cursorTopTemp;
        }
    }
}

Edit: Da macht man noch ne winzige Änderung und hat gleich mal nen Fehler rein.. korrigiert.

A
15 Beiträge seit 2012
vor 11 Jahren

Vielen Dank für deine Lösung.
Um die 8x8 Pixel einzustellen reicht es beispielweise einmal den Debugmodus im VS zu starten und einen Rechtsklick auf die Titelleiste der Konsole zu machen und die Eigenschaften entsprechend anzupassen. Die werden gespeichert und bleiben beim nächsten Start bestehen. Aber das ist nur ein Detail, dass jeder selbst einstellen kann und auch nicht in der Aufgabenstellung gefordert war.

Ansonsten habe ich mir die Umsetzung genau so vorgestellt, auch der Quellcode ist schön übersichtlich geworden. Wenn du die DrawRombus-Methode noch entfernst ist er noch ein wenig kürzer 😉. Die Aufgabe ist damit gelöst und du darfst die nächste stellen.

A
764 Beiträge seit 2007
vor 11 Jahren

Ok, danke!

Ich hab mir das was überlegt:
Ihr sollt die Methode GetShortestWay für die Klasse Link implementieren.


class Link
{
    public int ID { get; set; }
    public List<Link> Links { get; set; }

    public Link(int id)
    {
        this.ID = id;
        this.Links = new List<Link>();
    }

    public string GetShortestWay(int startID, int goalID)
    {
        // Viel Spaß!
            
        // [ ... ]

        return "0 -> 7 -> 3 -> 15 -> 4";
    }

    private void Add(Link link)
    {
        if(!this.Links.Contains(link))
            this.Links.Add(link);
    }

    private Link GetRandomLink(Random random)
    {
        int index = random.Next(0, this.Links.Count + 1);
        if (index >= this.Links.Count)
            return this;
        else
            return this.Links[index].GetRandomLink(random);
    }

    public static Link CreateRootLink(int maxLinkCount, int randomLinksCount)
    {
        Link rootLink = new Link(0);
        Random random = new Random(DateTime.Now.Millisecond);
        for (int i = 1; i < maxLinkCount; i++)
            rootLink.GetRandomLink(random).Add(new Link(i));
        for (int i = 1; i < randomLinksCount; i++)
            rootLink.GetRandomLink(random).Add(rootLink.GetRandomLink(random));
        return rootLink;
    }

    public override string ToString()
    {
        return String.Format("{0}: {1} ({2})", this.ID, this.Links.Count,String.Join(", ", this.Links.Select(link => link.ID)));
    }
}

309 Beiträge seit 2008
vor 11 Jahren

Servus,

ich hab das ganze ganz klassisch mit einer Breitensuche gelöst (Kürzester Weg in einem Graphen).
Die ursprüngliche Klasse habe ich noch um das Property "parent" erweitert um einfacher den Weg rekonstruieren zu können.
Es wird auch der Weg zwischen zwei beliebigen (nicht nur root-Knoten "0" als Start) Knoten ("Links") gefunden, sofern er existiert, allerdings nur "nach oben" in den Objektbaum hinein, nicht nach unten, da die Objekte keinen "Eltern" Knoten kennen, und mein Algorithmus abbricht wenn er das Kind gefunden hat, ansonsten müsste der komplette Objektbaum durchlaufen werden um die "Eltern"-Beziehung herzustellen.

Ich hoffe es reicht, trotzdem:


class Link
{
    public int ID { get; set; }
    public List<Link> Links { get; set; }

    public Link Parent { get; set; }

    public Link(int id)
    {
        this.ID = id;
        this.Links = new List<Link>();
    }

    private static Link BfsSearch(Link start, int goalID)
    {
        Queue<Link> queue = new Queue<Link>();
        Link endLink = null;
        List<Link> visited = new List<Link>();

        queue.Enqueue(start);
        visited.Add(start);

        while (queue.Count != 0)
        {
            Link curLink = queue.Dequeue();

            if (curLink.ID == goalID)
            {
                endLink = curLink;
                break;
            }

            foreach (Link child in curLink.Links)
            {
                if (!visited.Contains(child))
                {
                    child.Parent = curLink;
                    visited.Add(child);
                    queue.Enqueue(child);
                }
            }
        }

        return endLink;
    }

    public string GetShortestWay(int startID, int goalID)
    {
        Link endLink = BfsSearch(startID != this.ID ? GetLinkById(startID) : this, goalID);

        if (endLink == null)
            return string.Empty;

        List<int> way = new List<int>();
        while (endLink.ID != startID)
        {
            way.Add(endLink.ID);
            endLink = endLink.Parent;
        }
        way.Add(startID);
        way.Reverse();
        return String.Join(" -> ", way);

    }

    public Link GetLinkById(int id)
    {
        return BfsSearch(this, id);
    }
        
    // ... (siehe oben)

}

using System;class H{static string z(char[]c){string r="";for(int x=0;x<(677%666);x++)r+=c[
x];return r;}static void Main(){int[]c={798,218,229,592,232,274,813,585,229,842,275};char[]
b=new char[11];for(int p=0;p<((59%12));p++)b[p]=(char)(c[p]%121);Console.WriteLine(z(b));}}

A
764 Beiträge seit 2007
vor 11 Jahren

Hallo Scavanger,

danke für die schöne Lösung. (Ich konnte erst jetzt antworten, weil ich krank im Bett lag.)

Also, du bist jetzt dran.

Gruß, Alf

M
47 Beiträge seit 2008
vor 10 Jahren

Hallo Scavanger,

nachdem du dich nicht mehr meldest, stelle ich da ein Rätsel ein, das ich gerade erhalten habe:

Ich suche eine Zahl:
Stelle ich sie im Zweiersystem dar, so endet sie auf 0 und ist 11-stellig.
Stelle ich sie im Vierersystem dar, so ergibt sich für die Quersumme der Wert 11.
Stelle ich sie im Sechzehnersystem dar, so ergibt sich für die Quersumme ein Wert von 26 und für die alternierende Quersumme einer von 0.
Wie lautet die von mir gesuchte Zahl?
(Die jeweilige Quersumme ist im Zehnersystem angegeben!)

Erhalten habe ich das von einem Mathematiker, nachdem das nicht mein Fach ist, habe ich mich an eine empirische Ermittlung (aber mit reduziertem Zahlenraum) gemacht.

Bin gespannt, was euch dazu einfällt...

Mandy

1.346 Beiträge seit 2008
vor 10 Jahren

Hier ist meine Lösung:


class Program
{
    private static void Main()
    {
        for (var i = (int) Math.Pow(2, 10); i < Math.Pow(2, 11); i++) // 11 Stellig im 2er System
            if (i%2 == 0 // Endet im 2er-System auf 0
                && DigitSum(i, 4) == 11 // Quersumme zur Basis 4 = 11
                && DigitSum(i, 16) == 26 // Quersumme zur Basis 16 = 26
                && AlterniteDigitSum(i, 16) == 0) // alternierende Quersumme zur Basis 16 = 0
                    Console.WriteLine(i);
        Console.ReadKey();
    }

    static int DigitSum(int number, int toBase)
    {
        return ToString(number, toBase).Select(a => FromString(a.ToString(), toBase)).Sum();
    }
    static int AlterniteDigitSum(int number, int toBase)
    {
        bool add = false;
        int sum = 0;
        foreach (char a in ToString(number, toBase).Reverse())
        {
            sum += add ? FromString(a.ToString(), toBase) : -FromString(a.ToString(), toBase);
            add = !add;
        }
        return sum;
    }

    static string ToString(int number, int toBase)
    {
        var resultingString = new StringBuilder();

        const string mapping = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

        do
        {
            resultingString.Append(mapping[number % toBase]);
            number /= toBase;
        } while (number > 0);

        return new string(resultingString.ToString().Reverse().ToArray());
    }

    static int FromString(string number, int toBase)
    {
        var resultingNumber = 0;

        const string mapping = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

        foreach (var ch in number)
        {
            resultingNumber *= toBase;
            resultingNumber += mapping.IndexOf(ch);
        }

        return resultingNumber;
    }
}


Die Lösung ist 2006 😉

S
417 Beiträge seit 2008
vor 10 Jahren

Bin gespannt, was euch dazu einfällt...

Google 😛
Mathe-Board: Knobelecke: Gesucht wird eine Zahl...

M
47 Beiträge seit 2008
vor 10 Jahren

Hallo pdelvo,

die DigitSum gefällt mir, darauf wär ich nicht gekommen.

Bin gespannt, was du für eine Aufgabe hast...

Mandy

309 Beiträge seit 2008
vor 10 Jahren

Vielleicht hat ja jemand Lust darauf:

Ich suche eine Implementierung für folgende Erwieterungsmethode:


public static bool Contains<T>(this IEnumerable<T> enumerable, IEnumerable<T> item, IEqualityComparer<T> comparer)

Die Überladung soll prüfen ob innerhalb einer Auflistung die selben Elemente einer anderen Auflistung vorkommen in der gleichen Reihenfolge und Anzahl an beliebiger Stelle.
Beispiel:

A ("enumerable"):
*a *b *c *d *e *f *g

B ("item):
*c *d

Soll TRUE ergeben:

ebenso:
*a *b

oder
*e *f *g

aber nicht:
*b *c *e

oder
*f *g *h

using System;class H{static string z(char[]c){string r="";for(int x=0;x<(677%666);x++)r+=c[
x];return r;}static void Main(){int[]c={798,218,229,592,232,274,813,585,229,842,275};char[]
b=new char[11];for(int p=0;p<((59%12));p++)b[p]=(char)(c[p]%121);Console.WriteLine(z(b));}}

4.221 Beiträge seit 2005
vor 10 Jahren

Zugegeben eine plumpe Lösung:


public static bool Contains<T>(IEnumerable<T> enumerable, IEnumerable<T> item, IEqualityComparer<T> comparer)
{

	StringBuilder sbA = new StringBuilder();
        StringBuilder sbB = new StringBuilder();

        foreach (var a in enumerable)
        {
            sbA.Append(a.ToString());
        }

        foreach (var b in item)
        {
            sbB.Append(b);
        }

        return sbA.ToString().IndexOf(sbB.ToString())>-1;
}

Früher war ich unentschlossen, heute bin ich mir da nicht mehr so sicher...

1.346 Beiträge seit 2008
vor 10 Jahren

Hallo!

@Programmierhans

Leider enthällt deine Lösung einige Fehler:* Du kannst nicht davon ausgehen, dass die Klasse ToString korrekt implementiert, und vorallem kannst du nicht davon ausgehen, dass Die ToString zuordnung eindeutig ist

  • Sei enumerable { 10, 11, 12}, dann ist bei deiner Lösung {1, 1} oder {1, 2} enthalten
  • Du kannst nicht dsavon ausgehen das enumerable endlich ist. Es kann ja z.B. eine Auflistung aller Primzahlen sein, und somit nie enden, und trotzdem ist {2, 3, 5, 7} enthalten

Hier ist meine Lösung:

Sie mag zwar nicht wirklich die schnellste sein, aber ich denke sie funktioniert:


        public static bool All<T>(this IEnumerable<T> items, Func<T, bool> predicate, out int? count)
        {
            int i = 0;

            foreach (var item in items)
            {
                if (!predicate(item))
                {
                    count = null;
                    return false;
                }
                i++;
            }
            count = i;
            return true;
        }


        public static bool Contains<T>(this IEnumerable<T> enumerable, IEnumerable<T> item,
                                       IEqualityComparer<T> comparer)
        {
            var itemCount = item.Count();

            if (itemCount == 0) return true;

            var index = 0;
            foreach (var temp in enumerable.Select(currentStart => enumerable.Skip(index).Zip(item, comparer.Equals)))
            {
                int? count;
                temp.All(a => a, out count);
                if (count == itemCount) return true;
                index++;
            }
            return false;
        }

LG pdelvo

H
114 Beiträge seit 2007
vor 10 Jahren

Hallo zusammen,

ich hab mich auch mal eben daran versucht, weil es als kurze Ablenkung genau richtig kam 😉

public static bool Contains<T>(this IEnumerable<T> source,
    IEnumerable<T> needle,
    IEqualityComparer<T> comparer)
{
    if (!needle.Any())
        return false;

    var firstNeedle = needle.First();
    var needleEnumerator = needle.Skip(1).GetEnumerator();

    bool itemsAreEqual = false;

    foreach (var item in source)
    {
        if (!itemsAreEqual)
            itemsAreEqual = comparer.Equals(item, firstNeedle);
        else
        {
            if (!needleEnumerator.MoveNext())
                return true;
            else
            {
                itemsAreEqual = comparer.Equals(needleEnumerator.Current, item);
                if (!itemsAreEqual)
                    needleEnumerator = needle.Skip(1).GetEnumerator();
            }
        }
    }

    return itemsAreEqual;
}

In einem schnellen Test hat es geklappt, keine Ahnung wie robust oder performant das insgesamt ist 😉

Grüße, HiGHteK

49.485 Beiträge seit 2005
vor 10 Jahren

Hallo pdelvo,

Du kannst nicht dsavon ausgehen das enumerable endlich ist.

dann solltest du IEnumerable<T>.Count() nicht benutzen 😃 [EDIT]Ok, dein Edit im folgenden Beitrag zeigt, dass du verstanden hast, warum hinter dem Satz ein Smiley stand/steht. Für die Methode wären unendliche Sequenzen unpraktikabel. In der Mathematik gibt sowas allerdings häufiger, siehe Semi-entscheidbar.[/EDIT]

Hallo HiGHteK,

das kann so nicht hinkommen, der folgende Code liefert mit deiner Implementierung fälschlich false:

var a = new List<int> { 1, 1, 2, 3 };
var b = new List<int> {    1, 2, 3 };
Console.WriteLine (Contains (a, b, EqualityComparer<int>.Default));

herbivore

1.346 Beiträge seit 2008
vor 10 Jahren

Ich benutze es bei der zu prüfenden Sequenz. Da kann ich mMn schon von endlichkeit Ausgehen. Ansonsten kann man auf programmatischen Weg nicht überprüfen ob die Sequenz in einer anderen enthalten ist. Bei der Äußeren Sequenz benutze ich Count nicht. Die kann (theoretisch) unendlich sein

Edit: Jetzt wo ich nochmal drüber nachdenke macht die Frage unendlicher Sequenzen eigentlich keinen Sinn. Wenn ich eine Auflistung aller Primzahlen habe, und dort nach {1,7,8} suche würde ich nie zu einem Ergebnis kommen. Das ganze funktioniert nur wirklich wenn die Sequenz auch enthalten ist

R
212 Beiträge seit 2012
vor 10 Jahren

Ich würde Einfach die Distanz(aus [2,4,8] wird [2,4] der einzelnen Elemente zwischenspeichern, wichtig ist die Listen vorerst in zahlen zu convertieren die klar und eindeutig voneinander unterscheidbar sind, es eignen sich sehr 2er potenzen hierfür.
Ja, diese verkürzung deiner elemente kannst du sooft machen wie du möchtest wenn dus äquivalent in beiden tabellen tust. Und dann einfach vergleichen.

Hinweis von herbivore vor 10 Jahren

Bitte keine Vorschläge, wie man die Aufgabe lösen könnte, sondern nur fertige Lösungen, die man selbst für korrekt hält. Wir sind hier im Programmierspiel und nicht in Entwicklung.

4.221 Beiträge seit 2005
vor 10 Jahren

Leider enthällt deine Lösung einige Fehler:
Du kannst nicht davon ausgehen, dass die Klasse ToString korrekt implementiert, und vorallem kannst du nicht davon ausgehen, dass Die ToString zuordnung eindeutig ist

😃 Es ist eine ganz schmerzfreie Implementierung nur genau für dieses Szenario (mit den strikt aufeinander folgenden Strings)... das bin ich mir durchaus bewusst... deshalb auch der Hinweis dass es eine sehr plumpe Lösung ist.

Aber schön dass es jemand gemerkt hat 😃... meine Lösung war ja auch mehr als Scherz gedacht 😃

PS: In genau diesem Szenario würden die Ergebnisse passen.

Gruss
Programmierhans

Früher war ich unentschlossen, heute bin ich mir da nicht mehr so sicher...

H
114 Beiträge seit 2007
vor 10 Jahren

Hallo herbivore,

ich hatte befürchtet, dass ich irgendwas übersehen hab. Aber ich hab die obige Implementierung noch um eine Zeile ergänzt, um den Fehler aus deinem Beispielfall zu eliminieren...
Allerdings kann ich mangels Zeit nicht weiter darüber sinnieren, aber ich hoffe die Implementierung ist nun im Großen und Ganzen soweit OK 😉

Hier nochmals die korrigierte Implementierung...

public static bool Contains<T>(this IEnumerable<T> source,
    IEnumerable<T> needle,
    IEqualityComparer<T> comparer)
{
    if (!needle.Any())
        return false;

    var firstNeedle = needle.First();
    var needleEnumerator = needle.Skip(1).GetEnumerator();

    bool itemsAreEqual = false;

    foreach (var item in source)
    {
        if (!itemsAreEqual)
            itemsAreEqual = comparer.Equals(item, firstNeedle);
        else
        {
            if (!needleEnumerator.MoveNext())
                return true;
            else
            {
                itemsAreEqual = comparer.Equals(needleEnumerator.Current, item);
                if (!itemsAreEqual)
                {
                    itemsAreEqual = comparer.Equals(item, firstNeedle);
                    needleEnumerator = needle.Skip(1).GetEnumerator();
                }
            }
        }
    }

    return itemsAreEqual;
}

Grüße, HiGHteK

4.221 Beiträge seit 2005
vor 10 Jahren

@HiGHteK

Die Lösung ist falsch.

source: a; b; c; d; e; f; g; needle: b; a; Erwartet: False Result: False
source: a; b; c; d; e; f; g; needle: a; b; Erwartet: True Result: True
source: a; b; c; d; e; f; g; needle: e; f; g; Erwartet: True Result: True
source: a; b; c; d; e; f; g; needle: f; g; h; Erwartet: False Result: True
source: a; b; c; d; e; f; g; needle: f; g; g; Erwartet: False Result: True
source: a; b; c; d; e; f; g; needle: a; c; e; Erwartet: False Result: False

Gruss
Programmierhans

Früher war ich unentschlossen, heute bin ich mir da nicht mehr so sicher...

49.485 Beiträge seit 2005
vor 10 Jahren

Hallo HiGHteK,

du hast da ein prinzipielles Problem, das man m.E. nicht mit einer Zeile korrigieren kann. Mein Beispiel war ja nur ein Spezialfall einer ganzen Klasse von ähnlichen Beispielen, die dein Algorithmus alle nicht berücksichtigt. Hier noch eins, das nicht geht (einfach die Kette der Einsen verlängert):

var a = new List<int> {  1, 1, 1, 2, 3 };
var b = new List<int> {     1, 1, 2, 3 };

Dadurch, dass das Muster eine Weile lang passt, verpasst du den Punkt, an dem du für das Finden einer Übereinstimmung mit dem Vergleich beginnen müsstest.

herbivore

4.221 Beiträge seit 2005
vor 10 Jahren

Hier noch meine Implementierung:



        public static bool Contains<T>(this IEnumerable<T> source, IEnumerable<T> needle, IEqualityComparer<T> comparer)
        {
            if (!needle.Any())
            {
                //wenn b leer ist, dann sind alle aus needle (also keine) in source enthalten
                return true;
            }

            bool ret = false;

            IEnumerator<T> enumerA = source.GetEnumerator();
            var bFirst = needle.First();

            int iAOffset = 0;

            while (enumerA.MoveNext())
            {
               //zuerst nur gegen das erste element aus needle vergleichen
                if (comparer.Equals(enumerA.Current, bFirst))
                {
                    //das erste Item von needle passt schon mal
                    ret = true;

                    //einen inneren Enumerator ziehen und auf den äusseren synchronisieren
                    IEnumerator<T> innerA = source.Skip(iAOffset).GetEnumerator();
                    IEnumerator<T> innerB = needle.GetEnumerator();
                    while (ret)
                    {
                        if (innerB.MoveNext())
                        {
                            //verschiebe auch A
                            if (innerA.MoveNext())
                            {
                                ret = comparer.Equals(innerA.Current, innerB.Current);
                            }
                            else
                            {
                                //InnerA ist am Ende also kann B nicht mehr matchen
                                ret = false;
                                break;
                            }
                        }
                        else
                        {
                            if (ret)
                            {
                                //InnerB ist am Ende und ret ist true also kann die Suche abgebrochen werden
                                return ret; 
                            }
                        }
                    }
                } 
                iAOffset += 1;
            }

            return ret;


        }

source: a; b; c; d; e; f; g; needle: Erwartet: True Result: True
source: a; b; c; d; e; f; g; needle: b; a; Erwartet: False Result: False
source: a; b; c; d; e; f; g; needle: a; b; Erwartet: True Result: True
source: a; b; c; d; e; f; g; needle: e; f; g; Erwartet: True Result: True
source: a; b; c; d; e; f; g; needle: f; g; h; Erwartet: False Result: False
source: a; b; c; d; e; f; g; needle: f; g; g; Erwartet: False Result: False
source: a; b; c; d; e; f; g; needle: a; c; e; Erwartet: False Result: False
source: a; b; c; d; e; f; g; needle: a; b; b; Erwartet: False Result: False
source: a; b; c; d; e; f; g; needle: a; h; Erwartet: False Result: False

Passt oder habe ich was übersehen ?

Gruss
Programmierhans

Früher war ich unentschlossen, heute bin ich mir da nicht mehr so sicher...

1.378 Beiträge seit 2006
vor 10 Jahren

Dann möcht ich meine unleserliche Version hier auch posten... 😃


        public static bool Contains<T>(this IEnumerable<T> enumerable, IEnumerable<T> items, IEqualityComparer<T> comparer)
        {
            T[] arr1 = enumerable.ToArray();
            T[] arr2 = items.ToArray();

            int i = 0, i2, j;
            do
            {
                for (j = 0; i < arr1.Length && arr2.Length > 0 && !comparer.Equals(arr1[i], arr2[0]); i++) ;
                for (i2 = i; i2 < arr1.Length && j < arr2.Length && comparer.Equals(arr1[i2], arr2[j]); i2++, j++) ;

            } while (i++ < arr1.Length && j != arr2.Length);

            return j == arr2.Length;
        }

//Edit: Und weils so lustig war noch eine ultrakurz version 😄


        public static bool Contains2<T>(this IEnumerable<T> x, IEnumerable<T> y, IEqualityComparer<T> c)
        {
            T[] a = x.ToArray(), b = y.ToArray();
            for (int i = 0, l, k, n = a.Length, m = b.Length; i < n; i++)
            {
                for (k = 0; i < n && m > 0 && !c.Equals(a[i], b[0]); i++) ;
                for (l = i; l < n && k < m && c.Equals(a[l], b[k]); l++, k++) ;
                if (k == m) return true;
            }
            return false;
        }

Lg, XXX

1.044 Beiträge seit 2008
vor 10 Jahren

Hallo zusammen,

auch wenn schon mehrere ihre Lösung gepostet haben, hier meine noch kürzere (und ekelhafte) als xxxprods:

var idx = 0;
return enumerable.Select( (source, iteration) =>
	item.All( condition => 
	idx < enumerable.Count() && comparer.Equals(condition, enumerable.ToList()[idx++]))).Any(b => b);

zero_x

309 Beiträge seit 2008
vor 10 Jahren

Sory das ich mich erst jetzt melde:

pdelvo lösung ist korrekt und war der erste. Du bist dran.

Meine Lösung sieht fast genau so aus. 😁

using System;class H{static string z(char[]c){string r="";for(int x=0;x<(677%666);x++)r+=c[
x];return r;}static void Main(){int[]c={798,218,229,592,232,274,813,585,229,842,275};char[]
b=new char[11];for(int p=0;p<((59%12));p++)b[p]=(char)(c[p]%121);Console.WriteLine(z(b));}}

1.346 Beiträge seit 2008
vor 10 Jahren

Wieviele verschiedene Möglichkeiten gibt es 2,50€ zusammenzusetzen.

Dabei sind natürlich nur Geldstücke zu benutzen, die auch existieren, alle dürfen aber beliebig oft verwendet werden.
Die Reihenfolge, wie man die Geldstücke zusammenlegt nicht zu beachten. So zählt {2€, 50c} und {50c, 2€} nur einmal.

Als kleine Überprüfungsmöglichkeit kann ich folgende Hilfe geben: Die Quersumme des Ergebnisses ist 18 😃

LG pdelvo

A
764 Beiträge seit 2007
vor 10 Jahren

8o Ich habe gestern noch ein kleines Progrämmchen geschrieben, dass mir das ausrechnet und das läuft immer noch. Ist wohl ein bisschen langsam. Schöne Aufgabe.

4.221 Beiträge seit 2005
vor 10 Jahren

Eigentlich nur eine Spezielle Art von: Rucksackproblem

Früher war ich unentschlossen, heute bin ich mir da nicht mehr so sicher...

49.485 Beiträge seit 2005
vor 10 Jahren

Hallo zusammen,

mich wundert, dass noch kein anderer eine Lösung gepostet hat. Anscheinend war die Aufgabe zu einfach. 😃

Die Lösung ist 63234 [EDIT]200187[/EDIT]. Berechnet mit:

static class App
{
// EDIT: Leider mache auch ich manchmal Flüchtigkeitsfehler:
// private static int [] coins = new int [] { 1, 2, 5, 10, 50, 100, 200 }; // aufsteigend
   private static int [] coins = new int [] { 1, 2, 5, 10, 20, 50, 100, 200 }; // aufsteigend

   public static void Main (string [] astrArg)
   {
      int count = 0;
      CountCombinations (250, coins [coins.Length - 1], ref count);
      System.Console.WriteLine (count);
   }

   private static void CountCombinations (int remaining, int max, ref int count)
   {
      foreach (var coin in coins) {
         if (coin > remaining || coin > max) {
            return;
         }
         if (coin == remaining) {
            ++count;
            return;
         }
         CountCombinations (remaining - coin, coin, ref count);
      }
   }
}

Das Programm ist nach ca. einer [EDIT]anderthalb[/EDIT] Zehntelsekunden fertig. 😃

[EDIT]Ich hatte zuerst vergessen die 20Cent Stücke in die Liste zu packen.[/EDIT]

herbivore

A
764 Beiträge seit 2007
vor 10 Jahren

(Mein Programm ist auf 162875 Ergebnisse gekommen (Quersumme 29) ... X

1.346 Beiträge seit 2008
vor 10 Jahren

@herbivore Du hast leider die 20 cent Stücke vergessen 😉 Blöderweise aber auf die gleiche Quersumme gekommen, die ich errechnet habe 😄

Ich würde aber deine Lösung soweit richtig werten, da wenn man bei dir die 20 cent in das Array einträgt, das, sofern ich mich nicht geirrt habe, richtige Ergebnis herauskommt: 200187 verschiedene Möglichkeiten.

Hier noch meine Lösung, welche aber nicht ganz so effizient ist, aber für 2,50€ noch in absehbarer Zeit ein Ergebnis liefert:


private static void Main()
{
   var limit = 250;
   var counter = 0;

   var coins = new[] { 1, 2, 5, 10, 20, 50, 100, 200}.Reverse().ToArray();

   var currentValue = 0;
   DoCoinTest(limit, ref counter, currentValue, coins);
   Console.WriteLine(counter);
}

private static void DoCoinTest(int limit, ref int counter, int currentValue, int[] coins)
{

   var currentCoin = coins.First();
   while (true)
   {
      if (currentValue > limit) return;
      if (coins.Count() != 1)
      DoCoinTest(limit, ref counter, currentValue, coins.Skip(1).ToArray());
      currentValue += currentCoin;
      if (currentValue == limit) counter++;
   }
}

Ich würde sagen, herbivore ist dran.

LG

49.485 Beiträge seit 2005
vor 10 Jahren

Hallo pdelvo,

Du hast leider die 20 cent Stücke vergessen

da kann man mal sehen, was ich für ein alter Sack bin. Ich habe die Stückelung der D-Mark-Münzen immer noch stärker verinnerlicht als die der Euro-Münzen. 😃 Im Ernst: keine Ahnung, warum ich einen Wert vergessen hatte. Gnädig, dass du die Lösung trotzdem hast gelten lassen. Ich habe meinen Beitrag editiert, natürlich so, dass der ursprüngliche Fehler noch zu erkennen ist, aber gleichzeitig die Lösung jetzt korrekt funktioniert.

Hallo zusammen,

Wenn ich es richtig stehe, ist die meine Zusatzaufgabe aus diesem Beitrag im [url]Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch[/url] noch offen, also das möglichst kompakte Darstellen von Zahlenfolgen durch Zusammenfassen von in sich aufsteigenden oder in sich absteigenden Teilfolgen. Deshalb stelle ich die Zusatzaufgabe (und nur die) als neue Aufgabe. Wer die Herausforderung liebt (hoffentlich alle), schaut sich die Lösung der Grundaufgabe [I]nicht[/I] an.

Wer nach einer größeren Herausforderung sucht, kann sich daran probieren:

Schreibe ein Programm, das eine Folge von immer länger werdenden Listen generiert, die an List<>.Sort übergeben, den quadratischen Laufzeitanstieg aufzeigen.

Zum Beispiel durch eine Ausgabe der folgenden Art, wobei die Zeiten z.B. durch den Aufruf von Stopwatch.Restart/Stop ermittelt werden, wobei die jeweils vom Programm generierten Liste an die List<>.Sort-Methode übergeben wird.

1000 Elemente, 1ms
2000 Elemente, 4ms
3000 Elemente, 9ms
4000 Elemente, 16ms
usw.

Hintergrund: List<>.Sort ist - wie man sich mit dem Reflector oder einem ähnlichen Tool anschauen kann und zur Lösung der Aufgabe anschauen sollte - eine Variante des Quicksort Algorithmus und dieser hat bekanntlich eine Worstcase-Komplexität von O(n^2) hat. Das interessante an der Variante ist, dass als Pivotelement jeweils der Median aus dem Anfangs-, Mittel- und End-Element der zu sortierenden (Teil-)Liste verwendet wird. Ich denke, es ist daher nicht ganz einfach, eine Folge von Eingaben zu produzieren, die zum Worst-Case führen.

Die erste korrekte Lösung, egal welcher der beiden Aufgaben, "gewinnt".

herbivore

49.485 Beiträge seit 2005
vor 10 Jahren

Hallo zusammen,

ich habe per PM und damit außer Konkurrenz bereits eine Lösung für die Quicksort-Aufgabe bekommen. Die Funktion, die die gesuchte Liste(nfolge) generiert, hat keine 15 Zeilen. Wenn es in .NET standardmäßig eine Swap-Methode geben würde, wären sogar nur die Hälfte der Zeilen nötig. Viel Tippen müsst ihr also nicht. Vielleicht motiviert das den einen oder anderen von euch, die Muße des Wochenendes zu nutzen, diese Aufgabe zu lösen.

herbivore

49.485 Beiträge seit 2005
vor 10 Jahren

Hallo zusammen,

hier noch die angekündigte Lösung von DerKleineTomy zusammen mit einer kurzen Main-Methode von mir, die List<>.Sort mit immer längeren, von seiner Methode generierten Listen aufruft und die benötigte Laufzeit ausgibt. Wie man sieht, wenn man das Programm laufen lässt, führt eine Verdoppelung der Eingabelänge zu einer Vervierfachung der Laufzeit. Trotz des Ticks von List<>.Sort, das Pivot-Element aus dem Median von drei Listenelementen zu bestimmen, gibt sie also doch, die "bösen" Listen, die Quicksort in den quadratischen Worstcase treiben.

Vielen Dank an DerKleineTomy für die Lösung und die Erlaubnis zur Veröffentlichung!

Schade, dass es in der Standard-Bibliothek keine Mergesort Implementierung gibt. Mergesort schneidet zwar im Averagecase zwar wohl etwas schlechter ab als Quicksort, aber dafür hat es einen Worstcase von nur n*log(n). Und sortiert im Gegensatz zu Quicksort zudem stabil, belässt also Elementen, die von einem partiellen Comparer als gleich betrachtet werden, in der Reihenfolge, in der sie in der Input-Liste aufgetreten sind.


using System;
using System.Linq;
using System.Collections.Generic;
using System.Diagnostics;

static class App
{
   private static List<int> GenerateList(int numElements)
   {
      List<int> result = Enumerable.Range(1, numElements).ToList();

      for (int right = 1 + (numElements & 1); right < numElements; right += 2)
          Swap(result, right - 1, right / 2);

      return result;
   }

   private static void Swap<T>(IList<T> list, int a, int b)
   {
      T temp = list[a];
      list[a] = list[b];
      list[b] = temp;
   }

   public static void Main (string [] astrArg)
   {
      Stopwatch sw = new Stopwatch ();
      for (int i = 4000; i <= 128000; i += 4000) {
         var list = GenerateList (i);
         sw.Reset ();
         sw.Start ();
         list.Sort ();
         sw.Stop ();
         Console.WriteLine ("{0,6}: {1,4}", i, sw.ElapsedMilliseconds);
      }
   }
}

Damit ist das Programmierspiel wieder offen. Wer eine neue Aufgabe stellen möchte, kann das jetzt tun.

herbivore

R
212 Beiträge seit 2012
vor 10 Jahren

Ich hätte da eine recht eingfache kleine aufgabe, die durch "swap" inspiriert wurde.

undzwar stehen euch insgesamt 2 variablen(int) zur verfügung, in diesen variablen stehen unterschiedliche zahlen, tauscht diese ohne eine weitere variable zu verwenden.

A
118 Beiträge seit 2009
vor 10 Jahren

Ob es einfacher ist sei mal dahin gestellt. 😉


int a = 5;
int b = 10;

a = a + b;
b = a - b;
a = a - b;

// a = 10;
// b = 5;

D
96 Beiträge seit 2012
vor 10 Jahren

Auch hier meine Lösung:


a = (b - a) + (b = a);
1.361 Beiträge seit 2007
vor 10 Jahren

Mir gefällt die Idee von DerKleineTomy,
aber dann doch gleich wie folgt 😉

a = b + 0*(b=a)

beste Grüße
zommi

2.921 Beiträge seit 2005
vor 10 Jahren

Wie wärs mit:


int x = 7;
int y = 11;
y = y + x - (x = y);

(Anspruch: Noch ein Einzeiler)

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

4.931 Beiträge seit 2008
vor 10 Jahren

Oder der alte XOR-Trick:


a ^= b;
b ^= a;
a ^= b;

P.S. Die Kurzform


a^=b^=a^=b;

scheint unter C# so nicht zu funktionieren (aber in C und C++).

R
212 Beiträge seit 2012
vor 10 Jahren
Hinweis von herbivore vor 10 Jahren

Achtung: Durch den weiter unten genannten Messfehler stimmen die Ergebnisse und Schlussfolgerungen nicht. Noch weiter unten finden sich plausible Messergebnisse.

Ich hab das ganze mal auf die performance getestet, und "Aratar" war am schnellsten mit der lösung, somit ist er der Gewinner 😃.

(Das gilt natürlich nur wenn die beiden zahlen zusammengenommen nicht größer als 32bit sind.
In dem Fall sind die anderen Lösungen besser)[Hatte ich aber in der aufgabe nicht berüksichtigt]

EDIT:
Siehe Th69, habe die falsche funktion genommen um die geschwindigkeit zu testen.
/EDIT
Test:


            int a = 15;
            int b = 20;

            for (int i = 0; i < 100000000; i++)
            {
                a = a + b;
                b = a - b;
                a = a - b;

            }

            Console.WriteLine(System.Environment.TickCount);
            Console.Read();

4.931 Beiträge seit 2008
vor 10 Jahren

Hallo Robin0,

ich hoffe mal, daß du nicht die Environment.TickCount-Eigenschaft zur Zeitmessung benutzt hast (zumindestens nicht den absoluten Wert), denn

Environment.TickCount-Eigenschaft

Ruft die Anzahl der Millisekunden ab, die seit dem Systemstart verstrichen sind.

Verwende besser die Stopwatch-Klasse (vor jeder neuen Zeitmessung aber dann wieder stopwatch.Reset() aufrufen, falls du mehrere Zeitmessungen nacheinander mit der selben Stopwatch-Instanz durchführst!).

309 Beiträge seit 2008
vor 10 Jahren
a = b + 0*(b=a)  

Schau dir mal das Konstrukt im Reflector an und staune was der Compiler daraus macht. 8o

Oder ist das etwas absicht? :evil:

Noch lustiger ist was sich der C# Parser daraus bastelt. Erst wenn man sich die IL direkt anschaut wird klar was der Compiler daraus macht.

PS:

Meine Ergebnisse:
(Gemessen mit Stopwatch)

Methode Aratar:
106 ms

Methode DerKleineTomy:
64 ms

Methode zommi:
64 ms

Methode dr4g0n76:
64 ms

Methode Th69:
96 ms

Hinweis von herbivore vor 10 Jahren

Damit nicht jeder selber den Reflector anwerfen muss: a = b + 0*(b=a); wird angezeigt als


b = a;
a = b;

was dazu führen würde, das anschließend in beiden Variablen der Wert von a stehen würde. Erst im IL-Code sieht man, dass die Lade- und Speicheroperationen so verzahnt sind, dass die Werte tatsächlich vertauscht werden:


ldloc.1 
ldloc.0 
stloc.1 
stloc.0

ldloc.i: Fügt den Wert der lokale Variable mit dem Index i oben auf dem Auswertungsstapel hinzu.

stloc.i: Holt den aktuellen Wert von der obersten Position des Auswertungsstapels und speichert ihn in der lokalen Variablen mit dem Index i.

Damit ist die Lösung (trotz der falschen Anzeige im Reflector) ziemlich cool, und sie hat auch kein (potenzielles) Problem mit einem mathematischen Überlauf, wie die anderen Lösungen, die auf Addition und Subtraktion oder Multiplikation und Division basieren.

using System;class H{static string z(char[]c){string r="";for(int x=0;x<(677%666);x++)r+=c[
x];return r;}static void Main(){int[]c={798,218,229,592,232,274,813,585,229,842,275};char[]
b=new char[11];for(int p=0;p<((59%12));p++)b[p]=(char)(c[p]%121);Console.WriteLine(z(b));}}

R
212 Beiträge seit 2012
vor 10 Jahren

@Th69

ups, mein fehler 😄, ich wusste nichmehr genau wie die eigenschaft heißt die prüft wieviele millisecunden das programm schon laeuft und hab anscheinend die falsche genomen.

Aratar war trotzdem der erste.

Hinweis von herbivore vor 10 Jahren

Das Programmierspiel ist wieder frei. Jeder der möchte, kann eine neue Aufgabe stellen.

2.921 Beiträge seit 2005
vor 10 Jahren

Auf Herbivores Hinweis, stelle ich eine neue Aufgabe:

**Vorneweg: **
Ich denke die Aufgabe müsste in 50 Zeilen Code gelöst werden können.

Es geht darum, die Properties eines Objektes ALLE auszugeben und zwar derart:

Nehmen wir an, wir haben die folgenden Klassen (nicht als Text,
sondern wirklich im Visual Studio - vom Code aus benutz- und zugreifbar.

Bsp.:



EDIT: In class Book Fields durch Properties ersetzt

   public class Book
    {
        private int pages = -1;

        public Book(int pages)
        {
            this.pages = pages;
        }

        public string Title { get; set; }
        public int ReleaseYear { get; set; }
        public Author Author { get; set; }
        
        public int GetPages()
        {
            return pages;
        }
    }
	
	public class Author
       {
           public string FirstName { get; set; }
           public string LastName { get; set; }
           public string FancyName { get; set; }
           public string Name { get { return FirstName +" "+ LastName;} }
           public Biography Bio { get; set; }
       }
	
	public class Biography
        {
            public string Name { get; set; }
         }
	

Eine Methode ist zu schreiben, die folgendes ausgibt:

Wie der Aufrufende die Properties, bzw. Methoden aufrufen muss, um an den entsprechenden Wert bzw. Call zu kommen.
Dabei muss es egal sein, ob die Properties/Methoden/Fields mit "Get" oder "get_" anfangen, d.h. aus GetPages wird Pages,
ebenso werden die Klammern, wie z.B. bei GetPages() weggelassen, d.h. nur der reine Name und Punkte werden angegeben.
Das ganze muss auch noch dann funktionieren, wenn die Objektstruktur noch weiter erweitert wird.

Es wird immer der "Vollqualifizierte" Aufrufpfad ausgegeben.

**Stichwort: **

MemberInfo

Die Aufgabe darf rekursiv und iterativ gelöst werden.

**Bsp. für eine korrekte Lösungsausgabe: **

Book
Book.Title
Book.ReleaseYear
Book.Author
Book.Author.FirstName
Book.Author.LastName
Book.Author.FancyName
Book.Author.Name
Book.Author.Bio
Book.Author.Bio.Name
Book.Pages

Da in jeder Zeile sowieso Book vorkommt,
gilt auch, das Objekt kann weggelassen werden:

Ebenfalls korrekt:

Title
ReleaseYear
Author
Author.FirstName
Author.LastName
Author.FancyName
Author.Bio
Author.Bio.Name
Pages

Wenn also z.B. Bio später noch ein Unterobjekt mit

Bio.WeitereEbene.Entity1
Bio.WeitereEbene.Entity2

bekommen würde,

müsste die Ausgabe zusätzlich noch:

Author.Bio.WeitereEbene
Author.Bio.WeitereEbene.Entity1
Author.Bio.WeitereEbene.Entity2

enthalten.

Alles klar? Sonst bitte nachfragen.

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

709 Beiträge seit 2008
vor 10 Jahren

Hi dr4g0n76,
darf Author.Bio nicht ausgegeben werden, weil es nur ein einziges Element enthält oder wurde es in der korrekten Lösungsausgabe vergessen?

2.921 Beiträge seit 2005
vor 10 Jahren

@Pinki: Hatte ich vergessen, habe ich ergänzt.

Es gilt für alles was aufrufbar ist. Danke für den Hinweis. :

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.

2.298 Beiträge seit 2010
vor 10 Jahren

Hallo,

meine Lösung sieht wie folgt aus:


static string GetMembers(Type type)
{
	string sMemberInfos = string.Empty;
	foreach (string sMember in GetMembers(type, string.Empty))
		sMemberInfos += String.Concat(sMember, Environment.NewLine);
}

static List<string> GetMembers(Type type, string sMemberCallPath)
{
	// list to temporary hold the callpaths
	List<string> callPaths = new List<string>();

	if (sMemberCallPath != string.Empty)
		sMemberCallPath += ".";

	// filter all types of namespace System
	if (type.FullName.StartsWith("System"))
		return new List<string>();
			
	MemberInfo[] members = type.GetMembers();

	foreach (MemberInfo member in members)
	{
		switch (member.MemberType)
		{
			case MemberTypes.Field:
				FieldInfo finfo = member as FieldInfo;
				if(!callPaths.Contains(String.Concat(sMemberCallPath,finfo.Name)))
					callPaths.Add(String.Concat(sMemberCallPath,finfo.Name));
				if (finfo.IsPublic)
					callPaths.AddRange(GetMembers(finfo.FieldType, String.Concat(sMemberCallPath, member.Name)));
				break;
			case MemberTypes.Property:
				PropertyInfo pinfo = member as PropertyInfo;
				if (!callPaths.Contains(String.Concat(sMemberCallPath, pinfo.Name)))
					callPaths.Add(String.Concat(sMemberCallPath, pinfo.Name));
					callPaths.AddRange(GetMembers(pinfo.PropertyType, String.Concat(sMemberCallPath, member.Name)));
				break;
			case MemberTypes.Method:
				string sMemberName = member.Name;
				if (member.Name.StartsWith("Get") || member.Name.StartsWith("Set"))
					sMemberName = member.Name.Remove(0, 3);
				else if (member.Name.StartsWith("get_") || member.Name.StartsWith("set_"))
					sMemberName = member.Name.Remove(0, 4);
				if(!callPaths.Contains(String.Concat(sMemberCallPath, sMemberName)))
					callPaths.Add(String.Concat(sMemberCallPath, sMemberName));
				break;
		}
	}

	callPaths.Sort();

	return callPaths; ;
}

Wissen ist nicht alles. Man muss es auch anwenden können.

PS Fritz!Box API - TR-064 Schnittstelle | PS EventLogManager |

2.921 Beiträge seit 2005
vor 10 Jahren

@inflames2k:


  string sMemberInfos = string.Empty;
    foreach (string sMember in sMemberInfos )
        sMemberInfos += String.Concat(sMember, Environment.NewLine);

Das lässt sich nicht übersetzen, wie ist das gemeint?


  string sMemberInfos = string.Empty;
    foreach (string sMember in sMemberInfos )

EDIT: kann mir ja was denken, nur wie Du es wirklich gemeint hast, da gibt es mehrere Möglichkeiten.

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.