index | submit | rank | book

Computer Science by Example

<< 3. Programming Basics   |   4. Programming   |   5. Mathematical Foundations >>

4. Programming

Equipped with the programming basics, we will now learn programming in more depth. We will review all concepts of the previous chapter but try to deepen our understanding. We will also go through some new concepts such as lists, arrays and structured data types.

4.1. Data types

As we have seen in the previous chapter, in programming, we manipulate data of different types. Here are some standard data types used in programming:

• integers: …, -3, -2, -1, 0, 1, 2, 3, … Integers or whole numbers are used to represent integral quantities like the age of a person or the number of employees in a company. They are usually written in programs as-is by their decimal notation.

• floats: 0.5, 1.414, 1.618, 3.141, etc. Floats or floating point numbers can be used to represent fractional quantities like the height of a person or the amount of liquid in a container. They are usually written in programs as-is by their decimal notation with the fractional part coming after a dot.

• characters: a, b, ?, +, _, etc. Characters are letters, signs or symbols used in text, these include spaces, line breaks and tabs, which are each considered a character in programming terms. Depending on the context these may be restricted to a certain character set. They are usually written in programs surrounded by single-quotes: 'a', 'b', '?'.

• strings: Hello, World!, www.example.com, etc. A string is a sequence of characters. We use them when we want to represent a text. This can be a name, an address, etc.

• booleans: true or false. Booleans represent a truth value. Using booleans, we can represent: “Is the current user an administrator?”; “Has this order been paid for?”; “Is this integer an even number?”; “Is x greater than y?”; etc.

• sequences, arrays or lists: Arrays or lists can be used to represent an usually homogeneous sequence of values.

There are other data types not mentioned here and it is also possible for programmers to define their own data types. This will be discussed later in the book.

Please jump to the section describing the types available in the language of your choice.

$ python
>>> type(360)
<class 'int'>
>>> type(3.14)
<class 'float'>
>>> type("Some text")
<class 'str'>
>>> type('Some text')
<class 'str'>
>>> type(False)
<class 'bool'>
>>> type(True)
<class 'bool'>
>>> type([1,2,3])
<class 'list'>

char c;
int x;
float f;

pi :: Float
pi = 3.141592

4.2. Variables

In programming, we often deal with variables. A variable has a name and a value. For example: a variable x, may have a value of 10 associated with it; a variable name, may have the value "Mary Smith" associated with it. ◻

Variables can appear as parameters or arguments to functions or as explicit declarations. Take for example the following piece of pseudo-code in an imaginary programming language:

1. function triple(integer variable x)
2.     integer variable y
3.     y <- x * 3
4.     return y

On line 1, we see an integer variable x which is the only parameter or argument to the function triple. On line 2, we see an integer variable y which is local to the function triple and receives the value of x times 3 on the third line. When we call triple with 7 as its argument, x has the value of 7 and on line 3, y becomes 21. During different times and in different contexts, x and y assume different values. ◻

Variables have a scope where they are valid. Consider the following piece of pseudo-code:

1. function quadruple(integer variable x)
2.     integer variable y
3.     y <- x * 4
4.     return y

The variables x and y only have meaning in the scope of the quadruple function, i.e.: inside the quadruple function. For example, if the functions triple and quadruple are part of the same program, the x and y inside triple are different than the x and y inside quadruple despite having the same name.

In cases where we have a scope-within-a-scope, the inner scope usually takes precedence when referencing a variable. ◻

<name> = <value>

x = 12

> type(x)
<class 'int'>

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

<type> <name>;

int x;

int x = 12;

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

let <name> = <value>
in  <expression>

let x = 12
in  ...

triple :: Int -> Int
triple x  =  let y = x * 3
             in  y

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

4.3. Input and output

In this section we will review input and output, picking up on where we left of on the last chapter. We will learn how to process input line by line and we will review how to read and write values of different types.

Processing input line by line

In the exercises of the previous chapter, each run of solution programs processed a single test case. Exercises in this chapter are different, each run of solution programs should process a series of test cases. This should be done usually line-by-line until the end of file (EOF).

When redirecting input using <in.txt, EOF is reached at the actual end of file. When typing input from the command line, you can simulate EOF by holding “Ctrl” and pressing “d” on Linux and Windows or by holding “Command” and pressing “d” on Mac. We use either Ctrl-D or ^D for short to express this key combination.

Now, please jump to the section with the explanation of how to process input line by line for the language of your choice.

import sys

for line in sys.stdin:
    ...
    ...

while ( scanf("%i", &x)==1 ) {
    ...
    ...
}

io1 :: String -> String
io1 s  =  ...

io :: String -> String
io input  =  unlines (map io1 (lines input))

main :: IO ()
main  =  interact io

When solving the exercises of this chapter, do not feel tempted to accumulate output and produce everything at the end. It is good practice to actually produce output as you go. As soon as your program has enough information to produce output, just do it.

Now, we go to our first exercise involving the above patterns.

Programming exercise (repeat)

Write a program that reads a series of numbers from standard input (usually the keyboard) and repeats the same numbers on standard output. Here is an example session of such a program:

$ ./repeat
1
1
2
2
3
3
123
123
^D

1
2
3
123

1
2
3
123

Hint: there is no need to accumulate input. Just print output as you go: as soon as you read the first number, just print it on standard output. ◻

Before looking at the example solutions, try to solve the exercise using the patterns shown earlier in the chapter. Try at least for a few minutes, if you are stuck, read on. ◻

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

While we are able to read a number x we print number x. ◻

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

Yet again, 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.

import sys

for line in sys.stdin:
    x = int(line)
    print(x);

#include <stdio.h>

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

main :: IO ()
main  =  interact io

io :: String -> String
io input  =  unlines (map io1 (lines input))

io1 :: String -> String
io1 line  =  show (solve (read line))

solve :: Int -> Int
solve x  =  x

read :: String -> Int
show :: Int -> String

Once more, 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 perfect score there? ◻

Reading and writing different types

How to read and write different types will depend on the language you are using.

line = input()

for line in sys.stdin:
    ...

line = line.strip()

a, b, c = line.split()

int(string)

string = "123"
x = int(string)

float(string)

string = "123.45"
x = float(string)

string = input('Would you like to continue? (y/n) ')
should_continue  =  string == "y"

print(value)

print(value1, value2, ..., valueN)

char line[100];
fgets(line, 100, stdin);

char string[100];
scanf("%99s", string);

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

int f;
scanf("%f", &f);

char c;
scanf("%c", &c);

char c;
scanf(" %c", &c);

char c;
int should_continue;
printf("Do you want to continue? (y/n) ");
scanf(" %c", &c)
should_continue  =  c == 'y'

int i;
float f;
char c;
scanf(" %i %f %c", &i, &f, &c);

while (scanf("%i %i", ...) == 2) {
    ...
}

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

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

printf("%s %i %f %c\n", str, i, f, c);

line <- getLine

number <- readLn

read "123"

putStr "Would you like to continue? (y/n) "
line <- getLine
let shouldContinue  =  line == "y"

putStrLn string

show 123

print number

putStrLn (string ++ " " ++ show i ++ " " ++ show f)

Programming exercise (hi)

Write a program that reads several names from the standard input device and, for each name, prints Hello, <Name>! on the standard output device. Here is an example session with such a program:

$ ./hi
John
Hello, John!
Mary
Hello, Mary!
Smith
Hello, Smith!

Names are provided one per line, and do not contain spaces. Names are composed of letters of the English alphabet or dashes (-), and have no more than 30 characters.

John
Mary
Smith

Hello, John!
Hello, Mary!
Hello, Smith!

Before looking at the example solutions, try solving the exercise by yourself. Run your solution locally with the example input. Is it correct? If so, use the Online Judge to check against other test cases.

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

While we are able to read the string “name”, we print “Hello, name!”. ◻

import sys

for line in sys.stdin:
    name = line.strip()
    print("Hello, " + name + "!");

#include <stdio.h>

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

main :: IO ()
main  =  interact io

io :: String -> String
io input  =  unlines (map io1 (lines input))

io1 :: String -> String
io1 name  =  "Hello, " ++ name ++ "!"

Programming exercise (age)

Write a program that reads a series of strings and integers and prints a name and age message.

Input will consist of a several lines each 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

For each line of input, your program should produce a line containing the message:

<n> is <a> years old.

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

John 23
Jane 32

John is 23 years old.
Jane is 32 years old.

◻

Programming exercise (swap)

Write a program that reads a series of pairs of integers and strings and swaps them.

Input will consist of several lines each containing a number n and a string s separated by a single space where:

0 ≤ n ≤ 1000

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

For each line of input, you program should produce a line of output with the string s followed by number n.

123 abcdef
64 bits

abcdef 123
bits 64

Formatting floating point numbers

When printing floating point numbers, it is often useful to specify how many decimal places we want to see. How that is done depends on the language you are using. ◻

print("%.2f" % x)

print("Floats are %.2f and %f." % (x,y))

printf("%.2f\n" % x)

printf("Floats are %.2f and %f.", x, y)

printf "%.2f\n" x

printf "Floats are %.2f and %f." x y

Programming exercise (owes)

Write a program that reads an amount in dollars and two names then formats and prints the following message: <name1> owes $<amount> dollars to <name2>.

Input contains several lines each with a decimal number and two names separated by spaces. The decimal number is greater than 0.0 and smaller than 999.0 and has up to two decimal places. The two names have up to 30 characters.

For each line of input, output should contain a corresponding line with the following message: <name1> owes $<amount> dollars to <name2>. The amount should be rounded to two decimal places and have no leading zeroes.

Example input

1.5 John Mary
199 Jane Mario

Example output

John owes $1.50 dollars to Mary.
Jane owes $199.00 dollars to Mario.

◻

4.4. Functions

Functions in programming are similar to mathematical functions: they take arguments and have a return value.

Consider the mathematical function f(x) = 2x + 1. The function f can be applied to different integer values yielding different results:

• f(3) = 7. When applied to 3, f has the result of 7.
• f(6) = 13. When applied to 6. f has the result of 13.

A similar function could be constructed in programming. The following pseudo-code in an imaginary programming language implements f.

function f(x)
begin
    return 2 * x + 1
end

◻

Functions may take multiple arguments of different types. The return value of a function has a type as well. ◻

Functions in programming may also perform actions such as reading input, printing to the screen, creating an user entry on database, etc. A function that just performs an action and has no return value can be called a procedure. ◻

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

def f(x):
    return 2 * x + 1

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

int f(int x)
{
    return 2 * x + 1;
}

void do_something()
{
    ...
}

<name> :: <type>
<name> <pat1>  =  <value1>
<name> <pat2>  =  <value2>
...
<name> <pat3>  =  <value3>

f :: Int -> Int
f x  =  2 * x + 1

putStrLnTwice :: String -> IO ()
putStrLnTwice s  =  do
  putStrLn s
  putStrLn s

4.5. Operators

In programming, we can use operators to manipulate numbers, booleans, strings or sometimes even functions. ◻

Operators can be classified on the number of operands. An operator is unary when it operates on a single value, e.g.: the negation operator - in -1. An operator is binary when it operates on two values, e.g.: the addition operator + in 1 + 2. ◻

Operators can be used in either prefix, infix or postfix notations. Prefix notation is when an operator appears before the operands, e.g.: the negation operator - in -1. Infix notation is when an operator appears between the operands, e.g.: the addition operator + in 1 + 2. Postfix notation is when an operator appears after the operands. ◻

Arithmetic Operators

As we have seen before, we can use operators to manipulate numbers.

In most programming languages, you can use +, - and * to perform addition, subtraction and multiplication in numbers. They are usually binary and infix. This is true in Python, C and Haskell.

In most programming languages, you can also use the unary prefix operator - to negate a number, e.g.: -1, -360. This is also true in Python, C and Haskell.

Programming languages offer a way to group expressions so the computer knows what operation to perform first. In most programming languages, round brackets ( and ) are used for that. Saying (1 - 2) - 3 is different than 1 - (2 - 3) due to which subtraction is performed first. Python, C and Haskell use round brackets to group operations.

Operators can have a precedence, that is, what is operated first. In most contexts, multiplication precedes addition, for example, 2 + 3 * 4 is interpreted as 2 + (3 * 4) and not as (2 + 3) * 4 – multiplication is performed before addition when there are no brackets.

Programming languages can also offer operators for:

• fractional division: (5 / 2 = 2.5);
• integer division: (5 ÷ 2 = 2);
• modulus: 5 mod 2 = 1; and
• exponentiation: 5² = 25.

The symbols for these vary for each language. ◻

We will now review how to use numeric operators in Python, C or Haskell, please jump to the explanation for your chosen language. ◻

x `div` y
x `mod` y

We will now revisit several exercises from the previous chapter. This time you will need to process several test cases in a single run.

After compiling, running and testing your solutions locally, submit them to the Online Judge. This time, the test sets are tougher and include edge cases. Can you get a full score there?

Programming Exercise (triple)

Write a program that reads several number and prints their triple.

The input contains several lines each with one integer x where

-100 000 < x < 100 000.

Each line of output should contain a corresponding integer y where y = 3x.

2
360
123

6
1080
369

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

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

Hint. You do not need to accumulate input, print output as you go. As soon as you read a number, print its triple. On your screen typed input will be intercalated with program output. ◻

Programming Exercise (inc)

Write a program that reads several numbers and prints their increment, i.e. their value added to one.

Input contains several lines, each with a single integer x where - 100 000 000 ≤ x ≤ 100 000 000.

Each line of output contains a single corresponding integer y where y = x + 1.

2
123
1000

3
124
1001

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

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

◻

Programming Exercise (add)

Write a program that reads several pairs of numbers and, for each pair, prints the sum.

Each line of input contains two numbers x and y where

-2 000 000 000 ≤ x, y ≤ 2 000 000 000

For each line of input there should be a line of output with the result of adding x to y.

0 0
3 7
12 21
-123 321
1234 4321

0
10
33
198
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 the chosen language:

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

◻

Programming Exercise (mult)

Write a program that calculates the product of three numbers. Your program should read from the standard input and print to the standard output. The standard input and output devices are usually the keyboard and screen of a command line session.

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

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

Example input

2 3 4
3 7 1
234 321 -999

Example output

24
21
-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 the 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):

◻

Programming Exercise (pi)

Given the radius of a circle, calculate its circumference and area.

The circumference of a circle with radius r is given by 2 × π × r or two times pi times the radius. The area of a circle with radius r is given by π × r ² or pi times the square of the radius. The number π, or pi, is a mathematical constant with an irrational value of 3.141 592 653 …

Each line of input contains a decimal value r indicating the radius where 0 < r < 10000.0.

For each line of input, your program should produce two numbers, c and a indicating the circumference and area. They should be rounded to two decimal places.

1
12
6.6
0.159

6.28 3.14
75.40 452.39
41.47 136.85
1.00 0.08

Your program should implement two functions circumference and area. Each should take a double-precision floating point number and return a double-precision floating point number. Please see the information for your programming language of choice:

• C: double circumference(double r); and double area(double r);
• Python: def circumference(r): and def circumference(r):
• Haskell: circumference :: Double -> Double and area :: Double -> Double

Hint. The value of π (pi) is a real number so the only way to represent it as a floating point value is to use an approximation. Although you can use a hardcoded value of 3.141592653589793 for π it is better to use the one provided by your programming language of choice:

• in C, use M_PI from math.h;
• in Python, use pi from the math module (a.k.a.: math.pi);
• in Haskell use pi from the Prelude.

◻

Programming Exercise (box)

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 several lines with three natural numbers w, h and d where 0 < w, h, d ≤ 999. These numbers indicate respectively the width, height and depth of the given box.

For each line of input, output should contain three corresponding lines. The first corresponding line should indicate the volume in the following format:

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

The second corresponding line should indicate the area in the following format:

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

The third line should be blank.

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

Example input

1 1 1
3 4 5
2 2 2

Example output

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.

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.

The volume of a 2 by 2 by 2 box is 8.
The surface area of a 2 by 2 by 2 box is 24.

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 type: volume, area :: Int -> Int -> Int -> Int
• Python definitions: def volume(w,h,d):, def area(w,h,d):

◻

Operators are syntactic sugar

In theory, a programming language does not need operators to support arithmetic operations. Just functions are needed.

We could write x + y as simply add(x,y). However, that would become simply cumbersome as we create more intricate expressions. The simple x * y + z * w would become add(multiply(x,y),multiply(z,w)). For the same reason, in mathematics we write 1 + 2 instead of “one added to two”. So in practice, most languages have operators, and we do use them. ◻

Boolean Operators and Comparison Operators

As we have seen before, we can use operators to manipulate booleans. These booleans, or truth-values are commonly used in conditions.

In most programming languages, we find, negation, conjunction and disjunction boolean operators. These represent respectively the words “not”, “and” and “or” in natural language. These boolean operators take boolean values as arguments and return a boolean value. We also find comparison operators: equality, inequality, greater-than, greater-than-or-equal, etc. These comparison operators take two values and return a boolean value. ◻

$ python
>>> 1 < 2 and 2 < 3
True
>>> False or True
True
>>> not True
False

$ ghci
> 1 < 2  &&  2 < 3
True
> False || True
True
> not True
False

Exercises involving boolean operators will appear on the next section. ◻

4.6. Conditions

In programming, we use conditions to represent branching execution paths. If a condition is true, execute an action; otherwise, execute a different action. ◻

If-else conditions

We use if-else conditions when we want to encode two branching execution paths. Here is a quick review from previous chapter. ◻

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

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

if (<condition>)
    <command>;
else
    <command>;

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

Programming Exercise (oddeven)

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.

Input and output

The input contains several lines each with a natural number n where -2 000 000 000 ≤ n ≤ 2 000 000 000. Input is terminated by the end-of-file (EOF).

For each line of input, the output should contain either odd or even.

0
3
12
-7

even
odd
even
odd

◻

If-else-if conditions

We use if-else-if conditions when we want to encode several different execution paths. These conditions are simply nested if-else conditions. Here is a quick review from previous chapter. ◻

if <condition1>:
    <command1>
elif <condition2>:
    <command2>
else:
    <command3>

if <condition1>:
    <command1>
else:
    if <condition2>:
        <command2>
    else:
        <command3>

if (<condition1>) {
    <command1>;
} else if (<condition2>) {
    <command2>;
} else {
    <command3>;
}

if (<condition1>) {
    <command1>;
} else {
    if (<condition2>) {
        <command2>;
    } else {
        <command3>;
    }
}

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

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

Programming Exercise (order)

Write a program that reads several pairs 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 several lines each with a pair of numbers x and y where

-1 000 000 000 ≤ x, y ≤ 1 000 000 000.

For each line of input, output should contain a single line with either Yes or No indicating whether x < y.

1 3
10 9
-31337 -1337

Yes
No
Yes

Programming Exercise (good)

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 of several lines each with a single number h where 0 ≤ h < 24.

For each line of input, output should contain a corresponding line with either:

• Good morning,
• Good afternoon,
• Good evening or
• Hi.

11
15
20

Good morning
Good afternoon
Good evening

◻

Programming Exercise (bmi)

The Body Mass Index (BMI) can be used to classify weight in adults. The BMI of a person is given by the weight in kilogrammes divided by the square of the height in metres [WHO, CDC, NHS]. Based on the BMI, a person can be classified in one of four statistical categories: underweight, normal weight, overweight or obese. See the following table:

BMI = w/h² (kg/m²)

       BMI < 18.5  underweight
18.5 ≤ BMI < 25    normal weight
25   ≤ BMI < 30    overweight
30   ≤ BMI         obese

The above are statistical categories. To evaluate an individual’s health, one should consult with a trained healthcare provider.

Write a program that given the weight and height of a person prints the corresponding BMI classification.

The input consists of several lines, each containing two numbers h and w with up to two decimal points where

0.10 ≤ h < 3.00

1.0 ≤ w ≤ 999.9

For each line of input, the output should contain a single line with the corresponding BMI classification in lowercase letters: underweight, normal weight, overweight or obese.

1.75 69.9
1.60 65
1.91 111.1

normal weight
overweight
obese

◻

Programming Challenge (triangle)

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.)

All triangles can also be classified as right, obtuse and acute:

• obtuse triangles have one greater than 90° angle;
• right triangles have a 90° angle;
• acute triangles have three less than 90° angles.

Write a program that given three edge sizes determines:

• whether a triangle is scalene, isosceles or equilateral; and
• whether a triangle is right, obtuse or acute; or
• if the triangle is impossible.

Input consists of a several lines, each with three natural numbers x, y and z where

0 < x, y, z < 10 000

For each line of input, output should contain a line indicating both classifications or impossible.

3 4 5
3 3 1
6 4 3
1 1 1
7 2 3

scalene right
isosceles acute
scalene obtuse
equilateral acute
impossible

◻

Case conditions

When we want to make a decision based on the value of a variable we can use case conditions. Here is a pseudocode illustrating case conditions:

...
case x
    <A>:
        <action A>
    <B>:
        <action B>
    <C>:
        <action C>
    default:
        <default action>
...

If the value of variable x is “A”, action A is executed. If the value of variable x is “B”, action B is executed. If the value of variable x is “C”, action C is executed. Otherwise, the default action is executed. The regular program flow is continued afterwards. ◻

Here is an example, doing a different operation depending on the operator character provided on the input:

read number x, character o and number y
case o
    '+':
        r <- x + y
    '-':
        r <- x - y
    '*':
        r <- x * y
write "The result is:" r

Read a number x, a character c and a number y; let r become the result of an arithmetic operation depending on character c; write the resulting value of r.

x, o, y = input().split()
x = int(x)
y = int(y)
if o == "+":
    r = x + y
elif o == "-":
    r = x - y
elif o == "*":
    r = x * y
print(r)

switch (<variable>) {
case <A>:
    <command A>;
    break;
case <B>:
    <command B>;
    break;
case <C>:
    <command C>;
    break;
default:
    <default command>;
    break;
}

#include <stdio.h>
int main()
{
    int x, y, r;
    char c;
    scanf(" %d %c %d",&x,&c,&y);
    switch (c) {
    case '+':
        r = x+y;
        break;
    case '*':
        r = x*y;
        break;
    case '-':
        r = x-y;
        break;
    }
    printf("%d\n",r);
    return 0;
}

case <expr> of
<A> -> <result A>
<B> -> <result B>
<C> -> <result C>
_   -> <default result>

main :: IO ()
main = do
  line <- getLine
  let [x',o',y'] = words line
  let x = read x'
  let y = read y'
  let o = head o'
  case o of
    '+' -> print (x + y)
    '*' -> print (x * y)
    '-' -> print (x - y)
    _   -> print "error: unknown operator"

Programming Exercise (calc)

Write a program that is able to perform 5 operations: addition +, subtraction -, multiplication *, division / or exponentiation ^.

Input consists of several lines, each with a number x, a character o and another number y separated by spaces where

-2 000 000.00 ≤ x, y ≤ 2 000 000.00

o is +, -, *, / or ^

Output should contain a single line with the corresponding result of applying operator o to x and y. Output should be rounded to two decimal places.

Inputs are given so that the resulting value r is within the following range:

-2 000 000.00 ≤ r ≤ 2 000 000.00

1 + 2
3.5 * 6
7 - 12
20 / 3
-10 ^ 3

3.00
21.00
-5.00
6.67
-1000.00

◻

4.7. Repetition

In this section, we will review two repetition methods introduced in the last chapter: recursion and while loops. Then we will introduce for loops.

Recursion

Recursion is the act of referring back to itself. Recalling from previous chapter, a recursive definition is one that is defined in terms of itself. In turn, a recursive function is one that calls itself, i.e.: uses recursion. ◻

Example: the Sierpiński triangle. The Sierpiński triangle can be constructed by starting with a large triangle and inscribing smaller triangles in the above pattern repeatedly. The resulting image is recursive, you see the full image in parts of the image. Above, you can see it constructed up to six levels. ◻

Example: integer exponentiation. Exponentiation of integers can be defined recursively like so:

• b⁰ = 1
• bⁿ = b × bⁿ⁻¹

The value of b to the power of zero is one and the value of b to the power of n is b times b to the power of n-1.

The following function in pseudo-code performs integer exponentiation recursively:

function power(integer b, integer n)
    if n is equal to 0
        return 1
    else
        return b * power(b, n-1)

At each recursive step, the exponent is decremented by one and we multiply by the base once. ◻

While loops

In the previous section, we saw how to perform repetitions through recursion. In the previous chapter, we saw how to perform repetitions with a while loop which looks like the following in pseudo code:

while <condition>
    <commands>

While the <condition> is true, the computer will perform the given <commands>.

We will now review some other repetition methods. Please jump to the box describing the language of your choice. ◻

while <condition>:
    <commands>

while (<condition>) {
    <commands>;
}

For loops

An alternative to while loops are for loops which are used to perform a certain number of repeated actions. ◻

for <name> in <sequence>:
    <commands>

for i in range(4):
    print(i)

for (<init>; <condition>; <step>) {
    <commands>;
}

<init>;
while (<condition>) {
    <commands>;
    <step>;
}

for (i=0; i<4; i++)
    printf("%i\n",i);

The following exercises can be solved through any of the three repetition methods discussed in this section. You can try to solve each of them three times, each time using a different repetition method.

Programming Exercise (factorial)

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

n! = n × (n-1) × (n-2) × … × 2 × 1 × 0

Or, recursively:

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

Input will contain several lines with a single integer n where 0 ≤ n ≤ 12. Output should contain a line with the factorial of n.

4
6

24
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 (power)

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

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

for example

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

Input will contain several lines each with two integers b and n where

-1000 ≤ b ≤ 1000

0 ≤ n ≤ 30

For each line of input, output should contain a corresponding line with a single integer indicating the value of bⁿ.

Input will be given so that

-1 000 000 000 < bⁿ < 1 000 000 000

2 5
5 2

32
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. ◻

Programming Exercise (fibonacci)

Write a program that computes numbers 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 several lines, each with a single integer n indicating the position in the Fibonacci sequence.

For each line of input, output should contain a line with a corresponding number Fₙ indicating the Fibonacci number in position n.

3
8
6

2
21
8

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):

Your function is expected to have good performance. ◻

4.8. Sequences

So far, our programs involved mostly standalone variables, e.g.: an integer x, another integer i and a float f. We will now learn to deal with collections of values.

A list, array or sequence is a collection of values where the order does matter. For example, we may want to store a list of employees of a company or a queue of documents for processing. For this we use a list or array. ◻

Strings are sequences

We have already interacted with a sequences before. A string is a sequence of characters.

On sequences, we can perform indexing, that is, referring the element at a given position in a list. So, for example, in the string Hello we have character H at position 0; character e at position 1; character l at position 2; character l at position 3; character o at position 4. This string has the length of 5. ◻

$ python
>>> str = 'Hello'
>>> str[0]
'H'
>>> str[1]
'e'
>>> str[4]
'o'

char str[6] = "Hello";
printf("%c\n",str[0]);
printf("%c\n",str[1]);
printf("%c\n",str[4]);

$ ghci
> str !! 0
'H'
> str !! 1
'e'
> str !! 4
'o'

Programming Exercise (index-string)

Write a program that prints the character at position n of a given string.

Each line of input consists of a string s followed by a number n separated by a single space. For each line of input, there should be a line of output containing the character in position n of the corresponding string s.

Each given string has at most 60 characters.

Positions are indexed from 0. If the number given on the input is 0, you should print the first character; if the number given on the input is 1, you should print the second character; if the number given on the input is 2, you should print the third character; etc.

abcdef 0
xyz 2
Hello 1
World 4

a
z
e
d

◻

Sequences of integers

We can also have sequences of other types, for example, sequences of integers. Sequences of integers can be indexed in the same way we index strings.

<name> = [<element_0>, <element_1>, ..., <element_n>]

list = [11, 12, 13, 14]

print(list[0])

print(list[3])

int <name>[<n_elements>];

int <name>[<n_elements>] = {<element_0>, <element_1>, ..., <element_n>};

int array[4] = {11, 12, 13, 14};

printf("%i\n", array[0]);

printf("%i\n", array[3]);

char str[6] = "Hello";
printf("%c\n",str[0]);
printf("%c\n",str[1]);
printf("%c\n",str[4]);

[<element_0>, <element_1>, ..., <element_n>]

<element_0>:<element_1>:...:[]

[11,12,13,14]

11:12:13:14:[]

> [11,12,13,14] !! 0
11
> [11,12,13,14] !! 3
14

> head [11,12,13,14]
11
> tail [11,12,13,14]
[12,13,14]

Iterating

A common operation in lists is iterating through them, that is, going element by element and perform an operation.

for <element> in <list>:
    <commands>

for i in [11,12,13,14]
    print(i)

int array[4] = {11,12,13,14};
int i=0;
while (i<4) {
    printf("%i\n", array[i]);
    i = i + 1;
}

for (i=0; i<4; i++)
    printf("%i\n", array[i]);

map <function> <list>

$ ghci
> map show [0,1,2,3]
["0", "1", "2", "3"]

traverse <action> <list>

traverse print [0,1,2,3]

Reading lists of values

This section explains how to read lists of values.

$ python
>>> str.split('10 apples 20 bananas')
['10', 'apples', '20', 'bananas']

>>> '10 apples 20 bananas'.split()
['10', 'apples', '20', 'bananas']

>>> list = '10 apples 20 bananas'.split()
>>> list[0]
'10'
>>> list[1]
'apples'
>>> int(list[2])
20

>>> first, second, *rest, last = '10 a 20 b 30 c'.split()
>>> first
'10'
>>> second
'a'
>>> last
'c'
>>> rest
['20', 'b', '30']

int i;
int array[100];
for (i=0; i<6; i++)
    scanf("%d", &array[i]);

$ ghci
> words "10 apples 20 bananas"
["10","apples","20","bananas"]

> unwords ["10","apples","20","bananas"]
"10 apples 20 bananas"

> let string = "10 apples 20 bananas"
> let list = words string
> head list
"10"
> tail list
["apples","20","bananas"]
> init list
["10","apples","20"]
> last list
"bananas"

$ ghci
> let (first:second:etc) = list
> first
"10"
> second
"apples"
> etc
"20 bananas"

Programming Exercise (repeat-list)

Write a program that reads lists of integers from standard input and replicates the same integers on standard output.

Each line of input begins with a number L, indicating the number of integers to be repeated, followed by L numbers all separated by a single space.

For each line of input there should be a line of output with the number of integers followed by elements: followed by the numbers given in the input. Output values should not contain leading zeroes and should be separated by a single space.

Each list has at least one element and at most a hundred elements, i.e., 1 ≤ L ≤ 100.

4 1 2 3 4
2 32 16
3 12 360 60

4 elements: 1 2 3 4
2 elements: 32 16
3 elements: 12 360 60

◻

Now, let’s try to solve this exercise together. Again, avoid copy-pasting and take time to type everything.

import sys

for line in sys.stdin:
    length, *elements = line.split()
    length = int(length)
    print(length, "elements:", end='')
    for element in elements:
        element = int(element)
        print('', element, end='')
    print()

#include <stdio.h>
int main()
{
    int array[100];
    int lenght;
    int i;
    while (scanf("%d",&len)==1) {
        for (i=0; i<length; i++)
            scanf("%d",&array[i]);
        printf("%d elements:", len);
        for (i=0; i<len; i++)
            printf(" %d",array[i]);
        printf("\n");
    }
    return 0;
}

io1 :: String -> String
io1 s  =  show len ++ " elements: " ++ unwords (map show elements)
  where
  len:elements = map read (words s) :: [Int]

io :: String -> String
io input  =  unlines (map io1 (lines input))

main :: IO ()
main  =  interact io

Programming Exercise (index-ints)

Write a program that prints the character at position n of a given list.

Each line of input consists of a number n, followed by n numbers, followed by number i.

For each line of input there should be a line of output with a single integer aᵢ indicating the number at position i of the input list.

5 1 2 3 4 5 2
4 16 8 4 2 3
3 360 60 1080 0

3
2
360

◻

Programming Exercise (replace)

Write a program that replaces the character in a given position in a string.

Each line of input will consist of a string s, a natural number i and a character c.

For each line of input, there should be a line of output with a modified version of string s where the character at position i is replaced by character c.

String s is alphanumeric and is of up to 60 characters. This string is indexed from zero.

0 < |s| ≤ 60

0 ≤ i < |s|

Hallo 1 e
Bach 3 k
bitter 1 u

Hello
Back
butter

◻

4.11. Chapter remarks

In this chapter, we have reviewed what are data-types, what are variables, how to do input and output, how to write functions, how to use operators, how to write conditions, how to perform repetition and how to use sequences. ◻

4.12. Exercises

The exercises throughout this chapter were:

• repeat
• hi
• age
• swap
• owes
• triple
• inc
• add
• mult
• pi
• box
• oddeven
• order
• good
• bmi
• triangle
• calc
• factorial
• power
• fibonacci
• index-string
• repeat-list
• index-ints
• replace

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. ◻

<< 3. Programming Basics   |   4. Programming   |   5. Mathematical Foundations >>

index | submit | rank | book

Copyright © 2020-2023 Rudy Matela
All rights reserved