打印菱形以及斐波納契數(shù)列的幾種解法介紹
更新時(shí)間：2013年06月26日 15:22:33 作者：
本篇文章是對打印菱形及斐波納契數(shù)列的幾種解法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
1、編寫程序，打印*菱形
推出第i行要打印的空白個(gè)數(shù)及*號個(gè)數(shù)，用for循環(huán)依次打印各行
#include<stdio.h>
//總共要打印2*n-1行，逐行打印
void print1(int n)
{
int i,j;
for(i=1;i<=n;i++){//打印1至n行
for(j=1;j<=n-i;j++)//打印n-i個(gè)空格
printf(" ");
for(j=1;j<=2*i-1;j++)//打印2*i-1個(gè)*號
printf("*");
printf("\n");
}
for(;i<2*n;i++){//打印n+1至2*n-1行，同(2*n-i)行
for(j=1;j<=n-(2*n-i);j++)
printf(" ");
for(j=1;j<=2*(2*n-i)-1;j++)
printf("*");
printf("\n");
}
}
void main()
{
int n;//n是菱形邊上*號的個(gè)數(shù)
printf("enter n:");
scanf("%d",&n);
print1(n);
}
2、斐波納契數(shù)列（Fibonacci Sequence），又稱黃金分割數(shù)列，指的是這樣一個(gè)數(shù)列：
1、1、2、3、5、8、13、21、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F(0)=0，F(xiàn)(1)=1，F(xiàn)(n)=F(n-1)+F(n-2)（n>=2，n∈N*）.編寫程序，輸出F(20)的值。
這里給出四種不同的解法，注意遞歸和改進(jìn)的遞歸效率上有很大區(qū)別。
#include<stdio.h>
#include<math.h>
#include<time.h>
#define MAX 100
//遞歸
int f1(int n)
{
if(n==1 || n==0)
return 1;
return f1(n-1)+f1(n-2);
}
//改進(jìn)版的遞歸,去除重復(fù)計(jì)算
int f2(int n)
{
//保存中間結(jié)果的數(shù)組
static result[MAX]={1,1};
if(n==1 || n==0)
return 1;
if(result[n-1] == 0)
result[n-1]=f2(n-1);
if(result[n-2] == 0)
result[n-2]=f2(n-2);
return result[n-1]+result[n-2];
}
//用數(shù)組保存中間結(jié)果(來自陳孝杰)
int f3(int n)
{
int a[MAX],i;
a[1]=1;
a[0]=1;
for(i=2;i<=n;i++)
a[i]=a[i-1]+a[i-2];
return a[n];
}
//迭代
int f4(int n)
{
int i=2,a=1,b=1,sum=1;
while(i<=n){
sum=a+b;
a=b;
b=sum;
i++;
}
return sum;
}
void main()
{
long start,end;
start=clock();
printf("f(40)==%d\n",f1(40));
end=clock();
printf("用時(shí)：%d ms\n",end-start);
start=clock();
printf("f(40)==%d\n",f2(40));
end=clock();
printf("用時(shí)：%d ms\n",end-start);
start=clock();
printf("f(20)==%d\n",f3(20));
end=clock();
printf("用時(shí)：%d ms\n",end-start);
start=clock();
printf("f(20)==%d\n",f4(20));
end=clock();
printf("用時(shí)：%d ms\n",end-start);
}
運(yùn)行結(jié)果：
推出第i行要打印的空白個(gè)數(shù)及*號個(gè)數(shù)，用for循環(huán)依次打印各行
復(fù)制代碼 代碼如下:
#include<stdio.h>
//總共要打印2*n-1行，逐行打印
void print1(int n)
{
int i,j;
for(i=1;i<=n;i++){//打印1至n行
for(j=1;j<=n-i;j++)//打印n-i個(gè)空格
printf(" ");
for(j=1;j<=2*i-1;j++)//打印2*i-1個(gè)*號
printf("*");
printf("\n");
}
for(;i<2*n;i++){//打印n+1至2*n-1行，同(2*n-i)行
for(j=1;j<=n-(2*n-i);j++)
printf(" ");
for(j=1;j<=2*(2*n-i)-1;j++)
printf("*");
printf("\n");
}
}
void main()
{
int n;//n是菱形邊上*號的個(gè)數(shù)
printf("enter n:");
scanf("%d",&n);
print1(n);
}
2、斐波納契數(shù)列（Fibonacci Sequence），又稱黃金分割數(shù)列，指的是這樣一個(gè)數(shù)列：
1、1、2、3、5、8、13、21、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F(0)=0，F(xiàn)(1)=1，F(xiàn)(n)=F(n-1)+F(n-2)（n>=2，n∈N*）.編寫程序，輸出F(20)的值。
這里給出四種不同的解法，注意遞歸和改進(jìn)的遞歸效率上有很大區(qū)別。
復(fù)制代碼 代碼如下:
#include<stdio.h>
#include<math.h>
#include<time.h>
#define MAX 100
//遞歸
int f1(int n)
{
if(n==1 || n==0)
return 1;
return f1(n-1)+f1(n-2);
}
//改進(jìn)版的遞歸,去除重復(fù)計(jì)算
int f2(int n)
{
//保存中間結(jié)果的數(shù)組
static result[MAX]={1,1};
if(n==1 || n==0)
return 1;
if(result[n-1] == 0)
result[n-1]=f2(n-1);
if(result[n-2] == 0)
result[n-2]=f2(n-2);
return result[n-1]+result[n-2];
}
//用數(shù)組保存中間結(jié)果(來自陳孝杰)
int f3(int n)
{
int a[MAX],i;
a[1]=1;
a[0]=1;
for(i=2;i<=n;i++)
a[i]=a[i-1]+a[i-2];
return a[n];
}
//迭代
int f4(int n)
{
int i=2,a=1,b=1,sum=1;
while(i<=n){
sum=a+b;
a=b;
b=sum;
i++;
}
return sum;
}
void main()
{
long start,end;
start=clock();
printf("f(40)==%d\n",f1(40));
end=clock();
printf("用時(shí)：%d ms\n",end-start);
start=clock();
printf("f(40)==%d\n",f2(40));
end=clock();
printf("用時(shí)：%d ms\n",end-start);
start=clock();
printf("f(20)==%d\n",f3(20));
end=clock();
printf("用時(shí)：%d ms\n",end-start);
start=clock();
printf("f(20)==%d\n",f4(20));
end=clock();
printf("用時(shí)：%d ms\n",end-start);
}
運(yùn)行結(jié)果：
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)雙向鏈表，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)給圖片添加邊框功能，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-10-10
對比C語言中g(shù)etc()函數(shù)和ungetc()函數(shù)的使用
這篇文章主要介紹了對比C語言中g(shù)etc()函數(shù)和ungetc()函數(shù)的使用,是C語言入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-08-08
這篇文章主要介紹了插入排序的順序表實(shí)現(xiàn)代碼，有需要的朋友可以參考一下2014-01-01
Qt實(shí)現(xiàn)簡易計(jì)時(shí)器的示例代碼
計(jì)時(shí)器實(shí)現(xiàn)四個(gè)功能：開始計(jì)時(shí)、停止計(jì)時(shí)、暫停計(jì)時(shí)以及打點(diǎn)。當(dāng)點(diǎn)擊暫停時(shí)，開始按鈕和停止按鈕無法點(diǎn)擊。當(dāng)點(diǎn)擊停止時(shí)，開始按鈕和暫停按鈕無法點(diǎn)擊，此時(shí)停止按鈕變?yōu)榍辶?。本文將用Qt實(shí)現(xiàn)這樣的一個(gè)計(jì)時(shí)器，需要的可以參考一下2022-06-06
今天小編就為大家分享一篇opencv3/C++輪廓的提取與篩選方式，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-12-12
C語言動態(tài)內(nèi)存函數(shù)(malloc、calloc、realloc、free)詳解
在C語言中,動態(tài)內(nèi)存函數(shù)是塊重要的知識點(diǎn),以往,我們開辟空間都是固定得,數(shù)組編譯結(jié)束后就不能繼續(xù)給它開辟空間了,開辟的空間滿了,就不能在開辟空間了,學(xué)習(xí)本文章,我們就可以解決這個(gè)問題,向內(nèi)存申請空間,感興趣的小伙伴跟著小編一起來看看吧2023-08-08
本篇文章是對libxm進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要為大家介紹了C++中地圖按鍵排序?qū)崿F(xiàn)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-07-07
C++ vector模擬實(shí)現(xiàn)的代碼詳解
vector是表示可變大小數(shù)組的序列容器，就像數(shù)組一樣，vector也采用的連續(xù)存儲空間來存儲元素，本質(zhì)講，vector使用動態(tài)分配數(shù)組來存儲它的元素，本文將給大家詳細(xì)介紹一下C++ vector模擬實(shí)現(xiàn),需要的朋友可以參考下2023-07-07