bleiben wir mit der nächsten Aufgabe mal beim Thema char[ , ]
Gegeben sei folgende Methodensignatur:
int FindRoute(char[,])
Implementiert die Methode so, daß ein Weg aus einem übergebenen Labyrinth gefunden wird. Dabei gilt:
'#': Wand
' ': möglicher Weg
Füllt den gefundenen Weg im übergebenen Array mit '+'-Zeichen aus. Edit: Rückgabewert soll die Länge des gefundenen Weges sein.
Ihr könnt außerdem von folgenden Startbedingungen ausgehen:
Das Labyrinth ist immer vollständig mit einer Wand umrahmt, die eine Startöffnung in der ersten Zeile und einer Zielöffnung in der letzten Zeile aufweist. Dabei existiert mindestens ein Weg vom Start zum Ziel.
Es muss nicht der kürzeste Weg gefunden werden, bei mehreren Möglichkeiten reicht es, eine davon zu finden.
Eine Ausgabe auf der Konsole ist auch in dieser Aufgabe optional.
Wenn es zwei Wege gibt, werden zwar beide eingezeichnet
Nicht wenn 2 Wege zum selben Ausgang führen. Kann auch eigentlich nicht, weil nach dem ersten Fund der Ausgang blockiert ist.
Deine Lösung findet aber problemlos mehrere Ausgänge
Die Kriterien der Aufgabenstellung sind also aus meiner Sicht erfüllt
Damit wärst Du dann dran.
Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
Die Methode Calculate berechnet Pi. Der Parameter iterations gibt an wie viel mal iteriert werden soll. Das Property CircleRadius ist dazu gedacht, die Genauigkeit zu erhöhen: Statt mit dem Einheitskreis zu arbeiten (Radius = 1) kann man einen grösseren Radius einstellen und so ein genaueres Resultat erhalten.
public class MonteCarloPI : IMonteCarloPi
{
Random random = new Random();
int m_Radius = 0;
public int CircleRadius
{
get
{
return m_Radius;
}
set
{
m_Radius = value;
}
}
public double Calculate(int iterations)
{
double x = 0, y = 0;
int unter = 0;
for (int i = 0; i < iterations; i++)
{
x = random.NextDouble()+ random.Next(0,m_Radius);
y = random.NextDouble() + random.Next(0, m_Radius);
if(((x*x)+(y*y))≤(long)m_Radius*m_Radius))
unter++;
}
return (((double)unter / iterations) * 4);
}
}
war aber bestimmt anders gedacht oder?^^
Dieser Beitrag wurde 5 mal editiert, zum letzten Mal von prakti08 am .
Use the source, Luke!
Nur, weil man vor sich eine CPU hat, muß man das Denken nicht
einstellen.
wieso soll eigentlich die Berechnung mit einem größeren Radius genauer sein als mit 1?
Die Zufallszahlen werden ja ohnehin über NextDouble() gezogen und die Multiplikation mit einem int erhöht ja nicht die "Auflösung"...
Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
Wenn man es einfach mit dieser Zahl multipliziert wird das natürlich nichts. Man könnte aber z.b. Next(0, CircleRadius) verwenden: Da wird das Ergebnis natürlich zunehmend ungenau, wenn CircleRadius kleiner wird.
An und für sich ist der Double allerdings genauer als ein Int32. Ich könnte mir aber vorstellen, dass die Operation mit Ganzzahlen schneller geht als mit Gleitkommazahlen, getestet habe ich das allerdings nicht.
so.. hab den radius² auf long gecastet.. jetzt kann man auch int.MaxValue nutzen ;)
neue aufgabe
Schreiben Sie ein Programm, das mit Hilfe von Backtracking eine gültige Lösung für beliebige Sudoku ermittelt, falls eine solche existiert. Die Lösung kann direkt in das Sudoku eingetragen werden.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von prakti08 am .
Use the source, Luke!
Nur, weil man vor sich eine CPU hat, muß man das Denken nicht
einstellen.
hier machst Du - abgesehen davon, daß Radius 1 nicht mehr funktioniert, auch noch den systematischen Fehler, die Koordinaten mit (m_Radius-1) zu ermitteln und den Abstand mit (m_Radius) zu prüfen
Da der zweite Parameter von Rand.Next() bereits exklusiv ist, kannst Du dir die -1 aber auch sparen.
Genau genommen müsste IMHO da sogar eine +1 hin (eben wegen exklusiv)...
Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
Bei int.MaxValue kommt immer noch 0 raus. Es geht ja nicht darum, ob int.MaxValue rein passt, sondern darum, ob die Genauigkeit mit grösseren Werten für CircleRadius erhöht wird. Und das ist momentan so nicht gegeben.
da ich drauf angesprochen wurde und meine aufgabe wohl weiter oben untergegangen ist poste ich sie nochmal..
Schreiben Sie ein Programm, das mit Hilfe von Backtracking eine gültige Lösung für beliebige Sudoku ermittelt, falls eine solche existiert. Die Lösung kann direkt in das Sudoku eingetragen werden.
Edit: Das Sudoku liegt in Form eines 2Dim Arrays vor
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von prakti08 am .
Use the source, Luke!
Nur, weil man vor sich eine CPU hat, muß man das Denken nicht
einstellen.
Meine Lösung für die Soduku Aufgabe. Ich hoffe sie ist ungefähr dem genehm was du wolltest. Ich hab sie mit drei verschiedenen Sudokus verschiedener Schwierigkeitsgrade getestet und sie lieferte immer (ein) richtiges bzw das richtige Ergebnis in unter 300ms(Kann beim Deuggen abweichen). Bei der Eingabe von einem Sudoku, welches(wie bei meiner Lösung standartmäßig) mit Nullen gefüllt ist braucht sie 12 ms um eine oft im Internet als Beispielsudoku gesehene Lösung zu produzieren(ausprobieren;)). Die Klasse Sudoku wurde dabei Immutable gehalten(für die verwendete Rekursion recht praktisch:))
Zu sagen ist, dass man darauf achten sollte immer nur Mehrdimensionale Array mit wenigstens 9*9 Zahlen zu übergeben, anderes wird nicht abgefangen. Der restliche Code sollte nicht zu schnell zusammenbrechen(auch wenn bestimmte Teile nicht oft getestet wurde, da sie letztenendes nicht für die Gesamtlösung verwendet werden). Die entscheidenden Methoden sind die unteren 6(bis 9) welche auch ein wenig kommentiert sind(eher spärlich). Zu sagen ist, das eigentlich alles Null-basiert ist. Der Rest findet sich beim durschauen.
Benutzung:
class Program
{
static void Main(string[] args)
{
Sudoku s = new Sudoku(
new int[9, 9] {
{0,8,0,4,0,0,2,0,9},
{0,5,9,0,8,0,0,0,3},
{0,0,0,0,0,9,0,0,7},
{8,2,0,0,1,0,0,0,0},
{5,0,0,0,7,0,0,0,6},
{0,0,0,0,4,0,0,2,5},
{3,0,0,7,0,0,0,0,0},
{9,0,0,0,2,0,3,7,0},
{7,0,5,0,0,8,0,9,0}}
);
/*Sudoku s = new Sudoku(
new int[9, 9] {
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0}}
);*/
s.drawToConsole();
Sudoku solution = new Sudoku();
Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();
solution = s.findSolution();
stopWatch.Stop();
Console.WriteLine("Zeit: " + stopWatch.ElapsedMilliseconds + "ms");
solution.drawToConsole();
Console.ReadLine();
}
}
Eigentlicher Code:
class Sudoku
{
private int[,] m_content;
public Sudoku()
{
m_content = new int[9, 9];
for (int row = 0; row < 9; row++)
{
for (int column = 0; column < 9; column++)
{
m_content[row, column] = 0;
}
}
}
public Sudoku(int[,] content)
{
m_content = new int[9, 9];
for (int row = 0; row < 9; row++)
{
for (int column = 0; column < 9; column++)
{
m_content[row, column] = content[row, column];
}
}
}
public void drawToConsole()
{
for (int row = 0; row < 9; row++)
{
if (row % 3 == 0)
{
Console.WriteLine("-------------");
}
for (int column = 0; column < 9; column++)
{
if (column % 3 == 0) Console.Write("|");
Console.Write(m_content[row, column]);
}
Console.WriteLine("|");
}
Console.WriteLine("-------------");
}
public int[,] toArray()
{
return m_content;
}
private bool isRowValid(int row)
{
List<int> numbers = new List<int>();
for (int column = 0; column < 9; column++)
{
if (numbers.Contains(m_content[row, column]))
{
return false;
}
else if (m_content[row, column] != 0)
{
numbers.Add(m_content[row, column]);
}
}
return true;
}
private bool isColumnValid(int column)
{
List<int> numbers = new List<int>();
for (int row = 0; row < 9; row++)
{
if (numbers.Contains(m_content[row, column]))
{
return false;
}
else if (m_content[row, column] != 0)
{
numbers.Add(m_content[row, column]);
}
}
return true;
}
/// <summary>
/// Zero based!
/// </summary>
/// <param name="box">Box numbers from top-left to bottom right in each row from left to right</param>
/// <returns></returns>
private bool isBoxValid(int box)
{
List<int> numbers = new List<int>();
int boxRow = box ≤ 2 ? 0 : box ≤ 5 ? 1 : 2;
int boxColumn = box % 3;
for (int row = boxRow * 3; row < boxRow * 3 + 3; row++)
{
for (int column = boxColumn * 3; column < boxColumn * 3 + 3; column++)
{
if (numbers.Contains(m_content[row, column]))
{
return false;
}
else if (m_content[row, column] != 0)
{
numbers.Add(m_content[row, column]);
}
}
}
return true;
}
public bool isValid()
{
for (int i = 0; i < 9; i++)
{
if (!(isRowValid(i) && isColumnValid(i) && isBoxValid(i)))
{
Console.WriteLine((!isRowValid(i) ? "Row " : "") + (!isColumnValid(i) ? "Column " : "") + (!isBoxValid(i) ? "Box " : "") + i.ToString());
return false;
}
}
return true;
}
private bool isNumberValidAt(int row, int column, int value)
{
Sudoku s = insertNumberAt(row, column, value);
int box = (row < 3 ? 0 : (row < 6 ? 1 : 2)) * 3 + (column < 3 ? 0 : (column < 6 ? 1 : 2));
return s.isRowValid(row) && s.isColumnValid(column) && s.isBoxValid(box);
}
private List<int> getValidNumbersAt(int row, int column)
{
List<int> validNumbers = new List<int>();
Sudoku s;
for (int i = 1; i ≤ 9; i++)
{
s = insertNumberAt(row, column, i);
int box = (row < 3 ? 0 : (row < 6 ? 1 : 2)) * 3 + (column < 3 ? 0 : (column < 6 ? 1 : 2));
if (s.isRowValid(row) && s.isColumnValid(column) && s.isBoxValid(box))
{
validNumbers.Add(i);
}
}
return validNumbers;
}
public Sudoku insertNumberAt(int row, int column, int value)
{
int[,] newContent = m_content;
newContent[row, column] = value;
return new Sudoku(newContent);
}
public Sudoku findSolution()
{
// If the incoming Sudoku is already wrong dont jump into the solution algorithm
if (isValid())
{
Sudoku s = findSolution(0, 0);
return s == null ? new Sudoku() : s;
}
else
{
return new Sudoku();
}
}
private Sudoku findSolution(int row, int column)
{
// If ready...
if (row == 9)
return this;
// If row changed
if (column == 9)
column = 0;
if (m_content[row, column] == 0)
{
foreach (int i in getValidNumbersAt(row, column))
{
// Check next field
Sudoku s = (insertNumberAt(row, column, i).findSolution(column + 1 == 9 ? row + 1 : row, column + 1));
// If something comes back the solution was found!
if (s != null) return s;
}
return null;
}
else
{
return new Sudoku(m_content).findSolution(column + 1 == 9 ? row + 1 : row, column + 1);
}
}
}
zur Kontrolle: Es soll dieses Sudoku aus der Wikipedia sein.
Ich habe dabei Deinen Algorithmus nach über 10 Minuten abgebrochen. Mein eigener Code löst das in 2m20s, mit reinem Backtracking, also gehe ich davon aus dass da noch etwas schiefläuft...
Gruß, MarsStein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
nachdem Campac68 - auch nach einer entsprechenden Aufforderung per PM - keine neue Aufgabe gestellt hat, gebe ich das Spiel wieder frei. Wer eine nette Aufgabe hat, möge diese bitte posten. Achtet dabei vor dem Absenden darauf, dass euch keiner zuvorgekommen ist. Nur die erste neue Aufgabe zählt.
hier noch nachträglich eine gültige Lösung für die Sudoku-Aufgabe. Da herbivore das Spiel wieder freigegeben hat, erhebe ich aber keinen Anspruch auf die nächste Aufgabe.
Wenn jemand eine schöne Idee hat, biite sehr...
zum Sudoku-Code:
in der public-Methode muss 'values' die gültigen Werte enthalten. Der erste Wert muss der Wert sein, der für leere Felder benutzt wird
'blocksInRow' gibt an, wieviel Blöcke in einer Reihe liegen, so kann ein 12x12-Feld z.B. als 4x3 Blöcke (dann wäre die 4 anzugeben) oder als 3x4 Blöcke (dann wäre 3 anzugeben) interpretiert werden.
public static class SudokuSolver
{
static bool Solve<T>(T[,] sudoku, T[] values, int width, int height, int row, int col)
{
if(col == sudoku.GetLength(0))
{
col = 0;
row ++;
}
bool? result = (row == width * height) ? true : (bool?)null;
if((!result.HasValue) && sudoku[col,row].Equals(values[0]))
{
result = false;
for(int field = 1; (!result.Value) && (field < values.Length); field++)
{
result = true;
T val = values[field];
for(int i = sudoku.GetLength(0) - 1; result.Value && (i ≥ 0); i--)
{
result = !(val.Equals(sudoku[col,i]) || val.Equals(sudoku[i,row]));
}
int rowStart = height * (row / height);
int colStart = width * (col / width);
for(int i = rowStart; result.Value && (i < rowStart + height); i++)
{
for(int j = colStart; result.Value && (j < colStart + width); j++)
{
result = !val.Equals(sudoku[j,i]);
}
}
if(result.Value)
{
sudoku[col,row] = val;
result = Solve(sudoku, values, width, height, row, col+1);
sudoku[col,row] = result.Value ? val : values[0];
}
}
}
return result.HasValue ? result.Value : Solve(sudoku, values, width, height, row, col+1);
}
public static bool Solve<T>(T[,] sudoku, T[] values, int blocksInRow)
{
return Solve(sudoku, values, sudoku.GetLength(0) / blocksInRow, blocksInRow, 0, 0);
}
}
Gruß, MarsStein
Edit: Ich hatte eine Version mit vertauschten Col/Row eingestellt -> korrigiert.
Dieser Beitrag wurde 5 mal editiert, zum letzten Mal von MarsStein am .
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
using System;
using System.Diagnostics;
public class Parameter {
private string m_Name;
private object m_Value;
public Parameter(string name, object value) {
m_Name = name;
m_Value = value;
}
public Parameter(object value) {
m_Name = null;
m_Value = value;
}
public string Name {
get { return m_Name; }
}
public object Value {
get { return m_Value; }
}
}
public static class StringEx {
public static string Format(string format, params Parameter[] args) {
// Hier eure Implementierung!
throw new NotImplementedException();
}
}
public class Program {
public static void Main() {
Debug.Assert("This is SPARTA!" == StringEx.Format("This is $what!", new Parameter("what", "SPARTA")));
Debug.Assert("This is SPARTA!" == StringEx.Format("This is $1!", new Parameter("SPARTA")));
DateTime date = new DateTime(2010, 06, 12, 17, 18, 32);
Debug.Assert("Date is: 12.6.2010, Time is: 17:18:32" == StringEx.Format("Date is: ${date:Day}.${date:Month}.${date:Year}, Time is: ${date:Hour}:${date:Minute}:${date:Second}", new Parameter("date", date)));
Debug.Assert("17:18:32" == StringEx.Format ("${date:TimeOfDay:Hours}:${date:TimeOfDay:Minutes}:${date:TimeOfDay:Seconds}", new Parameter("date", date)));
Debug.Assert("$test = TEST" == StringEx.Format("$$test = $test", new Parameter("test", "TEST")));
}
}
Eure Aufgabe ist es nun, mal wieder eine Art von Parser zu entwickeln. Wie Ihr dabei vorgeht, bleibt diesmal euch überlassen.
Die unterstützten Formate sollen Folgende sein:
$var wird durch den Wert des Parameters mit dem Namen var ersetzt
$1 wird durch den Wert des ersten übergebenen Parameters ersetzt (ACHTUNG! das ist nicht 0-basiert!)
${var:Property1:Property2} wird durch den Wert von Property2 von Property1 des Parameters mit dem Namen var ersetzt
$$ wird durch ein einzelnes $ ersetzt (--> Escaping)
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von TheBrainiac am .
There are 10 types of people in the world:
Those, who think they understand the binary system
Those who don't even have heard about it
And those who understand "Every base is base 10"
There are 10 types of people in the world:
Those, who think they understand the binary system
Those who don't even have heard about it
And those who understand "Every base is base 10"
