相关疑难解决方法(0)

大多数拥有CS学位的人肯定会知道Big O代表什么.它可以帮助我们衡量算法的实际效率(如何),如果你知道你试图解决的问题属于哪个类别,你可以弄清楚是否仍然可以挤出那么少的额外性能.¹

但我很好奇,你如何计算或近似算法的复杂性？

¹ _{但正如他们所说,不要过度,过早优化是所有邪恶的根源,没有正当理由的优化也应该得到这个名称.}

什么是动态编程？

它与递归,记忆等有什么不同？

我已经阅读了维基百科上的文章,但我仍然不太了解它.

所以我试图在Fibonacci序列中尽可能紧凑地写出第n个数:

public uint fibn ( uint N ) 
{
   return (N == 0 || N == 1) ? 1 : fibn(N-1) + fibn(N-2);
}

但我想知道我是否可以通过改变来使其更加紧凑和高效

(N == 0 || N == 1)

进入单一比较.是否有一些奇特的位移操作可以做到这一点？

在Haskell中,如何基于第n个Fibonacci数等于第(n-2)个Fibonacci数加上第(n-1)个Fibonacci数的属性生成Fibonacci数？

我见过这个:

fibs :: [Integer]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

我真的不明白,或者它是如何产生无限列表而不是包含3个元素的列表.

我如何通过计算实际定义来编写haskell代码,而不是通过使用list函数做一些非常奇怪的事情？

我试图找到使用递归树的Fibonacci系列的复杂性,并因此得出height of tree = O(n)最坏情况cost of each level = cncomplexity = n*n=n^2

怎么回事O(2^n)？

我只是尝试用各种方法实现代码(在Java中),通过它可以计算斐波那契数列的第n项,并且我希望验证我学到了什么.

迭代实现如下:

public int iterativeFibonacci(int n)
{
  if ( n == 1 ) return 0;
  else if ( n == 2 ) return 1;
  int i = 0, j = 1, sum = 0;
  for ( ; (n-2) != 0; --n )
  {
    sum = i + j;
    i = j;
    j = sum;
  }
  return sum;
}

递归实现如下: -

  public int recursiveFibonacci(int n)
  {
    if ( n == 1 ) return 0;
    else if ( n == 2 ) …

我写了一个递归计算斐波纳契数的程序,用a ConcurrentHashMap和 computeIfAbsent()方法:

程序工作绝对正常,当我使用小值8,9,10,但当从程序的值增加永远停止时卡在无限循环中10 to 20

 public class Test {
    static Map<Integer, Integer> concurrentMap = new ConcurrentHashMap<>();

    public static void main(String[] args) {
        System.out.println("Fibonacci result for 20 is" + fibonacci(20));
    }

    static int fibonacci(int i) {
        if (i == 0)
            return i;

        if (i == 1)
            return 1;

        return concurrentMap.computeIfAbsent(i, (key) -> {
            System.out.println("Value is " + key);
            return fibonacci(i - 2) + fibonacci(i - 1);
        });
    }
}

有人可以告诉我为什么它会永远被卡住吗？

我是一名CSE学生,正准备参加编程竞赛.现在我正在研究Fibonacci系列.我有一个大小约为包含正整数的Kilo字节的输入文件.输入甲酸酯看起来像

3 5 6 7 8 0

零表示文件结束.输出应该如此

2 
5 
8 
13 
21 

我的代码是

#include<stdio.h>

int fibonacci(int n) {
  if (n==1 || n==2)
    return 1;
  else
    return fibonacci(n-1) +fibonacci(n-2);
}
int main() {
  int z;
  FILE * fp;    
  fp = fopen ("input.txt","r");    
  while(fscanf(fp,"%d", &z) && z) 
   printf("%d \n",fibonacci(z));
  return 0;
}

该代码适用于样本输入并提供准确的结果但问题是我的实际输入集它花费的时间超过我的时间限制.谁能帮我吗.

请考虑以下代码段:

int fib(int N)
{
   if(N<2) return 1;
   return (fib(N-1) + fib(N-2));
}

鉴于fib从主要调用N为10,35,67,...(比如说),总共拨打了多少电话fib？

这个问题有什么关系吗？

PS:这是一个理论问题,不应该被执行.

编辑:

我知道其他方法可以更快地计算Fibonacci系列.

我想要一个解决方案来计算fib被调用为fib(40),fib(50),...而没有编译器的帮助,并且在考试条件下你应该回答40个类似于这个规定的问题时间(约30分钟).

谢谢,

请参阅以下代码:

std::function<int(int)> makeFibonacci() {
    std::function<int(int)> fibonacci = [&fibonacci](int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 1;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    };
    return fibonacci;
};

int main() {
    std::function<int(int)> fibonacci = makeFibonacci();
    std::cout << fibonacci(6) << std::endl;
    return 0;
}

当我运行它时,数字8按预期输出.但是,当我将捕获更改&fibonacci为仅fibonacci用于副本捕获时,程序实际上会main在其运行的第一行上进行段错误makeFibonacci.

如果fibonacci(第2行)是makeFibonacci函数的局部函数,因此当函数退出时超出范围,如何通过引用捕获并递归使用？另外,为什么当我通过副本捕获lambda时程序会出现段错误？