6
$\begingroup$

I am teaching some high school students, also the first time programmers, some basic programming concepts and applications. When introducing loop I find that using it to check prime number (or find prime number) is a good example. It teaches them the concept of loop but also make them think, e.g. it just need to loop to $\sqrt{n} + 1$, no need to loop to $n$.

I would like to know other examples like that to introduce loop, not too easy or too hard (for high school students) and better to have some practical application.

$\endgroup$
1
  • $\begingroup$ The smallest factor (if it exists) if $n$ is guaranteed to be at most $\lfloor \sqrt{n} \rfloor$ $\endgroup$ – vonbrand May 4 at 2:05
3
$\begingroup$

I'm adding in a second answer to look at a few heftier assignments, worthy of a lab. These were created by a truly fantastic colleague of mine.

The game Nim is excellent for a loop with no arrays. You can use just three variables to keep track of the state of the game, and a variable and an if statement to deal with the player. (Kids at this level will often try to simply copy their code from player 1 for player 2, and won't think to simplify the structure by using a variable -- that's a good segue into the idea of defensive coding, wherein you assume that your code is always somehow buggy, and you make efforts not to proliferate the bugs all over the place. That same idea dovetails nicely into function calls as well.)

We also have an Electronic Piggy Bank assignment where the user can add in p (penny), n (nickel), d (dime) and q (quarter) as many times as they want. The program will keep a running tally of the amount in the piggy bank. The user can then type exit to finish up and see the final report. Again, this is a lab that requires keeping track of several variables, and motivated the use of loops and branching, but doesn't require arrays to be effective.

$\endgroup$
4
  • $\begingroup$ I feel the piggy bank assignment is bit easy for high school kids. Besides, for prime number I introduce for loop, for the answer about quotient/remainder I can introduce while loop, for piggy back, what is the main purpose ? Keeping track of several variables ? $\endgroup$ – Qiulang Dec 22 '20 at 2:33
  • 1
    $\begingroup$ @Qiulang I'm not sure what to tell you, other than that we do it. while (! input.equals("exit") ) can be a surprisingly hard structure for HS kids to suss out. Figuring out where to collect input, the placement of the !, and that you have to use .equals are all minor challenges, but they add up when they're put together like that. And, of course, we're talking about beginner beginners here -- if they had background, they wouldn't have to be practicing loops without arrays in the first place. The banking aspect is just a way to practice with strings, really. $\endgroup$ – Ben I. Dec 22 '20 at 2:50
  • $\begingroup$ On a side note do you explain to them why array index starts from 0 ? $\endgroup$ – Qiulang Dec 22 '20 at 3:46
  • $\begingroup$ @Qiulang Not that early, no, but eventually we do. (We have the benefit of a multi-year program.) On our first pass-through, it is a lot about the mechanics and the Big Ideas -- we don't delve much into smaller details until our second big pass, when they're ready to begin to absorb a lot of the logic behind the mechanisms they've built up practical experience with. $\endgroup$ – Ben I. Dec 22 '20 at 4:36
3
$\begingroup$

Note that the following are intended for the instructor, not always directly for the student. If used well they require some analysis, not just coding, from the student.

Use the fact that the sum of the first n odd numbers is $n^2$ to compute the integer square root of an integer.

Test data should include 63, 64, and 65 to catch edge cases.

This can be extended past the decimal point and optimized in various ways to compute more accurate approximations of square roots.


Notes on the above, but I suggest you try it before peeking:

To make it a bit more obvious, this involves using inverse functions and computing inverses. The loop actually needs to count subtractions and uses facts about perfect squares to compute square roots. That same idea might be exploited for other problems. Note that $\lfloor$ $\sqrt 65$ $\rfloor$ = 8.


Other simple things:

  • How many digits does an integer have?

  • How many bits are required to represent an integer? (Note that the structure is the same as the above)

  • How many times does zero (for example) appear in the decimal representation of an integer.

  • Sum of the digits of a given integer.

  • Is the number of 1 bits in a binary representation of an integer even or odd?

  • Read a real value x from input. Then read the successive coefficients of a polynomial from input and evaluate the polynomial at x. Note that the stopping condition needs to be specified and by varying it you can have different systems. Reading it from input is one of the obvious variations. Hardcoding it is another. Later on, the coefficients can be in an array, of course.

  • In teaching loops it is important to also give exercises where the correct number of iterations is zero. For example, give x and y, find the number of multiples of 3 that are larger than x but less than y. Don't exclude the initial condition y < x.

  • Nested loops: Once you have the solution to "is X prime?", how many primes are there between a given x and y?


A bit harder:

Euclid's algorithm.


Extensions:

  • Use other similar sums (than the sum of odds) to compute other things.

  • Look at the Wikipedia article on Taylor Series to get some ideas about how to approximate some interesting functions with sums.


A solution to the square root problem follows, using a personal (executable) pseudocode:

    $ "Computes the integer square root of a non-negative number";
    With
      value; current; count; odd; // integer variables
    Program
      Read value;
      current <- value;
      count <- 0;
      odd <- 1;

While current >= odd { current <- current - odd; odd <- odd + 2; count <- count + 1; }
Print "The integer square root of ", value, " is ", count; End

$\endgroup$
0
1
$\begingroup$

Given two positive integers $x$ and $y$, write a program that prints the quotient $\lfloor\frac{x}{y}\rfloor$ and the remainder $x\%y$, using only the "+" and "-" operations.

$\endgroup$
1
  • $\begingroup$ This is a good one. With prime number I introduce them the for loop, for this one I will introduce while loop $\endgroup$ – Qiulang Dec 22 '20 at 2:26
1
$\begingroup$

Since we introduce loops before we introduce arrays, we will often do simple programs like ask a user how many numbers they want to enter, and then find the sum of the numbers entered.

Similarly, they can practice these concepts a few times to find the maximum, minimum, and average of the numbers entered. Having a few very similar tiny projects like this can be useful as a way to let the kids internalize the structure a little and begin to feel comfortable with it.

You can also have them make a nice, rolling report of compound interest for a retirement calculator.

$\endgroup$
1
  • $\begingroup$ I think finding the max, min, avg do have "practical" application. $\endgroup$ – Qiulang Dec 22 '20 at 2:43
1
$\begingroup$

Write a loop that reverses the characters of a string.

$\endgroup$
1
  • $\begingroup$ I will let them do a in-place reverse, otherwise it is too easy. But that introduces another problem, we use python and string is immutable. If I then introduce list and string conversion I fear sidetracking the teaching of loop. $\endgroup$ – Qiulang Dec 23 '20 at 7:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.