騰訊的筆試題一道

?

搜羅了一些騰訊的筆試題目?

題目是這樣的：

?在如下8*6的矩陣中，請計算從A移動到B一共有多少種走法？要求每次只能向上揮著向右移動一格，并且不能經過P；

?	?	?	?	?	?	?	B
?	?	?	?	?	?	?	?
?	?	?	P	?	?	?	?
?	?	?	?	?	?	?	?
?	?	?	?	?	?	?	?
A	?	?	?	?	?	?	?

A）492

B）494

C）496

D）498

?

下面是博兄的思路，很給力。

倒數1???? 1??? =??? 1

倒數第2列?? 1+1+1+1+1=? 5

倒數第三列? 5+4+3+2+1= 15

這道題目完全可以這么理解?? 如果翻轉一下你會發現

p點先忽略?

發現什么了? ？

只要?到了最后一排就相當于接觸到了b?

所以???? 根據題意??

倒數1???? 1??? =??? 1
倒數2?? 1+1+1+1+1=? 5
倒數3?? 5+4+3+2+1=? 15
倒數4? 15+10+6+3+1= 35
倒數5? 35+20+10+4+1=70
倒數6? 70+35+15+5+1=126
倒數7? 126+56+21+6+1=210
倒數8? 210+84+28+7+1=330
全部相加 1+5+15+35+70+126+210+330=792
根據題意從A到B一共有792種走法
減去經過P的就是要求的那部分
經過p的?
可以根據倒數排數推出 從p點出發一共有15種走法
然后? 由圖中可以分析出? 能夠到達p點的路徑有20種
15*20=300
這就是經過p點所有路徑
那么? 792-300=492?

2。排列組合? C（12,7） - C(6,4)*C(6,3) = 492;

初看這個式子感覺看不太懂，稍微提示下，a點到b一點不論怎么走都要走12步，其中行必須走7步，列必須走5步。

C（12,7） = C（12,5）；

3.遞歸程序解法

下面我用程序進行驗證。

?

// shuju.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
using namespace  std;int numcout = 0;#define    px   2    //p點的x，y坐標
#define    py   3void fun(int m,int n)
{if(m==0 &&n==7){numcout++; return;}//進行判斷去除p點位于數組的2，3位置if(m==px&&n==py-1){m = m-1;     }if(m==px+1&&n==py){n = n+1;}if(m>=0 ){fun(m-1,n);}if(n<=6){fun(m,n+1);}
}int main(int argc, char* argv[])
{fun(5,0);           cout<<numcout;return 0;
}

?

?

?

思考，假如這道題規定按對角線斜著也能走，那們a點到b點有多少種走法呢？

?