index | submit | rank | book

Computer Science by Example

<< 2. Setting up what you need   |   3. Programming Basics   |   4. Programming >>

3. Programming Basics

This chapter explains the basics of programming. You will write your first program then learn how to: write to the screen, read from the keyboard, operate on integers, write conditionals and write loops. This will be just an introduction of each of these concepts – we will only explore them in-depth in the next chapter. ◻

If you are a first time programmer, go slow. Take the time to solve each of the exercises. When doing them, type everything instead of copy-pasting.

A first time programmer should expect to spend 4 to 8 hours to complete this chapter including all exercises. An experienced programmer should be able to solve all exercises in this chapter in less than 2 hours. ◻

3.1. Your first program

We will now write our first computer program where we say “hello” to the world of programming. We will learn to:

• write a computer program;
• use a compiler to transform source code into executable machine code;
• run a computer program;
• submit a solution to the CScx Online Judge.

Let’s begin with the description of the programming exercise.

Programming Exercise (hello)

Write a command line program that prints “Hello, World!” to the screen. If you call it from the command line, it should produce a single line containing the Hello, World! message. like so:

$ ./hello
Hello, World!

Recall from the previous chapter that the part that follows $ is what we type on the terminal. ◻

Here is a flowchart with an outline for a hello solution:

Flowcharts are used to describe programs graphically. The two stadiums (or “pills”) are terminals and indicate where the program begins or ends. The parallelogram represents an input or output action and the arrows indicate the flow. Start; print “Hello, World!”; End. ◻

Now, please jump to the section with the explanation for your chosen programming language: C, Python or Haskell.

When studying programming, avoid copying and pasting. Take time to actually type in the programs and commands in this book:

1. This will help you memorize the functions and commands you are using.
2. You will make mistakes like forgetting a close bracket ()) or a semicolon (;) — because of this you will be forced to deal with compile errors sooner which is an important part of being a programmer.
3. You will be forced to differentiate between special characters such as: ASCII-quotes (') and backquotes (`); or ASCII-double-quotes (") and typographic double-quotes (“ and ”). Of these, ASCII vertical quotes (') and double-quotes (") are the ones most frequently used in programming. ◻

print("Hello, World!")

$ python3 hello.py
Hello, World!

$ python3 hello.py
  File "examples/hello/hello.py", line 1
    print(Hello, World!")
                      ^
SyntaxError: invalid syntax

#include <stdio.h>

int main()
{
    printf("Hello, World!\n");
    return 0;
}

$ gcc hello.c -o hello

$ ./hello
Hello, World!

$ gcc hello.c -o hello
hello.c: In function ‘main’:
hello.c:5:29: error: expected ‘;’ before ‘return’

main :: IO ()
main = do
  putStrLn "Hello world!"

$ ghc hello.hs -o hello

$ ./hello
Hello, World!

$ ghc hello.hs -o hello
hello.hs:3:3: error:
    • Variable not in scope: putSrtnL :: [Char] -> IO ()
    • Perhaps you meant ‘putStrLn’ (imported from Prelude)
  |
3 |   putSrtnL "Hello, World!"
  |   ^^^^^^^^

Submit your solution. Whether you have used C, Python or Haskell, submit your solution to the Online Judge. After submission, go to your very own user page to check if you got a full score. Even though this is a simple exercise, it is useful to submit your solution as you will learn to interact with the Online Judge system which later will be used in more complex programming exercises.

If you did not get a full score, try looking back at exercise description. Remember since that the Online Judge is automated, the output of your solution has to match exactly. Check punctuation and case in your Hello, World! message.

If you did get a full score, congratulations! You solved your first “Computer Science by Example” exercise. Now, repetition is key: can you do this exercise tomorrow just from memory? If so, what about in a week? Trying to remember what you need to type is useful for learning. Try getting back to the hello exercise every day until you can do it from memory. In the meanwhile, read on. ◻

Programming Exercise (cscx)

Write a program that prints “Computer Science by Example”.

No input should be read.

The output should contain a single line with the Computer Science by Example message. This line should be terminated in a line break.

Example output

Computer Science by Example

◻

Hint: If you are unsure where to start, try adapting the “Hello World” program shown earlier in this chapter. Again, use a compiler or interpreter to be able to run and test your program. When you are sure you got it right, try submitting it to the Online Judge. ◻

3.2. Basic input and output

In a command line session, a program reads from the standard input and writes to standard output. The standard input is usually mapped to what is typed in the keyboard. The standard output is usually mapped to the screen. Input and output are often shortened as I/O. When we say we read or write something without qualifying where to and from standard I/O is implied. ◻

Reading and writing integer numbers

Integer numbers, or simply integers, are those that have no fractional parts: …, -2, -1, 0, 1, 2, 3, …

We can read integer numbers and store it on variables and we can print an integer value stored in a variable. Please skip to the description of how to do this in your programming language of choice. ◻

x = int(input())

print(x)

int x;
scanf("%i",&x);

printf("%i\n",x);

x <- readLn :: IO Int

print x

Programming Exercise (repeat1)

Write a program that reads a single number from standard input and repeats it on standard output. Here is an example command line session with this program:

$ ./repeat1
1
1

1

1

2

2

◻

Without looking at the solutions that follow, try to come up with the solution program on your own. Think for a couple of minutes at least. If you are stuck, read on. ◻

Here is a flowchart with an outline for a repeat1 solution:

Start; Read a number x; Print the number x; End. ◻

Now, please jump to the section explaining the solution for your chosen programming langauge. Again, avoid copying and pasting for best results.

Do not try to learn more than one language at once: if you are planning to learn more than one programming language, first go through the book using a single language, only then start with the second. For example, first do most of the exercises in Python, only then start doing them in C. ◻

x = int(input())
print(x)

#include <stdio.h>

int main()
{
    int x;
    scanf("%d",&x);
    printf("%d\n",x);
    return 0;
}

main :: IO ()
main = do
  x <- readLn :: IO Int
  print x

Wether our solution was in Python, C or Haskell, we could have named our variable x something else: y, an_integer_value, number, etc. ◻

Again, please do:

1. Compile your solution and run it locally. Does it behave as you expect it to?
2. Submit your solution to the Online Judge. Can you get a full score there? ◻

Reading and writing strings

A string is a sequence of characters. For example, Hello, World!, abcdef, 123456 are strings. In C, Python and Haskell, we can represent literal strings by enclosing characters in double-quotes: "Hello, World!", "abcdef" and "123456". These can be used as arguments to printing functions.

We can read strings from user input and store these into variables. ◻

str = input()

str = input().rstrip()

print(str)

char str[31];
scanf("%30s",str);

fgets(str, 31, stdin);

printf("%s\n",str);

str <- getLine

putStrLn str

Programming Exercise (hi1)

Write a program that reads a single name from the standard input device and prints Hello, <Name>! on the standard output device.

John

Hello, John!

Mary

Hello, Mary!

◻

Now, try to work out a solution before reading on the example solutions. ◻

Here is a flowchart with an outline for a hi1 solution:

We read a string into the variable “name”; then we print the string “Hello, name!”. ◻

name = input().rstrip()
print("Hello, " + name + "!")

Hello, John
!

#include <stdio.h>

int main()
{
    char name[31];
    scanf("%30s",name);
    printf("Hello, %s!\n",name);
}

main :: IO ()
main = do
  name <- getLine
  putStrLn ("Hello, " ++ name ++ "!")

Reading and writing multiple values

So far, we read and wrote single values. We can read and write multiple values as well. For example, we can read both a string and an integer in the same line. As usual, please jump to the explanation in your chosen language.

str, num = input().split()
num = int(num)

print("The string is", str, "and the number is", num)

char str[61];
int num;
scanf(" %60s %d", str, &num);
printf("The string is %s and the number is %d.", str, num);

line <- getLine
let [str, num'] = words line
let num = read num'

putStrLn ("The string is " ++ str ++ " and the number is " ++ show num)

Programming Exercise (age1)

Write a program that reads a string and an integer and prints a name and age message.

Input will consist of a single line containing a string n and a natural number a where

|n| ≤ 30, i.e.: the string n is no more than 30 characters

0 ≤ a ≤ 180

Your program should produce a single line containing the message:

<n> is <a> years old.

with <n> replaced by n and <a> replaced by a.

John 23

John is 23 years old.

Jane 32

Jane is 32 years old.

◻

Here is a flowchart with an outline for a solution to the age1 exercise:

We have the same pattern as before. We read the required items; then we print the required message. ◻

name, age = input().split()
age = int(age)
print(name, "is", age, "years old.")

#include <stdio.h>

int main()
{
    int age;
    char name[31];
    scanf(" %30s %d", name, &age);
    printf("%s is %d years old.\n", name, age);
    return 0;
}

main :: IO ()
main = do
  input <- getLine
  let [name, age'] = words input
  let age = read age' :: Int
  putStrLn (name ++ " is " ++ show age ++ " years old.")

You will have to solve the next exercise on your own. Do not worry, as it is very similar to previous exercises.

Programming Exercise (swap1)

Write a program that reads an integer and a string and prints them in swapped order. After reading number n and string s, it prints string s followed by number n.

Input will consist of a single line containing a natural number n and a string s.

|s| ≤ 30, i.e.: the string s is no more than 30 characters

0 ≤ n ≤ 1000

Your program should produce a single line containing the string s followed by the number n separated by a single space.

123 abcd

abcd 123

64 Apples

Apples 64

3.3. Basic functions and operators

Whether you are using Python, C or Haskell, you can perform integer operations such as addition, subtraction and multiplication. Addition is performed using the + operator, subtraction is performed using the - operator and multiplication is performed using the * operator. Multiplication has a higher precedence than addition and subtraction. These operations can appear anywhere in the program where we could place a number.

Here is an example interactive session with Python or Haskell:

> 1 + 1
2
> 2 + 3
5
> 2 * 3
6
> 10 * 3 - 2 * 5
20

The lines preceded by >, represent what we type in. The other lines are what is returned back by the interactive session. You can replicate the above command line session by going to your terminal, typing either python or ghci, then typing the above expressions. Some languages, like C, do not have interactive sessions. ◻

We can also apply functions to values and include these in expressions. One such example is the function abs which computes the absolute value of a number. The following examples set variable x to 10 times the absolute value of 3.

• Python x = 10 * abs(3)
• C x = 10 * abs(3);
• Haskell let x = 10 * abs 3

◻

We can also declare functions of our own. Please jump to the section with the explanation for your chosen language. ◻

def <name>(<argument>):
    <command1>
    <command2>
    ...
    return <result>;

def triple(x):
    return 3 * x

def triple(x):
    r = 3 * x
    return r

x = triple(3)

<type> <name>(<type> <argument>)
{
    <command1>;
    <command2>;
    ...
    return <result>;
}

int triple(int x)
{
    return 3 * x;
}

int triple(int x)
{
    int r;
    r = 3 * x;
    return r;
}

x = triple(3);

<name> :: <type> -> <type>
<name> <pattern>  =  <result>

triple :: Int -> Int
triple x  =  3 * x

triple 3

Programming Exercise (triple1)

Write a program that reads a single number from standard input and prints the triple of its value on standard output.

2

6

123

369

Your program should be implemented using a triple function that receives one integers as argument and returns an integer. Please refer to the information for your chosen language:

• C prototype: int triple(int x);
• Haskell type: triple :: Int -> Int
• Python definition: def triple(x):

◻

Here is a flowchart with an outline for a triple1 solution:

We read the number, then we print its triple. ◻

def triple(x):
    return 3 * x

x = int(input())
print(triple(x))

#include <stdio.h>

int triple(int i)
{
    return 3*i;
}

int main()
{
    int i;
    scanf("%d", &i);
    printf("%d\n",triple(i));
}

triple :: Int -> Int
triple x  =  3 * x

main :: IO ()
main = do
  x <- readLn
  print (triple x)

Programming Exercise (inc1)

Write a program that reads a single number and prints its increment, i.e. its value added to one.

The input contains a single line with one integer x where

0 ≤ x ≤ 100 000.

The output should contain a line with a single integer y where y = x + 1 and should be terminated by a line break.

2

3

123

124

Your program should be implemented using a inc function that receives one integers as argument and returns an integer. Please refer to the information for your chosen language:

• C prototype: int inc(int x);
• Haskell type: inc :: Int -> Int
• Python definition: def inc(x):

◻

Functions with more than one argument

We can also declare functions with more than one argument. ◻

def <name>(<argument1>, <argument2>, ..., <argumentN>):
    <command1>
    <command2>
    ...
    return <result>

def add(x, y):
    return x + y

<type> <name>(<type> <argument1>, <type> <argument2>, ...)
{
    <command1>;
    <command2>;
    ...
    return <result>;
}

int add(int x, int y)
{
    return x + y;
}

<name> :: <type1> -> <type2> -> ... -> <typeN> -> <type>
<name> <pattern1> <pattern2> ... <patternN>  =  <result>

add :: Int -> Int -> Int
add x y  =  x + y

Programming Exercise (add1)

Write a program that reads a pair of numbers and prints its sum.

The input contains a single line with two integers x and y where

0 ≤ x, y ≤ 100 000.

The output should contain a single integer z where z = x + y.

3 7

10

1234 4321

5555

Your program should be implemented using an add function that receives two integers as arguments and returns an integer. Please refer to the information for your chosen language:

• C prototype: int add(int x, int y);
• Haskell type: add :: Int -> Int -> Int
• Python definition: def add(x,y):

◻

Here is a flowchart with an outline for an add1 solution:

We read numbers x and y; we print x+y. ◻

def add(x,y):
    return x + y

x, y = input().split()
x = int(x)
y = int(y)
print(add(x,y))

#include <stdio.h>

int add(int x, int y)
{
    return x+y;
}

int main()
{
    int x, y;
    scanf("%d %d", &x, &y);
    printf("%d\n",add(x,y));
}

add :: Int -> Int -> Int
add x y = x + y

main :: IO ()
main = do
  line <- getLine
  let [x', y'] = words line
  let x = read x'
  let y = read y'
  print (add x y)

The example solutions above would behave the same if we ommitted the add function and replaced the call to add by simply x + y. This would be a more strightforward solution but the point here is to exercise the creation of functions. ◻

Now, the next couple exercises do not have example solutions in the book. Try figuring them out on your own and use the Online Judge to check your solutions. ◻

Programming Exercise (mult1)

Write a program that reads three numbers and prints their product.

Input consists of a single line with three natural numbers x, y and z where 0 ≤ x, y, z ≤ 999.

The output should contain a single line with an integer w where w = x × y × z.

3 7 1

21

234 321 999

75038886

Your program should be implemented using a mult function that takes three integers as arguments and returns an integer. Please refer to the information for your chosen language:

• C prototype: int mult(int x, int y, int z);
• Haskell type: mult :: Int -> Int -> Int -> Int
• Python definition: def mult(x,y,z):

◻

Hint: first try implementing your mult1 solution from scratch. If that is to difficult, try adapting your solution to add1: you will need to replace the addition operation and to consider an extra number on the input. ◻

Programming Challenge (box1)

Write a program that calculates the volume and the external surface area of a rectangular box given its width, height and depth.

Input consists of a single line with three natural numbers w, h and d where 0 < w, h, d ≤ 999. These numbers indicate respectively the width, height and depth of a given box.

The output should contain two lines. The first line of output should indicate the volume in the following format:

The volume of a <w> by <h> by <d> box is <v>.

The second line of output should indicate the area in the following format:

The surface area of a <w> by <h> by <d> box is <a>.

Replace <w>, <h> and <d> by the dimensions of the box in the same order given in the input. Replace <v> and <a> by the volume and area respectively.

Example input 1

1 1 1

Example output 1

The volume of a 1 by 1 by 1 box is 1.
The surface area of a 1 by 1 by 1 box is 6.

Example input 2

3 4 5

Example output 2

The volume of a 3 by 4 by 5 box is 60.
The surface area of a 3 by 4 by 5 box is 94.

Your program should be implemented using two functions volume and area. Each should take the 3 dimensions of a box and return its volume and surface area. Please refer to the information for your chosen language:

• C prototypes: int volume(int w,int h,int d); int area(int w,int h,int d);
• Haskell types: volume, area :: Int -> Int -> Int -> Int
• Python definitions: def volume(w,h,d):, def area(w,h,d):

◻

3.4. Basic conditions

We can execute different actions based on conditions. In this section we will learn how to: use basic comparison operators; declare if-else conditions; declare if-else-if conditions; and declare case conditions. ◻

Boolean values and comparison operators

A boolean value, or truth value, is either true or false. A comparison operator is one where the result is a boolean value. For example:

• if we ask “Is 2 equal to 1 + 1?” This is true.
• if we ask “Is 2 equal to 1?” This is false.
• if we ask “Is x equal to 2?” The answer will depend on the value of x – which in programming, may depend on user input.

In the three examples above, “is equal to” is a comparison operator and the answers to the questions, true and false are boolean values. Comparison operators may be applied to literal values or variables. ◻

Note that in Python, C and Haskell, the equality comparison operator is composed of two equals signs == this is to differentiate from the assignment operation symbol =. If we see, x == 3 we read “x is equal to y?” If we see, x = 3 we read “x becomes 3.” ◻

If-else conditions

Equipped with comparison operators, we can now use if-else conditions to execute different actions or commands depending on a boolean value. The following flowchart shows what we want to achieve:

Above, we execute action A or action B depending on the result of the boolean condition.

Here is an example flowchart: if a number is less than 10, we print “This number is less than 10.” otherwise we print “This number is greater than 9.” ◻

if <condition>:
    <command>
    <command>
    ...
    <command>
else:
    <command>
    <command>
    ...
    <command>

if x < 10:
    print("This number is less than 10.")
else:
    print("This number is greater than 9.")

if (<condition>) {
    <command>
    <command>
    ...
    <command>
} else {
    <command>
    <command>
    ...
    <command>
}

if (x < 10) {
    printf("This number is less than 10.");
} else {
    printf("This number is greater than 9.");
}

if <condition>
then <result1>
else <result2>

if x < 10
then putStrLn "This number is less than 10."
else putStrLn "This number is greater than 9."

Programming Exercise (oddeven1)

Write a program that prints whether a given natural number is odd or even. A number is even when it is disivible by two. A number is odd when it is not divisible by two.

The input contains a single line with a natural number n where 0 ≤ n ≤ 100 000. The output should contain a single line with odd or even.

12

even

7

odd

Hint: to check if a number is even you can check that the remainder of the division by two is zero.

• In Python and C, you can use the % operator. The expression x % 2 evaluates to the remainer of the division of x by 2.

• In Haskell, you can use the rem function. The expression rem x 2 evaluates to the remainer of the division of x by 2. You can alternatively use the functions odd and even which return a boolean value indicating whether a number is odd or even.

Without looking at the example solutions that follow try coming up with a solution yourself. If after a few minutes you are still stuck, read on. ◻

Here is a flowchart with an outline for a solution to the oddeven1 exercise:

We read a number x. If it is divisible by 2, we print “even”; Otherwise, we print “odd”. ◻

x = int(input())
if x % 2 == 0:
    print("even")
else:
    print("odd")

#include <stdio.h>

int main()
{
    int x;
    scanf("%d", &x);
    if (x%2 == 0) {
        printf("even\n");
    } else {
        printf("odd\n");
    }
    return 0;
}

main :: IO ()
main = do
  x <- readLn
  if even x
  then putStrLn "even"
  else putStrLn "odd"

Programming Exercise (order1)

Write a program that reads a pair of numbers and prints if they are in strict increasing order. In other words, if the second number is greater than the first.

Input will consist of a pair of numbers x and y where

0 ≤ x, y ≤ 100 000.

Output should contain a single line with either Yes or No indicating whether x < y.

1 3

Yes

10 9

No

◻

If conditions

In most programmign languages, you can have an if without an else, i.e.: the else clause is optional. This is true in Python and C. In Haskell the else clause is required.

Below is the flowchart for an if clause without an else.

When the condition is met, we execute the given action and then follow the normal flow. If the condition is not met, we skip the given action and then follow the normal flow. ◻

if <condition>:
    <command>
    <command>
    ...
    <command>

if (<condition>) {
    <command>
    <command>
    ...
    <command>
}

If-else-if conditions

To execute different code depending on multiple conditions we use if-else-if conditions.

In the above flowchart, we have two conditions and three different actions. If condition 1 is true, we execute action A and proceed with the normal flow. Otherwise, if condition 2 is true, we execute action B and proceed with the normal flow. Otherwise, we execute action C and proceed with the normal flow. ◻

Here is an example flowchart deciding if a number is negative, positive or zero.

If a number is less than zero, we print “negative” and carry on. Otherwise, if a number is greater than zero, we print “positive.” and carry on. Otherwise, the number must be zero, we print “zero” and carry on. ◻

if <condition1>:
    <command>
    <command>
    ...
    <command>
elif <condition2>:
    <command>
    <command>
    ...
    <command>
else:
    <command>
    <command>
    ...
    <command>

if x < 0:
    print("negative")
elif x > 0:
    print("positive")
else:
    print("zero")

if (<condition1>) {
    <command>;
    <command>;
    ...
    <command>;
} else if (<condition2>) {
    <command>;
    <command>;
    ...
    <command>;
} else {
    <command>;
    <command>;
    ...
    <command>;
}

if (x < 0) {
    printf("negative");
} else if (x > 0) {
    printf("positive");
} else {
    printf("zero");
}

if <condition1>
then <result1>
else if <condition2>
then <result2>
else <result3>

if <condition1>
  then <result1>
  else if <condition2>
         then <result2>
         else <result3>

if x < 0
then putStrLn "negative"
else if x > 0
then putStrLn "positive"
else putStrLn "zero"

<name> :: <type> -> ... -> <type>
<name> <pat> | <condition1> = <result1>
             | <condition2> = <result2>
             | otherwise    = <result3>

printSignum :: Int -> IO ()
printSignum x | x < 0      =  putStrLn "negative"
              | x > 0      =  putStrLn "positive"
              | otherwise  =  putStrLn "zero"

Programming Exercise (good1)

In English, we greet people by “Good morning”, “Good afternoon” or “Good evening” depending on the time of day.

Write a program that given the current hour (in 24 hours format) prints a good morning, good afternoon or good evening message according to the following list:

• “Good morning” between 4 and 11
• “Good afternoon” between 12 and 17
• “Good evening” between 18 and 23
• “Hi” otherwise

Input will consist with a single number h where 0 ≤ h < 24

Output should contain a single line with either: Good morning, Good afternoon, Good evening or Hi.

11

Good morning

15

Good afternoon

◻

Here is a flowchart with an outline for a solution to the good1 exercise:

We read the hour h and check the upper and lower bounds to decide what category to print. ◻

h = int(input())
if 4 <= h and h <= 11:
    print("Good morning")
elif 12 <= h and h <= 17:
    print("Good afternoon")
elif 18 <= h and h <= 23:
    print("Good evening")
else:
    print("Hi")

#include <stdio.h>

int main()
{
    int h;
    scanf("%d", &h);
    if (4 <= h && h <= 11) {
        printf("Good morning\n");
    } else if (12 <= h && h <= 17) {
        printf("Good afternoon\n");
    } else if (18 <= h && h <= 23) {
        printf("Good evening\n");
    } else {
        printf("Hi\n");
    }
}

main :: IO ()
main = do
  h <- readLn
  putStrLn $ good h

good :: Int -> String
good h |  4 <= h && h <= 11  =  "Good morning"
       | 12 <= h && h <= 17  =  "Good afternoon"
       | 18 <= h && h <= 23  =  "Good evening"
       | otherwise           =  "Hi"

Programming Exercise (signum1)

Write a program that reads an integer and prints whether it is positive, negative or zero.

Input will consist of a single number n where -100 ≤ n ≤ 100.

Output should contain a single line with either: positive, negative or zero.

60

positive

-33

negative

Programming Challenge (triangle1)

Every triangle can be classified as either scalene, isosceles or equilateral:

• equilateral triangles have all edges of the same size;
• isosceles triangles have exactly two edges of the same size;
• scalene triangles have three edges of different sizes.

(Some authors consider equilateral to be a special case of isosceles. For the purpose of this exercise, we use Euclid’s original definition and consider isosceles triangles those with exactly two edges of the same size.)

Write a program that given three edge sizes determines whether a triangle is scalene, isosceles, equilateral or impossible.

Input consists of a single line with three natural numbers x, y and z where 0 < x, y, z < 100

Output should contain a single line with just scalene, isosceles, equilateral or impossible.

3 4 5

scalene

3 3 1

isosceles

◻

3.5. Basic recursion

A recursive definition is one that is defined in terms of itself. For example, we can recursively define the factorial of a number as:

• The factorial of zero is one.
• The factorial of a natural number n is n times the factorial of n - 1.

In symbolic terms:

• 0! = 1
• n! = n × (n - 1)!

By the above definition, the factorial of 4 is 24

• 4! = 4 × 3!
• 4! = 4 × 3 × 2!
• 4! = 4 × 3 × 2 × 1!
• 4! = 4 × 3 × 2 × 1 × 0!
• 4! = 4 × 3 × 2 × 1 × 1
• 4! = 24.

Recursive definitions always have at least one base case and at least one recursive case. The base case makes it so that we do not infinitely use the definition. ◻

A common joke among Computer Scientists is “to understand recursion one must first understand recursion”. ◻

A recursive function is one that calls itself, i.e.: uses recursion. ◻

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

int factorial(int n)
{
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

factorial :: Int -> Int
factorial n  =  if n == 0
                then 1
                else n * factorial (n-1)

factorial :: Int -> Int
factorial 0  =  1
factorial n  =  n * factorial (n-1)

Recursive functions solve computational problems by breaking it into smaller problems. In the case of the factorial function above, it reduces the problem of computing the factorial of a number n, to the problem of computing the factorial of the decrement of n, i.e.: n-1. This makes sure we always reach our base case. Decrementing one of the received arguments before making a resursive call is a common recursive pattern. ◻

Programming Exercise (factorial1)

Write a program that computes the factorial of a number n, or simply n!.

Input will contain a single integer n where 0 ≤ n < 10. Output should contain a line with the factorial of n.

4

24

6

720

Your program should contain a factorial function that takes an integer and returns an integer. Please refer to the information for your chosen language:

• C prototype: int factorial(int n);
• Haskell type: factorial :: Int -> Int
• Python definition: def factorial(n):

◻

Programming Exercise (power1)

Write a program that performs integer exponentiation of a base b to the power of n.

bⁿ = b × … × b where b is repeated n times

for example

2⁵ = 2 × 2 × 2 × 2 × 2 = 32

Input will contain two integers b and n where 0 < b, n ≤ 9

2 5

32

5 2

25

Your program should contain a power function that takes two integers and returns an integer. The first integer argument should be the base and the second the exponent. Please refer to the information for your chosen language:

• C prototype: int power(int b, int n);
• Haskell type: power :: Int -> Int -> Int
• Python definition: def power(b, n):

You should perform the exponentiation as a series of multiplications. For this exercise, you should restrain from using your programming languages' built-in exponentiation functions. ◻

Hint: Try to come up with a recursive definition of exponentiation. What is the base case? What is the recursive case? What is the value of b¹? Can you define bⁿ in terms of bⁿ⁻¹? ◻

Programming Exercise (fibonacci1)

Write a program that computes a number in the fibonacci sequence. This sequence is defined recursively as follows:

• F₀ = 0
• F₁ = 1
• Fₙ = Fₙ₋₁ + Fₙ₋₂

That is, the zeroth Fibonacci number is zero and the first Fibonacci number is one. Other Fibonacci numbers are given by the sum of its two predecessors.

The first 10 numbers in the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21 and 34.

Input will consist of a single integer n indicating the position in the Fibonacci sequence.

Output should contain a single line with a number Fₙ indicating the Fibonacci number in position n.

3

2

8

21

Your program should contain a fibonacci function that takes an integer and returns an integer. Please refer to the information for your chosen language:

• C prototype: int fibonacci(int n)
• Haskell type: fibonacci :: Int -> Int
• Python definition: def fibonacci(n):

For the purposes of this exercise you should not worry about performance. Instead your should focus on correctness. Implement your fibonacci function in the most straightforward way possible. ◻

3.6. Basic loops

Programs may also involve repetition of certiain tasks. In most programming languages, this can be achieved through a while loop, like in the following pseudo-code:

...
while condition
    action
    action
    action
...

Here is a flowchart for the above pseudo-code:

The condition is checked, if it is true, we execute the sequence of actions and go back to checking the condition again. If the condition is ever false, we exit the while loop and carry on with executing the following code. ◻

For example, the following flowchart prints a countdown from three: “3, 2, 1, go!”

First, x becomes 3; Then, while x is greater than zero: print x then x becomes x - 1; at the end, print “Go!”. ◻

Often one of the actions changes the state of the program so that the condition is false at some point. In the above example we decrement the value of x to make sure it reaches zero. Failing to define a proper exit condition will yield an infinite loop – a program that never stops. This is one of the reasons why a computer program may freeze and stop responding. ◻

while condition:
    command
    command
    ...
    command

x = 3
while x > 0:
    print(x)
    x = x - 1
print("Go!")

while (condition) {
    command;
    command;
    ...
    command;
}

x = 3;
while (x > 0) {
    printf("%i\n",x);
    x = x - 1;
}
printf("Go!\n");

repeat ... = if condition
             then ... repeat ...
             else ...

countdown :: Int -> IO ()
countdown x | x > 0      =  do print x
                               countdown (x-1)
            | otherwise  =  do putStrLn "Go!"

countdown 3

Programming Exercise (hello2)

Similarly to the hello exercise, you should write a program that prints “Hello, World!” on the standard output device. This time however, you must first read from the standard input how many times the message should be printed.

Input consists of a single line containing an integer n indicating how many times the hello message should be printed.

1 ≤ n ≤ 1000

The output should contain n lines each containing Hello, World! exactly.

Example input

3

Example output

Hello, World!
Hello, World!
Hello, World!

◻

Here is a flowchart with an outline for a hello2 solution:

First, we read number n. Then, while n is greater than 0: we print “Hello World” and decrement n. ◻

n = int(input())
while n > 0:
    print("Hello, World!")
    n = n - 1

#include <stdio.h>

int main()
{
    int n;
    scanf(" %i", &n);
    while (n > 0) {
        printf("Hello, World!\n");
        n = n - 1;
    }
    return 0;
}

main :: IO ()
main = do
  n <- readLn
  hello n

hello :: Int -> IO ()
hello 0 = return ()
hello n = do
  putStrLn "Hello, World!"
  hello (n-1)

Programming Exercise (total)

Write a program that computes the total, i.e. sum, of a given list of numbers.

Input begins with a line containing an integer n indicating the number of lines that follow. The number n should not be included in the sum. Each of the n following lines contain an integer xᵢ to be accounted for the sum.

Your program should work for n and xᵢ in the following ranges:

1 ≤ n ≤ 1000

0 ≤ xᵢ ≤ 100 000

Output should contain a single line with an integer t = x₁ + x₂ + x₃ + … + xₙ.

3
1
2
3

6

4
10
20
30
40

100

◻

Here is a flowchart with an outline for a solution to the total exercise:

First, we read the number of integers to be read and store it on n. We set set the total to zero. We then read number x and add it to the total n times. We finally print the total. ◻

total = 0
n = int(input())
while (n > 0):
    x = int(input())
    total = total + x
    n = n - 1
print(total)

#include <stdio.h>

int main()
{
    int n, x, total=0;
    scanf(" %d",&n);
    while (n > 0) {
        scanf(" %d",&x);
        total = total + x;
        n = n - 1;
    }
    printf("%d\n",total);
    return 0;
}

main :: IO ()
main = do
  n <- readLn
  total n 0

total :: Int -> Int -> IO ()
total 0 t = print t
total n t = do
  x <- readLn
  total (n-1) (t+x)

Programming Exercise (countdown1)

Write a program that performs a countdown. It should read a single integer and it should print a countdown from that integer. With n as the input, your program should produce the following with one item per line: n, n-1, n-2, …, 2, 1, Go!

Example input

3

Example output

3
2
1
Go!

◻

Programming Exercise (seq1)

Write a program that produces a sequence of numbers. It should read a single line with two integers and it should produce a sequence starting from the first integer and ending on the second.

3 6

3
4
5
6

12 16

12
13
14
15
16

◻

3.7. Chapter remarks

In this chapter we have seen how to: perform I/O, declare and use functions, use operators, use conditionals and use loops. These are the basic tools for programming. Do not worry if you do not understand some of these concepts completely, as in the next chapter, we will revisit them in more depth. ◻

3.8. Exercises

The exercises throughout this chapter were:

• hello
• cscx
• repeat1
• hi1
• age1
• swap1
• triple1
• inc1
• add1
• mult1
• box1 (challenge)
• oddeven1
• order1
• good1
• signum1
• triangle1 (challenge)
• factorial1
• power1
• fibonacci1
• hello2
• total
• countdown1
• seq1

A good way to test your skills is to see if you are able to do these exercises without consulting the book or at least without looking at the example solutions. Submit your solutions to the Online Judge to make sure that they are correct. If you are comfortable with these exercises, it is time to move to the next chapter. ◻

<< 2. Setting up what you need   |   3. Programming Basics   |   4. Programming >>

index | submit | rank | book

Copyright © 2020-2023 Rudy Matela
All rights reserved