我正在努力学习如何正确地证明程序的正确性.我从头开始,在第一步/主题介绍中挂断了.
在本文关于全函数规划的文章中,给出了斐波那契函数的两个定义.传统的一个:
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
--fib (n+2) = fib (n+1) + fib (n+2) --The definition as given in the paper
--It seems incorrect to me. Typo?
和我以前从未见过的尾递归版本:
fib' n = f n 0 1
f 0 a b = a
f n a b = f (n-1) b (a+b)
该论文随后声称,通过归纳证明两个函数对所有正整数n都返回相同的结果是"直截了当"的.这是我第一次想到分析这样的程序.认为你可以证明两个程序是等价的,这是非常有趣的,所以我立即尝试通过归纳自己来做这个证明.要么我的数学技能都生锈了,要么任务实际上并不那么简单.
我证明了n = 1
fib' 1 = f 1 0 1
= f 0 1 1 …haskell correctness functional-programming fibonacci induction
我在这篇博客文章中找到了以下代码示例:
final String FIBONACCI =
"(?x) .? | ( \\2?+ (\\1|^.) )* ..";
for (int n = 0; n < 10000; n++) {
String s = new String(new char[n]);
if (s.matches(FIBONACCI)) {
System.out.printf("%s ", n);
}
}
输出: 0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 ...
如何(?x) .? | ( \\2?+ (\\1|^.) )* ..符合斐波那契数？
我写了一个递归计算斐波纳契数的程序,用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);
});
}
}
有人可以告诉我为什么它会永远被卡住吗？
我需要制作一个程序,询问打印的Fibonacci数量,然后将它们打印出来,如0,1,1,2 ...但我无法让它工作.我的代码看起来如下:
a = int(raw_input('Give amount: '))
def fib():
a, b = 0, 1
while 1:
yield a
a, b = b, a + b
a = fib()
a.next()
0
for i in range(a):
print a.next(),
我正在尝试实现以下功能,但它一直给我stack level too deep (SystemStackError)错误.
任何想法可能是什么问题？
def fibonacci( n )
[ n ] if ( 0..1 ).include? n
( fibonacci( n - 1 ) + fibonacci( n - 2 ) ) if n > 1
end
puts fibonacci( 5 )
我是一名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;
}
该代码适用于样本输入并提供准确的结果但问题是我的实际输入集它花费的时间超过我的时间限制.谁能帮我吗.
当k = 2时,我们都知道斐波那契数列.
即: 1,1,2,3,5,8,13
但这是2-fibonacci.像这样,我可以算第三个斐波那契:
1,1,2,4,7,13,24
而4-fibonacci:
1,1,2,4,8,15,29
......等等
我要问的是计算k-fibonacci系列中'n'元素的算法.
像这样:如果我要求fibonacci(n=5,k=4),结果应该是:8,即4-fibonacci系列中的第五个元素.
我没有在任何网站找到它.帮助的资源可能是mathworld
任何人？如果你知道python,我更喜欢.但如果没有,任何语言或算法都可以提供帮助.
提示我认为这可以帮助:让我们分析k-fibonacci系列,其中k将从1到5
k fibonacci series
1 1, 1, 1, 1, 1, 1, 1, 1,1, 1, 1, ...
2 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
3 1, 1, 2, 4, 7, 13, 24, 44, 81, ...
4 1, 1, 2, 4, 8, 15, 29, 56, 108, ...
5 1, 1, 2, 4, 8, 16, 31, 61, 120, ... …我需要一些帮助,我正在为Universiy的Programming II课程编写一个程序.问题是要求使用递归计算Fibonacci序列.必须将计算出的斐波纳契数存储在一个数组中,以阻止不必要的重复计算并减少计算时间.
我设法让程序在没有数组和记忆的情况下工作,现在我正在尝试实现它并且我被卡住了.我不确定如何构建它.我用谷歌搜索并略读了一些书,但没有找到太多帮助我解决如何实施解决方案.
import javax.swing.JOptionPane;
public class question2
{
static int count = 0;
static int [] dictionary;
public static void main(String[] args)
{
int answer;
int num = Integer.parseInt(javax.swing.JOptionPane.showInputDialog("Enter n:"));
javax.swing.JOptionPane.showMessageDialog(null,
"About to calculate fibonacci(" + num + ")");
//giving the array "n" elements
dictionary= new int [num];
if (dictionary.length>=0)
dictionary[0]= 0;
if (dictionary.length>=1)
dictionary[0]= 0;
dictionary[1]= 1;
//method call
answer = fibonacci(num);
//output
JOptionPane.showMessageDialog(null,"Fibonacci("+num+") is "+answer+" (took "+count+" calls)");
}
static int fibonacci(int n)
{
count++;
// Only …当我在数字的输入中意识到一些"奇怪的"形式时,我正在观察我在Haskell中的Fibobacci序列实现的结果.
首先,这是我提出的Haskell代码:
fib :: Integer -> [Integer]
fib 0 = [0]
fib 1 = [0, 1]
fib a = (fib' 0 1 [0,1] 1 a)
fib' :: Integer -> Integer -> [Integer] -> Integer -> Integer -> [Integer]
fib' n1 n2 l cont n
| cont == n = l
| otherwise = (fib' n2 n3 (l++[n3]) (cont+1) n)
where n3 = n2 + n1
对于像fib 10这样的东西,输出将是:[0,1,1,2,3,5,8,13,21,34,55]然后我想尝试像fib 1000这样的东西,而数字非常大,所有...我看到的是由","形成的一些奇怪的elipses,从列表中的每个Integer之间打印出来,例如:
所以我最大化了输出窗口的大小,看看这个奇怪的模式是否仍会重复,答案是肯定的:
我的问题是:
有人知道为什么在列表中的整数之间的","中出现这种模式？难道不应该更随机而不是像elipses一样吗？
我试图更好地理解递归以及return语句的工作原理.因此,我正在查看一段代码,用于识别与给定术语相关的斐波那契数 - 在这种情况下,4.我很难理解else语句.
def f(n):
if n == 0:
return 0
if n == 1:
return 1
else:
return f(n-1) + f(n-2)
f(4)
我已经尝试使用Visualize Python来检查每一步发生了什么,但是当它遇到else语句时我迷路了.
看起来它取n的值并减去1,以创建一个新的n值3,它返回到函数定义.所以它似乎只返回else语句中第一个函数的值.但是,写入else语句是为了返回2个函数f(n-1)+ f(n-2)的总和,在这种情况下我认为返回值是5？你能在一起添加2个功能吗？
在此先感谢您的帮助.
这是Visualize Python Sum of 2函数中代码的链接