应《网络安全法》要求，自2017年10月1日起，未进行实名认证将不得使用互联网跟帖服务。为保障您的帐号能够正常使用，请尽快对帐号进行手机号验证，感谢您的理解与支持！

24小时热门版块排行榜    

小木虫论坛-学术科研互动平台 » 计算模拟区 » 程序语言 » 其它 » Euler 工程 第十五题：从左上角到右下角有多少条路？
61/1返回列表
查看: 1827  |  回复: 5
只看楼主 @他人 存档 新回复提醒 (忽略) 收藏    在APP中查看
本帖产生 3 个 程序强帖 ，点击这里进行查看

holmescn

金虫 (正式写手)

[交流] Euler 工程 第十五题：从左上角到右下角有多少条路？ 已有4人参与

哈哈，题目越来越有意思了。下面这个题是个排列组合的题目。当然，不用那东西 也能解出来。大家来玩玩吧！

说有一个2x2的格子，从左上角到右下角有6条可行的路线（要求不要回头）如图：



那么一个20x20的格子有多少条路线呢？

记得，不只可以写代码，还可以做分析。大家一起来玩吧！

[ Last edited by holmescn on 2011-5-22 at 20:40 ]
回复此楼

» 猜你喜欢

» 本主题相关价值贴推荐，对您同样有帮助:
1楼 2011-05-22 20:37:06
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+2): 谢谢参与交流！ 2011-05-22 23:33:29
点A(n, n)的通道数是A(n-1, n)和A(n, n-1)条数之和，即A(n, n) = A(n-1, n)+A(n, n-1)。这个题目就是咱曾经做过的f(m, n) = f(m-1, n) + f(m, n-1)的题目，只是初始条件是f(1, n) = 1，f(m, 1) = 1。
不过，这个题是传说中的高考题，题解为m+n里面选出m或n条边的组合数C(m+n)m。
赞一下(2人) 回复此楼
漩涡的中心有一块空地，空空的。
2楼2011-05-22 22:41:39
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

huycwork

金虫 (著名写手)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 鼓励交流！ 2011-05-22 23:34:32
C++实现的各种解法：
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];
}
//组合数直接计算版本，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人) 回复此楼
漩涡的中心有一块空地，空空的。
3楼2011-05-22 22:48:27
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

libralibra

至尊木虫 (著名写手)

骠骑将军
★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
jjdg(金币+2): 辛苦了 2011-05-23 01:32:29
余泽成(程序强帖+1): 2011-05-23 19:22:42
分析,所有到a点的方法是"到b点方法+到c点方法之和"
递归分析回去发现,这正是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

结果+时间
CODE:
% Elapsed time is 0.008664 seconds.
% ans =
%               137846528820

[ Last edited by libralibra on 2011-5-23 at 00:21 ]
赞一下(3人) 回复此楼
matlab/VB/python/c++/Java写程序请发QQ邮件:790404545@qq.com
4楼2011-05-23 00:19:06
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

sudo

木虫 (正式写手)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3): 辛苦了！ 2011-05-23 19:23:33
引用回帖:
Originally posted by huycwork at 2011-05-22 22:41:39:
点A(n, n)的通道数是A(n-1, n)和A(n, n-1)条数之和，即A(n, n) = A(n-1, n)+A(n, n-1)。这个题目就是咱曾经做过的f(m, n) = f(m-1, n) + f(m, n-1)的题目，只是初始条件是f(1, n) = 1，f(m, 1) = 1。
不过，这个 ...

2楼应该得程序强帖啊~！数学解最美~

我再详细补充解释一下吧：

格子数m行n列的时候，所谓的从左上角到右下角的路线，需要且仅仅需要经过m+n条线段（否则走的就是“弯路”），其中n条是横线段，m条是竖线段，而且，如果能确定哪几步经过的是横线段，那么另外的步骤必然走的是竖线段，故所有组合数为

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

对于题目中的行列格子数相等的情况，答案简化为C(2n, n)

对于20x20的格子，路线总数为C(40, 20)

再形象一点说明，以1楼2x2的格子为例，起点到终点，经过的线段数为4条，其中2条横线段，2条竖线段，那么组合可以为：

横，横，竖，竖
横，竖，横，竖
横，竖，竖，横
竖，横，横，竖
竖，横，竖，横
竖，竖，横，横

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

PS：囧，刚才没看见3楼，上面当我什么都没说吧.....

[ Last edited by sudo on 2011-5-23 at 13:51 ]
赞一下(2人) 回复此楼
5楼2011-05-23 13:47:02
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

wangww2011

木虫 (著名写手)
★ ★ ★ ★
小木虫(金币+0.5):给个红包，谢谢回帖
余泽成(金币+3, 程序强帖+1): 鼓励交流！ 2011-05-23 19:23:58
楼上的都很快阿
我用的笨办法 二维数组 就是实现起来简单，结果
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人) 回复此楼
6楼2011-05-23 18:23:26
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
相关版块跳转 我要订阅楼主 holmescn 的主题更新
61/1返回列表
普通表情 龙 兔 虎 猫 高级回复 (可上传附件)
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考博] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +4 khieu8v8m0 2026-02-22 4/200 2026-02-23 06:46 by jsjzfl
[论文投稿] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +3 w89i99eaeh 2026-02-22 4/200 2026-02-23 06:36 by w4l55oybr1
[博后之家] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +4 khieu8v8m0 2026-02-22 5/250 2026-02-23 06:34 by w4l55oybr1
[公派出国] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +3 khieu8v8m0 2026-02-22 5/250 2026-02-23 06:29 by w4l55oybr1
[硕博家园] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +4 khieu8v8m0 2026-02-22 8/400 2026-02-23 06:24 by w4l55oybr1
[考研] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +4 usprnugpzw 2026-02-21 10/500 2026-02-23 04:58 by 5jlh3qtdvx
[论文投稿] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +3 khieu8v8m0 2026-02-22 6/300 2026-02-23 02:08 by 5jlh3qtdvx
[考博] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +5 3dfhjxgsh7 2026-02-22 6/300 2026-02-23 02:04 by 5jlh3qtdvx
[教师之家] 版面费该交吗 +7 苹果在哪里 2026-02-22 8/400 2026-02-22 22:37 by otani
[基金申请] 基金正文30页指的是报告正文还是整个申请书 +5 successhe 2026-02-16 6/300 2026-02-22 21:38 by 山西悬空寺空悬�
[基金申请] 面上可以超过30页吧？ +4 阿拉贡aragon 2026-02-22 4/200 2026-02-22 21:22 by 山西悬空寺空悬�
[教师之家] 为什么中国大学教授们水了那么多所谓的顶会顶刊，但还是做不出宇树机器人？ +5 欢乐颂叶蓁 2026-02-21 5/250 2026-02-22 21:15 by 山西悬空寺空悬�
[论文投稿] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +4 usprnugpzw 2026-02-21 6/300 2026-02-22 19:48 by w89i99eaeh
[考研] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +3 3dfhjxgsh7 2026-02-22 4/200 2026-02-22 16:52 by khieu8v8m0
[找工作] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +3 usprnugpzw 2026-02-22 3/150 2026-02-22 16:37 by khieu8v8m0
[公派出国] 售SCI一区文章，我:8 O5 51O 54,科目齐全,可+急 +3 usprnugpzw 2026-02-21 4/200 2026-02-22 16:27 by khieu8v8m0
[基金申请] “人文社科而论，许多学术研究还没有达到民国时期的水平” +4 苏东坡二世 2026-02-18 5/250 2026-02-22 16:07 by liangep1573
[基金申请] 什么是人一生最重要的？ +4 瞬息宇宙 2026-02-21 4/200 2026-02-22 11:44 by huagongfeihu
[基金申请] 今年春晚有几个节目很不错，点赞！ +11 瞬息宇宙 2026-02-16 12/600 2026-02-21 21:14 by lq493392203
[基金申请] 体制内长辈说体制内绝大部分一辈子在底层，如同你们一样大部分普通教师忙且收入低 +9 瞬息宇宙 2026-02-20 12/600 2026-02-21 10:39 by 欢乐颂叶蓁
信息提示
关闭
请填处理意见
关闭