wweiyiのblog

【解题报告】 POJ1958 奇怪的汉诺塔 在这样热浪滚滚的暑假，外面晴空高照，在家里刷刷题不妨是最好的选择 ——来自wweiyi语录 题目链接（翻译过的）： https://www.acwing.com/problem/content/98/ 题意简述：输出四个塔的汉诺塔分别从1个盘子到12个盘子的最少步数 我们看了题之后，可以知道这道题跟三个塔的汉诺塔一样，用递归，但是我们设先移走i个盘子到第二个塔或第三个塔，然后就转化成三个塔的问题了。 但是问题在于不知道i等于多少，而且直接输出12个值要用递归也会有些慢，所以我们做一下优化，记忆化一下，我们就可以很快的输出了 设三个塔n个盘子的步数为d[n],设四个塔n个盘子的步数为f[n] 动态转移方程如下 fn=min(fn,2fi+dn−i)f_n=min(f_n,2f_i+d_{n-i}) fn​=min(fn​,2fi​+dn−i​) 其中 1≤n,i≤121\leq n,i \leq 12 1≤n,i≤12 所以我们就解决了这道题目 代码如下 123456789101112131415161718192021222324...

【基础题目】A%B Problem 题目描述 C–语言是一种C的简化版，它仅有的三种运算符为++，–和==（没有=，+，-，*，/，%，<,>等任何其他运算符），也没有循环及goto语句，除此之外与C相同。使用C–编写一个函数int mod(int a,int b)，计算a除以b的余数。 ——来自wweiyi暑假集训 题意简述：只用++,–,==运算符和C++的其他功能来完成a%b的功能 提示：允许调用其他函数 这是一道神奇的题目，我想了大半天才想出来，甚至引来了老师的批评，接下来我说一说我的思路 这道题我们需要只用++,–,==和C++的其他功能来实现模运算，这个看起开似乎无法实现，因为不能够使用循环，因此，这道题的阴影加深了。 递归！循环的后裔！ 这里我们不能用循环，也就是我们需要使用类似循环的一个过程，递归来解决问题，递归是一种很常用的解决问题的方法，将一个大问题转换成一个子问题也许模运算就可以这样解决了。 ++，–，==三运算符！三符成虎！ 我们要解决模运算首先要解决减法运算的问题，因为a%b，就是a一直减b，减到a小于b为止，因此，我们可以先解决减法运算...

最大公约数的故事 最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。——来自《百度百科》 [^]: 两个数的最大公约数a，b一般用gcd（a，b）来表示，因此，我后文也会用gcd（ ， ）来表示两个数的最大公约数 最大公约数在计算机中也很常用，而对于这种数了解最深的非欧几里得莫属了！ 欧几里得 欧几里得（英文：Euclid；希腊文：Ευκλειδης，约公元前330年—公元前275年），古希腊人，数学家，被称为“几何之父”。他最著名的著作《几何原本》是欧洲数学的基础，提出五大公设，欧几里得几何，被广泛的认为是历史上最成功的教科书。欧几里得也写了一些关于透视、圆锥曲线、球面几何学及数论的作品。——来自《百度百科》 特别是数论方面有很深的造诣，因此我们今天计算机中关于数论的东西有很可观的一部分来自欧几里得，所以我们在这里看一下最大公约数。 如何算最大公约数？ 质因数分解法 这是一个好问题，最简单的方法是用质因数分解法 例如：gcd...

汉诺塔问题（Hanoi Tower Problem） 汉诺塔问题家喻户晓，它源于一个印度的神话，内容如下： 在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。 这个问题看起来十分可怕，实际上很简单。接下来就解决一个问题来体会这个小小问题中的大大的递归思想！ 有三根柱子，第一根柱子上有n个从下向上越来越小的圆盘。 目标：使第一根柱子上的n个圆盘按原样摆放在另一个柱子上。 注：一次移动一个圆盘，不可以出现大的盘子在小的盘子上面的情况。 解： 首先我们先玩一下这个游戏。 接着我们找出一个规律，要彻底地把这个塔移开，我们必须要移开上方的n-1个盘子，使最下面的盘子可以移动到另一个柱子上，然后在把上方的n-1个盘子移动到最下...