LeetCode——Fibonacci数列
タイトルの説明:
Fibonacci数列は、F[0]=0 F[1]=1 for each i≧2:F[i]=F[i-1]+F[i-2]と定義されているので、Fibonacci数列は、0,1,1,2,3,5,8,13,...、Fibonacci数列における数をFibonacci数と呼ぶ.あなたに1つのNをあげて、あなたはそれを1つのFibonacci数に変えたいと思って、すべてのステップはあなたは現在の数字のXをX-1あるいはX+1に変えることができて、今あなたに1つの数のNを求めて最低でどれだけのステップを必要としてFibonacci数に変えることができます.
説明を入力:
正の整数Nとして入力(1≦N≦1000000)
出力の説明:
最小ステップ数がFibonacci数になるように出力します.たとえば、次のようになります.
入力:15出力:2
問題解決の考え方:
まず私の解題の考え方を話しましょう:(1)まず私が考えたのは入力した正の整数が1000000コード実装:
Fibonacci数列は、F[0]=0 F[1]=1 for each i≧2:F[i]=F[i-1]+F[i-2]と定義されているので、Fibonacci数列は、0,1,1,2,3,5,8,13,...、Fibonacci数列における数をFibonacci数と呼ぶ.あなたに1つのNをあげて、あなたはそれを1つのFibonacci数に変えたいと思って、すべてのステップはあなたは現在の数字のXをX-1あるいはX+1に変えることができて、今あなたに1つの数のNを求めて最低でどれだけのステップを必要としてFibonacci数に変えることができます.
説明を入力:
正の整数Nとして入力(1≦N≦1000000)
出力の説明:
最小ステップ数がFibonacci数になるように出力します.たとえば、次のようになります.
入力:15出力:2
問題解決の考え方:
まず私の解題の考え方を話しましょう:(1)まず私が考えたのは入力した正の整数が1000000
#include
using namespace std;
// Fibonacci
int fib(int n)
{
int f0 = 0;
int f1 = 1;
int fn = 0;
for (int i = 2; i < n; i++)
{
fn = f0 + f1;
f0 = f1;
f1 = fn;
}
return fn;
}
int main()
{
int ret;
int array_fib[33]; // Fibonacci
for (int i = 0; i < 33; i++)
{
array_fib[i] = fib(i);
}
int N;
list<int>mod_arr;
cin >> N; // N
for (int i = 0; i < 33; i++)
{
if (N == array_fib[i])// Fibonacci ， 0
{
cout << 0;
return 0;
}
else // ，
{
if (array_fib[i] - N>0)
mod_arr.push_back(array_fib[i] - N);
else
mod_arr.push_back(-(array_fib[i] - N));
}
}
mod_arr.sort(); //
list<int>::iterator it = mod_arr.begin(); //
cout << *it << endl;
return 0;
system("pause");
}