# Lab 11 Generating an Element in a Group solution

\$14.99

Original Work ?

## Description

5/5 - (1 vote)

Problem Deﬁnition Consider the group G = (Z≥0,+) where + is the usual integer addition. The set {0,1} is a generating set for G, but you can also consider other generators. Note that 0 must be present in every generating set for G. Therefore, we do not need to explicitly state 0 — we can implicitly understand 0 to be in every generating set. Given a generating set S ⊆Z≥0 and an i ∈Z≥0, we can ask: how eﬃciently can we generate i using the elements in S. For example, let S = {1,5}1 and i = 11. You can generate 11 by the sequence 1 → 2 → 3 → 4 →···→ 10. More eﬃciently, you can generate 11 by 1 → 2 → 4 → 8 → 10 → 11. Optimally (i.e., most eﬃciently) you can generate 11 by 5 → 10 → 11 or 1 → 6 → 11. In general, you can deﬁne the eﬃciency of your generation by the number of times you use the + operator. Thus, the problem is: Given a set S ⊆ Z≥0 and an element i ∈ Z≥0, produce a sequence of elements generated from S such that you reach i most eﬃciently (i.e., fewest number of times you use the + operator). (In this lab exercise, bulk of your grade is for getting your program to work when S = {1}. Therefore, ﬁrst focus on that simple case. This will also help you get an intuition for how to solve the more general case when S can be an arbitrary subset of Z≥0.)
0.1 Command Line Arguments
Your command line argument for this assignment is a single input ﬁle name.
1Recall that 0 is implicitly in S
1
0.2 The Input File Format
Each input ﬁle should solve one instance of the problem. The format is as follows. First you must have an integer n which represents the number of elements of the generating set S. Then, you provide the elements in S one after another. Finally, you provide your value of i. You should allow your input to be in free format. Confer Lab 10 for what I mean by free format. You may assume that i and the largest element in S are never more than 100 and the cardinality of S is at most 10.
0.3 Output
The output should contain the following:
1. A sequence that leads to i.
2. The number of times you needed to use the + operator to reach the value i.
As an example, consider the input:
3 1 7 13 42
Then, the output format is:
13+7=20, 20+1 = 21, 21+21 = 42 Number of times we used the + operator = 3
The output format is not strict, but it should be very easy for the human reader to get the above two pieces of information.