Programmieraufgaben

volkard

Ich suche nach Programmieraufgaben für Anfänger.

Ich fange mal an:

http://www.programmieraufgaben.ch/
Abwechslunsgreiche Aufgaben für Anfänger. Die Lösung sind zum Teil so schlechter Stil, daß man sich da nicht viel abgucken sollte.

http://projecteuler.net/
Nur mathematische Aufgaben. Sehr gute Lösungen.

Aber auch Einzelaufgaben gehen, dann bitte Quelle angeben:

Eingabe: Eine positive Zahl n.

Wir haben ein Gefängnis mit n Zellen, die von 1 bis n durchnummeriert sind. Alle Zellentüren sind verschlossen.
Der Wärter kann nicht bewußt aufschließen oder zuschließen, sondern nur "umschließen". War vorher auf, ist dann zu, war vorher zu, ist dann auf.
Am ersten Tag geht der Wärter durch und schließt jede Zelle um.
Am zweiten Tag geht der Wärter durch und schließt jede zweite Zelle um, also die Zellen mit den Nummern 2, 4, 6, 8, und so weiter.
Am dritten Tag geht der Wärter durch und schließt jede dritte Zelle um, also die Zellen mit den Nummern 3, 6, 9, 12, und so weiter.
Und so weiter.
Am n-ten Tag schließer er nur noch die Zelle mit der Nummer n um.

a) Schreibe ein Programm, das das möglichst genau simuliert und dann ausgibt, welche Zellen offen sind (eine Liste der Zellennummern der Zellen, die offen sind).

b) Schreibe ein Programm, das möglichst performant das gleiche ausgibt.

Quelle: Idee aus weiß nicht mehr genau, entweder "Mathematischer Karneval" oder "Computer Kurzweil", beides von Martin Gardner.

Wenn möglich sollten die Aufgaben einigermaßen Sprachunabhängig sein, also nicht zum Beispiel, wie man in C# einen Prädikatdelegaten benutzt.

Unsortierte Masse an einfachen bis schweren algorithmischen Aufgaben: http://www.spoj.com/problems/

volkard

spoj schrieb:

Unsortierte Masse an einfachen bis schweren algorithmischen Aufgaben: http://www.spoj.com/problems/

Uih, Prima!

knivil

http://icpc.baylor.edu/worldfinals/problems

Kann man sich Loesungen anderer User bei http://www.spoj.com/problems/ anschauen?

Sone

Ich kann nicht widerstehen, volkards Aufgabe zu machen!

a) Schreibe ein Programm, das das möglichst genau simuliert und dann ausgibt, welche Zellen offen sind.

Also, der doofe Ansatz:

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>

int main()
{
	unsigned n;
	std::cin >> n;

	std::vector<bool> prison(n);

        for( unsigned i = 0; i != n; ++i )
	{
		for( unsigned j = i; j < n; j += i + 1 )
			prison[j] = !prison[j];
		std::copy( std::begin(prison), std::end(prison), std::ostream_iterator<bool>{std::cout << '\n'} );
	}
}

Und jetzt gab es eine böse Überraschung. Das Problem ist viel zu primitiv.

#include <iostream>

int main()
{
	unsigned n;
	std::cin >> n;

	unsigned counter = 2;
	while( n-- )
	{
		std::cout.put('1');
		for( unsigned i = 0; i != counter ; ++i )
		{
			if( !n-- )
				return 0;

			std::cout.put('0');
		}

		counter += 2;
	}
}

Und Sublineare Komplexität ist hier sowieso unmöglich.

Komm schon, volkard, da geht noch was.

volkard

gelöscht

volkard

Bitte in diesem Thread nur weiter Aufgaben sammeln.
Und über die Aufgaben selber reden.
Lösungen bitte in neuen Threads, damit eventuelle Diskussionen über Läsungen nicht alles hier sprengen.

Sone

volkard schrieb:

Sone schrieb:

...

Du solltest nur anzeigen, welche Zellen offen sind. Nicht alle Zellen.

Das macht es noch einfacher.

Da das Problem also offensichtlich nicht interessant ist, verzichte ich mal auf einen neuen Thread.

knivil

Und Sublineare Komplexität ist hier sowieso unmöglich.

Wenn man den Simulationsschritt weglaesst, dann ist das anzeigen der "geschlossenen" Zellen leicht berechenbar.

Komm schon, volkard, da geht noch was.

Du hast doch genug Aufgaben/Links praesentiert bekommen, also was willst du?

Sone

knivil schrieb:

Und Sublineare Komplexität ist hier sowieso unmöglich.

Wenn man den Simulationsschritt weglaesst, dann ist das anzeigen der "geschlossenen" Zellen leicht berechenbar.

Ich dachte, man muss den Zustand am Ende komplett anzeigen.

Mit der Abänderung hast du natürlich Recht, daher auch mein Kommentar.

Komm schon, volkard, da geht noch was.

Du hast doch genug Aufgaben/Links praesentiert bekommen, also was willst du?

Keine Ahnung, ich will mich nicht durch so viele uninteressante Probleme quälen wenn volkard doch sicher die interessanten kennt.

volkard

Könnte bitte jemand die Sone-Diskussion löschen oder in einen neuen Thread verlegen?

Sone Scheiße

knivil

@Sone: Dann nimm doch http://icpc.baylor.edu/download/worldfinals/problems/icpc2013.pdf da gibt es auch Testfaelle mitgeliefert. Ich selbst habe self-assembly gemacht. Aber es ist meist so, dass es trivial wird, wenn man die Loesung gefunden hat.

Sone

Aber es ist meist so, dass es trivial wird, wenn man die Loesung gefunden hat.

Deswegen mag' ich ja Probleme, die
1. Sehr einfach zu formulieren und verstehen sind. Also keine ellenlangen Dinger bei denen man nach zehn Saetzen tl;dr denkt.
2. keine "beste oder eindeutige Loesung" haben. Also kein eindeutiges Muster haben, sondern bei denen man die Loesung einfach optimieren muss.

Vorige Aufgabe ist zwar schoen kurz, hat aber diese eine eindeutige und schnell gefundene Loesung.

Hier ist eines, was ich aus diesen Gruenden gut fand: http://en.wikipedia.org/wiki/Gauss_circle_problem
Ich finde, es ist eine wirklich huebsche Aufgabe.

Die Aufgabe ist: Man habe einen Kreis mit Radius R. Packt man diesen nun auf den Ursprung eines Koordinatensystems - wie viele ganzzahlige Koordinaten liegen es nun auf ihm?

Edit: Danke, knivil, fuer deinen Link - http://icpc.baylor.edu/download/worldfinals/problems/icpc2013.pdf
Problem J ist interessant!

knivil

Du must schauen, bei Problem J ist das Zeitlimit 1 Sekunde. Ich vermute die Loesung ist trivial umzusetzen. Die Schwierigkeit ist sie zu finden.

knivil schrieb:

Du must schauen, bei Problem J ist das Zeitlimit 1 Sekunde. Ich vermute die Loesung ist trivial umzusetzen. Die Schwierigkeit ist sie zu finden.

Das denke ich nicht. Das Einfachste, was mir einfällt, ist ein Kreissweep. Der läuft zwar schnell, aber trotzdem muss man beim Implementieren auf einiges achten.