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
Mandy
myCSharp.de - Member



Dabei seit:
Beiträge: 47

beantworten | zitieren | melden

Hallo pdelvo,

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

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

Mandy
private Nachricht | Beiträge des Benutzers
Scavanger
myCSharp.de - Member

Avatar #avatar-3209.jpg


Dabei seit:
Beiträge: 323

beantworten | zitieren | melden

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));}}
private Nachricht | Beiträge des Benutzers
Programmierhans
myCSharp.de - Experte

Avatar #avatar-1651.gif


Dabei seit:
Beiträge: 4318
Herkunft: Zentralschweiz

beantworten | zitieren | melden

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...
private Nachricht | Beiträge des Benutzers
pdelvo
myCSharp.de - Member

Avatar #avatar-3354.png


Dabei seit:
Beiträge: 1407

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
HiGHteK
myCSharp.de - Member



Dabei seit:
Beiträge: 117

beantworten | zitieren | melden

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
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 pdelvo,
Zitat von 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
private Nachricht | Beiträge des Benutzers
pdelvo
myCSharp.de - Member

Avatar #avatar-3354.png


Dabei seit:
Beiträge: 1407

beantworten | zitieren | melden

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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von pdelvo am .
private Nachricht | Beiträge des Benutzers
Robin0
myCSharp.de - Member



Dabei seit:
Beiträge: 213

beantworten | zitieren | melden

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.

Moderationshinweis von herbivore (13.09.2013 - 06:58:56):

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.

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

Avatar #avatar-1651.gif


Dabei seit:
Beiträge: 4318
Herkunft: Zentralschweiz

beantworten | zitieren | melden

Zitat von pdelvo
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...
private Nachricht | Beiträge des Benutzers
HiGHteK
myCSharp.de - Member



Dabei seit:
Beiträge: 117

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Programmierhans
myCSharp.de - Experte

Avatar #avatar-1651.gif


Dabei seit:
Beiträge: 4318
Herkunft: Zentralschweiz

beantworten | zitieren | melden

@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...
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 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
private Nachricht | Beiträge des Benutzers
Programmierhans
myCSharp.de - Experte

Avatar #avatar-1651.gif


Dabei seit:
Beiträge: 4318
Herkunft: Zentralschweiz

beantworten | zitieren | melden

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...
private Nachricht | Beiträge des Benutzers
xxxprod
myCSharp.de - Experte

Avatar #avatar-2329.gif


Dabei seit:
Beiträge: 1420
Herkunft: Österreich\Wien

beantworten | zitieren | melden

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 :D


        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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von xxxprod am .
private Nachricht | Beiträge des Benutzers
zero_x
myCSharp.de - Member

Avatar #avatar-2567.gif


Dabei seit:
Beiträge: 1069
Herkunft: Koblenz

beantworten | zitieren | melden

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
zero_x | myCSharp.de - gemeinsam mehr erreichen

Für längere Zeit inaktiv.
private Nachricht | Beiträge des Benutzers
Scavanger
myCSharp.de - Member

Avatar #avatar-3209.jpg


Dabei seit:
Beiträge: 323

beantworten | zitieren | melden

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));}}
private Nachricht | Beiträge des Benutzers
pdelvo
myCSharp.de - Member

Avatar #avatar-3354.png


Dabei seit:
Beiträge: 1407

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 630

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Programmierhans
myCSharp.de - Experte

Avatar #avatar-1651.gif


Dabei seit:
Beiträge: 4318
Herkunft: Zentralschweiz

beantworten | zitieren | melden

Eigentlich nur eine Spezielle Art von: Rucksackproblem
Früher war ich unentschlossen, heute bin ich mir da nicht mehr so sicher...
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,

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
private Nachricht | Beiträge des Benutzers
Alf Ator
myCSharp.de - Member



Dabei seit:
Beiträge: 630

beantworten | zitieren | melden

Mein Programm ist auf 162875 Ergebnisse gekommen (Quersumme 29) ... X(
private Nachricht | Beiträge des Benutzers
pdelvo
myCSharp.de - Member

Avatar #avatar-3354.png


Dabei seit:
Beiträge: 1407

beantworten | zitieren | melden

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

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
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 pdelvo,
Zitat
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
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,

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
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,

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
private Nachricht | Beiträge des Benutzers
Robin0
myCSharp.de - Member



Dabei seit:
Beiträge: 213

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Aratar
myCSharp.de - Member



Dabei seit:
Beiträge: 126

beantworten | zitieren | melden

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;
private Nachricht | Beiträge des Benutzers
DerKleineTomy
myCSharp.de - Member



Dabei seit:
Beiträge: 106

beantworten | zitieren | melden

Auch hier meine Lösung:


a = (b - a) + (b = a);
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Mir gefällt die Idee von DerKleineTomy,
aber dann doch gleich wie folgt ;-)

a = b + 0*(b=a)

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

Avatar #avatar-1768.jpg


Dabei seit:
Beiträge: 3047
Herkunft: Deutschland

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers