Auf der Suche nach einem guten Bonus -Quiz für die Testeneffizienz (insbesondere die Effizienz im Zusammenhang mit der Zeit) [geschlossen

Question

Ich mache einmal pro Woche eine Einführung in das Informatik -Labor. Ich hatte gehofft, am Ende meines nächsten Labors einen kurzen Wettbewerb zu haben. Ich möchte ihnen einen solchen Codeblock geben:

public class EfficientCode{

    public static void main(){
        long startTime, endTime, executionTime;
        startTime = System.currentTimeMillis();

        yourEfficientMethod():
        endTime = System.currentTimeMillis();
        executionTime = endTime – startTime;

    }

    public static void doSomething(){
        // you do this part.  
    }

}

Sie werden die Dosenmethode implementieren, und die Person mit dem schnellsten Code erhält eine Handvoll Bonusmarken.

Das Problem ist, dass die Frage etwas einfach sein muss. Die Schüler haben ein gutes Verständnis für: Schleifen, wenn/sonst, Zeichen hinzuzufügen, Arrays usw.

Hier sind meine Ideen für die Frage:

• Finden Sie alle perfekten Zahlen zwischen 1 und 1.000.000. (Eine perfekte Zahl ist eine Zahl, bei der alle Faktoren der Zahl der Zahl addieren. IE: 6 = 3 + 2 + 1)
• Finden Sie alle Primzahlen zwischen 1 und 1.000.000

Ich denke, damit es einen messbaren Leistungsunterschied zwischen den Methoden gibt, müssen Sie etwas oft tun.

Answer 1

Weil dies eine Einführungsklasse ist und Ihre Schüler noch nicht die Sortierung behandelt haben, denke ich, dass es sehr schwierig sein wird, etwas Einfaches zu finden, das genug zu tun ist, interessant genug ist, um ein paar verschiedene Möglichkeiten zu haben, und komplex genug, dass es dort dort ist ist ein nennenswerter Geschwindigkeitsunterschied zwischen den verschiedenen Implementierungen auf einem modernen Computer. Ihr eigentliches Problem ist jedoch, dass alles, was einfach genug ist, dass sie es versuchen, bereits eine kanonische Implementierung zu haben, nur eine kurze Google -Suche entfernt.

Mein Vorschlag ist, die Herausforderung umzukehren. Lassen Sie Ihre Schüler um die knorrigste, langsamste und am meisten Gedächtnis -Hogging -Lösung konkurrieren, an die sie sich vorstellen können. Ich glaube, es ist so pädagogisch wertvoll, über all die falschen Möglichkeiten nachzudenken, etwas zu tun wie über das Recht zu denken, und es ist genauso schwierig, das Schlimmste zu sein wie das Beste zu sein. Es ist auch einfacher, Ergebnisse subjektiv zu sehen, da schlechter Code sein wird Ja wirklich langsam. Auch für eine Antwort googeln. In meiner (irrelevanten) Meinung hat dies schließlich den zusätzlichen Bonus, die Herausforderung mehr Spaß zu machen.

So etwas wie das Finden einer Zeichenfolge in einer anderen Saite ist einfacher gemacht als gut. Lassen Sie sie möglicherweise alle Primzahlen aus einer 2 -KB -Zeichenfolge zufälliger alphanumerischer Zeichen extrahieren. Viele Möglichkeiten, um ein Schweinohr von diesem Problem zu machen.

Answer 2

Einverstanden über "viele Male" für kurze Operationen, aber für längere, könnte einst ausreichen.

Ich schlage vor Projekt Euler, eine hervorragende Sammlung von Programmierfragen. Das Beste daran ist, dass die Probleme mit einer "One -Minute -Regel" ausgelegt sind. Die meisten Probleme sollten einen moderaten Computer weniger als eine Minute benötigen, um eine auszuführen effizient Algorithmus, um die Antworten zu finden. Also ein ausgezeichneter Ort zum Starten. :)

Answer 3

Zwei Dinge.

Erstens ist Effizienz mehr als Ausführungszeit. Es geht auch um Speicherverbrauch, Speicherzugriff, Dateisystem-/Ressourcenzugriff usw. Es gibt unzählige Dinge, die in Effizienz eingehen. Seien Sie also bitte explizit, dass Sie nach der Routine mit der kürzesten Laufzeit suchen. Andernfalls senden Sie eine gemischte Nachricht ...

Zweitens habe ich dieses Problem vor ungefähr 15 Jahren gehört und kann es nicht vergessen:

Erstellen Sie eine Liste aller 5-stelligen Zahlenpaare, die zu Summe sind 121212. Keine der 2 Zahlen kann jedoch eine Dezimalstellen wiederholen. So 1 kann nur einmal in beiden Zahl erscheinen. Ein Beispielergebnispaar ist also 98167 + 23045. Es gibt eine faire Zahl, und es ist einfach, eine Brute-Force-Lösung zu erstellen, aber eine effiziente Lösung erfordert einige Gedanken. Es gibt 192 einzigartige Paare ...

Answer 4

Das sind gute Ideen. Was ist mit einer Sortierfrage?

Answer 5

Das Sortieren einer Reihe von Zahlen könnte auch eine gute Idee sein, da es eine ganze Reihe von Algorithmen (Einfügen, Auswahl, Schnell, Haufen usw.) gibt, die alle unterschiedliche Leistungsmerkmale haben. Dies würde den Schülern auch die Möglichkeit geben, etwas über Big-O-Notation usw. zu lernen.