026.introductionToAlgorithms_算法初识

算法不是某一种编程语言的语法，而是解决问题时可以重复执行的一组明确步骤。上一篇用五层嵌套循环逐个检查找零方案，本篇利用数学结构减少不必要的枚举，作为算法思想的第一次实践。

本文继续研究同一个问题：顾客支付100元，购买5元商品后需要找零95元。假设商家拥有数量不限的50元、20元、10元、5元和1元纸币，并且只比较各面额的数量，不区分纸币交付顺序。

问题建模

设a、b、c、d、e分别表示50元、20元、10元、5元和1元纸币的数量。
100元纸币不参与找零，因为它本身大于95元；因此从枚举集合中直接排除。
每种方案都必须满足总金额恰好等于95元，且每种纸币数量都是非负整数。

方案集合可以写成非负整数解的集合：

$50a+20b+10c+5d+e=95$

数学计算

固定50元、20元和10元纸币的数量后，剩余金额为：

$R=95-50a-20b-10c$

5元纸币的数量d可以从0取到floor(R/5)。一旦d确定，1元纸币数量e就由剩余金额唯一确定。因此，固定a、b、c后，5元和1元纸币一共有：

$\left\lfloor\frac{R}{5}\right\rfloor+1$

这意味着统计时只需要枚举前三种纸币的数量，把每个剩余金额对应的5元、1元组合数直接加起来：

$N=\sum_{a=0}^{1}\sum_{b=0}^{\left\lfloor(95-50a)/20\right\rfloor}\sum_{c=0}^{\left\lfloor(95-50a-20b)/10\right\rfloor}\left(\left\lfloor\frac{95-50a-20b-10c}{5}\right\rfloor+1\right)=294$

例如a=0、b=0、c=0时，剩余95元可以由0到19张5元纸币组成，对应19+1=20种方案。第一种是95张1元，第二种是1张5元加90张1元。

优化后的代码

! 用三层嵌套循环统计95元找零的纸币组合。
! 固定50元、20元和10元后，用公式一次计算5元与1元的组合数。
program nestedLoopChangeOptiDemo
  implicit none

  integer :: changeAmount
  integer :: fiftyCount
  integer :: twentyCount
  integer :: tenCount
  integer :: fiveCount
  integer :: oneCount
  integer :: remainingAmount
  integer :: fiveOnePlanCount
  integer :: solutionCount
  integer :: resultUnit
  integer :: ioStatus

  changeAmount = 95
  solutionCount = 0

  open (newunit=resultUnit, file="result.txt", status="replace", &
        action="write", iostat=ioStatus)
  if (ioStatus /= 0) error stop "无法打开result.txt"

  write (resultUnit,"(A,I3,A)") "找零金额：", changeAmount, " 元"
  write (resultUnit,"(A)") "优化方法：三层循环 + 5元、1元组合公式"

  ! 固定前三种面额后，剩余金额满足：5*d+e=remainingAmount。
  ! d可以从0取到remainingAmount/5；d确定后，e唯一确定。
  do fiftyCount = 0, changeAmount / 50
    do twentyCount = 0, (changeAmount - 50 * fiftyCount) / 20
      do tenCount = 0, (changeAmount - 50 * fiftyCount - &
                        20 * twentyCount) / 10

        remainingAmount = changeAmount - 50 * fiftyCount - &
                          20 * twentyCount - 10 * tenCount
        fiveOnePlanCount = remainingAmount / 5 + 1
        solutionCount = solutionCount + fiveOnePlanCount

      end do
    end do
  end do

  write (resultUnit,"(A,I3,A)") "全部方案数量：", solutionCount, " 种"
  write (resultUnit,"(A)") "当50元、20元和10元纸币数量都为0时的前12种方案："

  ! 下面的循环只用于展示方案，不参与总数统计。
  do fiveCount = 0, min(11, changeAmount / 5)
    oneCount = changeAmount - 5 * fiveCount
    write (resultUnit,"(A,I3,A,I3,A,I3,A,I3,A,I3)") &
      "50元=", 0, " 20元=", 0, " 10元=", 0, &
      " 5元=", fiveCount, " 1元=", oneCount
  end do

  close (resultUnit)
end program nestedLoopChangeOptiDemo

算法结构

前三层do循环分别枚举50元、20元和10元纸币的数量。
remainingAmount表示固定前三种面额后还需要补齐的金额。
fiveOnePlanCount = remainingAmount / 5 + 1直接计算5元和1元纸币的组合数量，不再为统计结果逐个枚举它们。
最后的fiveCount循环只写出示例方案，不参与solutionCount统计。
resultUnit负责把计算结果写入result.txt，程序正常运行时不在终端输出结果。

编译运行

(base) hong@hongdeMacBook-Pro 026.introductionToAlgorithms % gfortran -Wall -Wextra -std=f2018 exampleNestedLoopOpti.f90
(base) hong@hongdeMacBook-Pro 026.introductionToAlgorithms % ./a.out
(base) hong@hongdeMacBook-Pro 026.introductionToAlgorithms % cat result.txt
找零金额： 95 元
优化方法：三层循环 + 5元、1元组合公式
全部方案数量：294 种
当50元、20元和10元纸币数量都为0时的前12种方案：
50元=  0 20元=  0 10元=  0 5元=  0 1元= 95
50元=  0 20元=  0 10元= 0 5元=  1 1元= 90
50元=  0 20元=  0 10元= 0 5元= 2 1元= 85
50元=  0 20元=  0 10元= 0 5元= 3 1元= 80
50元=  0 20元= 0 10元= 0 5元= 4 1元= 75
50元=  0 20元= 0 10元= 0 5元= 5 1元= 70
50元=  0 20元= 0 10元= 0 5元= 6 1元= 65
50元=  0 20元= 0 10元= 0 5元= 7 1元= 60
50元=  0 20元= 0 10元= 0 5元= 8 1元= 55
50元=  0 20元= 0 10元= 0 5元= 9 1元= 50
50元=  0 20元= 0 10元= 0 5元= 10 1元= 45
50元=  0 20元= 0 10元= 0 5元= 11 1元= 40

结果分析

025使用五层循环逐一检查5元和1元纸币的数量；026发现固定前三种面额后，5元数量一旦确定，1元数量就唯一确定，所以可以用公式直接计算这一组方案数量。

优化后仍然得到294种方案，但统计部分只保留三层循环。这里的关键不是改变问题，而是利用问题中已经证明的结构，把重复的枚举工作改成一次整数运算。

知识点总结

算法是解决问题的明确步骤，不等同于某一种语言语法。
数学建模可以帮助程序发现枚举空间中的规律。
固定部分变量后，如果剩余变量之间存在唯一关系，就可以用公式减少循环层数。
优化前后应使用相同结果进行验证，本例两种程序都得到294种方案。
结果写入文本文件后，程序输出和结果查看可以分离。