与斐波那契数列相关的算法题
好好学习，天天向上！
1.问题描述
1.Description 有一个斐波那契序列f[1],f[2],…和两个整数a,b。其中f[k]表示Fibonacci序列中第k个元素，求解f[a]+f[a+1]+…+f[b]是偶数还是奇数。 Fibonacci序列： 公式： 举例: f[1]=1,f[2]=1,f[3]=2,f[4]=3,f[5]=5,f[6]=8,… 2.Input 有多个测试用例。输入的第一行包含一个整数T（大约100），表示测试用例的数量。 对每个测试用例：第一行也是唯一一行包含两个整数a和b （1<a<=b<1010000）。 3.Output 对于每个测试用例输出一行，如果是 偶数输出为0，如果是奇数输出为1。 4.测试用例 输入 输出 输入测试用例个数 6 用例1 1，2 0 用例2 2，3 0 用例3 1，4 1 用例4 1，5 0 用例5 123456 ，234567897654321 0 用例6 123，201990427201904272019042720190427 1
2.问题分析
- 先让我们看看斐波那契数列有什么奇偶规律。细心观察发现从起开始，每三个斐波那契数列的元素呈现：奇数（1）、奇数（1）、偶数（0）的现象。（我们可以把每三个斐波那契序列元素作为一个整体）
- 其次，注意由于计算机的整数类型无法承载1010000的数，所以要考虑如何存储输入变量的问题。
- 再然后，我们需要把f[a]+f[a+1]+…+f[b]进行分析，决定该公式的主要两个因素是a和b分别mod3得到的位置。把a和b所得位置与整体相加的奇偶进行优化确定，具体分析视图：
- 最后，将a所得的奇偶数与b所得的奇偶数相加可得出最终结果。
3.上代码：
import java.util.Scanner;
public class AboutFibonacci {
//通过字符串的方式处理数组 获取所输值得到的位置
public static int simpleNumber(String s) {
int res=0;
for(int i=0;i<s.length();i++) {
res+=(int)s.charAt(i);
}
res=res%3;
return res;
}
public static int outPut(String a,String b) {
int sa = 0;//a每个位的数的总和
int sb = 0;
int ta=0;
int tb=0;
sa=simpleNumber(a);
sb=simpleNumber(b);
//根据a的位置给予奇偶数
if(sa==2) {
ta=1;
}else {
ta=0;
}
//根据b的位置给予奇偶数
if(sb==1) {
tb=1;
}else {
tb=0;
}
//通过异或运算得到最后的结果
return ta^tb;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//输入多少个测试用例
int num = scan.nextInt();
for(int i = 1;i <= num;i++) {
String s1 = scan.next();
String s2=scan.next();
System.out.println(outPut(s1,s2));
}
}
}
5.总结
学习算法题时，可以考虑自己先分析分析，然后多动手，很多问题是你动手的时候出现的。还是希望大家一起努力学习进步！
