热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

计蒜客斐波那契数列

百度熊对数学一直都非常感兴趣。最近在学习斐波那契数列的它,向你展示了一个数字串,它称之为“斐波那契”串: 1123581347112358134711




百度熊对数学一直都非常感兴趣。最近在学习斐波那契数列的它,向你展示了一个数字串,它称之为“斐波那契”串:

11235813471123581347112358......

聪明的你当然一眼就看出了这个串是这么构造的:

1.        先写下两位在0~9范围内的数字a, b,构成串ab;

2.        取串最后的两位数字相加,将和写在串的最后面。

上面百度熊向你展示的串就是取a = b = 1构造出来的串。

显然,步骤1之后不停地进行步骤2,数字串可以无限扩展。现在,百度熊希望知道串的第n位是什么数字。

输入数据的第一行为一个整数T&#xff08; T  1000&#xff09;表示有T组测试数据&#xff1b;每组测试数据为三个正整数a, b, n&#xff08;0 a, b <10, 0 ≤ 109&#xff09;。

对于每组测试数据&#xff0c;输出一行Case #c: ans”&#xff08;不包含引号&#xff09; c是测试数据的组数&#xff0c;从1开始。

提示&#xff1a;

1.        对于第一、二组数据&#xff0c;串为112358134711235

2.        对于第三组数据&#xff0c;串为14591459145914


样例输入

3
1 1 2
1 1 8
1 4 8

样例输出

Case #1: 1
Case #2: 3
Case #3: 9





/* 思路:其实从提示可以(隐约...)看出来, 这是一个针对周期串的处理(经过试验,确实是周期串) 而本质是要寻找周期串,但实际上提示已经给出了答案了..
*/
import java.util.Scanner;
public class Main
{ public static void main(String[] args) { Scanner cin &#61; new Scanner(System.in); //1.定义提示给出的两个周期串 String str1 &#61; "1123581347"; String str2 &#61; "1459"; int n &#61; cin.nextInt(); int cnt &#61; 0; while(n--!&#61;0) { int a &#61; cin.nextInt(); int b &#61; cin.nextInt(); int ch &#61; cin.nextInt(); //2.考虑a和b都为0的情况,若两者都是0周期串必然也是0,所以直接输出便可 if(a&#61;&#61;0 && b&#61;&#61;0) { System.out.println("Case #"&#43;(&#43;&#43;cnt)&#43;": "&#43;0); continue; } String str &#61; ""&#43;a&#43;b; String flag &#61; ""; /* 3.根据斐波那契,将尾部两个字符取出相加,添加到str尾部. 由于已经知道了周期串的规律,所以直接判断尾部是否为两种周期串 的其中一种便可,在设定标记退出循环 */ while(true) { int num &#61; (str.charAt(str.length()-2)-&#39;0&#39;)&#43;(str.charAt(str.length()-1)-&#39;0&#39;); str &#43;&#61; num; if(str.endsWith(str1)) { flag &#61; str1; break; } if(str.endsWith(str2)) { flag &#61; str2; break; } } /* 4.当ch的输入大于str的长度时,那么落点必然是在周期串上, 所以直接求出落点便可,要考虑ch等于0的情况 而假若ch的输入小于str的长度时,那直接输出该落点便可 */ if(ch > str.length()) { ch &#61; ch - (str.length()-flag.length()); ch %&#61; flag.length();if(ch&#61;&#61;0)ch&#61;flag.length(); System.out.println("Case #"&#43;(&#43;&#43;cnt)&#43;": "&#43;flag.charAt(ch-1));continue; } System.out.println("Case #"&#43;(&#43;&#43;cnt)&#43;": "&#43;str.charAt(ch-1)); } }
}






推荐阅读
author-avatar
世界著名墙头草
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有