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

Avatar #avatar-2999.png


Dabei seit:
Beiträge: 180
Herkunft: Österreich

beantworten | zitieren | melden

Ich hatte es sinngemäs so verstanden: Keine Stacks um die Rekursive Variante iterativ zu implementieren.

Aber gut, dann hier das ganze mit Listen


        static void Main(string[] args) {
            for (int i = 1; i < 7; i++) {
                Console.WriteLine("== {0} =============================", i);
                Move(i);
            }
        }

        static void Move(int n) {
            List<int>[] sticks = new List<int>[3];

            for (int i = 0; i < sticks.Length; i++) {
                sticks[i] = new List<int>();
            }
            //Fill Stick 1
            for (int i = n; i > 0; i--) {
                sticks[0].Add(i);
            }


            int lastTargetStick = -1;


            while (sticks[0].Count > 0 || sticks[1].Count > 0) {
                for (int i = 0; i < sticks.Length; i++) {
                    if (lastTargetStick != i && sticks[i].Count > 0) {
                        if (sticks[(i + 1) % sticks.Length].Count == 0 && sticks[(i + 2) % sticks.Length].Count == 0) {
                            if (sticks[i].Count % 2 == 0) {
                                lastTargetStick = (i + 1) % sticks.Length;
                            } else {
                                lastTargetStick = (i + 2) % sticks.Length;
                            }
                            Console.WriteLine("Nr. {0} von {1} nach {2}", sticks[i][sticks[i].Count-1], i + 1, lastTargetStick + 1);
                            sticks[lastTargetStick].Add(sticks[i][sticks[i].Count-1]);
                            sticks[i].RemoveAt(sticks[i].Count - 1);
                            break;
                        } else {
                            if (sticks[(i + 1) % sticks.Length].Count > 0 && sticks[i][sticks[i].Count - 1] > sticks[(i + 1) % sticks.Length][sticks[(i + 1) % sticks.Length].Count -1] &&
                                sticks[(i + 2) % sticks.Length].Count > 0 && sticks[i][sticks[i].Count - 1] > sticks[(i + 2) % sticks.Length][sticks[(i + 2) % sticks.Length].Count - 1]) {
                                continue;
                            }
                            if ((sticks[(i + 1) % sticks.Length].Count == 0 || sticks[i][sticks[i].Count - 1] < sticks[(i + 1) % sticks.Length][sticks[(i + 1) % sticks.Length].Count - 1]) &&
                                (sticks[(i + 1) % sticks.Length].Count > 0 && sticks[i][sticks[i].Count - 1] % 2 != sticks[(i + 1) % sticks.Length][sticks[(i + 1) % sticks.Length].Count - 1] % 2 ||
                                 sticks[(i + 2) % sticks.Length].Count > 0 && sticks[i][sticks[i].Count - 1] % 2 == sticks[(i + 2) % sticks.Length][sticks[(i + 2) % sticks.Length].Count - 1] % 2 ||
                                 sticks[(i + 2) % sticks.Length].Count > 0 && sticks[i][sticks[i].Count - 1] > sticks[(i + 2) % sticks.Length][sticks[(i + 2) % sticks.Length].Count - 1])) {
                                lastTargetStick = (i + 1) % sticks.Length;
                            } else {
                                lastTargetStick = (i + 2) % sticks.Length;
                            }
                            Console.WriteLine("Nr. {0} von {1} nach {2}", sticks[i][sticks[i].Count - 1], i + 1, lastTargetStick + 1);
                            sticks[lastTargetStick].Add(sticks[i][sticks[i].Count - 1]);
                            sticks[i].RemoveAt(sticks[i].Count - 1);
                            break;
                        }
                    }
                }
            }
            
        }
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 dechavue,

Stacks zur Repräsentation des Inhalts der Stäbe sind schon ok. Daran habe ich gar nicht gedacht, weil der Inhalt der Stäbe für die Ausgabe der Zugfolge nicht benötigt wird. Oder anders ausgedrückt, um ausgeben zu können, welche Scheibe man im x-ten Zug von wo nach wo bewegen muss, braucht man keine Repräsentation des Inhalts der Stäbe, sondern kann das alleine aus der Nummer des Zugs (und der Höhe des Anfangsturms) ausrechnen. Siehe Gibt es Rekursionen die sich nicht in eine Iteration umwandeln lassen?.

Insofern war schon deine erste Lösung ok. Du bist also mit der nächsten Aufgabe dran.

(Wobei ich noch verstehen muss, wie deine Lösung funktioniert. Ich habe erstmal nur die Ausgabe überprüft, um den Fortgang dieses Threads nicht zu bremsen. Vielleicht sagst du, wenn du deine Aufgabe stellst, nebenbei auch noch was zu der Idee deines Hanoi-Lösungsansatzes).

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

Avatar #avatar-2999.png


Dabei seit:
Beiträge: 180
Herkunft: Österreich

beantworten | zitieren | melden

Gut, dann bleiben wir gleich bei Iterativen Varianten.
Ich hätte gerne eine iterative Implementierung des Quicksort

Zu meiner Lösung:
Ich am iPhone ein TvH Spiel, bei dem die Scheiben immer abwechseld gefärbt sind.
Mir ist dann mal aufgefallen, dass beim optimalen Lösen niemals 2 gleichfarbige Scheiben aufeinanderliegen.
Daraus, und aus der Start-Bedingung, dass bei einer geraden Stapelhöhe zuerst auf das "Nicht-Zielfeld" gelegt werden muss und bei einer Ungeraden Stapelhöhe der erste Zug auf das Zielfeld erfolgen muss, ergibt sich der Ablauf von selbst:
Das nächste Ziel ist immer der Stein, mit einer anderen Farbe, bei dem die Breite größer ist, oder ein leeres Feld.
Wichtig ist noch, dass wenn beide Ziele möglich wären, das nicht leere Feld bevorzugt wird.
Die Quelle ergibt sich daraus, dass der zuletzt umgelegte Stein nicht bewegt werden darf + welcher andere Stein umgelegt werden kann.
Die abwechselnden Farben repräsentieren bei mir die Scheibenbreite % 2

Ich habe noch einen Ablauf eines 3er und 4er turms in den Anhang gegeben, zum besseren Verständnis des "Farb - Systems"


Nachtrag: Ich sehe gerade, bei meinem algo könnte man den ersten Zweig des ifs ( if (sticks[(i + 1) % sticks.Length].Count == 0 && sticks[(i + 2) % sticks.Length].Count == 0) {) komplett aus den Schleifen herausziehen, da es nur beim ersten Durchlauf true sein kann. Dann wäre der Algo eventuell auch etwas verständlicher.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von dechavue am .
Attachments
private Nachricht | Beiträge des Benutzers
F.Z.
myCSharp.de - Member



Dabei seit:
Beiträge: 160

beantworten | zitieren | melden

Hallo,

 private static int[] Quicksort(int[] ZuSortieren)
        {
            int[] Sortiert = new int[ZuSortieren.Length];
            int Pivot;
            List<List<List<int>>> Liste = new List<List<List<int>>>();
            List<List<int>> Startliste = new List<List<int>>();
            Startliste.Add(ZuSortieren.ToList());
            Liste.Add(Startliste);

            for (int AnzahlEbenen = 0; AnzahlEbenen < Liste.Count; AnzahlEbenen++)
            {
                List<List<int>> NeuEbene = new List<List<int>>();
                for (int AnzahlListen = 0; AnzahlListen < Liste[AnzahlEbenen].Count; AnzahlListen++)
                {
                    if (Liste[AnzahlEbenen][AnzahlListen].Count > 1)
                    {
                        List<int> Kleiner = new List<int>();
                        List<int> Groesser = new List<int>();
                        List<int> DoppelteWerte = new List<int>();

                        Pivot = Liste[AnzahlEbenen][AnzahlListen][(int)Liste[AnzahlEbenen][AnzahlListen].Count / 2];

                        for (int i = 0; i < Liste[AnzahlEbenen][AnzahlListen].Count; i++)
                        {
                            if (Liste[AnzahlEbenen][AnzahlListen][i] < Pivot)
                                Kleiner.Add(Liste[AnzahlEbenen][AnzahlListen][i]);
                            else if (Liste[AnzahlEbenen][AnzahlListen][i] > Pivot)
                                Groesser.Add(Liste[AnzahlEbenen][AnzahlListen][i]);
                            else
                            {
                                if (Groesser.Contains(Pivot))
                                {
                                    DoppelteWerte.Add(Liste[AnzahlEbenen][AnzahlListen][i]);
                                }
                                else
                                    if (Kleiner.Count > Groesser.Count)
                                        Groesser.Add(Pivot);
                                    else
                                        Kleiner.Add(Pivot);
                            }
                        }
                        NeuEbene.Add(Kleiner);
                        if(DoppelteWerte.Count>0)
                            NeuEbene.Add(DoppelteWerte);
                        NeuEbene.Add(Groesser);
                    }
                    else
                    {
                        NeuEbene.Add(Liste[AnzahlEbenen][AnzahlListen]);
                    }
                    if (Liste[AnzahlEbenen].Count == ZuSortieren.Length)
                    {
                        for (int i = 0; i < ZuSortieren.Length; i++)
                            Sortiert[i] = Liste[AnzahlEbenen][i][0];
                        return Sortiert;

                    }
                }
                Liste.Add(NeuEbene);
            }
            return null;
        }

Aufruf:

            int[] ZuSortieren = {-1, 10, 4, 1, 9, 5, 3,2, 6, 7, 8 ,2};
            ZuSortieren= Quicksort(ZuSortieren);

Ich hoffe ich habe dich richtig verstanden.

Beste Grüße
FZ

EDIT: Es gab Probleme bei gleichen Werten
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von F.Z. am .
"We better hurry up and start coding, there are going to be a lot of bugs to fix."
private Nachricht | Beiträge des Benutzers
dechavue
myCSharp.de - Member

Avatar #avatar-2999.png


Dabei seit:
Beiträge: 180
Herkunft: Österreich

beantworten | zitieren | melden

Deine Implementierung scheint Probleme zu haben wenn gleiche Werte vorkommen.

Da ich dann weg muss und heute nicht mehr dazukomme mir eine Alternativlösung anzuschauen, lass ichs mal durchgehen.

Dann stell deine Aufgabe
private Nachricht | Beiträge des Benutzers
F.Z.
myCSharp.de - Member



Dabei seit:
Beiträge: 160

beantworten | zitieren | melden

Hallo,

Danke für den Hinweis, ich werds mir nochmal genauer ansehen.

Die nächste Aufgabe:
Das Pascalsche-Dreick bis zur n-ten Zeile ausgeben.

z.B. n=3
      1
     1 1
    1 2 1
   1 3 3 1

Grüße
FZ
"We better hurry up and start coding, there are going to be a lot of bugs to fix."
private Nachricht | Beiträge des Benutzers
tobho
myCSharp.de - Member



Dabei seit:
Beiträge: 2

beantworten | zitieren | melden


int wert = 3;
Console.Out.WriteLine("1");
for (int i = o; i ≤ wert; i++)
{
    Console.Out.Write("1");
    for (int a = 1; a ≤ i; a++)
    {
        Console.Out.Write(i+1);
    }
Console.Out.WriteLine("1");

Gruß Tobi
private Nachricht | Beiträge des Benutzers
winSharp93
myCSharp.de - Experte

Avatar #avatar-2918.png


Dabei seit:
Beiträge: 6155
Herkunft: Stuttgart

beantworten | zitieren | melden

Zitat von tobho
[...]
*Räusper*: Pascalsches Dreieck

Geht sicherlich noch besser, aber egal


int[] currentLine = new int[] { };
int[] previousLine;

int max = 5;
for (int n = 0; n < max; n++)
{
    previousLine = currentLine;
    currentLine = new int[previousLine.Length + 1];
    currentLine[0] = 1;
    currentLine[currentLine.Length - 1] = 1;
    for (int i = 1; i < currentLine.Length - 1; i++)
        currentLine[i] = previousLine[i - 1] + previousLine[i];

    Console.Write(new string(' ', max - currentLine.Length));
    for (int i = 0; i < currentLine.Length; i++)
        Console.Write(currentLine[i] + " ");

    Console.WriteLine();
}

Console.ReadLine();

//EDIT:
Ich wusste, ich habe was vergessen:

(Gar nicht so leicht irgendetwas zu finden, dann eben etwas Klassisches )
Ein Programm, das eine Primfaktorzerlegung einer beliebigen Zahl durchführt.
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von winSharp93 am .
private Nachricht | Beiträge des Benutzers
Uwe81
myCSharp.de - Member



Dabei seit:
Beiträge: 285
Herkunft: Ludwigshafen

beantworten | zitieren | melden


class Primes {
    static IEnumerable<int> DividerSequence() {
        yield return 2;
        yield return 3;       
        for(int i = 6; true; i+=6){
            yield return i - 1;
            yield return i + 1;
        }
    }

    public static ICollection<int> GetPrimeFactors(int number) {
        if (number ≤ 0) {
            throw new ArgumentException("Positive integer expected.", "number");
        }

        LinkedList<int> primeFactors = new LinkedList<int>();
        foreach (int factor in DividerSequence()) {
            while (number % factor == 0) {
                primeFactors.AddLast(factor);
                number /= factor;
            }
            if (factor * factor > number) {
                break;
            }
        }
        if (number > 1) {
            primeFactors.AddLast(number);
        }
        return primeFactors;
    }
}

class Program{
    static void Main(string[] args) {
        for (int number = 1; number < 100; number++) {
            ICollection<int> primeFactors = Primes.GetPrimeFactors(number);
            Console.WriteLine(
                "n={0}, Primes=[{1}]", 
                number,
                string.Join(", ", primeFactors.Select(x => x.ToString()).ToArray()));
        }
    }
}




Neue Aufgabe:
Man teste ohne Verwendung der Logarithmusfunktion mit einem einzigen Statement, ob eine Integer eine Zweierpotenz ist.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Uwe81 am .
private Nachricht | Beiträge des Benutzers
edsplash
myCSharp.de - Member

Avatar #avatar-3111.jpg


Dabei seit:
Beiträge: 411

beantworten | zitieren | melden


(number & (number - 1)) == 0

Neue Aufgabe

Eine Implementierung des erweiterten euklidischen Algorithmus
(Rekursiv oder Iterativ)
using Skill
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Zitat von edsplash

(number & (number - 1)) == 0

Du musst allerdings noch die 0 ausschließen. (0 ist keine Zweierpotenz)
Siehe Rausfinden ob eine Zahl 2^x ist.

beste Grüße
zommi
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 zommi, hallo edsplash,

es muss mehr ausgeschlossen werden als die 0. Bei der C#-Integer-Arithmetik, muss es heißen:

number > 0 && (number & (number - 1)) == 0

Denn sonst wird zusätzlich zu dem Fehler bei der 0 bei int.MinValue (-2.147.483.648 bzw. 0x80000000) entweder eine OverflowException ausgelöst (checked) oder die Zahl fälschlich als Zweierpotenz erkannt (unchecked).

herbivore

PS: Damit habe ich wohl die erste korrekte Lösung. :-) Aber ich nehme als nächste Aufgabe einfach die, die edsplash vorgegeben hat.
private Nachricht | Beiträge des Benutzers
F.Z.
myCSharp.de - Member



Dabei seit:
Beiträge: 160

beantworten | zitieren | melden

Hallo,

static void Main(string[] args)
        {
            int a=10,b=78;
            int[] Werte = Euklid(a, b);
            Console.WriteLine("{0} = {1} * {2} + {3} * {4}", Werte[0], Werte[1], a, Werte[2], b);
            Console.ReadLine();
        }

        private static int[] Euklid(int a, int b)
        {
            if(b==0)
                return new int[]{a,1,0};
            int[] Strich = Euklid(b, a % b);
            int[] Werte = new int[3];
            Werte[0] = Strich[0];
            Werte[1] = Strich[2];
            Werte[2] = Strich[1] - (int)(a / b) * Strich[2]; ;
            return Werte;
        }

Nächste Aufgabe:

Den erweiterten euklidischen Algorithmus iterativ implementieren.

Grüße FZ
"We better hurry up and start coding, there are going to be a lot of bugs to fix."
private Nachricht | Beiträge des Benutzers
abra_joe
myCSharp.de - Member



Dabei seit:
Beiträge: 27

Themenstarter:

beantworten | zitieren | melden


        static void Main(string[] args)
        {
           int z1 = Int32.Parse(Console.ReadLine());
           int z2 = Int32.Parse(Console.ReadLine());
           while (z2!=0)
           {
               if (z1 > z2)
                   z1 -= z2;
               else
                   z2 -= z1;
           }
           Console.WriteLine(z1);
           Console.ReadLine();
        }

stimmt doch oder?
private Nachricht | Beiträge des Benutzers
m0rius
myCSharp.de - Member

Avatar #avatar-3125.png


Dabei seit:
Beiträge: 1043

beantworten | zitieren | melden

Hallo abra_joe,

es geht um den erweiterten euklidischen Algorithmus (s. Wikipedia-Artikel).

m0rius
Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg
private Nachricht | Beiträge des Benutzers
abra_joe
myCSharp.de - Member



Dabei seit:
Beiträge: 27

Themenstarter:

beantworten | zitieren | melden

muss ich wohl übersehen haben
tut mir leid....
private Nachricht | Beiträge des Benutzers
LuckyGeorge
myCSharp.de - Member

Avatar #avatar-3262.jpg


Dabei seit:
Beiträge: 72

beantworten | zitieren | melden

Vielleicht nicht die schönste Implementierung aber das sollte es eigentlich sein:


static void Main()
{
	bool parseOk = false;
	int a=0, b=0;
	while (!parseOk)
	{
		Console.WriteLine("Integer Wert a: ";);
		parseOk = Int32.TryParse(Console.ReadLine(), out a);
	}
	parseOk = false;
	while (!parseOk)
	{
		Console.WriteLine("Integer Wert b: ";);
		parseOk = Int32.TryParse(Console.ReadLine(), out b);
	}

	int ggT, x, y;

	if (a > b)
	{
		ExtendedEuclidian(a, b, out ggT, out x, out y);
		Console.WriteLine(a + " * " + x + " + " + b + " * " + y + " = " + ggT);
		Console.WriteLine(a * x + b * y == ggT ? "Stimmt!" : "Stimmt net!";);
	}
	else
	{
		ExtendedEuclidian(b, a, out ggT, out x, out y);
		Console.WriteLine(b + " * " + x + " + " + a + " * " + y + " = " + ggT);
		Console.WriteLine(b * x + a * y == ggT ? "Stimmt!" : "Stimmt net!";);
	}
	Console.ReadKey();
}

private static void ExtendedEuclidian(int a, int b, out int ggT, out int x, out int y)
{
	if (a%b == 0)
	{
		x = 0;
		y = 1;
		ggT = b*y;
		return;
	}

	int dggT, dX, dY, divRem;
	ExtendedEuclidian(b, a % b, out dggT, out dX, out dY);
	x = dY;
	y = dX - dY * Math.DivRem(a, b, out divRem);
	ggT = a * x + b * y;
}

Hatte noch ein Pseudocodeschnippsel in alten Vorlesungsunterlagen ....

*EDIT*: Formatierung angepasst.
private Nachricht | Beiträge des Benutzers
m0rius
myCSharp.de - Member

Avatar #avatar-3125.png


Dabei seit:
Beiträge: 1043

beantworten | zitieren | melden

Hallo LuckyGeorge,

deine Implementierung ist rekursiv, gewollt war eine iterative ...

m0rius
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von m0rius am .
Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg
private Nachricht | Beiträge des Benutzers
LuckyGeorge
myCSharp.de - Member

Avatar #avatar-3262.jpg


Dabei seit:
Beiträge: 72

beantworten | zitieren | melden

Ok, wer lesen kann ist klar im Vorteil. Nun aber:


        private static void ExtendedEuclidianIterative(int a, int b, out int ggT, out int x, out int y)
        {
            x = 0;
            y = 1;
            int dX = 1, dY = 0;

            while(b != 0)
            {
                int divRem;
                int divQuot = Math.DivRem(a, b, out divRem);
                int temp = b;
                b = divRem;
                a = temp;

                temp = x;
                x = dX - divQuot * x;
                dX = temp;

                temp = y;
                y = dY - divQuot*y;
                dY = temp;
            }

            ggT = a;
            x = dX;
            y = dY;
        }

PS: Stammt natürlich nicht von mir sondern aus der Wiki. Nur was soll man bei solchen Algorithmen denn machen ....
private Nachricht | Beiträge des Benutzers
F.Z.
myCSharp.de - Member



Dabei seit:
Beiträge: 160

beantworten | zitieren | melden

Hallo LuckyGeorge,

dein Algorithmus scheint in Ordnung zu sein, nun darfst du auch die nächste Aufgabe stellen.

Viel Spaß mit diese Thread wünscht
FZ
"We better hurry up and start coding, there are going to be a lot of bugs to fix."
private Nachricht | Beiträge des Benutzers
LuckyGeorge
myCSharp.de - Member

Avatar #avatar-3262.jpg


Dabei seit:
Beiträge: 72

beantworten | zitieren | melden

Ok, dann mal weg von den reinen Algorithmen.

Ich hätte gern die Implementierung des Marienbad Spieles mit einem Computergegner. Als Darstellung reicht die Anzahl der Hölzer als Zahl der jeweiligen Reihe. Die Ausgangsposition sieht also so aus:

1
3
5
7

Der Computergegner soll, wenn es möglich ist, die optimale Strategie fahren. Optional kann auch noch berechnet werden ob für die jeweilige Spielsituation des Computergegners eine Gewinnstrategie existiert. Einen Hinweis dazu, wie das gehen kann findet ihr hier:

http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo14.php

Die Aufgabe ist ein wenig umfangreicher als ein reiner Algorithmus aber die meiste Arbeit bezieht sich eigentlich auf die Eingabe. Falls eine solche Aufgabe den Rahmen des Threads sprengt - ich hätte auch noch eine etwas kleinere.
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

die vorgabe lautet "in ca. 50 zeilen code umsetzbar".
LuckyGeorge
myCSharp.de - Member

Avatar #avatar-3262.jpg


Dabei seit:
Beiträge: 72

beantworten | zitieren | melden

[offtopic]@JAck30lena: Hmm, ich finde in diesem Thread mindestens 3 Lösungen die dieser Vorgabe nicht entsprechen und so aufwendig ist die Implementierung auch nicht.[/offtopic]

Aber gut, dann die etwas weniger spassige Aufgabe:
Das Programm muss einen Kreis "zeichnen" können durch Eingabe des Radius. Als Zeichenfeld soll ein einfaches 2 Dimensionales boolsches Array verwendet werden bei dem der Hintergrund false und der Kreis selbst true ist. Der Mittelpunkt des Kreises ist immer der Mittelpunkt des Arrays.
Die Implementierung darf nicht den naiven Ansatz verwenden, dh. einfach nur die Berechnung der Koordinaten durch:

x = R*cos(alpha) und y = R*sin(alpha)

ist nicht ausreichend. Ich schätze, daß die Implementierung in 50 Zeilen mit Eingabe möglich ist da der eigentliche Algorithmus ca. 20 Zeilen umfasst.
private Nachricht | Beiträge des Benutzers
Siassei
myCSharp.de - Member



Dabei seit:
Beiträge: 411

beantworten | zitieren | melden

Hallo,

ich erwecke das Thema mal aus dem Winterschlaf. Ich lass immer mit hohem Interesse mit.
Zitat
Die Implementierung darf nicht den naiven Ansatz verwenden, dh. einfach nur die Berechnung der Koordinaten durch:
x = R*cos(alpha) und y = R*sin(alpha)
Am Ende lässt sich alles darauf zurück führen :-) Dennoch gibt es wohl ein paar Möglichkeiten, da du das Koordinatensystem nicht festgelegt hast ;-)
Ich benutze die ganze normale Kreisgleichung: R² = x² + y² mit: x [-R ; R]

/// <summary>
/// 
/// </summary>
/// <param name="args">
/// A <see cref="String[]"/>
/// </param>
public static void Main(String[] args)
{
	uint R = 1;
	uint aufl = 1;
	bool[][] a = calcCircleArray (R, aufl);

	int i, j;
	for (i = 0; i < a.Length; i++) {
		for (j = 0; j < a[i].Length; j++)
			if (a[i][j])
				System.Console.Write ("+");
			else
				System.Console.Write ("#");

		System.Console.WriteLine ();
	}
}


/// <summary>
/// 
/// </summary>
/// <param name="R">
/// 	Radius des Kreises
/// </param>
/// <param name="n">
/// 	Auflösung: xStep = R * n
/// </param>
/// <returns>
/// 	
/// </returns>               
public static bool[][] calcCircleArray (uint R, uint n)
{
	uint xStep = R * n;
	uint xMax = xStep << 1;
	
	return calcCircleArray (R, n, xMax + 1, xMax + 1);
}


/// <summary>
/// 
/// </summary>
/// <param name="R">
/// 	Radius des Kreises
/// </param>
/// <param name="n">
/// 	n * R = Werte in X-Richtung für R
/// 	n: Bits für die Zahl 1
/// 
/// 	Auflösung: xStep = R * n
/// 	xmax = xStep * R ≤ xLength
/// 	xmax = xStep * R ≤ yLength
/// </param>
/// <param name="xLength">
/// 	Länge des Array in x-Richtung
/// 	xmax = xStep * R ≤ xLength
/// </param>
/// <param name="yLength">
/// 	Länge des Array in y-Richtung
/// 	xmax = xStep * R ≤ yLength
/// </param>
/// <returns>
/// 	
/// </returns>
public static bool[][] calcCircleArray (uint R, uint n, uint xLength, uint yLength)
{
	uint xStep = R * n;
	uint xMax = xStep << 1;
	uint xm = xLength >> 1;
	uint ym = yLength >> 1;

	if (xLength < xMax)
		throw new ArgumentException ("xLength = " + xLength + " < xMax = " + xMax);
	
	else if (yLength < xMax)
		throw new ArgumentException ("yLength = " + yLength + " < xMax = " + xMax);
	
	else if ((xStep << 1) ≥ xLength)
		throw new ArgumentException ("xStep * 2 = " + xStep * 2 + " ≥ xLength = " + xLength);
	
	else if ((xStep << 1) ≥ yLength)
		throw new ArgumentException ("xStep * 2 = " + xStep * 2 + " ≥ yLength = " + yLength);

	// init. Array
	bool[][] res = new bool[xLength][];
			
	for (uint i = 0; i < res.Length; i++) {
		res[i] = new bool[yLength];
	}

	// Berechne Array
	// Kreisformel: R² = x² + y²
	double y;
	double R2 = Math.Pow (xStep, 2.0);
//			double xmd = (double) xm;
			double ymd = (double) ym;
	
	// Optimierung noch möglich
	for (uint i = 0; i ≤ xStep; i++) {
		y = Math.Sqrt (R2 - Math.Pow (i, 2.0));
		
		if(Double.IsNaN(y)) // Außerhabl des Wertebereiches
		   continue;
		
		res[xm + i][(int) Math.Round(ymd + Math.Round(y))] = true;
		res[xm - i][(int) Math.Round(ymd + Math.Round(y))] = true;
		
		res[xm + i][(int) Math.Round(ymd - Math.Round(y))] = true;
		res[xm - i][(int) Math.Round(ymd - Math.Round(y))] = true;
	}

	return res;
}

Ausgabe:
#+#
+#+
#+#

// Edit: Rundungsfehler reduziert

@fz 7090 Das liegt daran, dass ich den y-Wert zu bald in int überführe
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Siassei am .
private Nachricht | Beiträge des Benutzers
F.Z.
myCSharp.de - Member



Dabei seit:
Beiträge: 160

beantworten | zitieren | melden

Hallo,

dein Code ergibt für größere R kein geschlossenen Kreis...

Grü0e FZ
"We better hurry up and start coding, there are going to be a lot of bugs to fix."
private Nachricht | Beiträge des Benutzers
LuckyGeorge
myCSharp.de - Member

Avatar #avatar-3262.jpg


Dabei seit:
Beiträge: 72

beantworten | zitieren | melden

Sorry, hatte gestern und heute Mamutbesprechungen und habe die Antwort jetzt erst gesehen.
Grundsätzlich gilt, was fz7090 schon sagte - leider kein geschlossener Kreis. Der Grund liegt in der von Dir verwendeten Kreisformel welche sich nur bedingt auf diskrete Darstellungen übertragen lässt. Es gibt einen Weg ohne Quadrat und Wurzel .... der aber so (mit Absicht) nicht gefordert ist, also keine Angst.

Grundsätzlich bist Du schon auf dem richtigen Weg, da Du die Spiegelung an den Achsen beachtet und damit nicht den rein naiven Ansatz gewählt hast. Nun noch die Lücken schliessen und Du hast es. ;)
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3430
Herkunft: Trier -> München

beantworten | zitieren | melden

Hallo,
Zitat
Es gibt einen Weg ohne Quadrat und Wurzel ....
...und nennt sich Bresenham-Algorithmus.
Ich hab ihn mal für den Spezialfall angepasst.

  class Program
  {
    static void BuildOctant(int r, bool[,] res)
    {
      int f = 1 - r;
      int fx = 0;
      int fy = -2*r;
      int x = 0;
      int y = r;
    
      res[x+r, y+r] = true;
      while (x < y)
      {
        if (f ≥ 0)
        {
          y--;
          fy += 2;
          f += fy;
        }
        x++;
        fx += 2;
        f += fx + 1;
        res[x+r, y+r] = true;
      }
    }
    public static void Main(string[] args)
    {
      int r = 0;
      Console.Write("Radius: ");
      while(!(int.TryParse(Console.ReadLine(), out r) && (r > 0))){
        Console.WriteLine("Der Radius muss eine Ganzzahl größer 0 sein!");
        Console.Write("Radius: ");
      }
      bool[,] res = new bool[2*r+1, 2*r+1];
      // Grundoktant
      BuildOctant(r, res);
      //Spiegelung:
      for(int y = 2*r; y ≥ 3*r/4; y--)
      {
        for(int x = r; x ≤ 2*r; x++)
        {
          res[y, x] = res[x, y];
          res[2*r-x, y] = res[x, y];
          res[x, 2*r-y] = res[x, y];
          res[2*r-x, 2*r-y] = res[x, y];
        }
      }
      // Ausgabe:
      for(int y = 0; y ≤ 2*r; y++)
      {
        for(int x = 0; x ≤ 2*r; x++)
        {
          Console.Write(res[x, y] ? "0" : "x");
        }
        Console.WriteLine();
      }
      Console.ReadKey();
    }
  }
Ausgabe mit r=1:
x0x
0x0
x0x
Ausgabe mit r=15:
xxxxxxxxxxxx0000000xxxxxxxxxxxx
xxxxxxxxx000xxxxxxx000xxxxxxxxx
xxxxxxx00xxxxxxxxxxxxx00xxxxxxx
xxxxxx0xxxxxxxxxxxxxxxxx0xxxxxx
xxxxx0xxxxxxxxxxxxxxxxxxx0xxxxx
xxxx0xxxxxxxxxxxxxxxxxxxxx0xxxx
xxx0xxxxxxxxxxxxxxxxxxxxxxx0xxx
xx0xxxxxxxxxxxxxxxxxxxxxxxxx0xx
xx0xxxxxxxxxxxxxxxxxxxxxxxxx0xx
x0xxxxxxxxxxxxxxxxxxxxxxxxxxx0x
x0xxxxxxxxxxxxxxxxxxxxxxxxxxx0x
x0xxxxxxxxxxxxxxxxxxxxxxxxxxx0x
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
x0xxxxxxxxxxxxxxxxxxxxxxxxxxx0x
x0xxxxxxxxxxxxxxxxxxxxxxxxxxx0x
x0xxxxxxxxxxxxxxxxxxxxxxxxxxx0x
xx0xxxxxxxxxxxxxxxxxxxxxxxxx0xx
xx0xxxxxxxxxxxxxxxxxxxxxxxxx0xx
xxx0xxxxxxxxxxxxxxxxxxxxxxx0xxx
xxxx0xxxxxxxxxxxxxxxxxxxxx0xxxx
xxxxx0xxxxxxxxxxxxxxxxxxx0xxxxx
xxxxxx0xxxxxxxxxxxxxxxxx0xxxxxx
xxxxxxx00xxxxxxxxxxxxx00xxxxxxx
xxxxxxxxx000xxxxxxx000xxxxxxxxx
xxxxxxxxxxxx0000000xxxxxxxxxxxx

Hab leiuder heut keine Zeit mehr für was neues... das muss bis morgen warten.

Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3430
Herkunft: Trier -> München

beantworten | zitieren | melden

Hallo,

also doch noch auf die Schnelle die nächste Aufgabe:
Schreibt eine Funtion, die aus 2 übergebenen Integer-Arrays der Länge 4 (ein Geheimnis und ein Versuch) ermittelt, wie viele schwarze und weiße Pins bei einem Mastermind-Spiel zu setzen sind.
Gleiche Werte entsprechen gleichen Farben. Mehrfachbenutzung einer Farbe im Geheimnis ist möglich.
Die Methode soll die Signatur

bool MastermindTest(int[] geheimnis, int[] versuch,
                    out int schwarz, out int weiss)
besitzen, und true zurückgeben, wenn alle Farben im Versuch mit denen im Geheimnis in der exakten Reihenfolge übereinstimmen (richtige Lösung).
Gruß, MarsStein
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von MarsStein am .
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
private Nachricht | Beiträge des Benutzers
Campac68
myCSharp.de - Member



Dabei seit:
Beiträge: 68

beantworten | zitieren | melden

Hi,

Ich hab genau 4minuten und 28sekunden programmiert würde mich mal interessieren ob diese tolle Funktion hier das bringt was du wolltest(Achtung: 0 ist bei mir keine Farbe d.h. falls 0 als Farbe benutzt wird, müsste man etwas ergänzen wie: wenn ein Array 0 enthält dann alles Inkrementieren):

        
bool MastermindTest(int[] geheimnis, int[] versuch, out int schwarz, out int weiss)
        {
            schwarz = 0;
            weiss = 0;
            for (int i = 0; i < 4; i++)
            {
                if (geheimnis[i] == versuch[i])
                {
                    geheimnis[i] = 0;
                    schwarz++;
                }
                else if (geheimnis.Contains(versuch[i]))
                {
                    for (int i2 = 0; i2 < 4; i2++)
                    {
                        if (geheimnis[i2] == versuch[i])
                        {
                            geheimnis[i2] = 0;
                            break;
                        }
                    }
                    weiss++;
                }
            }
            if (schwarz == 4) return true;
            return false;
        }

Ok ich geb zu das is weder kurz noch elegant, aber dafür schnell;)

Mfg Campac
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 Campac68,
Zitat
Ich hab genau 4minuten und 28sekunden programmiert
das war wohl etwas zu wenig Zeit oder du hättest zumindest nochmal soviel Zeit in den Test investieren sollen :-) denn die Funktion ist falsch, d.h. sie liefert nicht in allen Fällen das richtige Ergebnis. Sie liefert in bestimmten Situationen zuwenig schwarz, z.B. in folgendem Fall (laut Wikipedia darf eine Farbe mehr als einmal vorkommen):

MastermindTest (new int [] {1, 2, 3, 3},
                new int [] {3, 1, 3, 2},
                out schwarz, out weiss);

Ergebnis ist 0 4 statt korrekt 1 3.

herbivore
private Nachricht | Beiträge des Benutzers