目录
如果数组 A = ( a 0 , a 1 , ⋯ . a n − 1 ) A=(a_0,a_1,⋯.a_{n-1}) A=(a0,a1,⋯.an−1)满足以下条件, 就说它是一个斐波那契数组:
现在, 给出一个数组 A A A, 你可以执行任意次修改, 每次修改将数组中的某 个位置的元素修改为一个大于 0 的整数。请问最少修改几个元素之后, 数组 A A A 会变成一个斐波那契数组。
输入的第一行包含一个整数
n
n
n,表示数组
A
A
A 中的元素个数。
第二行包含
n
n
n 个整数
a
0
,
a
1
,
⋯
.
a
n
−
1
,
a_0,a_1,⋯.a_{n-1},
a0,a1,⋯.an−1,相邻两个整数之间用一个空格分隔。
输出一行包含一个整数表示最少需要修改数组 A A A 中的几个元素之后, 数组 A A A 可以变为一个斐波那契数组。
5
1 2 2 4 8
3
2 ≤ n ≤ 1 0 5 , 1 ≤ a i ≤ 1 0 6 。 2≤n≤10^5,1≤a_i≤10^6。 2≤n≤105,1≤ai≤106。
首先考虑斐波那契数组具有什么性质，我们令
a
0
=
a
1
=
1
a_0=a_1=1
a0=a1=1去打印出前30位斐波那契数。
不难发现，在不到30位的情况下，斐波那契数组的值已经超出了1e6，而注意到题目给定的
a
i
a_i
ai 的最大值才为 1e6。这说明其实后面的数我们根本无需考虑，都是必须要修改的。
接下来我们就只需要考虑前30位数最多可以保留多少个数，假设最多可以保留x个数，那么答案就为n-x。
对于斐波那契数列，如果
a
0
a_0
a0 确定了，那么整个数列都确定了。所以我们可以枚举
a
0
a_0
a0 的值，枚举的范围为
[
1
,
1
0
6
]
。
[1,10^6]。
[1,106]。然后去计算出前三十位的值，看与原数组符合预期的数有多少个，所有符合预期的数量取一个最大值x，最终答案即为n-x。
时间复杂度 O ( 30 ∗ 1 0 6 ) O(30*10^6) O(30∗106)
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 3e7
for (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();
}
}
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int V=1000000;
int n;
int arr[50];
int res=inf;
int main()
{
scanf("%d",&n);
int count=n;
//只需要考虑前30位数
if(n>30) n=30;
for(int i=1;i<=n;++i){
scanf("%d",&arr[i]);
}
//起始的数(f[1]的值)
for(int i=1;i<=V;++i){
//a,b,c作为滚动数组枚举斐波那契数
LL 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=min(count-ans,res);
}
printf("%d\n",res);
return 0;
}
v=1000000
res=float("inf")
n=int(input())
count=n
if n>30:
n=30
arr=[0]*50
l=list(map(int,input().split()))
for i in range(1,n+1):
arr[i]=l[i-1]
for i in range(1,v+1):
a,b,c=i,i,0
ans=0
if arr[1]==a:
ans=ans+1
if arr[2]==b:
ans=ans+1
for j in range(3,31):
c=a+b
if c>v:
break
if c==arr[j]:
ans=ans+1
a,b=b,c
res=min(count-ans,res)
print(res)```
如何在buildr项目中使用Ruby？我在很多不同的项目中使用过Ruby、JRuby、Java和Clojure。我目前正在使用我的标准Ruby开发一个模拟应用程序，我想尝试使用Clojure后端(我确实喜欢功能代码)以及JRubygui和测试套件。我还可以看到在未来的不同项目中使用Scala作为后端。我想我要为我的项目尝试一下buildr(http://buildr.apache.org/)，但我注意到buildr似乎没有设置为在项目中使用JRuby代码本身!这看起来有点傻，因为该工具旨在统一通用的JVM语言并且是在ruby中构建的。除了将输出的jar包含在一个独特的、仅限ruby
在rails源中:https://github.com/rails/rails/blob/master/activesupport/lib/active_support/lazy_load_hooks.rb可以看到以下内容@load_hooks=Hash.new{|h,k|h[k]=[]}在IRB中，它只是初始化一个空哈希。和做有什么区别@load_hooks=Hash.new 最佳答案 查看rubydocumentationforHashnew→new_hashclicktotogglesourcenew(obj)→new_has
我的主要目标是能够完全理解我正在使用的库/gem。我尝试在Github上从头到尾阅读源代码，但这真的很难。我认为更有趣、更温和的踏脚石就是在使用时阅读每个库/gem方法的源代码。例如，我想知道RubyonRails中的redirect_to方法是如何工作的:如何查找redirect_to方法的源代码？我知道在pry中我可以执行类似show-methodmethod的操作，但我如何才能对Rails框架中的方法执行此操作？您对我如何更好地理解Gem及其API有什么建议吗？仅仅阅读源代码似乎真的很难，尤其是对于框架。谢谢! 最佳答案 Ru
我的假设是moduleAmoduleBendend和moduleA::Bend是一样的。我能够从thisblog找到解决方案,thisSOthread和andthisSOthread.为什么以及什么时候应该更喜欢紧凑语法A::B而不是另一个，因为它显然有一个缺点？我有一种直觉，它可能与性能有关，因为在更多命名空间中查找常量需要更多计算。但是我无法通过对普通类进行基准测试来验证这一点。 最佳答案 这两种写作方法经常被混淆。首先要说的是，据我所知，没有可衡量的性能差异。(在下面的书面示例中不断查找)最明显的区别，可能也是最著名的，是你的
几个月前，我读了一篇关于rubygem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：
我目前正在使用以下方法获取页面的源代码:Net::HTTP.get(URI.parse(page.url))我还想获取HTTP状态，而无需发出第二个请求。有没有办法用另一种方法做到这一点？我一直在查看文档，但似乎找不到我要找的东西。 最佳答案 在我看来，除非您需要一些真正的低级访问或控制，否则最好使用Ruby的内置Open::URI模块:require'open-uri'io=open('http://www.example.org/')#=>#body=io.read[0,50]#=>"["200","OK"]io.base_ur
前言作为一名程序员，自己的本质工作就是做程序开发，那么程序开发的时候最直接的体现就是代码，检验一个程序员技术水平的一个核心环节就是开发时候的代码能力。众所周知，程序开发的水平提升是一个循序渐进的过程，每一位程序员都是从“菜鸟”变成“大神”的，所以程序员在程序开发过程中的代码能力也是根据平时开发中的业务实践来积累和提升的。提高代码能力核心要素程序员要想提高自身代码能力，尤其是新晋程序员的代码能力有很大的提升空间的时候，需要针对性的去提高自己的代码能力。提高代码能力其实有几个比较关键的点，只要把握住这些方面，就能很好的、快速的提高自己的一部分代码能力。1、多去阅读开源项目，如有机会可以亲自参与开源
嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来
注意：本文主要掌握DCN自研无线产品的基本配置方法和注意事项，能够进行一般的项目实施、调试与运维AP基本配置命令AP登录用户名和密码均为：adminAP默认IP地址为：192.168.1.10AP默认情况下DHCP开启AP静态地址配置：setmanagementstatic-ip192.168.10.1AP开启/关闭DHCP功能：setmanagementdhcp-statusup/downAP设置默认网关：setstatic-ip-routegeteway192.168.10.254查看AP基本信息：getsystemgetmanagementgetmanaged-apgetrouteAP配
文章目录git常用命令（简介，详细参数往下看）Git提交代码步骤gitpullgitstatusgitaddgitcommitgitpushgit代码冲突合并问题方法一：放弃本地代码方法二：合并代码常用命令以及详细参数gitadd将文件添加到仓库：gitdiff比较文件异同gitlog查看历史记录gitreset代码回滚版本库相关操作远程仓库相关操作分支相关操作创建分支查看分支：gitbranch合并分支：gitmerge删除分支：gitbranch-ddev查看分支合并图：gitlog–graph–pretty=oneline–abbrev-commit撤消某次提交git用户名密码相关配置g