holmescn

金蟲 (正式寫手)

程序強帖: 37
應(yīng)助: 1 (幼兒園)
金幣: 1918.8
散金: 275
紅花: 1
帖子: 699
在線: 102.6小時
蟲號: 913482
注冊: 2009-11-26
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結(jié)構(gòu)

[交流] Euler 工程第十五題：從左上角到右下角有多少條路？已有4人參與

哈哈，題目越來越有意思了。下面這個題是個排列組合的題目。當(dāng)然，不用那東西也能解出來。大家來玩玩吧！

說有一個2x2的格子，從左上角到右下角有6條可行的路線（要求不要回頭）如圖：

那么一個20x20的格子有多少條路線呢？

記得，不只可以寫代碼，還可以做分析。大家一起來玩吧！

[ Last edited by holmescn on 2011-5-22 at 20:40 ]

回復(fù)此樓

» 猜你喜歡

一志愿中海洋材料工程專碩330分求調(diào)劑已經(jīng)有3人回復(fù)
328求調(diào)劑，英語六級551，有科研經(jīng)歷已經(jīng)有9人回復(fù)
【同濟軟件】軟件（085405）考研求調(diào)劑已經(jīng)有3人回復(fù)
一志愿吉林大學(xué)材料學(xué)碩321求調(diào)劑已經(jīng)有4人回復(fù)
267一志愿南京工業(yè)大學(xué)0817化工求調(diào)劑已經(jīng)有7人回復(fù)
一志愿華中科技大學(xué)，080502，354分求調(diào)劑已經(jīng)有3人回復(fù)
一志愿中國海洋大學(xué)，生物學(xué)，301分，求調(diào)劑已經(jīng)有4人回復(fù)
一志愿武理材料305分求調(diào)劑已經(jīng)有6人回復(fù)
材料專碩英一數(shù)二306 已經(jīng)有3人回復(fù)
085600材料與化工調(diào)劑 324分已經(jīng)有7人回復(fù)

» 本主題相關(guān)價值貼推薦，對您同樣有幫助:

Euler 工程第四十四題已經(jīng)有4人回復(fù)
Euler 工程第四十二題: 三角詞已經(jīng)有4人回復(fù)
Euler 工程第四十一題已經(jīng)有5人回復(fù)
Euler 工程第三十八題已經(jīng)有9人回復(fù)
Euler 工程第三十七題已經(jīng)有6人回復(fù)
Euler 工程第三十六題：已經(jīng)有18人回復(fù)
Euler 工程第三十五題：循環(huán)質(zhì)數(shù) 已經(jīng)有16人回復(fù)
Euler 工程第三十二題：pandigital 數(shù) 已經(jīng)有3人回復(fù)
Euler 工程第三十一題: 換零錢已經(jīng)有10人回復(fù)
Euler 工程第三十題已經(jīng)有12人回復(fù)
Euler 工程第廿九題：有多少不同的項? 已經(jīng)有30人回復(fù)
Euler 工程第廿八題：旋轉(zhuǎn)矩陣對角線的和已經(jīng)有6人回復(fù)
Euler 工程第廿七題：系數(shù)的積已經(jīng)有15人回復(fù)
Euler 工程第廿六題：最長的循環(huán)節(jié) 已經(jīng)有9人回復(fù)
Euler 工程第廿五題：Fibonacci 數(shù)列第一個包含1000個數(shù)字的項已經(jīng)有3人回復(fù)
Euler 工程第廿四題：全排列的第100萬項已經(jīng)有19人回復(fù)
Euler 工程第廿三題：已經(jīng)有16人回復(fù)
Euler 工程第廿二題: 姓的總分已經(jīng)有13人回復(fù)
Euler 工程第廿題：100! 的各項和已經(jīng)有5人回復(fù)
Euler 工程第十九題：每月第一天是周日的天數(shù) 已經(jīng)有4人回復(fù)
Euler 工程第十八題：三角陣上最大的和已經(jīng)有12人回復(fù)
Euler 工程第十六題：2的1000次方的各項和已經(jīng)有14人回復(fù)
Euler 工程第14題：找最長的數(shù)列已經(jīng)有9人回復(fù)
Euler 工程第十一題：相鄰元素乘積最大已經(jīng)有10人回復(fù)
Euler 工程第三題：尋找600851475143的最大質(zhì)因子已經(jīng)有18人回復(fù)

1樓 2011-05-22 20:37:06

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

huycwork

金蟲 (著名寫手)

程序強帖: 22
應(yīng)助: 0 (幼兒園)
金幣: 953
散金: 663
紅花: 8
沙發(fā): 13
帖子: 1080
在線: 264.1小時
蟲號: 1257243
注冊: 2011-04-06
專業(yè): 金融學(xué)

★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
余澤成(金幣+2): 謝謝參與交流！ 2011-05-22 23:33:29

點A(n, n)的通道數(shù)是A(n-1, n)和A(n, n-1)條數(shù)之和，即A(n, n) = A(n-1, n)+A(n, n-1)。這個題目就是咱曾經(jīng)做過的f(m, n) = f(m-1, n) + f(m, n-1)的題目，只是初始條件是f(1, n) = 1，f(m, 1) = 1。
不過，這個題是傳說中的高考題，題解為m+n里面選出m或n條邊的組合數(shù)C(m+n)m。

贊一下(2人)

回復(fù)此樓

漩渦的中心有一塊空地，空空的。

2樓2011-05-22 22:41:39

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

huycwork

金蟲 (著名寫手)

程序強帖: 22
應(yīng)助: 0 (幼兒園)
金幣: 953
散金: 663
紅花: 8
沙發(fā): 13
帖子: 1080
在線: 264.1小時
蟲號: 1257243
注冊: 2011-04-06
專業(yè): 金融學(xué)

★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
余澤成(金幣+3, 程序強帖+1): 鼓勵交流！ 2011-05-22 23:34:32

C++實現(xiàn)的各種解法：

CODE:

#include 

enum {BUFSZ = 20};

//迭代f(m, n) = f(m, n-1)+f(m-1, n)的版本

double eular15(int m = 20, int n = 20){

        if(m < n){

                std::swap(m, n);

        }

        double buf[BUFSZ];

        for(int i = 0; i < BUFSZ; ++i)

                buf[i] = 1;

        for(int i = 0; i < n; ++i){

                buf[i] += buf[i];

                for(int j = i; j < m - 1; ++j){

                        buf[j+1] = buf[j] + buf[j+1];

                }

        }

        return buf[m-1];

}

//組合數(shù)直接計算版本，m+n里面選出m個和選出n個是一樣的

double _eular15(int m = 20, int n = 20){

        double r1 = 1, r2 = 1;

        for(int i =  n + 1; i <= m+n; ++i){

                r1 *= i;

        }

        for(int i = 1; i <= n; ++i){

                r2 *= i;

        }

        return r1/r2;

}

int main(){

         std::cout<
         std::cout<<_eular15()<
}

贊一下(2人)

回復(fù)此樓

漩渦的中心有一塊空地，空空的。

3樓2011-05-22 22:48:27

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

libralibra

至尊木蟲 (著名寫手)

驃騎將軍

程序強帖: 40
應(yīng)助: 817 (博后)
金幣: 12914.1
紅花: 64
帖子: 2238
在線: 287.3小時
蟲號: 696514
注冊: 2009-02-05
專業(yè): 計算機軟件

★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
jjdg(金幣+2): 辛苦了 2011-05-23 01:32:29
余澤成(程序強帖+1): 2011-05-23 19:22:42

分析,所有到a點的方法是"到b點方法+到c點方法之和"
遞歸分析回去發(fā)現(xiàn),這正是matlab中的pascal矩陣

于是我偷懶了

matlab code

CODE:

 %% How many routes are there through a 20×20 grid?

function result = euler15()

tic;

a = pascal(21);

result = a(end,end);

toc;

end

結(jié)果+時間

CODE:

% Elapsed time is 0.008664 seconds.

% ans =

%               137846528820 

[ Last edited by libralibra on 2011-5-23 at 00:21 ]

贊一下(3人)

回復(fù)此樓

matlab/VB/python/c++/Java寫程序請發(fā)QQ郵件:790404545@qq.com

4樓2011-05-23 00:19:06

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

sudo

木蟲 (正式寫手)

程序強帖: 16
應(yīng)助: 6 (幼兒園)
金幣: 1297.6
散金: 1486
紅花: 20
帖子: 588
在線: 641小時
蟲號: 1211394
注冊: 2011-02-24
性別: GG
專業(yè): 文藝美學(xué)

★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
余澤成(金幣+3): 辛苦了！ 2011-05-23 19:23:33

引用回帖:

Originally posted by huycwork at 2011-05-22 22:41:39:
點A(n, n)的通道數(shù)是A(n-1, n)和A(n, n-1)條數(shù)之和，即A(n, n) = A(n-1, n)+A(n, n-1)。這個題目就是咱曾經(jīng)做過的f(m, n) = f(m-1, n) + f(m, n-1)的題目，只是初始條件是f(1, n) = 1，f(m, 1) = 1。
不過，這個 ...

2樓應(yīng)該得程序強帖啊~！數(shù)學(xué)解最美~

我再詳細(xì)補充解釋一下吧：

格子數(shù)m行n列的時候，所謂的從左上角到右下角的路線，需要且僅僅需要經(jīng)過m+n條線段（否則走的就是“彎路”），其中n條是橫線段，m條是豎線段，而且，如果能確定哪幾步經(jīng)過的是橫線段，那么另外的步驟必然走的是豎線段，故所有組合數(shù)為

C(m+n, m) 或者 C(m+n, n)

對于題目中的行列格子數(shù)相等的情況，答案簡化為C(2n, n)

對于20x20的格子，路線總數(shù)為C(40, 20)

再形象一點說明，以1樓2x2的格子為例，起點到終點，經(jīng)過的線段數(shù)為4條，其中2條橫線段，2條豎線段，那么組合可以為：

橫，橫，豎，豎
橫，豎，橫，豎
橫，豎，豎，橫
豎，橫，橫，豎
豎，橫，豎，橫
豎，豎，橫，橫

一共為C(4, 2)=(4*3)/(2*1)=6種走法~

PS：

囧，剛才沒看見3樓，上面當(dāng)我什么都沒說吧.....

[ Last edited by sudo on 2011-5-23 at 13:51 ]

贊一下(2人)

回復(fù)此樓

5樓2011-05-23 13:47:02

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

wangww2011

木蟲 (著名寫手)

程序強帖: 13
應(yīng)助: 11 (小學(xué)生)
金幣: 4023.1
散金: 2709
紅花: 18
沙發(fā): 1
帖子: 1915
在線: 1537.1小時
蟲號: 772953
注冊: 2009-05-17
性別: GG
專業(yè): 凝聚態(tài)物性 II ：電子結(jié)構(gòu)

★ ★ ★ ★
小木蟲(金幣+0.5):給個紅包，謝謝回帖
余澤成(金幣+3, 程序強帖+1): 鼓勵交流！ 2011-05-23 19:23:58

樓上的都很快阿
我用的笨辦法二維數(shù)組就是實現(xiàn)起來簡單，結(jié)果

CODE:

137846528820

elapsed time=0.000000 seconds.

代碼：

CODE:

#include 

#include 

#include 

#define TIMERSTART clock_t start_time,stop_time;double elapsed_time;start_time = clock();

#define TIMERSTOP stop_time = clock();elapsed_time=(double)(stop_time-start_time)/CLOCKS_PER_SEC;printf("elapsed time=%f seconds.\n",elapsed_time);

long long euler15(int n){

  int i,j;

  long long a[n+1][n+1];

  for(i=0;i
     a[i][0]=1;

     a[0][i]=1;

  }

  for(i=1;i
      for(j=1;j
         a[i][j]=a[i-1][j]+a[i][j-1];

      }

  }

  return a[n][n];

}

int main(void){ 

 TIMERSTART;

 printf("%lld\n",euler15(20));

 TIMERSTOP;

  return 0;

}

贊一下(2人)

回復(fù)此樓

6樓2011-05-23 18:23:26

已閱回復(fù)此樓關(guān)注TA 給TA發(fā)消息送TA紅花 TA的回帖

最具人氣熱帖推薦 [查看全部]	作者	回/看	最后發(fā)表

[考研] 085601專碩，總分342求調(diào)劑，地區(qū)不限 +5	share_joy 2026-03-16	5/250	2026-03-18 14:48 by haxia
[考研] 0817 化學(xué)工程 299分求調(diào)劑有科研經(jīng)歷有二區(qū)文章 +7	rare12345 2026-03-18	7/350	2026-03-18 14:31 by laoshidan
[考研] 280求調(diào)劑 +6	咕嚕曉曉 2026-03-18	7/350	2026-03-18 11:25 by 無際的草原
[考研] 308求調(diào)劑 +4	是Lupa啊 2026-03-16	4/200	2026-03-17 17:12 by ruiyingmiao
[考研] 材料工程專碩274一志愿211求調(diào)劑 +6	薛云鵬 2026-03-15	6/300	2026-03-17 11:05 by 學(xué)員h26Tkc
[考研] 考研調(diào)劑 +3	淇ya_~ 2026-03-17	5/250	2026-03-17 09:25 by Winj1e
[考研] 0703化學(xué)調(diào)劑，求各位老師收留 +8	秋有木北 2026-03-14	8/400	2026-03-16 15:21 by 哦哦123
[考研] 070303 總分349求調(diào)劑 +3	LJY9966 2026-03-15	5/250	2026-03-16 14:24 by xwxstudy
[考博] 東華理工大學(xué)化材專業(yè)26屆碩士博士申請 +6	zlingli 2026-03-13	6/300	2026-03-15 20:00 by ryzcf
[考研] 材料與化工 323 英一+數(shù)二+物化，一志愿：哈工大本人本科雙一流 +4	自由的_飛翔 2026-03-13	5/250	2026-03-14 19:39 by hmn_wj
[考研] 中科大材料專碩319求調(diào)劑 +3	孟鑫材料 2026-03-13	3/150	2026-03-14 18:10 by houyaoxu
[考研] 265求調(diào)劑 +4	威化餅07 2026-03-12	4/200	2026-03-14 17:23 by userper
[考研] ［0860］321分求調(diào)劑，ab區(qū)皆可 +4	寶貴熱 2026-03-13	4/200	2026-03-13 22:01 by 星空星月
[考研] 311求調(diào)劑 +3	冬十三 2026-03-13	3/150	2026-03-13 20:41 by JourneyLucky
[考研] 求調(diào)劑 +5	一定有學(xué)上- 2026-03-12	5/250	2026-03-13 18:31 by ms629
[考研] 工科材料085601 279求調(diào)劑 +8	困于星晨 2026-03-12	10/500	2026-03-13 15:42 by ms629
[考研] 328化工專碩求調(diào)劑 +4	。，。，。，。i 2026-03-12	4/200	2026-03-13 14:44 by JourneyLucky
[考研] 085600材料與化工 309分請求調(diào)劑 +7	dtdxzxx 2026-03-12	8/400	2026-03-13 14:43 by jxchenghu
[考研] 材料301分求調(diào)劑 +5	Liyouyumairs 2026-03-12	5/250	2026-03-13 14:42 by JourneyLucky
[考研] 308求調(diào)劑 +3	是Lupa啊 2026-03-12	3/150	2026-03-13 14:30 by 求調(diào)劑zz