大一的中等键盘

Posted on Edited on

算法设计与分析报告4 实验四 动态规划

本文发布地址：

  1. https://cmd.dayi.ink/WNa3RGNaShmf_vPpUemWxA?both
  2. https://type.dayiyi.top/index.php/archives/237/
  3. https://blog.dayi.ink/?p=82
  4. https://www.cnblogs.com/rabbit-dayi/p/17816598.html

1.爬楼梯问题

  • 小明住在 N 层楼梯之上，然后他可以一次 一脚 1 个台阶，一脚 2 个台阶，问总共多少种方法。
  • 一个楼梯共有 n 级台阶，每次可以走一级或者两级，问从第 0 级台阶走到第 n 级台阶一共有多少种方案。

  • 状态表示：
    f[i]表示 0->i 个台阶有多少种方案
    有限集合的值
    属性：数值

  • 状态计算：
    对于 f[i] 的计算：

    • 对于第 i 层台阶
      • 我可以从 i-1 上一层到 i 层
      • 我可以从 i-2 上两层到 i 层
    • 由于表示的是方案数：
      • f[i-1] 表示从 0->i-1 层的方案数
      • f[i-2] 表示从 0->i-2 层的方案数
    • 而 f[i] 的方案数是：
      • 上一层的方案数（也就是从 f[i-1] 过来）
      • 上两层的方案数（也就是从 f[i-2] 过来）

  • 由状态可以推出状态转移方程
    $f[i] = f[i-1]+f[i-2]$

可以写代码（对于 N 范围比较小）

Read more »

Posted on Edited on

算法设计与分析报告5 贪心算法

本文发布地址（方便阅读）：

  1. https://cmd.dayi.ink/WfnxTsYRQ4OdwI587BGDRQ
  2. https://blog.dayi.ink/?p=89
  3. https://www.cnblogs.com/rabbit-dayi/p/17817387.html
  4. https://type.dayiyi.top

1. 硬币找零问题

贪心

就是假设我们是收银员，需要找零，然后需要选取最少的硬币数量给他人。

我们直接从最大的依次给，给不了就给再小的，很爽。

但贪心的原理是子问题最优解推出整体问题最优解，也就是最优子结构，而对于子问题，只考虑当前怎么做最优，而不考虑整体情况，对于这个我们就只考虑现在需要的硬币而不考虑整体需要多少硬币。

实际的贪心问题需要证明，但是都贪心了，就贪心一点，不要那么多，直接做贪！

1
2
3
4
5
6
7
8
9
10
11
12
13
n = eval(input()) #要贪心的数额
arr = [10,5,1] # 面额
ans = 0
for i in arr:
  if n>=i:
    k = n//i #整除
    n -= i*k
    ans += k
    print(f"[info]{i} * {k}")

if ans ==0:
  print(-1)
else:print(ans)

  1. 最大面额的硬币比任何其他可能的硬币组合能表示的最大金额还要大。 这意味着任何较大金额的找零都应该首先尽可能多地使用最大面额的硬币
  2. 较小的硬币面额能被较大的硬币面额整除。
  3. 组合属性。 对于任意两个硬币面额a和b，如果a > b，那么对于任何金额x，如果x能够用a来找零，那么x - b也能用a来找零。移除一个较小面额的硬币并不会改变剩余金额能否用较大面额的硬币找零。也就是说，x可以被a整除或者x大于a，那么从x中减去b（得到的金额是x-b）仍然能够使用面额为a的硬币找零。
    Read more »
0%