@toc

1、问题描述

如果数组 $A=(a_0,a_1,...,a_{n-1})$满足以下条件, 就说它是一个斐波那契数组:

1. $n \ge 2$;
2. $a_0=a_1$
3. 对于所有的 i*(*i≥2), 都满足 $a_i=a_{i-1}+a_{i-2}$。

现在, 给出一个数组 A, 你可以执行任意次修改, 每次修改将数组中的某 个位置的元素修改为一个大于 0 的整数。请问最少修改几个元素之后, 数组 A 会变成一个斐波那契数组。

输入格式

输入的第一行包含一个整数 n, 表示数组 A 中的元素个数。

第二行包含 n 个整数 $a_0,a_1,...,a_{n-1}$,相邻两个整数之间用一个空格分隔。

输出格式

输出一行包含一个整数表示最少需要修改数组 A 中的几个元素之后, 数组 A* 可以变为一个斐波那契数组。

样例输入

5
1 2 2 4 8

样例输出

3

样例说明

将原数组修改为 (1,1,2,3,5)(1,1,2,3,5), 最少修改三个元素变成了一个斐波那契数组。

评测用例规模与约定

对于所有评测用例, $2\le n\le 10^5,1\le a_i\le 10^6$ 。

运行限制

• 最大运行时间：3s
• 最大运行内存: 512M

2、解题思路

我们先用初始值 $a_0=1$观察下斐波那契数组，输出上几十个数看看，写一个递归就是实现：

public static int FN(int n){
        if(n==1||n==2){
            return 1;
        }
        return FN(n-1)+FN(n-2);
}

从上图可以看到，第31项的值已经大于1000000，而题目要求的输入数据范围是 $1\le a_i\le 10^6$，，所以第30项后面的值都需要修改。那我们其实都能通过遍历解决这个问题。

确定斐波那契数列的初始值:这里我们还需要确定斐波那契梳理的初始值，因为题目中并没有说初始值就是1，这个我们可以通过遍历的方式求解，我们将初始值从1取到1000000，然后根据这个初始值生成斐波那契数列，但是生成的时候需要做判断，保证数列中的每个值都 $\le 1000000$。

然后我们比较控制台输入的数组和我们生成的正确斐波那契数组匹配的个数，取匹配个数最大的那一个即可。

我们输入数组的总数减去最大匹配个数就是我们需要修改的次数(值大于1000000的都是需要修改的)。

这里暴力是可以的，因为就算从1开始数组也才只有30个值，更别说初始值更大的时候，那数组个数就更小了。

3、代码实现

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
//超过1000000的值都是需要修改的
public class Main {
    static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    static int max=0;//输入数列与正确的斐波那契数列匹配的最大值
    static int items=0; //正确数组中，值不超过1000000的个数
    static int[] arr=new int[1000010];  //输入数组
    static int[] f=new int[1000010];    //正确的斐波那契数组
    public static final int N=1000000;
    public static void main(String[] args) throws IOException {
        int n = nextInt();
        for (int i = 0; i <n; i++) {
            arr[i]=nextInt();
        }
        for (int i = 1; i <=N ; i++) {
            getFibon(i);    //生成以i为初项的斐波那契数列
            //将输入数组与生成的斐波那契数列匹配
            int count = compare();
            max=Math.max(max,count);    //找出匹配个数最多的次数
        }
        //总项数-匹配的最大值就是最少需要修改的次数
        System.out.println(n-max);
    }
    //将输入数组与生成的斐波那契数列匹配,返回匹配的个数
    public static int compare(){
        int count=0;
        for(int i=0;i<items;i++){
            if(arr[i]==f[i]){
                count++;
            }
        }
        return count;
    }

    //根据指定初始值生成斐波那契数列
    public static void getFibon(int first){
        items=2;
        f[0]=f[1]=first;
        for (int i = 2;; i++) {
            f[i]=f[i-1]+f[i-2];
            if(f[i]>N){
                break;
            }
            items++;
        }
    }
    public static int nextInt() throws IOException{
        st.nextToken();
        return (int)st.nval;
    }
}

测试用例：

提交看是否可以AC