约瑟夫问题，找零钱问题

刺骨的言语ヽ痛彻心扉 2022-04-24 15:52 139阅读 0赞

假设拿着山芋的孩子在队列的前面。当拿到山芋的时候，这个孩子将先出列再入队列，把他放在队列的最后。经过 num 次的出队入队后，前面的孩子将被永久移除队列。并且另一个周期开始，继续此过程，直到只剩下一个名字（队列的大小为 1）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbmpoT0s_size_16_color_FFFFFF_t_70][]

def hotPotato(namelist, num):
        output=[]
        simqueue = []
        for name in namelist:
            simqueue.insert(0,name)
        while len(simqueue) > 1:
            for i in range(num):
                simqueue.insert(0,simqueue.pop())
            output.append(simqueue.pop())
        return simqueue.pop(),output
    print(hotPotato(["a","b","c","d","e","f"],1))#每间隔一个删除

('e', \['b', 'd', 'f', 'c', 'a'\])

一个动态规划算法来解决我们的找零问题。dpMakeChange 有三个参数：一个有效硬币值的列表，我们要求的找零额，以及一个包含每个值所需最小硬币数量的列表。 当函数完成时， minCoins 将包含从 0 到找零值的所有值的解。

def dpMakeChange(coinValueList,change,minCoins):
        for cents in range(change+1):
            coinCount = cents
            for j in [c for c in coinValueList if c <= cents]:
                if minCoins[cents-j] + 1 < coinCount:
                    coinCount = minCoins[cents-j]+1
            minCoins[cents] = coinCount
        return minCoins[change]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbmpoT0s_size_16_color_FFFFFF_t_70]: /images/20220212/27d6ebba72714dcd87198e51f4da2dcf.png

发表评论取消回复

表情：

评论列表（有 0 条评论，139人围观）

还没有评论，来说两句吧...

相关阅读

相关约瑟夫问题

约瑟夫问题作者：Ackarlix 这是一个非常经典的问题：n个骑士编号1，2，...，n，围坐在圆桌旁，编号为k的骑士从1开始报数，报到m的骑士出列，然后下一个位置再从1

刺骨的言语ヽ痛彻心扉/ 2022年09月19日 13:29/ 0 赞/ 185 阅读

相关约瑟夫问题

约瑟夫问题如下： n个人围成一圈，从1号开始报数，报到m就退出，剩下的人从下一个人开始继续报数。。。问最后剩下的是谁？也可问每个人的死亡顺序. 这一题在数据量比较小的

太过爱你忘了你带给我的痛/ 2022年08月10日 17:55/ 0 赞/ 133 阅读

相关约瑟夫问题

约瑟夫环问题：一圈共有N个人，开始报数，报到M的人自杀，然后重新开始报数，问最后自杀的人是谁？ ![Center][] 第一种方法：循环思想

待我称王封你为后i/ 2022年08月08日 00:39/ 0 赞/ 168 阅读

相关约瑟夫问题

Problem Description n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被

￡神魔★判官ぃ/ 2022年07月14日 12:44/ 0 赞/ 166 阅读

相关约瑟夫问题

约瑟夫问题 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [ Statis

分手后的思念是犯贱/ 2022年06月18日 05:24/ 0 赞/ 165 阅读

相关约瑟夫问题

<table> <tbody> <tr> <td>成绩</td> <td>10</td> <td>开启时间</td> <td>2017

╰半夏微凉°/ 2022年06月02日 08:57/ 0 赞/ 256 阅读

相关约瑟夫问题

1.知识点：循环链表 2.题意：n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人继续游戏，请输出最后一个人的编号 3.注意事项：

心已赠人/ 2022年05月30日 04:46/ 0 赞/ 156 阅读

相关约瑟夫问题

Problem Description n个人想玩残酷的死亡游戏，游戏规则如下： n个人进行编号，分别从1到n，排成一个圈，顺时针从1开始数到m，数到m的人被杀，剩下的人

我就是我/ 2022年05月16日 06:06/ 0 赞/ 170 阅读

相关约瑟夫问题，找零钱问题

假设拿着山芋的孩子在队列的前面。当拿到山芋的时候，这个孩子将先出列再入队列，把他放在队列的最后。经过 num 次的出队入队后，前面的孩子将被永久移除队列。并且另一个周期开始，继

刺骨的言语ヽ痛彻心扉/ 2022年04月24日 15:52/ 0 赞/ 140 阅读

相关约瑟夫问题

约瑟夫问题 ![在这里插入图片描述][20181114211743434.jpg] 题目描述：开始有5个人围成圆形，从0号开始，数2个人，谁被数到就

灰太狼/ 2022年04月16日 00:46/ 0 赞/ 182 阅读