首页 > 试题广场 >

扭蛋机

[编程题]扭蛋机
  • 热度指数：11915 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
22娘和33娘接到了小电视君的扭蛋任务：
一共有两台扭蛋机，编号分别为扭蛋机2号和扭蛋机3号，22娘使用扭蛋机2号，33娘使用扭蛋机3号。
扭蛋机都不需要投币，但有一项特殊能力：
扭蛋机2号：如果塞x（x范围为>=0整数）个扭蛋进去，然后就可以扭到2x+1个
扭蛋机3号：如果塞x（x范围为>=0整数）个扭蛋进去，然后就可以扭到2x+2个
22娘和33娘手中没有扭蛋，需要你帮她们设计一个方案，两人“轮流扭”（谁先开始不限，扭到的蛋可以交给对方使用），用“最少”的次数，使她们能够最后恰好扭到N个交给小电视君。

输入描述:
输入一个正整数，表示小电视君需要的N个扭蛋。


输出描述:
输出一个字符串，每个字符表示扭蛋机，字符只能包含"2"和"3"。
示例1

输入

10

输出

233

备注:
1<=N<=1e9
算法知识视频讲解
添加回答
Python
隣の風头像 隣の風

这样也可以通过，贪心体现出用最少的次数？哪里体现必须交替扭蛋？ 

def solve(n):
    if n <= 0:
        return ''
    if n % 2 == 0:
        return solve(n//2-1) + '3'
    return solve(n//2) + '2'

def solve_v2(n):
    ans = ''
    while n > 0:
        if n % 2 == 0:
            ans = '3' + ans
            n = n // 2 - 1
        else:
            ans = '2' + ans
            n = n // 2
    return ans


编辑于 2020-09-03 23:21:17 回复(0)
Python
0b100001101000头像 0b100001101000 
n = int(input())
o = []
while n:
    o.append('3' if n%2 == 0 else '2')
    n = (n-1)//2
print(''.join(o[::-1]))

发表于 2019-09-09 15:52:50 回复(1)
Python
雷凌云头像 雷凌云
这道题可以简化成走方格
初始位置是x=0，然后每步有两种选择
1、第一种选择是走到编号为 2*x+1 的方格，代号为 ‘2’
2、第一种选择是走到编号为 2*x+2 的方格，代号为 ‘3’
求一种可以正好走到 编号为 n 的方式 
# 逆推法：根据最后一步的奇偶，判断前一步的选择
n = int(input())
res = ''
while n > 0:
    if (n-2) % 2:
        n = (n-1) // 2
        res = '2' + res
    else:
        n = (n-2) // 2
        res = '3' + res
print(res)



发表于 2019-08-22 16:01:14 回复(0)
Python
大佬求带。。头像 大佬求带。。 
def helper(num):
    res = ""
    while num>0:
        if ((num-2)/2)%1==0:
            res = '3'+res
            num = (num-2)/2
        if ((num-1)/2)%1==0:
            res =  '2'+res
            num = (num-1)/2
    return res
if __name__ == "__main__":
    obj = int(input())
    ans = helper(obj)
    print(ans)

发表于 2019-05-07 13:37:44 回复(3)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 哔哩哔哩 测试工程师 PHP工程师 递归 2019 数学 Java工程师
来自：哔哩哔哩 2019秋招...
上传者：小小
难度：
5条回答 12478浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号