Debian Codegraph @

tests/inputs/fib.dfy

raw
1 /*
2 https://dafny.org/latest/OnlineTutorial/guide
3 */
4 function fib(n: nat): nat
5 {
6 if n == 0 then 0
7 else if n == 1 then 1
8 else fib(n - 1) + fib(n - 2)
9 }
10 method ComputeFib(n: nat) returns (b: nat)
11 ensures b == fib(n) // Do not change this postcondition
12 {
13 // Change the method body to instead use c as described.
14 // You will need to change both the initialization and the loop.
15 if n == 0 { return 0; }
16 var i: int := 1;
17 var a := 0;
18 b := 1;
19 while i < n
20 invariant 0 < i <= n
21 invariant a == fib(i - 1)
22 invariant b == fib(i)
23 {
24 a, b := b, a + b;
25 i := i + 1;
26 }
27 }