| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1169 人关注过本帖
标题:求问百度百科上“时间和空间最优算法”的杨辉三角算法
只看楼主 加入收藏
TimVan
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2016-10-27
结帖率:0
收藏
已结贴  问题点数:10 回复次数:5 
求问百度百科上“时间和空间最优算法”的杨辉三角算法
程序代码:
/* yh-rt1.c - 时间和空间最优算法 */
#include <stdio.h>
#include <stdlib.h>
int main()
{
    int s = 1, h;                    // 数值和高度
    int i, j;                        // 循环计数
    
    printf("请输入你需要的杨辉三角的行数\n");                   // 输出第一个 1
    scanf("%d", &h);                 // 输入层数
    printf("1\n");                   // 输出第一个 1
    
    
    for (i = 2; i <= h; s = 1, i++)         // 行数 i 从 2 到层高
    {
        printf("1");                // 第一个 1
        
        for (j = 1; j <= i - 2; j++) // 列位置 j 绕过第一个直接开始循环
            //printf("%d ", (s = (i - j) / j * s));
            printf("%d", (s = (i - j) * s / j));        //   这一行实在看不懂
        
        printf("1\n");               // 最后一个 1,换行
    }
    
    getchar();                       // 暂停等待
    return 0;
}

            

printf("%d", (s = (i - j) * s / j)); ,就是这一行实在看不懂
我会用二项式定理,以及上一行的对应数,以及前一列的对应数相加的方法求解……然而这个摘自百度百科的算法实在看不懂
求热心人帮忙

另这是求直角的杨辉三角,效果如下:
    1
    1    1
    1    2    1
    1    3    3    1
    1    4    6    4    1
搜索更多相关主题的帖子: 百度百科 杨辉三角 空间 
2016-10-27 17:08
TimVan
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2016-10-27
收藏
得分:0 
求好心人帮一下忙...
2016-10-28 02:08
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:5 
观察每行的数字迭代规律可得(i,j)=(i,j-1)*(j-i)/j=s*(j-i)/j

这应该是从现象总结的规律。如果要证明,从(i,j)=(i-1,j-1)+(i-1,j)=...的方向迭代过去在迭代回来估计就能证明了。不过我脑子转不过来,就不去证明了

φ(゜▽゜*)♪
2016-10-28 08:04
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9007
专家分:53942
注 册:2011-1-18
收藏
得分:5 
一言以蔽之:杨辉三角中第m行第n列的值 就是 组合数c(m,n)

以第4行为例:
第0列是 1
第1列是 1 * 4/1
第2列是 1 * 4/1 * 3/2
第3列是 1 * 4/1 * 3/2 * 2/3
第4列是 1 * 4/1 * 3/2 * 2/3 * 1/4

故有代码:
程序代码:
#include <stdio.h>

int main( void )
{
    unsigned h = 5; // 高度
    for( unsigned m=0; m!=h; ++m )
    {
        putchar( '1' );
        for( unsigned n=1, c=1; n<=m; ++n )
        {
            c = c*(m-n+1)/n;
            printf( " %u", c );
        }
        putchar( '\n' );
    }
}

2016-10-28 09:00
TimVan
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2016-10-27
收藏
得分:0 
回复 4楼 rjsp
感谢斑竹
我再思考思考……
2016-11-01 02:10
TimVan
Rank: 1
等 级:新手上路
帖 子:4
专家分:0
注 册:2016-10-27
收藏
得分:0 
回复 3楼 书生牛犊
感谢……
我也觉得要用数学归纳法
2016-11-01 02:11
快速回复:求问百度百科上“时间和空间最优算法”的杨辉三角算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.016172 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved