## Three Homework Problems

### August 4, 2015

1. If *a* is no larger than *b* or *c*, then it is the smallest, so the answer is the sum of the squares of *b* and *c*. Otherwise, rotate the input and try again. This is one of the simplest examples of recursion that I know, and one of the best for introducing recursion to students, better than a factorial or fibonacci number:

`(define (f a b c)`

(if (and (<= a b) (<= a c))

(+ (* b b) (* c c))

(f b c a)))

```
```

`> (f 1 2 3)`

13

> (f 2 1 3)

13

> (f 3 1 2)

13

> (f 3 3 3)

18

2. We repeatedly strip the trailing digit, building its reversal as we go, and compare at the end:

`(define (palin? n)`

(let loop ((m n) (r 0))

(if (zero? m)

(= r n)

(loop (quotient m 10)

(+ (* 10 r) (remainder m 10))))))

```
```

`> (palin? 12345)`

#f

> (palin? 12321)

#t

3. This is more of a math problem than a programming problem, but I’ve seen it in more than one beginning programming textbook, so here it is. I’m not entirely sure it’s fair to give the problem without explaining the math, but I usually see the problem in exactly the form given on the previous page.

You *don’t* want to compute the factorial and count zeroes; the intermediate calculation of the factorial is huge. Instead, observe that the number of trailing zeroes depends on the number of factors of 10 = 2 × 5, and since there are more factors of 2 than of 5, the number of trailing zeroes is the same as the number of factors of 5. And that’s easy to calculate: for example, 973! has ⌊973/5⌋ = 194 factors of 5, plus ⌊973/25⌋ = 38 additional factors of 5 in the 5^{2} terms, plus ⌊973/125⌋ = 7 additional factors of 5 in the 5^{3} terms, plus ⌊973/625⌋ = 1 additional factor of 5 in the 5^{4} terms, a total of 240 factors of 5. Given that, the program is easy to write:

`(define (tens n)`

(let loop ((n n) (z 0))

(if (zero? n) z

(let ((n (quotient n 5)))

(loop n (+ z n))))))

```
```

`> (tens 973)`

240

You can run the program at http://ideone.com/VDLHqW.

Students: If you use these solutions in your programs, be sure to give proper attribution.

Do they still make people start with Java? I wasn’t sure if I was expected to write javadoc comments and stuff, but this was quite enough sheer tedium for me already. Probably I should have written static tests instead of making it take arguments on the command line. Should I worry about overflowing int in the first problem? If yes, why? If not, why not?

Today I give the sourcecode processor the actual lang.

@Jussi: I was just reading this morning that Python is now the dominant first language for programming students. And if you use Python, you don’t have to worry about integer overflow. I agree with you: Java is a horrible first language. Although probably not too much worse than FORTRAN, which was my first language.

@Praxis, thanks, I’m glad to hear that about Python. I was taught in Pascal in the CS department after I had already met some line-numbered Basics, 6502 assembler and Forth on my own. Then our CS folks switched to Java as the main teaching language. (Scheme was a candidate. I saw them talk about Scala later. Now I’m not up to date). We’ve used Lisp, Prolog, Perl in the linguistics department over the years, and now we have indeed Python. Scheme I got on my own, but it used to be a teaching language in a university of technology here. (And since Java became more a lawsuit than a programming language, I cut my personal ties to it as far as I could. Mainly by rewriting my largest project from scratch, in Scheme. It needed rewriting anyway.)

Show us these problems in FORTRAN? :)

@Jussi @Praxis Java was my first language in school as well, and I believe they have since switched to Python. Although I think Scheme would probably be a better choice.

Here are some Haskell solutions. We should only need two comparisons to find the biggest two of three. The tens function just repeated divides by 5 and adds the results. The palindrome check uses the double-speed list iterator to only reverse the first half of the list (and keep the list comparison short).

It was Pascal at university in my day (as well as Lisp, Prolog and some Occam, if anyone remembers that). The local place here has used ML for many years for introductory programming, though sadly there is some sort of Java option these days as well.

In honor of my first programming language (a modified FORTRAN 77 on punch cards):

Didn’t test enough. There was a off by 1 bug in FUNCTION TWO.

Here is an improved main program that reads data from standard input and a revised TWO().

Here’s a sample input file (use redirections to feed the file to stdin).

and a sample run

Here are some Python solutions.

The sum of squares function is like the Haskell solution above, doing a partial sort of the three numbers in a couple of comparisons. The trailing zero computation is also similar: repeatedly divide by 5 and add. The palindromic number test now computes the digits from either end and stops when a discrepancy is found, so we can reject non-palindromes without converting each digit.

Scala:

1. List(a,b,c).sorted.slice(1, 3).map(x=>x*x).sum

2. n.toString().reverse==n.toString()

3.

def factorialTrailingZeroesCount(n: Long):Long = {

if (n<5) 0

else n/5 + factorialTrailingZeroesCount(n/5)

}

@Jaime: nice solution for the first :)

Here’s another Haskell version. Maybe not quite in the manner of a beginning programmer (sorry!), but I still tried to keep it “naive”.

A solution in Modern Fortran. I picked a slightly different solution to problem 2. I don’t quite understand the solution to problem 3, so I re-used the one many others posted above.