피 보 나치 찾기 (데이터 구조)

은 인 곤 의 2 판 7.25 문제
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

#define MOD 50
#define SIZE 13

int fib_search(int x, int n, int fib[], int ar[])
{
    int k = 2, l = 1, r = n, mid, offset = 0;

    while (fib[k] - 1 < n) k++;
    while (l <= r)
    {
        mid = offset + fib[k - 1];
        if (ar[mid] == x) return mid;
        else if (ar[mid] > x) k--;
        else {
            k -= 2;
            offset = mid;
        }
        r = fib[k] - 1;
    }
    return -1;
}

int main()
{
    int fib[SIZE] = { 0, 1 }, ar[13], i, x;

    srand(time(0));
    cout << "       n = 12    。" << endl;
    //cout << "fib: " << fib[0] << " " << fib[1] << " ";
    for (i = 2; i < SIZE; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
        //cout << fib[i] << " ";
    }
    //cout << endl;
    cout << "ar : ";
    for (ar[0] = 0, i = 1; i < SIZE; i++) {
        ar[i] = ar[i - 1] + rand() % MOD;
        cout << ar[i] << " ";
    }
    while (true) {
        cout << "
(-1 ):" << endl; cin >> x; if (x == -1) break; cout << fib_search(x, SIZE - 1, fib, ar) << endl; } return 0; }

좋은 웹페이지 즐겨찾기