原始计算器-动态方法 [英] Primitive Calculator - Dynamic Approach

问题描述

对于以下问题，我很难找到正确的解决方案:

您的目标被给定一个正整数n，找到从数字1开始获得数字n所需的操作.

更具体地说，我在下面的评论中提供了该测试用例.

 #失败的案例#3/16 :(错误的答案)#得到:15预期:14# 输入:#96234##您的输出:#15#1 2 4 5 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234#正确的输出:#14#1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234#(使用时间:0.10/5.50，使用的内存:8601600/134217728.)def best_sequence(n):顺序= []而n> == 1时:sequence.append(n)如果n％3 == 0:n = n//3optimum_sequence(n)elif n％2 == 0:n = n//2optimum_sequence(n)别的:n = n-1optimum_sequence(n)返回颠倒(顺序)输入= sys.stdin.read()n = int(输入)序列=列表(optimal_sequence(n))列印(len(sequence)-1)对于x依次:打印(x，end ='') 

看起来我应该输出9，而我要输出4&5但我不确定为什么不是这种情况.解决此问题的最佳方法是什么?

解决方案

您正在做一个贪婪的方法.当n == 10时，假设这是最好的步骤，则检查并查看是否可以被2整除，在这种情况下是错误的.

您需要做的是正确的动态编程. v [x] 将保留获得结果 x 的最少步骤.

  defsolve(n):v = [0] *(n + 1)#使得v [n]在那里v [1] = 1#序列到1的长度为1对于范围(1，n)中的i:如果不是v [i]:继续如果v [i + 1] == 0或v [i + 1]>v [i] + 1:v [i + 1] = v [i] + 1#对于i * 2和i * 3类似解决方案= []当n>1:solution.append(n)如果v [n-1] == v [n]-1:n = n-1如果n％2 == 0且v [n//2] == v [n] -1:n = n//2#同样适用于n//3solution.append(1)返回反向(解) 

I'm having some trouble getting the correct solution for the following problem:

Your goal is given a positive integer n, find the minimum number of operations needed to obtain the number n starting from the number 1.

More specifically the test case I have in the comments below.

 # Failed case #3/16: (Wrong answer)
    # got: 15 expected: 14
    # Input:
    # 96234
    #
    # Your output:
    # 15
    # 1 2 4 5 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
    # Correct output:
    # 14
    # 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
    #  (Time used: 0.10/5.50, memory used: 8601600/134217728.)


    def optimal_sequence(n):
        sequence = []

        while n >= 1:
            sequence.append(n)

            if n % 3 == 0:
                n = n // 3
                optimal_sequence(n)

            elif n % 2 == 0:
               n = n // 2
               optimal_sequence(n)

            else:
               n = n - 1
               optimal_sequence(n)

        return reversed(sequence)

    input = sys.stdin.read()
    n = int(input)
    sequence = list(optimal_sequence(n))
    print(len(sequence) - 1)
    for x in sequence:
        print(x, end=' ')

It looks like I should be outputting 9 where I'm outputting 4 & 5 but I'm not sure why this isn't the case. What's the best way to troubleshoot this problem?

解决方案

You are doing a greedy approach. When n == 10, you check and see if it's divisible by 2 assuming that's the best step, which is wrong in this case.

What you need to do is proper dynamic programming. v[x] will hold the minimum number of steps to get to result x.

def solve(n):
  v = [0]*(n+1)  # so that v[n] is there
  v[1] = 1  # length of the sequence to 1 is 1
  for i in range(1,n):
    if not v[i]: continue
    if v[i+1] == 0 or v[i+1] > v[i] + 1: v[i+1] = v[i] + 1
    # Similar for i*2 and i*3
  
  solution = []
  while n > 1:
    solution.append(n)
    if v[n-1] == v[n] - 1: n = n-1
    if n%2 == 0 and v[n//2] == v[n] -1: n = n//2
    # Likewise for n//3
  solution.append(1)
  return reverse(solution)

这篇关于原始计算器-动态方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！