代做Programming、代写Java程序设计、代写data留学生、Python，c++代做

日期：2020-10-10 11:09

Lab session 5: Imperative Programming

This is the 5th lab of a series of weekly programming labs. You are required to solve these

programming exercises and submit your solutions to the automatic assessment system Themis.

The system is 24/7 online. Note that the weekly deadlines are very strict (they are given for the

CET time zone)! If you are a few seconds late, Themis will not accept your submission (which

means you failed the exercise). Therefore, you are strongly advised to start working on the

weekly labs as soon as they appear. Do not postpone making the labs! You can find Themis via

the url https://themis.housing.rug.nl

The theme of this lab is recursion. Each problem must be solved using recursion! The

teaching assistants will (after the deadline) manually check the submissions that are accepted

by Themis. If a passed program does not make use of recursion, then the scored

points are subtracted by the teaching assistants.

Problem 1: Quadratic Sums

The number 142 can be written as a sum of squares of positive integers in 7 different ways:

142 = 12 + 22 + 42 + 112

= 12 + 42 + 52 + 62 + 82

= 12 + 42 + 52 + 102

= 22 + 32 + 42 + 72 + 82

= 22 + 52 + 72 + 82

= 32 + 42 + 62 + 92

= 52 + 62 + 92

In these sums, a square is used at most once (i.e. a sum containing a sub expression of the form

a

2 + a

2

is not allowed). Moreover, the order of the terms is irrelevant (so 2

2 + 52

and 5

2 + 22

are

considered to be the same expression).

Write a program that accepts on its input an integer n (where 1 ≤ n ≤ 1600), and outputs in

how many different ways n can be expressed as a sum of squares of positive integers.

Problem 2: Zipping Strings

The input of this exercise consists of a non-negative integer n, and three strings consisting of

uppercase letters from the alphabet (without spaces, tabs, etc.). The objective is to determine

whether the third string can be produced from the first two strings by zipping the first two strings

in such a way that the order of the letters of both strings is preserved. Moreover, it is allowed to

insert at most n auxiliary letters. The output of your program should be YES if this is possible,

and NO otherwise. You may assume that each string consists of at most 32 letters.

For example, if we are allowed to insert one auxiliary letter, then we can produce the string

PROGRAMMING from the strings PROM and GAMING as follows:

The array a is given and consists of positive integers that satisfy 1 ≤ a[i] ≤ 20 for all i.

Moreover, the given b satsifies 1 ≤ b ≤ 100. We want to know the number of solutions of the

above equation, where all x[i] are non-negative integers.

For example, the equation 5 · x[0] + 7 · x[1] + 9 · x[2] + 11 · x[3] = 42 has 9 unique solutions:

The input of this problem is a single line that starts with an integer n (the number of coeffi-

cients) folowed by a colon (:). You may assume that 1 ≤ n ≤ 10. Next, there are n coefficients

a[i]. The input is terminated with the value b (the right hand side of the equation). The output

of your program must be the number of solutions of the given equation.

Problem 4: Grid Colouring Puzzle

In this problem we consider a colouring puzzle for a 9 × 9 grid of cells. Cells must be coloured

with one of the colours RED, GREEN, BLUE, YELLOW, or WHITE. Given a grid in which

some cells have been coloured already, the puzzle is to colour the remaining cells such that no

cell has a neighbour (north, east, south, west) with the same colour. Moreover, in each row or

column no colour may appear more than twice.

The input for this problem is a grid of 9 × 9 characters. We use the letters ’R’, ’G’, ’B’,

’Y’, and ’W’ to denote coloured cells, and ’#’ to denote empty (non-coloured) cells. The

output of your program must be the solution of the puzzle, or ’NO SOLUTION’ if no solution

exists. You may assume that a puzzle has at most one solution.