Java教程

算法复习

本文主要是介绍算法复习,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

第三章

5. 汉诺塔问题

// 从a经过b移动n个盘子到c
void hanoi(int n, int a, int b, int c) {
    hanoi(n-1, a, c, b);
    print(f"从{a}移1个到{c}");
    hanoi(n-1, b, a, c);
}

6. 整数分划问题

求一个函数P(n),返回n的不同分划数。
例子:P(6)=6,因为有如下分划:
6
5+1
4+2
3+3
2+2+2
1+1+1+1+1+1

设函数Q(a,b),表示a的所有加数不大于b的分划数。P(n)=Q(n,n)。
则:
(1) Q(a,a)=Q(a,a-1)+1
如,6的分划有6=6和其他不含6的分划。
(2) Q(a,b)=Q(a,b-1)+Q(a-b,b)
a的不大于b分划包括含b的和不含b的,第一项表示不含b的,第二项表示含b的。

7. 输出每一位(低到高)

void print_digits(int n){
    if(n<10) print(n);
    else
    {
        print(n % 10);
        print_digits(n / 10);
    }
}

8. 输出每一位(高到低)

void print_digits(int n){
    if(n<10) print(n);
    else
    {
        print_digits(n / 10);
        print(n % 10);
    }
}

10. 输出组合(m选k)

例如,m=5, k=3,输出结果为
5 4 3
5 4 2
5 4 1
5 3 2
5 3 1
5 2 1
4 3 2
4 3 1
4 2 1
3 2 1

int K = 0;
int a[100];

// comb(m,k)负责固定a[k],递归下一层comb(m-1,k-1)固定a[k-1],
// 回来后a[k]取下一个值。
// 如果k等于1,就不需要递归,直接输出每个值即可。
void comb(int m, int k) {
    // mm 是下一层递归的m 
    for(int i = m; i >=k ; i--) {
        a[k] = i;
        if(k > 1)
            comb(i-1,k-1);
        else {
            for(int j = K; j > 0; j--)
                std::cout << a[j] << " ";
            std::cout << "\n";
        }
    } 
}

void C(int m, int k)
{
    K = k;
    memset(a, 0, sizeof(a));
    comb(m,k);
}

20. 趣味矩阵

a[i][j]表示第i行第j列。

35. 称重问题

有10箱子产品,每箱1000件,正品每件100克,其中有几箱为次品,每件次品比正品轻10克,问是否能只称1次,就找出哪些是次品。

第一箱取1个,第二箱取2个,第三箱取4个,第四箱取8个...

比如轻了70g,就是第1、2、3箱是次品。

36. 狼找兔子问题/循环移数问题

循环移数的问题:有n个数,循环后移k个位置。只有1个辅助空间。如何移动?


可以分成gcd(n,k)组,每组内的数进行循环移动。如n=12,k=8时,分组如下:

1 2 3 4 1 2 3 4 1 2 3 4

据此编码即可。

狼找兔子问题:有一个狼要找兔子吃,狼每隔k个洞找一下,有n个洞,找到头就返回去,请问兔子躲哪里永远不会被找到?

同理,还是分组,只要兔子不在狼那一组就没事。如果gcd(n,k)=1即n,k互质,则兔子必死。

39. 中国余数问题

\[x \equiv r_1(\mod t_1) \]

\[x \equiv r_2(\mod t_2) \]

\[x \equiv r_3(\mod t_3) \]

求\(n\)。

\[n=t_2t_3k_1r_1+ t_1t_2k_2r_2+ t_1t_2k_3r_3 \]

其中:\(k_i, i=1,2,3\)应该满足以下条件

\[t_2t_3k_1 \equiv 1(\mod t_1) \]

\[t_1t_2k_2 \equiv 1(\mod t_2) \]

\[t_1t_2k_3 \equiv 1(\mod t_3) \]

找到这三个系数带入即可得\(n\)。最后结果模一个\(t_1t_2t_3\)。

40. 上台阶问题

有n阶台阶,一次能上1级或2级,求有几种上法。

倒过来想:
\(f(n) = f(n-1) + f(n-2)\)

第四章

倒推法

5. 穿越沙漠问题

车子穿越1000m的沙漠,总装油量500升,耗油量1L/km,请问如何建立油站最省油(求油站的位置和油量)?

  • 汽车是一点一点“挪”过去的,即在起点和第一站之间往返建立好第一站后,就只用第一站的油在第一站和第二站之间往返(再也不回起点了),建立好第二站后,就只用第二站的油在第二站和第三站之间往返(再也不回第一站了)......

  • 建立好下一站后,上一站的油刚好用完,车内恰好没油,一切从0开始。

  • 每次向终点出发时汽车应该满载,没有为什么,贪婪的思想。

  • 倒着推,从终点到倒数第一站,一定是500m才能让第一站的油刚好用完。倒数第一站到倒数第二站之间的路程要走三次,其中两次是向终点出发,应该满载,所以倒数第二站存1000L

  • 接下来看距离,因为倒数第一站的油(500L)全部来自倒数第二站,所以倒数第二站还剩下1000-500=500L,这500L全部用于往返倒数一二站,这段路走了3次,所以距离为500/3km。

蛮力法vs聪明法

12. 狱吏问题

让狱吏n次通过一排锁着的n间牢房,第k次通过,转动第k,2k,3k,...间牢房的钥匙(切换开/关状态,即开变关、关变开)。问经过n次后,哪些牢房的锁是开的?

:(不用蛮力的方法)
利用因子个数,比如4号门,它的因子有1、2、4,说明它在第1、2、4轮会切换状态。切换了3次,最终应该是开的(假设n>=4)。

那么求一个门最终开不开,就是求它的不同因子的个数,奇数就开,偶数就不开。

然后我们发现,只有完全平方数拥有奇数个不同因子,因为因子都是成对出现的,“不同因子的个数”为奇数,说明有一对因子是一样的。

最后发现,解决这个问题,只需找到不大于n的完全平方数即可

分治法

14. 残缺棋盘


分治算法,简单说就是三个小块把空当凑到中间,正好再填一个。

15. 求数列的最大子列和


分治算法,将数列等分成2段,则最大子列的位置分为3中情况。

  • 全部在左段
  • 全部在右段
  • 跨左右段

前两种情况递归解决,第三种情况从中间向两侧各找最大子列,然后合并即是整体的最大子列。

17. 找数组中第二小的数


分治算法,分成两段,各求最小2个数。然后再4个数中选出最小的2个。

18. 找数组中第k小的数


用快速排序的第一步“切分“。先得到一个锚点p,p左边的数都比p小,右边的都比p大。
然后数p左边有几个,记作l。

如果l=k-1那么p就是答案
如果l>k-1,那么就递归在左半边找第k个数
如果l<k-1,那么就递归在右半边找第k-p个数

贪心法

通过取局部最优达到全局最优的策略。

19. 删数字


若各位数字递增,则删除最后一个数字,否则删除第一个递减区间的首字符。然后回到串首,按上述规则再删除下一个数字。重复以上过程s次即可。

23. 取数游戏

2个人轮流取2n个数中的n个数(全程明牌),取数之和大者为胜。请问先手如何永远胜利?

先手先看奇位置上的数的和大还是偶位置上的数的和大,哪个大就确保自己只取这些数,对面取不到这些数即可。换言之,不让对手取两个连续的数就行。

动态规划

递归+保存结果 的

25. 投资问题

将n元分配给m个项目,\(g_i(x)\)为第i个项目分配得x元所得到的利润。求最大利润的分配方案。

设\(f_i(x)\)为将资源\(x\)分配给前\(i\)个项目所得到的最大利润,则:

\[f_1(x)=g_1(x) \]

\[f_i(x)=max\{g_i(k)+f_{i-1}(x-k)\}_{k=0}^{x} \]

26. 矩阵连乘问题

构造数组\(r_i\)。表示第\(i+1\)个矩阵的行数和第\(i\)个矩阵的列数。

矩阵\(Mi...Mj\)的最小乘法次数

\[\begin{equation} f(i,j)= \begin{cases} 0 & {i=j} \\ r_ir_{i+1}r_{i+2} & {i=j-1} \\ min(f(i,k)+f(k+1,j)+r_ir_{k+1}r_{j+1})& {i\le k < j} \\ \end{cases} \end{equation} \]

27. 最长子序列

第五章

子集树:

第1层 1号元素选还是不选
第2层 2号元素选还是不选
...

共\(2^n\)个叶子结点

排列树:

第1层 1号元素放哪(n个选择)
第2层 2号元素放哪(n-1个选择)
...
共\(n!\)个叶子结点

活结点:还可以展开的结点
E结点:正在展开的结点
死结点:无法再展开的结点

8皇后问题

这篇关于算法复习的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!