Lemmy - 1 year ago 47

Python Question

I would like to ask you how can I get a list of operations I have to do to obtain the result.

The simple example:

There is a number N. Your goal is to find out the minimum operations (x/3, x/2, x-1) you have to do to get 1.

So for example minop(10) = 3 (because **1.** 10-1=9, **2.** 9/3=3, **3.** 3/3=1).

This function is very simple with bottom-up approach in Python:

`# the opt is an optimum nuber of operations for index to get to one`

# the op list should be a list of operations but it does not work

# correctly. For minop(10) would return opt = 3 (three

#operations), op = [1,3,3] (minus one, divide three, divide three)

opt = [0,0,0,0,0,0,0,0,0,0,0,0] # optimum number of operation for i

op = []

def minop(n):

opt[1]=0

for i in range(2,n+1):

opt[i]=opt[i-1]+1

op.append(1) # INCORRECT

if i%2==0:

opt[i] = min(1+opt[i/2],opt[i])

op[-1]=2 # INCORRECT

if i%3==0:

opt[i] = min(1+opt[i/3],opt[i])

op[-1]=3 # INCORRECT

return opt[n],op

As you can see, the op list should contain minimum list of operations (represented by numbers) needed to get from

`n`

`1`

Answer

The most important error in your code is that you update `opt[i]`

in both `if`

blocks even if the operation does not yield a better result.

Here is a corrected version of your code:

```
def minop(n):
op = [[], []]
for i in range(2,n+1):
ref = i-1
best = 1
if i%2==0 and len(op[i/2]) < len(op[ref]):
ref = i/2
best = 2
if i%3==0 and len(op[i/3]) < len(op[ref]):
ref = i/3
best = 3
op.append([best] + op[ref][:]) # slice to get separate copy
return len(op[n]), op[n]
print minop(10)
```

It outputs:

```
(3, [1, 3, 3])
```

Meaning: 3 operations, which are `-1`

, `/3`

, `/3`

.

See it run on eval.in

Source (Stackoverflow)