取糖果-分糖果的问题_gargden

http://blog.sina.com.cn/u/1622289947

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

取糖果-分糖果的问题

(2021-04-06 11:27:00)

分类：研究-学习

看到书本中还有这个内容，我感觉自己无从下手，到网上找找资料，虽然在作业帮中找到了答案，但程序设计还是无从下手。

不过还是找到了更多的知识点，这个主题有太多的知识点可以展开分析了！

很多也不是太看得懂，先记录下来。

======

有9颗糖果 ,甲乙两人轮流取糖,每次只能取1颗或2颗,谁取得最后一颗谁就赢!怎样取?

谁先取到第六颗谁赢.

================

糖果一共有10颗，两人轮流从中拿走1颗或2颗，谁拿到最后一颗糖果谁就获胜．想一想：如果让你先拿，第一次应该拿几颗才能确保获胜？

先拿1颗，使这袋糖果剩下9颗，然后，就看着另一个人拿，若另一个人拿1个，第一个人就拿2个，若另一个人拿2个，第一个人就拿1个，9÷3=3，这样3轮，最后一颗，保证是第一个人的．

答：如果我先拿．第一次拿1颗才能确保他获胜．

本题考点：

最佳对策问题．

考点点评：

关键是9是3的倍数关系，另外，最后一轮还剩3个，最后一个人不可能全部拿走．

============

笔试真题：100颗糖果，甲乙轮流从糖果盒中取出糖果，每次可取出2、4或6颗，若取得最后糖果的玩家为最终胜者，若甲先取z则（甲获胜，乙获胜，平局，不确定）

解析：

想让甲赢，只需保证最后剩8颗糖（乙取2颗，甲取4颗；乙取4颗，甲取4颗；乙取6颗，甲取颗），甲就可以赢。那么甲只要保证最后剩余8颗糖，甲就能赢。

那么该如何保证最后剩余8颗糖呢？其实只要保证甲第一次取糖后，剩余的数字为8的整数倍（即8可以整除剩余数字），每次乙取对应数量的糖数，甲只要保证所取的糖数与乙取得糖数和为8，甲就能胜。100%8=4，所以本题中，甲第一次取4颗糖，然后呢在后面的取数中，甲只要保证，每回合甲所取的糖数与乙上回合所取的糖数和为8，甲就一定能赢。所以最终甲获胜。

========================

小学数学 > 题目详情

6．一堆水果糖有20颗，两人轮流从中拿走1颗或2颗，谁拿到最后一颗谁就获胜．让你先拿，第一次应该拿2颗才能确保获胜．如果有37颗糖，第一次应该拿1颗才能确保获胜．

分析 1+2=3颗，如果有20颗糖，20÷3=6…2，第一次先拿走2颗，然后再保证以后每次拿的数量都与另一人拿的数量和都是3即可获胜；

同理，如果有37颗糖，37÷3=12…1，第一次先拿走1颗，然后再保证以后每次拿的数量都与另一人拿的数量和都是3即可获胜．

解答解：1+2=3（颗）；

20÷3=6…2则：先拿2颗，使这袋糖果剩下18颗，然后，就看着另一个人拿，若另一个人拿1颗，第一个人就拿2颗；若另一个人拿2颗，第一个人就拿1个；9÷3=3，这样3轮，最后一颗，保证是先拿的．

同理：37÷3=12…1，先拿走1颗，然后再保证以后每次拿的数量都与另一人拿的数量和都是3即可获胜．

故答案为：2，1．

点评本题关键根据余数确定先拿的颗数，以后每次拿的颗数始终都与另一人拿的颗数和是3，一定会赢．

==========================================

Leetcode练习(Python)：第292题：Nim 游戏：你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。

题目：

Nim 游戏：你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。

你们是聪明人，每一步都是最优解。编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。

示例:

输入: 4

输出: false

解释: 如果堆中有 4 块石头，那么你永远不会赢得比赛；因为无论你拿走 1 块、2 块还是 3 块石头，最后一块石头总是会被你的朋友拿走。

思路：

一开始看这道题很懵，每个人都是聪明人，每一步都是最优解，在有些情况下，可能会出现可能是输也可能是赢的情况。针对这道题，将自己代入，自己想要赢，在别人会输的情况下找自己的最优解。距离自可以得出，如果是4的整数倍赢不了，其他都可以赢。

程序：

class Solution:

def canWinNim(self, n: int) -> bool:

if n == 0:

return False

result = bool(n % 4)

if result == 0:

return False

elif result != 0:

return True

==================

Python练习（21）-分糖果-中

问题描述:

10个小孩围城一圈分糖果，老师分给第1个小孩10块，第2个小孩2块，第3个小孩8块，第4个小孩22块，第5个小孩16块，第6个小孩4块，第7个小孩10块，第8个小孩6块，第9个小孩14块，第10个小孩20块。然后所有的小孩同时将手中的糖分一半给右边的小孩；糖块数为奇数的人可向老师要一块。

问经过这样几次后大家手中的糖的块数一样多？每人各有多少块糖？

网址

https://blog.csdn.net/qq_43243022/article/details/83118787

分析：

首先，糖的传递a[i]=(a[i]+a[i-1])/2，要用到小索引元素，所以应该从大到小遍历，记得每次循环前先取出a[9]，最后加到a[0]

判断是否是奇数

构造全相等的判断函数

#构造糖块全相等的判断函数

def isequal(c):

s=0

for v in range(len(c)-1):

if c[v]!=sum(c)/len(c):

s+=1

if s==0:

return True

#主体函数

a=[10,2,8,22,16,4,10,6,14,20]

k=1

while k < 100:

last=a[9]

a[0]=(a[0]+last)/2

if a[0]%2!=0:

a[0]=a[0]+1

for i in range(9,0,-1):

a[i]=(a[i]+a[i-1])/2

#此处在循环内直接判断是否是奇数。如果再来一个循环的话for i in range(10)，复杂度大大增加。

if a[i]%2!=0:

a[i]=a[i]+1

k+=1

if isequal(a):

continue

print k,a

————————————————

原文链接：https://blog.csdn.net/qq_43243022/article/details/83118787

总结：

1 判断函数构造错误

2 判断是否是奇数的时候，我开始用的是重新遍历一遍for i in range(10)，复杂度大大增加，优化为在循环内直接判断。

3 开始将a[0]的赋值错误地放到了for i 循环里面了，这样每次a[0]都被累加赋值了，应该是外面，每次大循环赋值一次

4 平均数array.mean()只有在numpy数组才能用

————————————————

原文链接：https://blog.csdn.net/qq_43243022/article/details/83118787

========================================

Python|贪心的分发糖果

问题描述

分发糖果（力扣135）：

老师想给孩子们分发糖果，有N个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。

你需要按照以下要求，帮助老师给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。

相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？

示例 1:

输入: [1,0,2]

输出: 5

解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

示例 2:

输入: [1,2,2]

输出: 4

解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。

解决方案

规则：相邻的孩子中，评分高的孩子必须获得更多的糖果。

通俗的讲，评分为2的孩子得到了1个，相邻的评分为3的孩子最少得到2个。要注意的是：满足规则且糖果总数最少的情况下，相邻的两个评分相同的孩子得到的糖果数量是不同的（比如上面的示例2）。

根据这个规则并且题目要求糖果总数最少，就可以利用贪心思想，在遍历过程中，每一步都尽量少给糖（给评分高的人一个满足规则，给两个也满足规则。但最优的话就是只给一个），按照规则一定要加的时候才加一个，不违背规则的时候就一定不能加。

思路：为了更容易理清思路，可以兵分两路，从左到右和从右到左分别考虑。这样先找从左到右满足规则最少的糖果，再找从右到左的，最后取两边都满足的值，也就是最大值，然后相加之和就是所求最少糖果总数。

题目代码：

class Solution:

def candy(self, ratings: List[int]) -> int:

# 记录从左到右按规则每个孩子所得最少糖果

r = [1] * len(ratings)

# 记录从右到左按规则每个孩子所得最少糖果

l = r.copy()

for i in range(1, len(ratings)):

# 从左到右开始添加糖果数量

if ratings[i] > ratings[i-1]:

r[i] = r[i-1] + 1

# 从右到左开始添加糖果数量

if ratings[-i-1] > ratings[-i]:

l[-i-1] = l[-i] + 1

# 最后取最大值的相加之和

return sum([max(a, b) for a, b in zip(r, l)])

结语

题目要求的是糖果总和最小，就可以利用贪心算法局部最优的选择，即贪心选择来达到。

贪心算法的基本思路就是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。

=================

蓝桥杯试题：分糖果（python实现)

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏：

每个小朋友都把自己的糖果分一半给左手边的孩子。

一轮分糖后，拥有奇数颗糖的孩子由老师补给1个糖果，从而变成偶数。

反复进行这个游戏，直到所有小朋友的糖果数都相同为止。

你的任务是预测在已知的初始糖果情形下，老师一共需要补发多少个糖果。

输入格式

程序首先读入一个整数N(2

接着是一行用空格分开的N个偶数（每个偶数不大于1000，不小于2）

输出格式

要求程序输出一个整数，表示老师需要补发的糖果数。

样例

样例输入

2 2 4

样例输出

代码

N = int(input()) # 孩子的个数

s = list(map(int, input().split())) # 每个孩子的糖果数

ans = sum(s) # 开始总的糖果数

a = s[0] // 2 # 上一个孩子给下一个孩子的糖果数

while len(s) != s.count(s[0]): # 当每个人糖果数不一样时执行

for i in range(N):

if i + 1 == N:

# 让最后一个孩子的下一个指向第一个孩子

i = -1

# 分糖果

s[i+1], a = s[i+1] + a - s[i+1] // 2, s[i+1] // 2

if s[i+1] % 2 != 0: # 奇数时加1

s[i+1] += 1

ans = sum(s)-ans # 补发的糖果数

print(ans)

==================

力扣LeetCode【每日一题】—— 数学问题分糖果 II（Python3）

难度：简单

类型：数学

题目：我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

技巧：“再回到队伍的起点” --> 求余运算%

示例 1：

输入：candies = 7, num_people = 4

输出：[1,2,3,1]

解释：

第一次，ans[0] += 1，数组变为 [1,0,0,0]。

第二次，ans[1] += 2，数组变为 [1,2,0,0]。

第三次，ans[2] += 3，数组变为 [1,2,3,0]。

第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

示例 2：

输入：candies = 10, num_people = 3

输出：[5,2,3]

解释：

第一次，ans[0] += 1，数组变为 [1,0,0]。

第二次，ans[1] += 2，数组变为 [1,2,0]。

第三次，ans[2] += 3，数组变为 [1,2,3]。

第四次，ans[0] += 4，最终数组变为 [5,2,3]。

LZ看完题目第一反应就是暴力方法遍历，可以运行但是代码写得太丑，发现了更直观简练的写法记录下来。

第二个方法用等差数列求和来简化问题，降低时间复杂度。

方法1：遍历数组

class Solution:

def distributeCandies(self, candies: int, num_people: int) -> List[int]:

count = 1

ans = [0] * num_people # list([0 for x in range(num_people)])

while candies > 0:

for i in range(num_people):

if candies > count :

ans[i] += count

candies -= count

count += 1

else:

ans[i] += candies

candies = 0

return ans

凝练版（去掉for循环和if条件）：

class Solution:

def distributeCandies(self, candies: int, num_people: int) -> List[int]:

ans = [0] * num_people

i = 0

while candies > 0:

ans[i % num_people] += min(i + 1, candies)

candies -= min(i + 1, candies)

i += 1

return ans

1. 用求余%运算符解决了“重头再来” ，省去了for语句

2. 用min()比较代替if...else

执行用时 :36 ms, 在所有 Python3 提交中击败了90.37%的用户

内存消耗 :13.4 MB, 在所有 Python3 提交中击败了23.58%的用户

时间复杂度：O(max(G,N))，G 为糖果数量，N 为人数

空间复杂度：O(1)

方法2：（涉及高中数学知识点等差数列；二元一次方程求根公式；向下取整int()\、floor()）

作者：quantumdriver

https://leetcode-cn.com/problems/distribute-candies-to-people/solution/xiang-xi-jie-shi-shu-xue-fang-fa-zen-yao-zuo-gao-z/

class Solution:

def distributeCandies(self, candies: int, num_people: int) -> List[int]:

n = num_people

# 套用上面推出来的公式，直接计算可以完整发放糖果的次数p

p = int((2 * candies + 0.25)**0.5 - 0.5)

# 继续套用公式，算出完整发放糖果以后剩余的糖果数量

R = int(candies - (p + 1) * p * 0.5)

# 迭代rows轮，cols是倒霉孩子的下标

rows, cols = p // n, p % n

# 小朋友们端好了碗，等你发糖

kids = [0] * n

for i in range(n):

# 性感coder，在线发糖

kids[i] = (i + 1) * rows + int(rows * (rows - 1) * 0.5) * n

# 最后一轮or在p

if i < cols:

kids[i] += i + 1 + rows * n

# 最后的那个倒霉孩子开心的拿到了R颗糖

kids[cols] += R

return kids

执行用时 :36 ms, 在所有 Python3 提交中击败了90.37%的用户

内存消耗 :13.4 MB, 在所有 Python3 提交中击败了23.58%的用户

时间复杂度：O(N)

空间复杂度：O(1)

题目来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/distribute-candies-to-people

————————————————

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：假期出游（二）zj博物馆

后一篇：又见沈大业看电子小说！！！

新浪BLOG意见反馈留言板　欢迎批评指正