3的功率分解功率

Question

因此，我试图编写一个程序，它使用3的幂产生整数的分解，即: 1，3，9，27和81。只能在每次计算中使用数字一次。

示例：

1=1

2=3-1

3=3

4=3+1

5=9-3-1

我如何解决这个问题，同时也考虑到负数？它适用于大多数数字，但不适用于5，例如，它包括3次两次。

add = True;
ans = ""
nums = [1, 3, 9, 27, 81] #list of powers of 3

check = result
while(check): #loop through the value if it exsists
    distance = abs(check - 1)
    close = 1
    for i in nums:
        temp_distance = abs(check-i)
        if (distance and (distance >= temp_distance)): #check if the distance is greater than the temp distance and not a perfect match
            distance = temp_distance
            close = i
        else: #if its a perfect match then no calculation needed
            break
    if close > check: 
        add = not add
    check = distance
    if check:
        ans += str(close)
        if add:
            ans += ' + '
        else:
            ans += ' - '
    else:
        ans += str(close) 

Answer 1

一种方法是将数字转换为三元基系统。例如：

32(10 = 1012(3 = 27 + 3 + 2*1

在这里，(b表示数字位于基b中。根据您的算法，数字应该只使用一次，所以您必须这样做：

1)创建一个函数，将整数转换为三次方的列表。

def powerthree(input):
  if input<0: return powerthree(abs(input))
  powthree = []
  while input > 0:
    powerthree.append(input % 3)
    input /= 3
  powethree.reverse() #Reverse to show factors decreasing to 1
  return powethree

2)在列表开头添加一个虚拟0：

pw3 = [0] + powerthree(input)

3)从右向左扫描列表。如果元素为2，则设置为-1，并将1添加到列表的前一个元素，直到位置1。

def accomodate(pw3list):
  for i in xrange(-1, -len(pw3list), -1): #Run from right to left, rememember that Python allows negative indices!
    if pw3list[i] == 2:
      pw3list[i] = -1
      pw3list[i-1]+=1
  return pw3list

4)可容纳列表中的值指示您是应该添加、减还是跳过三的幂。写下结果：

def printresult(orignumber, pw3list):
  print "%d = " % orignumber,
  for i in xrange(len(pw3list)):
    pow3 = 3 ** (len(pw3list) - i - 1)
    print "%d" % (pow3 * pw3list[i])

应该使用32示例打印的

32 = 27 + 9 - 3 - 1

希望我帮过你！正如我通常说的，英语不是我的母语，所以在我的帖子中可能会犯错误。更正永远是受欢迎的。