2 favorous favorous 于 2014.12.15 00:50 提问

斐波那契数列的应用问题

著名的斐波那契数列:Fn = Fn-1 + Fn-2 (F1=F2=1),前几个斐波那契数为,1,1,2,3,5,8,13,21….
某一个整数可以拆成若干彼此不同的斐波那契数之和,比如13=13,13=5+8,13=2+3+8;16=1+2+13,16=1+2+5+8,16=3+13,16=3+5+8
现在求解这样一个问题,给定某个数值n,求有多少种方案可以把该数分解成若干彼此不同的斐波那契数之和。
求各位大神帮忙,明天就要交代码了,现在还没思路。。。可以用数组存储吗?

2个回答

devmiao
devmiao   Ds   Rxr 2014.12.15 02:02
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 13;
            foreach (var item in Resolve(Fibonacci(n).ToArray(), new int[] { 0 }, n))
                Console.WriteLine(string.Join(" + ", item.Select(x => x.ToString())) + " = " + n.ToString());
        }

        static IEnumerable<IEnumerable<int>> Resolve(IEnumerable<int> source, IEnumerable<int> cur, int seed)
        {
            if (seed == cur.Sum()) return new List<IEnumerable<int>> { cur.Where(x => x > 0) };
            return source.Except(cur)
                .Where(x => x + cur.Sum() <= seed && x > cur.Last())
                .SelectMany(x => Resolve(source, cur.Concat(new int[] { x }), seed));
        }

        static IEnumerable<int> Fibonacci(int max)
        {
            int m = 1, n = 1;
            yield return m;
            while (n <= max)
            {
                yield return n;
                n = n + m;
                m = n - m;
            }
        }
    }
}

2 + 3 + 8 = 13
5 + 8 = 13
13 = 13
Press any key to continue . . .

devmiao
devmiao   Ds   Rxr 2014.12.15 02:04

1000的运行结果:
2 + 3 + 8 + 21 + 34 + 89 + 233 + 610 = 1000
2 + 3 + 8 + 55 + 89 + 233 + 610 = 1000
2 + 3 + 8 + 144 + 233 + 610 = 1000
2 + 3 + 8 + 377 + 610 = 1000
2 + 3 + 8 + 987 = 1000
5 + 8 + 21 + 34 + 89 + 233 + 610 = 1000
5 + 8 + 55 + 89 + 233 + 610 = 1000
5 + 8 + 144 + 233 + 610 = 1000
5 + 8 + 377 + 610 = 1000
5 + 8 + 987 = 1000
13 + 21 + 34 + 89 + 233 + 610 = 1000
13 + 55 + 89 + 233 + 610 = 1000
13 + 144 + 233 + 610 = 1000
13 + 377 + 610 = 1000
13 + 987 = 1000
Press any key to continue . . .

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!