深圳价格实惠的网站建设公司,模板网站建设青岛,加个自己的网站,在线网站制作系统目录1.斐波那契数组1.题目描述2.输入格式3.输出格式4.样例输入5.样例输出6.数据范围7.原题链接2.解题思路3.Ac_code1.Java2.C3.Python1.斐波那契数组
1.题目描述
如果数组 A(a0,a1,⋯.an−1)A(a_0,a_1,⋯.a_{n-1})A(a0,a1,⋯.an−1)满足以下条件, 就说它是一个斐波那契…
目录1.斐波那契数组1.题目描述2.输入格式3.输出格式4.样例输入5.样例输出6.数据范围7.原题链接2.解题思路3.Ac_code1.Java2.C3.Python1.斐波那契数组
1.题目描述
如果数组 A(a0,a1,⋯.an−1)A(a_0,a_1,⋯.a_{n-1})A(a0,a1,⋯.an−1)满足以下条件, 就说它是一个斐波那契数组:
n≥2;n≥2;n≥2;a0a1a_0a_1a0a1对于所有的 i(i≥2),i(i≥2),i(i≥2),都满足 aiai−1ai−2。a_ia_{i-1}a_{i-2}。aiai−1ai−2。
现在, 给出一个数组 AAA, 你可以执行任意次修改, 每次修改将数组中的某 个位置的元素修改为一个大于 0 的整数。请问最少修改几个元素之后, 数组 AAA 会变成一个斐波那契数组。
2.输入格式
输入的第一行包含一个整数 nnn,表示数组 AAA 中的元素个数。 第二行包含 nnn 个整数 a0,a1,⋯.an−1,a_0,a_1,⋯.a_{n-1},a0,a1,⋯.an−1,相邻两个整数之间用一个空格分隔。
3.输出格式
输出一行包含一个整数表示最少需要修改数组 AAA 中的几个元素之后, 数组 AAA 可以变为一个斐波那契数组。
4.样例输入
5 1 2 2 4 8
5.样例输出
3
6.数据范围
2≤n≤105,1≤ai≤106。2≤n≤10^5,1≤a_i≤10^6。2≤n≤105,1≤ai≤106。
7.原题链接
斐波那契数组
2.解题思路
首先考虑斐波那契数组具有什么性质我们令 a0a11a_0a_11a0a11去打印出前30位斐波那契数。 不难发现在不到30位的情况下斐波那契数组的值已经超出了1e6而注意到题目给定的 aia_iai 的最大值才为 1e6。这说明其实后面的数我们根本无需考虑都是必须要修改的。
接下来我们就只需要考虑前30位数最多可以保留多少个数假设最多可以保留x个数那么答案就为n-x。
对于斐波那契数列如果 a0a_0a0 确定了那么整个数列都确定了。所以我们可以枚举 a0a_0a0 的值枚举的范围为[1,106]。[1,10^6]。[1,106]。然后去计算出前三十位的值看与原数组符合预期的数有多少个所有符合预期的数量取一个最大值x最终答案即为n-x。
时间复杂度O(30∗106)O(30*10^6)O(30∗106)
3.Ac_code
1.Java
import java.io.*;
import java.util.Scanner;public class Main {static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static int[] arr new int[50];static int V 1000000;public static void main(String[] args) throws IOException {Scanner sc new Scanner(System.in);//表示无穷大int res 0x3f3f3f3f;int n sc.nextInt();int count n;//我只读入前三十个数if (n 30) n 30;for (int i 1; i n; i) {arr[i] sc.nextInt();}//枚举开头是多少 30*1e6 3e7for (int i 1; i V; i) {int a i, b i, c 0;int ans 0;if (arr[1] a) ans;if (arr[2] b) ans;for (int j 3; j 30; j) {c a b;//这里是一个减枝if (c V) break;if (c arr[j]) ans;a b;b c;}res Math.min(count - ans, res);}out.println(res);out.flush();}
}2.C
#includebits/stdc.h
using namespace std;
typedef long long LL;
const int inf 0x3f3f3f3f;
const int V1000000;int n;
int arr[50];
int resinf;
int main()
{scanf(%d,n);int countn;//只需要考虑前30位数if(n30) n30;for(int i1;in;i){scanf(%d,arr[i]);}//起始的数(f[1]的值)for(int i1;iV;i){//a,b,c作为滚动数组枚举斐波那契数LL ai,bi,c0;int ans0;if(arr[1]a) ans;if(arr[2]b) ans;for(int j3;j30;j){cab;//没必要继续下去if(cV) break;if(carr[j]) ans;ab,bc;}resmin(count-ans,res);}printf(%d\n,res);return 0;
}3.Python
v1000000
resfloat(inf)
nint(input())
countn
if n30:n30
arr[0]*50
llist(map(int,input().split()))
for i in range(1,n1):arr[i]l[i-1]
for i in range(1,v1):a,b,ci,i,0ans0if arr[1]a:ansans1if arr[2]b:ansans1for j in range(3,31):cabif cv:breakif carr[j]:ansans1a,bb,cresmin(count-ans,res)
print(res)
