歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

2016百度春招筆試題

一、前言

前幾個星期的面試題都有點稀奇古怪,這個星期來一個正常點的題目,可是這題目可能對於個別人來說是如此的熟悉但又很陌生。因為那是我們高中時常做的題目,現在卻還給老師了。那讓我們好好回憶一下。

二、題目

6× 9的的方格中,起點的左下角,終點在右上角,從起點到終點,只能從下向上,從左向右走,問一共有多少種不同的走法。
A. 4200
B. 5005
C. 1005
D. 以上都不正確

三、解題

當然這道題有點異議,為什麼這樣說呢?因為題目沒有明確說明是按方格來走還是按照線來走。

首先我們嘗試下按方格來走,得到的結果是什麼?要想知道結果,我們需要知道題目想考察我們什麼,很顯然,題目其實考察我們高中非常熟悉的排列組合的問題,完完全全就是高中的題目,可是現在可能對於我們來說又是如此的陌生。這道題如果按方格來走的話,結果就是 C(5, 13) = 1287 。13 是哪裡來的,5 又是哪裡來的,思考之前,我們可以先看一張圖。

根據圖片可以看出,13 就從左下角到右上角一個要走的格子數,5 就是走的行數,為什麼是從 13 個中選 5 個來組合就知道一共有多少種走法呢?其實因為我們只要知道了行數的 5 個的位置我們就知道列數 8 個格子的位置,當然你也可以 13 選 8 ,結果都是一樣的。為啥一樣,貼一張圖來回憶起我們遺忘的記憶吧。

因此,按走的是格子來算,結果是 C(5, 13) = C(8, 13) = 1287

其實這道題目想表達的意思是按線來算的,可是原理還是跟上面一樣的

因此,按走的是線來算,結果是 C(6, 15) = C(9, 15) = 5005

四、類似的題目

其實這種題目很多大企業大公司都會作為面試題,比如我們來看看下面兩道類似的題目:

1.阿裡巴巴的筆試題目

說 16 個人按順序去買燒餅,其中 8 個人每人身上只有一張 5 塊錢,另外 8 個人每人身上只有一張 10 塊錢。燒餅 5 塊一個,開始時燒餅店老板身上沒有錢。16 個顧客互相不通氣,每人只買一個。問這 16 個人共有多少種排列方法能避免找不開錢的情況出現。

假設付 5 塊錢的人都是 1,付 10 塊錢的人都是 0 ,則排隊順序可能為1111111100000000 或各種 1 與 0 的排列組合,那麼總共的排列順序就是C(16,8),這裡跟上面的都是一樣的,但是為了避免找不開錢,則從左到右時,不能有 0 的數目小於 1 的數目的情況出現。如果出現這種情況,則必然存在第2m+1 個數目時(即某個奇數數目),前 2m+1 個數目中有 m+1個0,m 個 1 。那麼在剩余的 16-2m-1 個數目中,即 15-2m 個數目中,必然存在著 8-m-1 個 0 ,8-m 個 1 ,即 7-m 個 0 ,8-m 個 1 。現在再把剩余的 16-2m-1 個數目中的 0 與 1 互換,則為 8-m 個0,7-m 個 1 ,這個時候,整個數列就變為了 9 個 0,7 個 1 。所以一個不符合要求的數目為 9 個 0 和 7 個 1 組成。因此,結果為 C(16,8)-C(16,9)= 12870 - 11440 = 1430

2.2012騰訊實習招聘筆試題

在圖書館一共6個人在排隊,3個還《面試寶典》一書,3個在借《面試寶典》一書,圖書館此時沒有了面試寶典了,求他們排隊的總數?

其實這些問題可以轉化為下面的格路問題,從左下角到右上角,不能是對角線,有多少種方案。不過加了限制條件而已,這道題跟阿裡巴巴那道面試題一樣,結果為:結果為 C(6,3)-C(6,4)= 20 - 15 = 5

五、編程

GitHub:https://github.com/TwoWater/Interview/tree/master/Interview


package com.liangdianshui;

/**
 * <p>
 * 6× 9的的方格中,起點的左下角,終點在右上角,從起點到終點,只能從下向上,從左向右走,問一共有多少種不同的走法。
 *  A. 4200 
 *  B. 5005
 *  C. 1005 
 *  D. 以上都不正確
 * </p>
 * 
 * @author liangdianshui
 *
 */
public class Catalan {

    public static void main(String[] args) {
        System.out.println(func(6, 9));
    }

    public static int func(int m, int n) {

        if (m < 1 || n < 1) {
            return 1;
        }

        return func(m - 1, n) + func(m, n - 1);
    }
}

Copyright © Linux教程網 All Rights Reserved