(ACM系列之一)从简单开始

本人冒着被投新手帖或隐藏帖的危险，预备在本论坛持续发布一个ACM算法题Java版的帖子。

我只有一个简单的目的，让“爱思考、爱编程”成为一种习惯。

当然不能只有代码的堆砌。很多大师和专家在研究设计模式、算法和很多Java的基础，关于面向对象、性能、并发和各种开源项目的帖子层出不穷，小弟也在此论坛受益菲浅。本着“你快乐，我快乐，大家快乐”的原则，小弟的帖子开始出现了。若有不当，可投新手或隐藏，论坛积分已是浮云，“失去的一定能找回来”。

做一件事情当然需要从简单的开始，循序渐进。所谓“欲速则不达，贪多嚼不烂”啊！！

此贴是第一帖，下面进入正题：

题目是这样的：

A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

这几个简单的单词我就不翻译了。我主要说说我的解法。

对于这个题，我相信给许许多多的程序员的第一印象就是递归。递归是一个伟大的发明，是一种美丽的思想。生活中处处有递归。

不过在java中，递归也有危险。对海量数据而言，递归会造成java对内存溢出，我刚学编程那会儿，可是遇到过不少。

对于这道题而言，是需要先分析的。这是一道简单的概率题（我知道，我知道，新手帖嘛。。）

仔细观察，就会发现，这道题的规律，当然是除了递归性质之后的规律。

首先，f(1) = 1,f(2) = 1。这个是前提，在代码中体现在if判断中。

最重要的是第三个式子，f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7。(mod翻译成java语言为%)

首先，我们会发现f(n)的取值范围为0-6，且未等概率的。同样f(n-1)与f(n-2)的取值范围也为0-6，同样为等概率的。

其次，我们可以认为f(n)是由f(n-1)与f(n-2)组合而成的，A和B是常量，f(n-1)与f(n-2)的取值范围确定，且为等概率事件，那么就有7*7=49种结果。那么我的思想就是重复计算（我知道这不是最好的算法，这也是我发帖来讨论的原因），还是利用递归思想，循环计算M次，而M = n % 49。即去总次数去掉重复结果计算后的次数。

在代码中，我用left代替了A * f(n - 1)，用right代替了B * f(n - 2)。

现在，就可以上代码了。

package org.fantasizer.algorithms.acm.p1005;

public class Main {
	public static void main(String[] args) {
		System.out.println(calculate(1, 1, 3));
		System.out.println(calculate(1, 2, 10));
		System.out.println(calculate(1, 2, 100000000));
	}

	public static long calculate(int A, int B, int n) {
		if (n == 1 || n == 2) {
			return 1;
		}

		long left = 1;
		long right = 1;

		long result = 0;
		for (int i = 2; i < n % 49; i++) {
			result = (A * left + B * right) % 7;
			right = left;
			left = result;
		}
		return result;
	}
}

最后说一下，讨论是用来学习的一种很好的方式。

评论

27 楼 liuxuejin 2011-04-07  

好东西，lz估计精通算法的程序员还是挺少的，比如我，我需要这些帖！

26 楼 fzuwwl 2011-04-07  

kimmking 写道

f(n) = A * f(n - 1) + B * f(n - 2)，给定f1,f2

广义斐波拉契，直接能求出来通项公式。
1、先化成1阶递推
另 α,β为 x^2=A*x+B的两个根，β>α,
则f(n+2)+β*f(n+1)=α*(f(n+1)+β*f(n))=....=α^n*(f2+β*f1)
另 D=f2+β*f1，则
f(n+2)-β^n*f2=D*(β^n-β^(n-1)*α+ ... β*α^(n-1)
另t=α/β,
f(n+2) = β^n*D*(1-(-t)^n)/(1+t) + -β^n*f2

等式右边全是已知数，直接能求出来f(n+2)
为了简化计算，计算右边的值的每一步，都先Mod 7再计算即可。

是有这么一个公式，但是把n代入这个公式后要求式子的值似乎也有难度

25 楼 fzuwwl 2011-04-07  

当n的达到几万亿或者更大的程度的时候，你这段求解代码是非常低效的；而实际上这个递推问题可以用矩阵算法来求解，时间复杂度可以降到O(log2 n)

24 楼 fivestarwy 2011-04-06  

囧，看了讨论，估计TLE一片啊，还是kimmking正解

23 楼 yangguo 2011-04-06  

在ACM世界里，这道题属于弱智题的行列，竟让这么多人望而生畏，都是培训惹的祸。。。

22 楼 kimmking 2011-04-06  

alosin 写道

高等数学。。。。。。。

离散、组合数学，或者数论、不定方程/连分数里会涉及这些

21 楼 kimmking 2011-04-06  

f(n) = A * f(n - 1) + B * f(n - 2)，给定f1,f2

广义斐波拉契，直接能求出来通项公式。
1、先化成1阶递推
另 α,β为 x^2=A*x+B的两个根，β>α,
则f(n+2)+β*f(n+1)=α*(f(n+1)+β*f(n))=....=α^n*(f2+β*f1)
另 D=f2+β*f1，则
f(n+2)-β^n*f2=D*(β^n-β^(n-1)*α+ ... β*α^(n-1)
另t=α/β,
f(n+2) = β^n*D*(1-(-t)^n)/(1+t) + -β^n*f2

等式右边全是已知数，直接能求出来f(n+2)
为了简化计算，计算右边的值的每一步，都先Mod 7再计算即可。

20 楼 hardPass 2011-04-06  

唉，太复杂了，没看懂啥意思。

还是用递归最简单，你说堆栈溢出？其实当然有办法解决啦！

递归转循环

public class AcmTest {
	
	public static int [] r; //也可以用简单的两个变量来存储f(n-1)和f(n-2)
	
	public static int a;
	
	public static int b;
	
	public static int n;
	
	public static void process(int n){
		if(n<3) {
			r[n] = 1;
			
			return;
		}
		
		r[n] = (a * r[n-1] + b * r[n-2]) % 7;
	}
	
	public static int calculate(int n, int a, int b){
		r = new int[n + 1];
		AcmTest.a = a;
		AcmTest.b = b;
		for (int i = 1; i <= n; i++) {
			process(i);			
		}
		
		return r[n];
		
	}
	
	public static void main(String args[]){
		int a = 2;
		int b = 2;
		//for (int i = 1; i <= 10000; i++) {
		//	System.out.println(calculate(i,a,b));
		//}
		System.out.println(calculate(3002,a,b));
	}
}

第2版本：

public class AcmTest {
	
	public static int fp1; // 存储 f(n-1)
	
	public static int fp2; // 存储 f(n-2)
	
	public static int a;
	
	public static int b;
	
	public static void process(int n){
		
		if(n<3) {
			fp2 = fp1;
			fp1 = 1;
			return;
		}
		
		int tmp = (a * fp1 + b * fp2) % 7;
		fp2 = fp1;
		fp1 = tmp;
	}
	
	public static int calculate(int n, int a, int b){
		fp1 = 0;
		fp2 = 0;
		AcmTest.a = a;
		AcmTest.b = b;
		for (int i = 1; i <= n; i++) {
			process(i);			
		}
		
		return fp1;
		
	}
	
	public static void main(String args[]){
		int a = 2;
		int b = 2;
		for (int i = 1; i <= 10; i++) {
			System.out.println(calculate(i,a,b));
		}
		System.out.println(calculate(3002,a,b));
	}
}

19 楼 yangyi 2011-04-06  

解循环的条件是
存在 连续的解x,y 使得：
x == n-2 且 y== n-1
因为 x 取值为0-6， y也为0-6，则xy组合的可能为49种
根据抽屉原理，当n == 50时，必然至少存在一次循环
因此，通过0-49的遍历，首先找出循环点，然后根据n的大小确定循环中的解

18 楼 lzyzizi 2011-04-06  

楼主，你的思路明显是有问题的，在对于n%49没有任何依据，你先写一个没有优化的算法对你这个优化的进行检证就会发现在n>49的时候就错误了~
1.从这个等式你就可以看书f(n)依赖的是f(n-1)和f(n-2)，而对于你摸49比如f(50)变成了
依赖f(1) f(0)了，你能证明f(1) f(0)和 f(49) f(48)相等么？
2.当n=49时，n%49=0 你的循环直接跳出了 ，这个代码本身是有逻辑错误的~

我的测试代码如下~在n<49时 均正确

def c1(a,b,n):
    if n==1 or n==2:
            return 1
    left = 1
    right = 1
    r = 0
    for i in xrange(2,n%49):
            r = (a*left + b*right)%7
            left,right = r,left
    return r

def c2(a,b,n):
    if n==1 or n==2:
            return 1
    left = 1
    right = 1
    r = 0
    for i in xrange(2,n):
            r = (a*left + b*right)%7
            left,right = r,left
    return r


def main():
    for  n in range(3,55):
        print "%d:"%n,c2(2,2,n),c1(2,2,n)

17 楼 xijieqjx 2011-04-06  

动态规划会好一些吧。

16 楼 mylazygirl 2011-04-06  

迭代么，呵呵

15 楼 yangguo 2011-04-06  

用java是完全没有问题的，本人有大量实践。楼主不必与人云亦云的一般见识。

14 楼 s929498110 2011-04-06  

记得ACM里面有的算法题很精辟啊

有一道题后面添加的条件是： 程序运行时间必须小于1S（java必须小于2S）

如果追求算法上的效率，使用java就勉强了。 即便你实现了，由于算法上的复杂性，你的代码可维护性和阅读性就大大降低了

13 楼 alosin 2011-04-06  

高等数学。。。。。。。

12 楼 mtnt2008 2011-04-05  

IcyFenix 写道

珠海的……BNUZ？

在JE中贴算法的帖子，很难引起关注的。去各大OJ站的讨论版玩吧。

+1

去poj吧

11 楼 agapple 2011-04-05  

看见ACM了进来瞄一下，貌似不适合这个版块。

10 楼 喜羊羊与灰太狼 2011-04-05  

用java写？估计过几天你就会发帖问为什么总是TLE了...

9 楼 forsecond 2011-04-05  

其实还好的啊。支持下

8 楼 yangyi 2011-04-05  

这是一个改进的斐波那契序列%49这块应该还可以再改进一下