首页 > 代码库 > 杨辉三角型----衍生
杨辉三角型----衍生
还是昨天那个题,http://www.cnblogs.com/092-zhang/p/4148925.html
昨天那个程序的时间复杂度在本人能力范围内基本不可再优化,空间复杂度为O(2^n),导致有随着输入规模的增大而增大。
后突然发现此图是杨辉三角的变种,过通过数学方法优化算法。
1 /* Unusual Triangle */ 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <time.h> 5 6 int count2N(long n) //计算n的阶乘中包含‘因子2‘的个数 7 { 8 int rlt=0; 9 10 while(n/2 > 0)11 {12 n = n/2;13 rlt += n;14 }15 16 return rlt;17 }18 19 int main(void)20 {21 long n;22 long i, j;23 char *outputStr[2] = {" ","* "};24 int isStar;25 clock_t start, finish;26 double duration;27 28 start = clock();29 while(scanf("%d", &n)!= EOF && n != 0)30 {31 printf("The Triangle Scale is %d:\n", n);32 33 n = 1<<(n-1); //确定规模34 for(i=0; i<n; i++) //循环打印35 {36 isStar = count2N(i);37 for(j=i;j<n;j++) //打印前面的空格38 printf(*outputStr+1);39 40 for(j=0; j<=i; j++) //打印花印41 if(isStar-count2N(j)-count2N(i-j) <= 0)42 printf(*(outputStr+1));43 else44 printf(*outputStr);45 printf("\n");46 }47 }48 49 finish = clock();50 duration = (double)(finish - start) / CLOCKS_PER_SEC;51 printf( "%f seconds\n", duration );52 53 return EXIT_SUCCESS;54 }
改过之后没有输入规模的限制,然后效率上个人也很满意。
杨辉三角型----衍生
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。