精华内容
下载资源
问答
  • 斐波那契序列为1,1,2,3,5,8,13.......序列中的下一个数字为之前前两个数字的运算和。 方法1:矩阵思想 [0,1] [a] [b]  [1,1] * [b] = [a+b] ...

    斐波那契序列为1,1,2,3,5,8,13.......序列中的下一个数字为之前前两个数字的运算和。

    方法1:矩阵思想

                       [0,1]         [a]    [b]                                        

                    [1,1]    *    [b] = [a+b]       

    import pandas as pd
    import numpy as np
    
    
    def func(n):
        a=np.mat([[0,1],[1,1]])
        b=np.mat([[1],[1]])
        c=b
        for i in range(1,n):
            print(c[[1], [0]])
            c=a*c
    
    func(50)

     方法二:

    递归思想,但递归由于较耗时,这里利用缓存将参数n和结果保存到字典a中,速度为0.007s。

    a={}
    def fun(n):
        if a.get(n):
            return a[n]
    
        if n in [1,2]:
            return 1
        else:
            a[n]=fun(n-1)+fun(n-2)
            return a[n]
    start=time.time()
    print(fun(400))
    print(time.time()-start)

     方法三:

    生成器,对于递归,若较多时,仍旧不合适。

    #生成器思想
    def fun(n):
        a=0
        b=1
        for i in range(1,n):
            sum=a+b
            yield sum
            a=b
            b=sum

     

    转载于:https://www.cnblogs.com/xuehaiwuya0000/p/11604773.html

    展开全文
  • 斐波那契序列算法

    2021-01-26 06:24:35
    public class FibonacciHeap<T extends Comparable> { private Node<T> minNode; private int size; public FibonacciHeap() { minNode = null; size = 0; } private FibonacciHeap(Node<...privat

    public class FibonacciHeap<T extends Comparable> {

    private Node<T> minNode;
    private int size;
    
    public FibonacciHeap() {
        minNode = null;
        size = 0;
    }
    
    private FibonacciHeap(Node<T> node) {
        minNode = node;
        size = 1;
    }
    
    private FibonacciHeap(Node<T> minNode, int size) {
        this.minNode = minNode;
        this.size = size;
    }
    
    public boolean isEmpty() {
        return minNode == null;
    }
    
    public void clear() {
        minNode = null;
        size = 0;
    }
    
    public Node<T> insert(T key) {
        Node<T> node = new Node<T>(key);
        minNode = mergeLists(minNode, node);
        size++;
        return node;
    }
    
    public Node<T> findMinimum() {
        return minNode;
    }
    
    public void decreaseKey(Node<T> node, T newKey) {
        if (newKey.compareTo(node.key) > 0) {
            throw new IllegalArgumentException("New key is larger than old key.");
        }
    
        node.key = newKey;
        Node<T> parent = node.parent;
        if (parent != null && node.compareTo(parent) < 0) {
            cut(node, parent);
            cascadingCut(parent);
        }
        if (node.compareTo(minNode) < 0) {
            minNode = node;
        }
    }
    
    private void cut(Node<T> node, Node<T> parent) {
        removeNodeFromList(node);
        parent.degree--;
        mergeLists(minNode, node);
        node.isMarked = false;
    }
    
    private void cascadingCut(Node<T> node) {
        Node<T> parent = node.parent;
        if (parent != null) {
            if (node.isMarked) {
                cut(node, parent);
                cascadingCut(parent);
            } else {
                node.isMarked = true;
            }
        }
    }
    
    public void delete(Node<T> node) {
        // This is a special implementation of decreaseKey that sets the
        // argument to the minimum value. This is necessary to make generic keys
        // work, since there is no MIN_VALUE constant for generic types.
        node.isMinimum = true;
        Node<T> parent = node.parent;
        if (parent != null) {
            cut(node, parent);
            cascadingCut(parent);
        }
        minNode = node;
    
        extractMin();
    }
    
    public Node<T> extractMin() {
        Node<T> extractedMin = minNode;
        if (extractedMin != null) {
            // Set parent to null for the minimum's children
            if (extractedMin.child != null) {
                Node<T> child = extractedMin.child;
                do {
                    child.parent = null;
                    child = child.next;
                } while (child != extractedMin.child);
            }
    
            Node<T> nextInRootList = minNode.next == minNode ? null : minNode.next;
    
            // Remove min from root list
            removeNodeFromList(extractedMin);
            size--;
    
            // Merge the children of the minimum node with the root list
            minNode = mergeLists(nextInRootList, extractedMin.child);
    
            if (nextInRootList != null) {
                minNode = nextInRootList;
                consolidate();
            }
        }
        return extractedMin;
    }
    
    private void consolidate() {
        List<Node<T>> aux = new ArrayList<Node<T>>();
        NodeListIterator<T> it = new NodeListIterator<T>(minNode);
        while (it.hasNext()) {
            Node<T> current = it.next();
    
            while (aux.size() <= current.degree + 1) {
                aux.add(null);
            }
    
            // If there exists another node with the same degree, merge them
            while (aux.get(current.degree) != null) {
                if (current.key.compareTo(aux.get(current.degree).key) > 0) {
                    Node<T> temp = current;
                    current = aux.get(current.degree);
                    aux.set(current.degree, temp);
                }
                linkHeaps(aux.get(current.degree), current);
                aux.set(current.degree, null);
                current.degree++;
            }
    
            while (aux.size() <= current.degree + 1) {
                aux.add(null);
            }
            aux.set(current.degree, current);
        }
    
        minNode = null;
        for (int i = 0; i < aux.size(); i++) {
            if (aux.get(i) != null) {
                // Remove siblings before merging
                aux.get(i).next = aux.get(i);
                aux.get(i).prev = aux.get(i);
                minNode = mergeLists(minNode, aux.get(i));
            }
        }
    }
    
    private void removeNodeFromList(Node<T> node) {
        Node<T> prev = node.prev;
        Node<T> next = node.next;
        prev.next = next;
        next.prev = prev;
    
        node.next = node;
        node.prev = node;
    }
    
    private void linkHeaps(Node<T> max, Node<T> min) {
        removeNodeFromList(max);
        min.child = mergeLists(max, min.child);
        max.parent = min;
        max.isMarked = false;
    }
    
    // Union another fibonacci heap with this one
    public void union(FibonacciHeap<T> other) {
        minNode = mergeLists(minNode, other.minNode);
        size += other.size;
    }
    
    // Merges two lists and returns the minimum node
    public static <T extends Comparable<T>> Node<T> mergeLists(
            Node<T> a, Node<T> b) {
    
        if (a == null && b == null) {
            return null;
        }
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }
    
        Node<T> temp = a.next;
        a.next = b.next;
        a.next.prev = a;
        b.next = temp;
        b.next.prev = b;
    
        return a.compareTo(b) < 0 ? a : b;
    }
    
    public void print() {
        System.out.println("Fibonacci heap:");
        if (minNode != null) {
            minNode.print(0);
        }
    }
    
    public static class Node<T extends Comparable<T>>
            implements Comparable<Node<T>> {
    
        private T key;
        private int degree;
        private Node<T> parent;
        private Node<T> child;
        private Node<T> prev;
        private Node<T> next;
        private boolean isMarked;
        private boolean isMinimum;
    
        public Node() {
            key = null;
        }
    
        public Node(T key) {
            this.key = key;
            next = this;
            prev = this;
        }
    
        public T getKey() {
            return key;
        }
    
        public int compareTo(Node<T> other) {
            return this.key.compareTo(other.key);
        }
    
        private void print(int level) {
            Node<T> curr = this;
            do {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < level; i++) {
                    sb.append(" ");
                }
                sb.append(curr.key.toString());
                System.out.println(sb.toString());
                if (curr.child != null) {
                    curr.child.print(level + 1);
                }
                curr = curr.next;
            } while (curr != this);
        }
    }
    
    // This Iterator is used to simplify the consolidate() method. It works by
    // gathering a list of the nodes in the list in the constructor since the
    // nodes can change during consolidation.
    public static class NodeListIterator<T extends Comparable<T>>
            implements Iterator<Node<T>> {
    
        private Queue<Node<T>> items = new LinkedList<Node<T>>();
    
        public NodeListIterator(Node<T> start) {
            if (start == null) {
                return;
            }
    
            Node<T> current = start;
            do {
                items.add(current);
                current = current.next;
            } while (start != current);
        }
    
        public boolean hasNext() {
            return items.peek() != null;
        }
    
        public Node<T> next() {
            return items.poll();
        }
    
        public void remove() {
            throw new UnsupportedOperationException(
                    "NodeListIterator.remove is not implemented");
        }
    }
    

    }

    展开全文
  • 给定一个数字字符串 S,比如 S = “123456579”,我们可以将它分成斐波那契式的序列 [123, 456, 579]。 形式上,斐波那契序列是一个非负整数列表 F,且满足: 0 <= F[i] <= 2^31 - 1,(也就是说,每个整数...

    题目

    给定一个数字字符串 S,比如 S = “123456579”,我们可以将它分成斐波那契式的序列 [123, 456, 579]。

    形式上,斐波那契式序列是一个非负整数列表 F,且满足:

    0 <= F[i] <= 2^31 - 1,(也就是说,每个整数都符合 32 位有符号整数类型);
    F.length >= 3;
    对于所有的0 <= i < F.length - 2,都有 F[i] + F[i+1] = F[i+2] 成立。
    另外,请注意,将字符串拆分成小块时,每个块的数字一定不要以零开头,除非这个块是数字 0 本身。

    返回从 S 拆分出来的任意一组斐波那契式的序列块,如果不能拆分则返回 []。

    示例 1:
    
    输入:"123456579"
    输出:[123,456,579]
    示例 2:
    
    输入: "11235813"
    输出: [1,1,2,3,5,8,13]
    示例 3:
    
    输入: "112358130"
    输出: []
    解释: 这项任务无法完成。
    示例 4:
    
    输入:"0123"
    输出:[]
    解释:每个块的数字不能以零开头,因此 "01""2""3" 不是有效答案。
    示例 5:
    
    输入: "1101111"
    输出: [110, 1, 111]
    解释: 输出 [11,0,11,11] 也同样被接受。
    

    提示:

    1 <= S.length <= 200
    字符串 S 中只含有数字。

    链接:https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence

    解题记录

    • 通过回溯算法计算,每次获取一段字符转化为数字
    • 注意数字的不能大于Integer.MAX_VALUE
    • 两位数字开头不能为0等情况
    /**
     * @author: ffzs
     * @Date: 2020/12/8 下午7:46
     */
    public class Solution {
    
        public List<Integer> splitIntoFibonacci(String S) {
            List<Integer> res = new ArrayList<>();
            dfs(S.toCharArray(), res, 0);
            return res;
        }
    
        private boolean dfs(char[] cs, List<Integer> list, int index) {
            if (index == cs.length) return list.size() >= 3;
    
            long curL = 0L;
            for (int i = index; i < cs.length; i++) {
                if (i > index && cs[index] == '0') break;
                curL = curL * 10 + cs[i] - '0';
                if (curL > Integer.MAX_VALUE) break;
                int cur = (int)curL, size = list.size();
                if (size >= 2) {
                    int sum = list.get(size-1) + list.get(size-2);
                    if (cur < sum) continue;
                    else if (cur > sum) break;
                }
                list.add(cur);
                if (dfs(cs, list, i+1)) return true;
                else list.remove(list.size()-1);
            }
            return false;
        }
    }
    

    image-20201208204032867

    展开全文
  • 将数组拆分成斐波那契序列 https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/ 给定一个数字字符串 S,比如 S = "123456579",我们可以将它分成斐波那契式的序列 [123, 456, 579]。 形式上...

     

    力扣842. 将数组拆分成斐波那契序列

    https://leetcode-cn.com/problems/split-array-into-fibonacci-sequence/

    给定一个数字字符串 S,比如 S = "123456579",我们可以将它分成斐波那契式的序列 [123, 456, 579]。

    形式上,斐波那契式序列是一个非负整数列表 F,且满足:

    0 <= F[i] <= 2^31 - 1,(也就是说,每个整数都符合 32 位有符号整数类型);
    F.length >= 3;
    对于所有的0 <= i < F.length - 2,都有 F[i] + F[i+1] = F[i+2] 成立。
    另外,请注意,将字符串拆分成小块时,每个块的数字一定不要以零开头,除非这个块是数字 0 本身。

    返回从 S 拆分出来的任意一组斐波那契式的序列块,如果不能拆分则返回 []。

     

    示例 1:

    输入:"123456579"
    输出:[123,456,579]
    示例 2:

    输入: "11235813"
    输出: [1,1,2,3,5,8,13]
    示例 3:

    输入: "112358130"
    输出: []
    解释: 这项任务无法完成。
    示例 4:

    输入:"0123"
    输出:[]
    解释:每个块的数字不能以零开头,因此 "01","2","3" 不是有效答案。
    示例 5:

    输入: "1101111"
    输出: [110, 1, 111]
    解释: 输出 [11,0,11,11] 也同样被接受。

    回溯算法

    回溯算法模板

    bool backtrack("原始参数") {
        //终止条件(递归必须要有终止条件)
        if ("终止条件") {
            //一些逻辑操作(可有可无,视情况而定)
            return true;
        }
    
        for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
            //一些逻辑操作(可有可无,视情况而定)
    
            //做出选择
    
            //递归
            if(backtrack("新的参数"))return true;
            //一些逻辑操作(可有可无,视情况而定)
    
            //撤销选择
        }
        return false;
    }
    // 842splitIntoFibonacci.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
    //
    
    #include <iostream>
    #include<vector>
    #include<string>
    using namespace std;
    class Solution {
    public:
        vector<int> splitIntoFibonacci(string S) {
            vector<int>result;
            if(backtrack(result,0,S)){ 
                return result; 
            }
            else
            {
                vector<int>resulttemp;
                return resulttemp;
            }
        }
        bool backtrack(vector<int>&result,int index,string S) {
            //终止条件(递归必须要有终止条件)
            //边界条件判断,如果截取完了,并且res长度大于等于3,表示找到了一个组合。
            if (index==S.length() && result.size()>=3)
            {
                return true;
            }
            for (int i = index; i < S.length(); i++)
            {
                //两位以上的数字不能以0开头
                if (S[index]=='0' && i>index)
                {
                    break;
                }
                //截取字符串转化为数字
                long long num = stringtonum(S,index,i+1);
                //如果截取的数字大于int的最大值,则终止截取,代表到最末尾了
                if (num>INT_MAX)
                {
                    break;
                }
                //做出选择
                int resultsize = result.size();
                //如果截取的数字大于result中前两个数字的和,说明这次截取的太大,直接终止,因为后面越截取越大
                if (resultsize>=2 && num>((long long)result[resultsize-1]+ (long long)result[resultsize - 2]))
                {
                    //
                    break;
                }
                //如果截取的数字小于result中前两个数字的和,说明这次截取的太小,continue,继续后移
                if (resultsize >= 2 && num < ((long long)result[resultsize - 1] + (long long)result[resultsize - 2]))
                {
                    continue;
                }
                //先把数字num添加到集合result中
                result.push_back(num);
                //递归
                //如果找到了就直接返回
                if (backtrack(result,i+1,S))
                {
                    return true;
                }
                //撤销选择
                //如果没找到,就会走回溯这一步,然后把上一步添加到集合res中的数字给移除掉
                result.pop_back();
            }
            return false;
        }
        //相当于截取字符串S中的子串然后转换为十进制数字
        long long stringtonum(string S,int start,int end) {
            long long num = 0;
            for (int i = start; i < end; i++)
            {
                num = num * 10 + (S[i] - 48);
            }
            return num;
        }
    };
    int main()
    {
        Solution s;
        string S;
        S = "214748364721474836422147483641";
        auto result = s.splitIntoFibonacci(S);
        for (int i = 0; i < result.size(); i++)
        {
            cout << result[i] << "  ";
        }
        cout << "\n";
        std::cout << "Hello World!\n";
    }
    

     

    展开全文
  • 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887,...
  • 给定一个数字字符串 S,比如 S = “123456579”,我们可以将它分成斐波那契式的序列 [123, 456, 579]。 形式上,斐波那契序列是一个非负整数列表 F,且满足: 0 <= F[i] <= 2^31 - 1,(也就是说,每个整数...
  • 其实题意也不是很难,就是给你一个字符串,都是数字,然后让你将这个字符串拆开,组成一个斐波那契序列,也就是说,至少要拆分成三个数字,且要满足,后一项是前两项的和。 代码我就说下我自己的一些理解 class ...
  • 算法学习---将字符串拆分成斐波那契序列 给定一个数字字符串 S,比如 S = “123456579”,我们可以将它分成斐波那契式的序列 [123, 456, 579]。 形式上,斐波那契式序列是一个非负整数列表 F,且满足: 0 <= F[i]...
  • 想看更多算法题,可以扫描上方二维码关注我微信公众号“数据结构和算法”,截止到目前我已经在公众号中更新了500多道算法题,其中部分已经整理成了pdf文档,截止到目前总共有800多页(并且还会不断的增加),可以在...
  • 问题:给你一个严格单调递增的数组,请问数组里最长的斐波那契序列的长度是多少?例如,如果输入的数组是[1, 2, 3, 4, 5, 6, 7, 8],由于其中最长的斐波那契序列是1, 2, 3, 5, 8,因此输出应该是5。 分析:这是...
  • 斐波那契序列

    2017-06-07 19:35:03
    Fibonacci数列如下:  / 0 n=0 f(n)= 1 n=1  \ f(n-1)+f(n-2) n=2 算法1:递归 #include using namespace std; int Fibonacci(int n) {
  • 这道题其实并不难,斐波那契序列里面起作用的也就是前两个数,第一个和第二个数确定了,那么整个数列就确定了,那么后面我们只需要验证就可以了, 思路:我们可以循环取前两个数,然后验证后面的数是否符合要求,...
  • 斐波那契查找算法

    2020-08-16 12:56:12
    对于连续的序列提高了效率 3.斐波那契查找 package search; import java.util.Arrays; public class FibonacciSearch { public static int maxSize = 20; public static void main(String[]
  • 斐波那契序列 集锦

    2012-04-19 21:12:11
    斐波那契序列 集锦 http://www.cnblogs.com/Knuth/archive/2009/09/04/1559951.html [定理1] 标准Fibonacci序列(即第0项为0,第1项为1的序列)当N大于1时,一定有f(N)和f(N-1)互质 其实,结合“互质”的定义,和...
  • python 斐波那契数列 算法

    热门讨论 2021-01-18 15:43:56
    斐波那契数,通常用F(n)表示,形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,F(1) = 1 F(n) = F(n - 1) + F(n - 2),其中 n > 1 给你 n ,请...
  • 难度:中等题目:给定一个数字字符串S,比如S = "123456579",我们可以将它分成斐波那契式的序列[123, 456, 579]。形式上,斐波那契序列是一个非负整数列表F,且满足:0 <= F[i] <= 2^31 - 1,(也就是说,每...
  • 利用循环队列编写求k阶斐波那契序列中第n+1项fn的算法 ##记录一下自己做题时的历程 错误示例: SqQueue Q; Q.base=(ElemType )malloc(ksizeof(ElemType)); Q.maxSize=k; Q.front=Q.rear=0; if(k<1||Q.maxSize<...
  • 难度:中等题目:给定一个数字字符串S,比如S = "123456579",我们可以将它分成斐波那契式的序列[123, 456, 579]。形式上,斐波那契序列是一个非负整数列表F,且满足:0 <= F[i] <= 2^31 - 1,(也就是说,每...
  • 4阶斐波那契序列如下:f0=f1=f2=0, f3=1,…,fi=fi-1+fi-2+fi-3+fi-4, 利用容量为k=4的循环队列,构造序列的前n+1项(f0, f1 , f2 ,… fn ),要求满足fn ≤200而fn+1 >200。 算法 对于一个队列,总有四个值在...
  • K阶斐波那契的定义:第k和k+1项为1,前k - 1项为0,从k项之后每一项都是前k项的和 例如: k=3; 0,0,1,1,2,4,7,13规律: 后一项等于前一项的2倍减去前K+1项 13 = 2*7 -1 7 = 2*4 -1 4 =2*2-0 C语言实现#include #...

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 363
精华内容 145
关键字:

斐波那契序列算法