作为新手,我真的很想学习如何让代码尽可能简单,同时完成它应该做的工作。
我做的题来自Project Euler , 它说
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
找出序列中所有偶数项的总和 不超过四百万。
下面是我的代码。我想知道简化这个的最好方法是什么,首先删除所有 .get(list.length()-1 )..... 如果可能的话,这些东西将是一个好的开始,但我真的不知道知道怎么做吗?
谢谢
public long fibb()
{
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
while((list.get(list.size() - 1) + (list.get(list.size() - 2)) < 4000000)){
list.add((list.get(list.size()-1)) + (list.get(list.size() - 2)));
}
long value = 0;
for(int i = 0; i < list.size(); i++){
if(list.get(i) % 2 == 0){
value += list.get(i);
}
}
return value;
}
最佳答案
其他回答者都给出了很好的答案。我想向您展示重构是如何运作的,不仅仅是针对这个了解斐波那契数的特定问题,而是作为一个迭代过程,小心地将代码削减到最低限度。重构让我们从工作但复杂的代码开始,并逐步将其逐步削减。让我向您展示您在朝着最终解决方案努力的过程中可以采取的所有中间步骤。
注意:我已将您的初始起始值更改为 1 和 1,而不是 1 和 2。严格来说,斐波那契数列以两个 1 开头,如 1、1、2、3、5...
第 1 步 - 反转列表
对于初学者来说,要摆脱重复的 list.size() - x
表达式,您可以按相反 的顺序添加数字。然后找到最近的两个数字就更简单了。
public long fibb()
{
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(1);
while (list.get(0) + list.get(1) < 4000000) {
// Use list.add(0, ...) to add entries to the *front*.
list.add(0, list.get(0) + list.get(1));
}
long value = 0;
for (int i = 0; i < list.size(); i++) {
if (list.get(i) % 2 == 0) {
value += list.get(i);
}
}
return value;
}
第 2 步 - 切换到链表
让我们将 ArrayList
切换为 LinkedList
。在数组的开头插入是低效的,而它是在链表上的快速操作。
沿着这些思路,我们需要摆脱第二个循环中的 get()
调用。使用链表按索引查找条目很慢。为此,我将第二个循环更改为使用 for (variable: container)
语法。
public long fibb()
{
// Changed to use a linked list for faster insertions.
List<Integer> list = new LinkedList<Integer>();
list.add(1);
list.add(1);
// Using get() is normally a bad idea on linked lists, but we can get away
// with get(0) and get(1) since those indexes are small.
while (list.get(0) + list.get(1) < 4000000) {
list.add(0, list.get(0) + list.get(1));
}
long value = 0;
// Altered loop to avoid expensive get(i) calls.
for (Integer n: list) {
if (n % 2 == 0) {
value += n;
}
}
return value;
}
第 3 步 - 合并循环
下一个优化是结合两个循环。您可以在生成偶数时检查偶数,而不是先生成所有数字然后再检查偶数。
public long fibb()
{
List<Integer> list = new LinkedList<Integer>();
long value = 0;
list.add(1);
list.add(1);
while (list.get(0) + list.get(1) < 4000000) {
int next = list.get(0) + list.get(1);
list.add(0, next);
if (next % 2 == 0) {
value += next;
}
}
return value;
}
第 4 步 - 消除列表
现在您可能会注意到,您永远不会引用索引 1 以外的数字。位置 2 及以后的数字将不再使用。这暗示您甚至不需要再保留所有数字的列表。由于您正在检查生成的偶数,因此您现在可以丢弃除最近的两个数字之外的所有数字。
另外,作为一个小细节,我们将 value
重命名为 total
。
public long fibb()
{
int a = 1, b = 1;
long total = 0;
while (a + b < 4000000) {
// Calculate the next number.
int c = a + b;
// Check if it's even.
if (c % 2 == 0) {
total += c;
}
// Shift the values.
a = b;
b = c;
}
return total;
}
关于java - 如何清理我的代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/3037765/