2020/11/6 斐波那契数列练习
程序员文章站
2024-03-21 22:39:46
...
把猎豹网校的c++基础看完了,基础语法已经差不多了,继承多态封装准备在师兄考的视频里看,之前看effective c++有一些些概念比较陌生就没有看下去,今天开始重新啃。
概念复习:给数组添加元素的时候,不能写
vector<int> ivec;
for (vector<int>::size_type ix = 0; ix != 10; ++ix)
ivec[ix] = ix; // disaster: ivec has no elements
因为现在这个数组里没有元素,vector的下标操作不能添加元素。
但是可以使用如下方法:
vector<int> ivec; // empty vector
for (vector<int>::size_type ix = 0; ix != 10; ++ix)
ivec.push_back(ix);
于是写了斐波那契数列的初版本,没有使用指针。用户输入元素标号,输出对应的元素值。
#include <iostream>
#include <vector>
using namespace std;
int feeeb(int num)
{
int first = 0;
int second = 1;
vector<int> result;
int temp;//数组中的元素
result.push_back(0);
result.push_back(1);
for (vector<int>::size_type p=0 ; p < num-2; p++)
{
//if (num <= 1)
//{
// cout << "invalid number." << endl;
// //return -1;
//}
//else
//{
temp = first + second;
result.push_back(temp);
first = second;
second = temp;
//}
}
return temp;
}
int main()
{
cout << "please enter the number" << endl;
int num;
cin >> num;
if (num < 0)
{
cout << "error" << endl;
}
else
cout << feeeb(num) << endl;
system("pause");
return 0;
}
//注意输入异常的处理,在主程序中输出错误提示即可,如果在主程序中返回-1则直接退出程序,system(“pause”)也无法暂停。
//如果在子函数中输出return -1则向main函数中输出的值为-1,而不是返回异常。
网上去搜相关的试题发现还有递归求解,自己写了一下,很简单:
#include <iostream>
using namespace std;
int feeb(int num)
{
if (num == 1) return 0;
if (num == 2) return 1;
else return feeb(num - 2) + feeb(num - 1);
}
int main()
{
cout << "please enter the num:" << endl;
int num_in;
cin >> num_in;
if (num_in <= 0) cout << "error!" << endl;
else cout << feeb(num_in) << endl;
system("pause");
return 0;
}
但是递归的时间代价比较大,时间复杂度是n的指数级别
时间复杂度之所以这么大,是因此计算过程中存在着重复计算。以f(10)为例,f(10)=f(9)+f(8),f(9)=f(8)+f(7)。其中的f(8)就是重复计算的。
还可以用动态数组求解,下面这个链接讲的比较详细。
https://www.cnblogs.com/xwdreamer/archive/2012/05/15/2501606.html
在看《effective c++》时候看到了关于输入异常的讨论:
exit(-1);
直接种植整个程序,这个时候要加入头文件
include <cstdlib>
但是这种方式太过激烈,还有抛出异常的方法(未完持续)