codeforces 225B（Well-known Numbers） 扩展斐波那契数列 Java

斐波那契数列的扩展题，看懂题意，不难。

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;
/**
* 题意：扩展斐波那契数。
* 满足以下条件 F[0] = 0 ; F[1] = 1 ; F[n] = F[n] = F[n-1] + F[n-2] + ... + F[n-k]
* 求该数列中，和为 inputSum 的任何一组斐波那契数的个数和值
*
* 分析：构造满足条件的斐波那契数组，之后遍历求解。
*
* @author TinyDolphin
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
int inputSum;
int inputK;
int[] F = new int[100050]; // 存储新的斐波那契数
int[] ans = new int[1005]; // 存储相加和为 inputSum 的一组斐波那契数
while (in.hasNext()) {
inputSum = in.nextInt();
inputK = in.nextInt();
F[0] = 0;
F[1] = 1;
int sum = F[0] + F[1];
int end = 0; // 记录 F[index] 数组中小于 inputSum 的最大斐波那契数的下标。
// 构造新的斐波那契数组 F[n] = F[n-1] + F[n-2] + ... + F[n-k]
for (int index = 2; F[index - 1] < inputSum; index++) {
F[index] = sum;
// 累加，需要减去前面多余的斐波那契数
sum = sum + F[index] - F[index - inputK >= 0 ? index - inputK : 0];
end = index;
}
sum = 0;
int count = -1;
// 找出和为 inputSum 的任意一组数
for (int index = end; index >= 0; index--) {
if (sum + F[index] <= inputSum) {
ans[++count] = F[index];
sum += F[index];
}
}
// 输出控制，考虑特殊情况
if (count == 0) {
out.println(2);
out.print(1 + " " + 0 + "rn");
}else {
// 以下控制输出
out.println(count + 1);
for (int index = 0; index <= count; index++) {
out.print(ans[index] + (index == count ? "rn" : " "));
}
}
}
out.flush();
}
}

最后

以上就是殷勤乌龟为你收集整理的codeforces 225B（Well-known Numbers） 扩展斐波那契数列 Java的全部内容，希望文章能够帮你解决codeforces 225B（Well-known Numbers） 扩展斐波那契数列 Java所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。