首页 > 代码库 > 杨辉三角型----衍生

杨辉三角型----衍生

2024-08-06 16:32:32   220人阅读

还是昨天那个题，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 }

改过之后没有输入规模的限制，然后效率上个人也很满意。

 

杨辉三角型----衍生


联系
我们