標題:
費氏數列的兩種解法
[打印本頁]
作者:
tonyh
時間:
2023-5-13 19:03
標題:
費氏數列的兩種解法
1. 遞迴
2. 動態規劃
Java
// 0 1 1 2 3 5 8 ...
public class Ch01 {
Ch01()
{
System.out.println("費氏數列第12項: "+f(12));
System.out.println("費氏數列第23項: "+f(23));
System.out.println("費氏數列第37項: "+f(37));
System.out.println("費氏數列第42項: "+f(42));
}
int f(int n)
{
if(n<2)
return n;
else
return f(n-2)+f(n-1);
}
public static void main(String[] args) {
long start=System.currentTimeMillis();
new Ch01();
long end=System.currentTimeMillis();
System.out.println("花費: "+(end-start)+" 毫秒");
}
}
/*
f(5)
=f(3)+f(4)
=f(1)+f(2)+f(2)+f(3)
=1+f(0)+f(1)+f(0)+f(1)+f(1)+f(2)
=1+0+1+0+1+1+f(0)+f(1)
=1+1+1+1+1=5
*/
複製代碼
// 0 1 1 2 3 5 8 ...
public class Ch02 {
Ch02()
{
long data[]=new long[90];
data[0]=0;
data[1]=1;
for(int i=2; i<90; i++)
data[i]=data[i-2]+data[i-1];
System.out.println("費氏數列第12項: "+data[12]);
System.out.println("費氏數列第23項: "+data[23]);
System.out.println("費氏數列第37項: "+data[37]);
System.out.println("費氏數列第42項: "+data[42]);
System.out.println("費氏數列第59項: "+data[59]);
System.out.println("費氏數列第89項: "+data[89]);
}
public static void main(String[] args) {
long start=System.currentTimeMillis();
new Ch02();
long end=System.currentTimeMillis();
System.out.println("花費: "+(end-start)+" 毫秒");
}
}
複製代碼
C++
#include<bits/stdc++.h>
using namespace std;
int f(int n)
{
if(n<2)
return n;
else
return f(n-2)+f(n-1);
}
int main()
{
cout<<"費氏數列第12項: "<<f(12)<<endl;
cout<<"費氏數列第23項: "<<f(23)<<endl;
cout<<"費氏數列第37項: "<<f(37)<<endl;
cout<<"費氏數列第42項: "<<f(42)<<endl;
cout<<"花費: "<<clock()<<" 毫秒"<<endl;
return 0;
}
複製代碼
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long data[90];
data[0]=0;
data[1]=1;
for(int i=2; i<90; i++)
data[i]=data[i-2]+data[i-1];
cout<<"費氏數列第12項: "<<data[12]<<endl;
cout<<"費氏數列第23項: "<<data[23]<<endl;
cout<<"費氏數列第37項: "<<data[37]<<endl;
cout<<"費氏數列第42項: "<<data[42]<<endl;
cout<<"費氏數列第59項: "<<data[59]<<endl;
cout<<"費氏數列第89項: "<<data[89]<<endl;
cout<<"花費: "<<clock()<<" 毫秒"<<endl;
return 0;
}
複製代碼
作者:
王法棣
時間:
2023-5-13 19:49
本帖最後由 王法棣 於 2023-5-13 19:54 編輯
package ch1;
public class ch1 {
ch1()
{
System.out.println("費氏數列第12項: "+f(12));
System.out.println("費氏數列第23項: "+f(23));
System.out.println("費氏數列第37項: "+f(37));
System.out.println("費氏數列第42項: "+f(42));
}
int f(int n)
{
if(n<2)
return n;
else
return f(n-2)+f(n-1);
}
public static void main(String[] args) {
long s=System.currentTimeMillis();
new ch1();
long e=System.currentTimeMillis();
System.out.println(e-s);
}
}
複製代碼
package ch1;
public class ch1 {
ch1()
{
long data[]=new long[90];
data[0]=0;
data[1]=1;
for(int i=2;i<90;i++)
data[i]=data[i-1]+data[i-2];
System.out.println("費氏數列第12項: "+data[12]);
System.out.println("費氏數列第23項: "+data[23]);
System.out.println("費氏數列第37項: "+data[37]);
System.out.println("費氏數列第42項: "+data[42]);
System.out.println("費氏數列第59項: "+data[59]);
System.out.println("費氏數列第89項: "+data[89]);
}
public static void main(String[] args) {
long s=System.currentTimeMillis();
new ch1();
long e=System.currentTimeMillis();
System.out.println(e-s);
}
}
複製代碼
作者:
王秉鈞
時間:
2023-5-13 19:53
public class Ch69 {
Ch69()
{
System.out.println("費事數列地12巷"+f(12));
System.out.println("費事數列地12巷"+f(23));
System.out.println("費事數列地12巷"+f(37));
System.out.println("費事數列地12巷"+f(42));
}
}
int f(int n)
{
if(n<2)
return n;
else
return f(n-2)+f(n-1);
}
public static void main(String[] args){
long start=System.currentTimeMills();
System.out.println("花費"+(end-start)+"毫秒");
}
}
複製代碼
作者:
曾元瑜
時間:
2023-5-13 19:53
public class D1 {
D1(){
System.out.println("費氏數列第12項:"+f(12));
System.out.println("費氏數列第23項:"+f(23));
System.out.println("費氏數列第37項:"+f(37));
System.out.println("費氏數列第42項:"+f(42));
}
int f(int n)
{
if(n<2)
return n;
else
return f(n-2)+f(n-1);
}
public static void main(String[] args) {
long s=System.currentTimeMillis();
new D1();
long e=System.currentTimeMillis();
System.out.println("花費:"+(e-s)+"毫秒");
}
}
複製代碼
作者:
盧禹廷
時間:
2023-5-13 19:54
public class Ch01 {
Ch01()
{
long data[]=new long[90];
data[0]=0;
data[1]=1;
for(int i=2; i<90; i++)
data[i]=data[i-2]+data[i-1];
System.out.println("費氏數列第12項: "+data[12]);
System.out.println("費氏數列第23項: "+data[23]);
System.out.println("費氏數列第37項: "+data[37]);
System.out.println("費氏數列第42項: "+data[42]);
System.out.println("費氏數列第59項: "+data[59]);
System.out.println("費氏數列第89項: "+data[89]);
}
public static void main(String[] args) {
long start=System.currentTimeMillis();
new Ch01();
long end=System.currentTimeMillis();
System.out.println("花費: "+(end-start)+" 毫秒");
}
}
複製代碼
作者:
陳依彤
時間:
2023-5-13 20:08
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long data[90];
data[0]=0;
data[1]=1;
for(int i=2; i<90; i++)
data[i]=data[i-2]+data[i-1];
cout<<"費氏數列第12項: "<<data[12]<<endl;
cout<<"費氏數列第23項: "<<data[23]<<endl;
cout<<"費氏數列第37項: "<<data[37]<<endl;
cout<<"費氏數列第42項: "<<data[42]<<endl;
cout<<"費氏數列第59項: "<<data[59]<<endl;
cout<<"費氏數列第89項: "<<data[89]<<endl;
cout<<"花費: "<<clock()<<" 毫秒"<<endl;
return 0;
}
複製代碼
作者:
張博竣
時間:
2023-5-13 20:17
public class Ch69 {
Ch69()
{
System.out.println("費事數列地12巷"+f(12));
System.out.println("費事數列地12巷"+f(23));
System.out.println("費事數列地12巷"+f(37));
System.out.println("費事數列地12巷"+f(42));
}
}
int f(int n)
{
if(n<2)
return n;
else
return f(n-2)+f(n-1);
}
public static void main(String[] args){
long start=System.currentTimeMills();
System.out.println("花費"+(end-start)+"毫秒");
}
}
複製代碼
作者:
黃子倢
時間:
2023-5-20 19:13
public class Ch01 {
Ch01()
{
System.out.println("費氏數列第12項: "+f(12));
System.out.println("費氏數列第23項: "+f(23));
System.out.println("費氏數列第37項: "+f(37));
System.out.println("費氏數列第42項: "+f(42));
}
int f(int n)
{
if(n<2)
return n;
else
return f(n-2)+f(n-1);
}
public static void main(String[] args) {
long start=System.currentTimeMillis();
new Ch01();
long end=System.currentTimeMillis();
System.out.println("花費: "+(end-start)+" 毫秒");
}
}
複製代碼
作者:
王秉鈞
時間:
2023-5-20 19:40
public class Ch71 {
Ch71()
{
long data[]=new long[90];
data[0]=0;
data[1]=1;
for(int i=2;i<90;i++);
System.out.println("地12巷"+data[12]);
System.out.println("地23巷"+data[23]);
System.out.println("地37巷"+data[37]);
System.out.println("第42巷"+data[42]);
System.out.println("地59巷"+data[59]);
System.out.println("地89巷"+data[89]);
}
public static void main(String[] args){
long start=System.currentTimeMillis();
new Ch71();
long end=System.currentTimeMillis();
System.out.println("spend"+(end-start)+"0.001sec");
}
}
複製代碼
歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/)
Powered by Discuz! 7.2