牛牛切木棒

[编程题]牛牛切木棒

热度指数：472 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一根长度为a $(3 \leq a \leq 1e18)$ 的木棒，现在想将木棒分成一些段（每段木棒长度必须为整数），使得分隔后的木棍中，任意三段都不能构成三角形，求木棒最多被分成几段呢？

示例1

输入

输出

说明

可以分成1 1 3三段

备注:

算法知识视频讲解

Java

牛客196305255号

其实就是一个求斐波那契数列和问题。

 public int stick (long a) {
         ArrayList<Long> list=new ArrayList<>();
		list.add(1l);
		list.add(1l);
		long count=a-2;
		while(true) {
		    int k=list.size()-1;
		    long n=list.get(k)+list.get(--k);
			if(count<n)
				break;
			else {
				list.add(n);
				count-=n;
			}  
		}
	   return list.size();
    }

发表于 2020-12-05 20:01:14 回复(0)