Scribd
Upload
21 views

Algorithms WS1

The document contains a worksheet focused on computational thinking and algorithms, presenting three tasks. Task 1 includes problems related to identifying a celebrity among people, finding a fake coin among identical coins, and a river crossing puzzle involving soldiers and a boat. Task 2 describes the dice game 'Beetle,' outlining its rules and suggesting how to decompose the game into modules for programming.

Uploaded by

wow what
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
21 views

Algorithms WS1

The document contains a worksheet focused on computational thinking and algorithms, presenting three tasks. Task 1 includes problems related to identifying a celebrity among people, finding a fake coin among identical coins, and a river crossing puzzle involving soldiers and a boat. Task 2 describes the dice game 'Beetle,' outlining its rules and suggesting how to decompose the game into modules for programming.

Uploaded by

wow what
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Worksheet 1 Computational thinking

Unit 5 Algorithms

Worksheet 1 Computational thinking

Task 1
1. Solve this problem:
A celebrity among a group of n people is a person who knows nobody but is known to
everybody else.
How can you identify the celebrity by only asking people the following question:
“Do you know this person?”
Write out your algorithm.

If n=1,

that one person is inanely a celebrity by a definition.

If n>2,

than choose 2 people from "n" group "A" and "b" and ask whether "A" is knows "B", remove "A"

from remaining people from who can be celebrity.

If "A" dose not know's "B", than remove "B".

Than solving the problem from the same recursively method from the same "n" group until the

"n-1" group of people who can be the celebrity.

2. You have a pile of 8 identical coins, and you know one of them is a fake and is lighter than
the genuine coins. What is the minimum number of weighings needed to identify the fake
coin with a two-pan balance scale without weights?
Write out your algorithm.

You need to find out the weight of the genuine coins which needs takes 2 weigh-ins to find out

and then you need to find the coin with less weigh which will at minimum will take 1 try so a total

of 3 weigh ins.

1
Worksheet 1 Computational thinking
Unit 5 Algorithms
3. A Decrease and Conquer problem
A group of 25 soldiers must cross a wide and deep river. There are two boys playing in a
rowboat by the shore. The boat is tiny, however, that it can only hold two boys or one
soldier. How can the soldiers get across the river and leave the boys in joint possession of
the boat? How many times does the boat pass from shore to shore in your algorithm?

15 times

2
Worksheet 1 Computational thinking
Unit 5 Algorithms

Task 2
3 “Beetle” is a dice game for 2 or more players, played with a single six-sided die.
The objective is to be the first to draw all parts of a beetle. At each turn, a player rolls the
die to decide which part can be drawn.
The body has to be drawn first, by throwing a 6. Head, legs and tail can then be drawn
when the correct value is shown on the die.
Eyes and antennae cannot be drawn until the head is drawn.
The first person to draw all the body parts is the winner.

Throw Part Count


Six Body 1
Five Head 1
Four Tail 1
Three Leg 4
Two Antenna 2
One Eye 2

Imagine that you are going to write a program to allow a player to play Beetle against the
computer.
Decompose this game into component parts or modules.

Each player rolls the dice once. The player with the highest roll is the starting player. Ties for
the highest score are rerolled until one player has the highest score.

Players take it in turn to roll the dice starting with the starting player and proceeding clockwise
round the table.

Each body part can be drawn when a particular number has been rolled and if any parts
required for the part rolled have already been rolled.

On a roll of 6 the beetle’s body can be drawn.

On a roll of 5 the beetle’s head can be drawn if the body has already been drawn.

On a roll of 4 the beetle’s eyes can be drawn if the head has already been drawn.

On a roll of 3 the beetle’s Feelers can be drawn if the head has already been drawn.

On a roll of 2 the beetle’s tail can be drawn if the beetle’s body has already been drawn.

On a roll of 1 the beetle’s legs can be drawn if the body has already been drawn.

3
Worksheet 1 Computational thinking
Unit 5 Algorithms
Which modules, if any, could be reused if you are asked to write a program for a different
dice game?

The things you can draw when you roll a certain number on a dice.

4
Worksheet 1 Computational thinking
Unit 5 Algorithms

You might also like