1.写出斐波那契二分检索，即使用斐波那契数列二分有序序列，查找某给定元素，找到返回下标，找不到返回-1

好的，斐波那契二分检索可以分为以下几个步骤：

1. 构建一个斐波那契数列，数列中每个数都是前两个数之和，起始值为0和1，直到最后一个数大于等于有序序列的长度为止。
2. 使用斐波那契数列中前一个数作为分割点，将有序序列分为两部分。
3. 比较分割点处的元素与要查找的元素，如果相等，则返回分割点的下标；如果要查找的元素比分割点处的元素小，则在斐波那契数列中向前一步，将分割点更新为前一个斐波那契数，重复步骤2；如果要查找的元素比分割点处的元素大，则在斐波那契数列中向前两步，将分割点更新为前两个斐波那契数之和，重复步骤2。
4. 如果最终在有序序列中未找到要查找的元素，则返回-1。

以下是斐波那契二分检索的Python实现代码：

def fibonacci_search(arr, val):
    # 构建斐波那契数列
    fib = [0, 1]
    while fib[-1] < len(arr):
        fib.append(fib[-1] + fib[-2])

    # 初始化指针和分割点
    left, mid, right = 0, 0, len(arr) - 1
    while fib:
        # 获取当前分割点
        k = fib.pop()
        # 计算分割点位置
        mid = left + k - 1
        if mid > right:
            mid = right
        # 比较分割点处的元素与要查找的元素
        if arr[mid] == val:
            return mid
        elif arr[mid] > val:
            # 在左半部分继续查找
            right = mid - 1
        else:
            # 在右半部分继续查找
            left = mid + 1
    # 没有找到要查找的元素
    return -1

使用示例：

arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
val = 7
index = fibonacci_search(arr, val)
if index != -1:
    print("元素 %d 在序列中的下标为 %d" % (val, index))
else:
    print("元素 %d 不在序列中" % val)

输出结果：

元素 7 在序列中的下标为 3