算法分析复习重点

复习重点

子集数

01背包

排列树

（可以求出所有的解，但是是残缺的）

n-皇后

n的全排列

回溯法就是对隐式图的深度优先搜索算法

（勤劳或许也是一种诅咒）

八皇后回溯的过程

解空间

结点的扩展规则

搜索解空间（一直往下走）首先深度优先，数据结构好的话可以使用栈

活结点和死结点

智能计算优化问题

（写代码要有自己的风格和模式）

要用自己的脑子来判断

马的遍历问题

使用数组的下标，来记录它的增量

深度优先搜索往下去走

八个状态如何来安排

数据结构设计 dep = n*m 求解到成功

试探完毕也就出来了

二维数组

（生命是非常短暂的，我们需要在有限的生命中去尽力探索这个世界，我们不应该被既定的许多东西束缚住，那不是生命本身的意义，我们不应该被生活所欺骗）

（很多东西只有你有足够的认知和知识储备，你才能够理解许多大师的话语和深意）

回溯的题目

二十层的嵌套循环

题目类型

选择，填空，分析（辨析），代码补全，算法设计

排列及排列树的回溯搜索

如何使用回溯法写出n的全排列

在这个例子中，permute 函数接受一个整数n，生成从1到n的全排列。backtrack 函数是回溯的核心，它通过递归的方式尝试每个可能的数字排列，直到找到一个完整的排列。

注意事项：

backtrack 函数中的 path 参数表示当前的路径，result 参数用于存储所有找到的全排列。
如果当前路径的长度等于数组的长度，就表示找到了一个全排列，将其加入到结果中。
在循环中，检查数字是否已经在路径中，如果没有，则选择该数字，递归到下一个位置，然后回溯，撤销选择，继续尝试下一个数字。

这是一个基本的回溯法例子，可以根据具体问题的要求进行适当的调整。

对角线不准相同，不能是一个定值

是所有排列数的一个骨髓

画出了全排列的那个树

有没有被使用过，互不重复

什么叫做全排列吗？

交换其中任意两个，别重复也别漏

写成活的不缺数字不考虑这个事情

如果不是个写代码的老手，会看不懂

运行速度会慢一些，由用户输入，写成具体有几个数的全排列

回溯法全排列

try(int t)
{ int j;
if (t>n)
{output();}
else
for(j=t;j<=n;j++)
{swap(t,j);
try(t+1):
swap(t,j);/回溯时，恢复原来的排列/

}}

try(int t)
{
    int j;

    // 如果当前处理的位置 t 超过了总数 n，说明已经生成了一种排列，输出结果
    if (t > n)
    {
        output();
    }
    else
    {
        // 遍历当前位置 t 到 n 的所有可能的值
        for (j = t; j <= n; j++)
        {
            // 将当前位置 t 的元素与位置 j 的元素交换
            swap(t, j);

            // 递归调用 try 函数，处理下一个位置 t+1
            try(t + 1);

            // 回溯时，恢复原来的排列，将之前交换的元素还原
            swap(t, j);
        }
    }
}

try(1):
  for j = 1 to 3:
    swap(1, 1)  # 选择了数字1放在第一个位置
    try(2):
      for j = 2 to 3:
        swap(2, 2)  # 选择了数字2放在第二个位置
        try(3):
          for j = 3 to 3:
            swap(3, 3)  # 选择了数字3放在第三个位置
            try(4):
              t > n，输出排列 [1, 2, 3]
            回溯，执行 swap(3, 3) 恢复原来的排列 [1, 2, 3]
        回溯，执行 swap(2, 2) 恢复原来的排列 [1, 2, 3]
      for j = 3 to 3:
        swap(2, 3)  # 选择了数字3放在第二个位置
        try(3):
          ...
        回溯，执行 swap(2, 3) 恢复原来的排列 [1, 2, 3]
    回溯，执行 swap(1, 1) 恢复原来的排列 [1, 2, 3]
  for j = 2 to 3:
    swap(1, 2)  # 选择了数字2放在第一个位置
    try(2):
      ...
    回溯，执行 swap(1, 2) 恢复原来的排列 [1, 2, 3]
  for j = 3 to 3:
    swap(1, 3)  # 选择了数字3放在第一个位置
    try(2):
      ...
    回溯，执行 swap(1, 3) 恢复原来的排列 [1, 2, 3]

当 t=1，n=3 时，整个过程如下：

try(1):
- 第一次循环，j 的初始值是1。
  - 执行 swap(1, 1)，选择了数字1放在第一个位置。
  - 递归调用 try(2)。
try(2):
- 第一次循环，j 的初始值是2。
  - 执行 swap(2, 2)，选择了数字2放在第二个位置。
  - 递归调用 try(3)。
try(3):
- 第一次循环，j 的初始值是3。
  - 执行 swap(3, 3)，选择了数字3放在第三个位置。
  - 递归调用 try(4)。
try(4):
- 在这里，t > n，输出当前排列 [1, 2, 3]。
- 回溯，执行 swap(3, 3) 恢复原来的排列 [1, 2, 3]。
回到 try(3):
- 第二次循环，j 的初始值是3。
  - 执行 swap(3, 3)，选择了数字3放在第三个位置。
  - 递归调用 try(4)。
try(4) （第二次调用）:
- 在这里，t > n，输出当前排列 [1, 2, 3]。
- 回溯，执行 swap(3, 3) 恢复原来的排列 [1, 2, 3]。
回到 try(2):
- 第二次循环，j 的初始值是2。
  - 执行 swap(2, 2)，选择了数字2放在第二个位置。
  - 递归调用 try(3)。
try(3) （第二次调用）:
- 第一次循环，j 的初始值是3。
  - 执行 swap(3, 3)，选择了数字3放在第三个位置。
  - 递归调用 try(4)。
try(4) （第三次调用）:
- 在这里，t > n，输出当前排列 [1, 3, 2]。
- 回溯，执行 swap(3, 3) 恢复原来的排列 [1, 2, 3]。
回到 try(3) （第二次调用）:
- 第二次循环，j 的初始值是3。
  - 执行 swap(3, 3)，选择了数字3放在第三个位置。
  - 递归调用 try(4)。
try(4) （第四次调用）:
- 在这里，t > n，输出当前排列 [1, 3, 2]。
- 回溯，执行 swap(3, 3) 恢复原来的排列 [1, 2, 3]。
回到 try(2):
- 第三次循环，j 的初始值是3。
  - 执行 swap(2, 3)，选择了数字3放在第二个位置。
  - 递归调用 try(3)。
try(3) （第三次调用）:
- 第一次循环，j 的初始值是3。
  - 执行 swap(3, 3)，选择了数字3放在第三个位置。
  - 递归调用 try(4)。
try(4) （第五次调用）:
- 在这里，t > n，输出当前排列 [2, 1, 3]。
- 回溯，执行 swap(3, 3) 恢复原来的排列 [1, 2, 3]。
回到 try(3) （第三次调用）:
- 第二次循环，j 的初始值是3。
  - 执行 swap(3, 3)，选择了数字3放在第三个位置。
  - 递归调用 try(4)。
try(4) （第六次调用）:
- 在这里，t > n，输出当前排列 [2, 1, 3]。
- 回溯，执行 swap(3, 3) 恢复原来的排列 [1, 2, 3]。
回到 try(2):
- 第四次循环，j 的初始值是3。
  - 执行 swap(2, 3)，选择了数字3放在第二个位置。
  - 递归调用 try(3)。
try(3) （第四次调用）:
- 第一次循环，j 的初始值是3。
  - 执行 swap(3, 3)，选择了数字3放在第三个位置。
  - 递归调用 try(4)。
try(4) （第七次调用）:
- 在这里，t > n，输出当前排列 [2, 3, 1]。
- 回溯，执行 swap(3, 3) 恢复原来的排列 [1, 2, 3]。
回到 try(3) （第四次调用）:
- 第二次循环，j 的初始值是3。
  - 执行 swap(3, 3)，选择了数字3放在第三个位置

留学咨询

1.2024年国内考研报名已经截至，据统计今年报考人数已经突破500W人!

从往年的数据可以看出，国内考研人数逐年增加，考生竞争压力也变得越来越大，学历的价值也越来越重要。相比国内，国外的研究生学制整体来说较短一些，且入学申请政策相较于国内考研来说也更加灵活，比如国内一年-考、一考定胜负，在国外会更加丰富一些，不会一局定“输赢”。不仅如此，国外还可以同时申请多所学校和多个专业，甚至还可以选择多国联申，只要选校、选专业的策略正确，一般都可以申请到比较满意的院校和专业。考研总是存在各种变数，大家只有做好“两手准备，才能拥有双重保障”。

2.Niche发布2024年全美最难进入的大学排名！

从榜单中可以看出，上榜的美国大学，无论是综合大学还是文理学院，录取率普遍低于10%，真是当之无愧的“高冷校”，申请难度可想而知。加州理工学院、斯坦福大学、麻省理工学院一直是“精英和学霸的聚集地”，无论是科研实力、师资力量，还是国际影响力，都享有极高赞誉。正因如此，大学招生官在考察申请者时，往往更青睐优秀且富有创造力和独特性的学生。
波莫纳学院仍是全美最难录取的文理学院，斯沃斯莫尔学院、鲍登学院、科尔比学院等，录取难度丝毫不逊于顶尖综合性大学。

完整排名链接：https://www.niche.com/colleges/search/hardest-to-get-in/?type=private&type=public

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/217659.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！