资讯专栏INFORMATION COLUMN

上云采购季！| 爆款云服务器低至4.6元/月，首单享0.9折

免费试用
首页/文章专栏/一篇算法讲解的注解

一篇算法讲解的注解

fevin / 456人阅读

摘要：前言从公式到算法之前的完整路径应该是数学公式中文公式中文算法英文算法偶然看到一篇算法文章，讲解了百度校园招聘之编程题的核心算法思路，我根据它又整理出自己的解题思路。

前言

从公式到算法之前的完整路径应该是：
数学公式->中文公式->中文算法->英文算法

偶然看到一篇算法文章，讲解了百度2016校园招聘之编程题的核心算法思路，我根据它又整理出自己的解题思路。

第一题

题目在原文中可以找到，这里就直接讲解具体的是如何做的。
首先，输入行号（整数n），接着是每行的数据
那可以定义函数为

/**
 * 解题函数
 * @param  {int}    $row_num 行号
 * @param  {Array}  $rows    每行的数据，其元素为string型，即一行数据
 * @return {Array}           每行数据在总排列中第几小，形如：[1, 3, 454]
 */
function question($row_num, $rows = []) {}

读取到了数据，就要一条一条先由string转化为数组，(在PHP中，string类型可以直接当数组使用，就可以免掉这一步)再计算其序号。我们将结果存储在数组$orders中。

现在我们拿到了

$row_num = 3;
$rows = [
    "abcdefghijkl",
    "bcdefghaijkl",
    "bcdefghijkla",
];

$orders = [];
foreach ($rows as $row) {
    $orders[] = get_order($row);
}

get_order方法即计算一行数据序号的方法。

依照公式，对于每一行数据，我们首先还是要遍历该数据中每个字符，再获取该字符在整个

$row = "abcdefghijkl";

序号= a在字段表中的大小 a在字符串的位号的阶乘 + b在字段表中的大小 b在字符串的位号的阶乘 + ... l在字段表中的大小 * l在字符串的位号的阶乘

我们这里遍历这个字符串，计算这个字母：
在字段表中的大小 * 在字符串的位号的阶乘

最后将所有字母的值都加起来，即是该字符串的序号。

$order = 0;
for($i = 1; $i =< 12; $i ++) {
    $order += get_rank($row[$i]) * get_jeicheng(12 - $i);
}
伪代码： 
$序号 = 0;
for($i = 1; $i =< 12; $i ++) {
    $序号 += 当前字母在字母表中的排序 * 字母在字符中的位号阶乘;
}

这里有一个优化点，即求阶乘。
原文中作者是直接计算阶乘，但其实我们已经可以确定，要用到的也就是十二个阶乘值，所以其实可以只计算一遍，将这十个阶乘值都存在数组中，实际计算过程中要用到哪个直接取就行了。

第二道题

第二道题里，大部分流程都和第一道题一样，只有核心算法那里不同。

定义函数为

/**
 * 解题函数
 * @param  {int} $row_num 行号
 * @param  {Array}  $rows 每行数据在总排列中第几小，形如：[1, 3, 454]
 * @return {Array}        每行的数据，其元素为string型，形如：["abcdefghijkl", "abcdeghijklf"]
 */
function question2($row_num, $orders = []) {}

现在我们拿到了

$row_num = 3;
$orders = [
    1
    3,
    454,
];

$rows = [];
foreach ($orders as $order) {
    $rows[] = get_row($order);
}

get_row($order);

获得了单个order。假设是 454 ，则根据公式，其对应字母为

题目中是12个字符，范围太大，原文中为了说明公式，将范缩小至4个字符。
假设只有abcd四个字符，单个order为9时，其对应字母为bcda。计算公式为
1、9 / 6 = 1 ... 3
2、3 / 2 = 1 ... 1
3、1 / 1 = 1 ... 0

所以我们可得到计算公式了：
从最高位开始，我们来将数字还原为字段
【abcd的排序都是从0位开始排】
1*3! + 1*2! + 1*1! + 0*0! = 9
我们现在来分解以上公式的意义，先来看1*3!
它的中文意义为
【abcd中第1位大的字母】*3!
abcd中，a排第0位、b排第1位、c排第2位、d排第3位，所以这里就是b作为字符串最高位的字母。【b***】
接下来来看1*2!
由于abcd四个字母中b已经确定下来了，所以现在它的中文意义为 【剩余字母中第1位大的字母】，即【acd中第1位大的字母】*2!
acd中，a排第0位、c排第1位、d排第2位，所以这里就是c作为字符串第3位的字母。
【bc**】
好了，道理都懂了，接下来依次类推，我们即可将字符串还原为【bcda】

所以，现在换成12位字母，算法要如何处理呢？
首先，假设我们拿到了order = 456；
接着，先计算最高位的字母，用order / 11!，获得其取整结果 和 取余结果。
根据其取整结果，即可知道最高位的字母在当前12字母的排位，我们可以确定当前字母了。
取余结果即可继续用于计算下一位字母。依次类推，即可将字符串还原回来。

伪代码：

$序号 = 456;
$字符串 = "";
$字母表 = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l"];
for($i = 11; $i >= 0; $i --) {
    $取整结果 = $序号 / $i 的阶乘;
    $取余结果 = $序号 % $i 的阶乘;
    $当前字母 = $字母表[$取整结果];
    更改字母表，把取出来的字母后面的字母都向前移动一位
    $字符串 .= $当前字母;
    $序号 = $取余结果;
}

第三题原文已经解释得很清楚了，这里就跳过。

第四题

第四题其实是四道算法题中最最复杂的，但原文作者可能是嫌解释太麻烦，反倒讲解得最少。这里就重点解析第四道题的算法。

首先，我们来还原题目。

以样例为例：
n = 2, a = 1, b = 3, x = 4，
则从[1, 3]中取出2个数的组合共有六对：
(1, 1), (1, 2), (1, 3),
(2, 2), (2, 3),
(3, 3)
其中，能组合成4，即相加为4的只有(1, 3), (2, 2)。

假设n=2, x=4的概率表示为rate(4, 2)，其概率计算公式为
取两个数和为4概率 = 取一个数为1的概率取一个数为3的概率 + 取一个数为2的概率取一个数为2的概率 + 取一个数为3的概率*取一个数为1的概率
rate(4, 2) = rate(1, 1)*rate(3, 1) + rate(2,1)*rate(2,1) + rate(3,1)*rate(1,1)
可以进一步归纳为
rate(4,2) = rate(1,1)*rate((4-1),1) + rate(2,1)*rate(4-2,1) + rate(3,1)*rate((4-3),1)
我们现在将数字替换为字母
rate(x,n) = rate(1,n-1)*rate(x-1,n-1) + rate(2,n-1)*rate(x-2,n-1) + rate(3,n-1)*rate(x-3,n-1)

现在，我们将[1, 3]区间替换成字母[a,b]，公式可以进一步归纳为
rate(x,n) = rate(a,1)*rate(x-a,n-1) + rate(a+1,1)*rate(x-(a+1),n-1) + ... + rate(b,1)*rate(x-b,n-1)
其中x-b>=a

至此，我们已可以确定，在区间[a,b]内取n个数其和为x的概率即为rate(x,n)，这可以处理为一个递归函数，当n=1时，即可确定其值。

伪代码

$区间下限 = a;
$区间上限 = b;
$区间数字个数 = $区间上限 - $区间下限 + 1;
function rate($x, $n) {
    // 当只取一个数时，其概率可以确定下来了
    if($n == 1) {
        if($x > $区间上限 || $x < $区间下限) {
            return 0;
        } else {
            return 1/$区间数字个数;
        }
    }

    $概率 = 0;
    for($i = $区间上限; $i < $区间下限; $i ++) {
        if($x-$i < $区间下限) break;

        $概率 += rate($i,1)*rate($x-$i, $n-1);
    }
    return $概率;
}

虽然我的解析过程过于啰嗦，但是它绝对够详细。如果有一天我忘记了这道算法，再回过头来看，也能保证自己可以看懂。

服务器托管 超融合服务器 中的注解 标签html的讲解 java的注解声明 java注解的作用

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/21547.html

相关文章

  • Java进阶之路

    摘要：探索专为而设计的将探讨进行了何种改进，以及这些改进背后的原因。关于最友好的文章进阶前言之前就写过一篇关于最友好的文章反响很不错，由于那篇文章的定位就是简单友好，因此尽可能的摒弃复杂的概念，只抓住关键的东西来讲，以保证大家都能看懂。 周月切换日历 一个可以进行周月切换的日历，左右滑动的切换月份，上下滑动可以进行周，月不同的视图切换，可以进行事件的标记，以及节假日的显示，功能丰富 Andr...

    sushi 评论0 收藏0

  • Java相关

    摘要：本文是作者自己对中线程的状态线程间协作相关使用的理解与总结，不对之处，望指出，共勉。当中的的数目而不是已占用的位置数大于集合番一文通版集合番一文通版垃圾回收机制讲得很透彻，深入浅出。 一小时搞明白自定义注解 Annotation（注解）就是 Java 提供了一种元程序中的元素关联任何信息和着任何元数据（metadata）的途径和方法。Annotion(注解) 是一个接口，程序可以通过...

    wangtdgoodluck 评论0 收藏0

  • Spring AOP就是这么简单啦

    摘要：是一种特殊的增强切面切面由切点和增强通知组成，它既包括了横切逻辑的定义也包括了连接点的定义。实际上，一个的实现被拆分到多个类中在中声明切面我们知道注解很方便，但是，要想使用注解的方式使用就必须要有源码因为我们要 前言 只有光头才能变强 上一篇已经讲解了Spring IOC知识点一网打尽！，这篇主要是讲解Spring的AOP模块~ 之前我已经写过一篇关于AOP的文章了，那篇把比较重要的知...

    Jacendfeng 评论0 收藏0

  • Java3y文章目录导航

    摘要：前言由于写的文章已经是有点多了，为了自己和大家的检索方便，于是我就做了这么一个博客导航。 前言 由于写的文章已经是有点多了，为了自己和大家的检索方便，于是我就做了这么一个博客导航。 由于更新比较频繁，因此隔一段时间才会更新目录导航哦～想要获取最新原创的技术文章欢迎关注我的公众号：Java3y Java3y文章目录导航 Java基础 泛型就这么简单 注解就这么简单 Druid数据库连接池...

    KevinYan 评论0 收藏0

  • Spring自动注入的简单实现

    摘要：有多种注入的策略，比如按照装配名称，或者是默认实现了接口或者抽象类的子类实例对象来注入。这个方法中，做了一些简单的判断，如果这个类本身就不是一个抽象类或者不是一个接口，那么这个类就是第一个合适的类。 申明：本文不是讲解Spring如何使用注解，本文只是通过一个简单的实现，来理解Spring是如何注入一个对象的。   用过Spring的同学都知道，Spring利用注解来实现依赖注入，使得...

    joyvw 评论0 收藏0

发表评论

登陆后可评论

0条评论

fevin

男|高级讲师
我要私信

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<