鱼C论坛

 找回密码
 立即注册
查看: 4541|回复: 26

[技术交流] Python:每日一题97(答题领鱼币)

[复制链接]
发表于 2017-9-9 16:32:38 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 冬雪雪冬 于 2017-9-9 18:45 编辑

我们在92题中说到“1,2,4,8,16,32,64和128这8个数字利用加法可以得到1~255中的任意数字”
现在把题目变换一下,用1, 3, 9, 27等3的幂,利用加法和减法组成任意的整数,3的幂可以使用其中任意一个或几个,但每个数字只能使用一次,例如:
  1. >>> fun(40)
  2. 40 = 27 + 9 + 3 + 1
  3. >>> fun(41)
  4. 41 = 81 - 27 - 9 - 3 - 1
  5. >>> fun(12345)
  6. 12345 = 19683 + 27 + 9 - 6561 - 729 - 81 - 3
复制代码


现在我们就一起编写这个函数吧,要求参数为一个正整数,函数最后打印出结果或return返回结果。

其实负数也可以做,为了简单点,就取1~n的正整数了。

我的解法:

游客,如果您要查看本帖隐藏内容请回复

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-9-9 18:41:52 From FishC Mobile | 显示全部楼层
1=1
2=3-1
3=3
4=3+1
5=9-4=9-(3+1)
6=9-3
7=9-2=9-(3-1)
8=9-1
9=9
10=9+1
11=9+2=9+(3-1)
12=9+3
13=9+4=9+(3+1)
14=27-13=27-(9+3+1)
其实可以利用动态规划解的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-9-9 19:55:45 | 显示全部楼层
       感觉很像二进制,百度下存在一种对称三进制:将 -1,0,1作为基。如楼上说的十进制14转化成对称三进制则为:1TTT(我们将-1用T代替)即:3^3-3^2-3^1-3^0=27-9-3-1.如果用纯粹的三进制则会出现2:
       对称三进制: 14除3补1  5除3补1 2除3补1 1除3余1             即得到1TTT
       普通三进制: 14除3余2  4除3余1 1除3余1             即得到112=9+3+2
       综上可以使用对称三进制思路写任意数余2补1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2017-9-9 20:36:41 From FishC Mobile | 显示全部楼层
楼上的112=9+3+2是怎么解的?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-9-10 08:05:49 From FishC Mobile | 显示全部楼层
本帖最后由 jerryxjr1220 于 2017-9-10 08:25 编辑
jerryxjr1220 发表于 2017-9-9 18:41
1=1
2=3-1
3=3


写个递归算法。

  1. def calc(n):
  2.   i = 0
  3.   while n>3**i:
  4.     i+=1
  5.   else:
  6.     if n==3**i:
  7.       return str(n)
  8.     else:
  9.       if n>(3**i)/2.0:
  10.         return str(3**i)+'-'+calc(3**i-n).replace('-','*').replace('+','-').replace('*','+')
  11.       else:
  12.         return str(3**(i-1))+'+'+calc(n-3**(i-1))

  13. print(calc(12345))
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
冬雪雪冬 + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-9-10 08:26:36 | 显示全部楼层
1、换成另类三进制表示,,逢2进1自己变-1,算权重;2、字符串操作,接上符号输出
  1. def fun(n):
  2.     num = []
  3.     while n:
  4.         n, m = divmod(n, 3)
  5.         if m == 2:
  6.             n += 1
  7.             m = -1
  8.         num.append(m)

  9.     result = "+".join(str(3**i*num[i]) for i in range(len(num)) if num[i])
  10.     return result.replace("+-", "-")
复制代码

评分

参与人数 1荣誉 +4 鱼币 +4 收起 理由
冬雪雪冬 + 4 + 4

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 1 反对 0

使用道具 举报

发表于 2017-9-10 11:06:58 | 显示全部楼层
左手十字 发表于 2017-9-9 20:36
楼上的112=9+3+2是怎么解的?

普通三进制就是看余数,然后反过来就是这个数了。
在举个栗子:
15/3商 5 余 0   
5/3  商 1 余 2 (到这一步就可以了,只要商为0,1,2就可以直接出来了)
1/3  商 0 余 1
反过来 1 2 0  等于15
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-9-10 15:41:42 | 显示全部楼层
路过学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-9-11 19:20:41 | 显示全部楼层

def calc(n):
  i = 0
  while n>3**i:
    i+=1
  else:
    if n==3**i:
      return str(n)
    else:
      if n>(3**i)/2.0:
        return str(3**i)+'-'+calc(3**i-n).replace('-','*').replace('+','-').replace('*','+')
      else:
        return str(3**(i-1))+'+'+calc(n-3**(i-1))

print(calc(12345))

评分

参与人数 1荣誉 +2 鱼币 +2 收起 理由
冬雪雪冬 + 2 + 2

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-9-13 22:15:40 | 显示全部楼层
只好来看看答案了。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-9-14 21:44:25 | 显示全部楼层
偷偷看一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-1 22:32:35 | 显示全部楼层
#Magic Power of Three

def Index_three(n):
    if n<=0:
        return False
    i = 0
    while True:
        if pow(3,i)<=n<pow(3,i+1):
            return i,i+1
        i += 1

#print(Index_three(0))

def add_sub(n):
    if n<=0:
        return "请输入大于0的数!!!"
    elif n==1:
        return "1"
    elif n>1:
        index_n = Index_three(n)
        if n == pow(3,index_n[0]):
            return "{}".format(n)
        else:
            if n<=(pow(3,index_n[1])//2):
                return "{0} + {1}".format(pow(3,index_n[0]),add_sub(n-pow(3,index_n[0])))
            else:
                add_sub_str = add_sub(pow(3,index_n[1])-n)
                if len(add_sub_str)>1:
                    #print(add_sub_str[2])
                    for i in range(len(add_sub_str)):
                        if add_sub_str[i] == '+':
                            add_sub_str = add_sub_str[:i] + '-' + add_sub_str[i+1:]
                        elif add_sub_str[i] == '-':
                            add_sub_str = add_sub_str[:i] + '+' + add_sub_str[i+1:]
                return "{0} - {1}".format(pow(3,index_n[1]),add_sub_str)

#print(add_sub(3))

def main():
    for i in range(12345,12346):
        add_sub_str = "{0} = {1} ".format(i,add_sub(i))
        print(add_sub_str)
    return

if __name__ == "__main__":
    main()
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-3-2 05:56:40 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-3-2 05:57:29 | 显示全部楼层
{:
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-4-25 08:53:28 | 显示全部楼层
一条小鱼儿 发表于 2017-9-9 19:55
感觉很像二进制,百度下存在一种对称三进制:将 -1,0,1作为基。如楼上说的十进制14转化成对称三进 ...

这个思路强
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-4-25 09:39:51 | 显示全部楼层
import math
def fun(n):
    new = []
    while True:
        if n%3 == 2:
            new.append(-1)
            n = (n+2)
        elif n%3 == 1:
            new.append(1)
            if n == 1:
                break     
        else:
            new.append(0)
        n = n//3
    new.reverse()
    new1 = []
    j = len(new)-1
    for i in range(len(new)):
        new1.append(new[i] * 3 **j)
        j -= 1
    string = "+".join(map(str, new1)).replace("+-", "-").replace("+0", "")
    #return string
    #string
    #print(new, new1, string)
    #string1 = []
    #for i in range(len(string) - 1, 0, -1):
        #string1.append(string[i])
        #if string[i] == "-" :
           # continue
   # string1.reverse()
    return string
        
fun(12345645464)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-4-25 10:49:12 | 显示全部楼层
回复
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

头像被屏蔽
发表于 2018-8-13 13:17:00 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-8-2 16:34:18 | 显示全部楼层
回复看咪咪
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-5-6 15:02:03 | 显示全部楼层
看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 19:56

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表