31 lines
669 B
Plaintext
31 lines
669 B
Plaintext
function GC(s: string, n: nat): nat
|
|
requires n <= |s|
|
|
{
|
|
if n == 0 then 0 else GC(s, n - 1) + (if s[n - 1] == 'G' || s[n - 1] == 'C' then 1 else 0)
|
|
}
|
|
|
|
lemma GCAtMost(s: string, n: nat)
|
|
requires n <= |s|
|
|
ensures GC(s, n) <= n
|
|
{
|
|
if n > 0 { GCAtMost(s, n - 1); }
|
|
}
|
|
|
|
method GCContent(s: string) returns (f: real)
|
|
requires |s| > 0
|
|
ensures f == (GC(s, |s|) as real) / (|s| as real)
|
|
ensures 0.0 <= f <= 1.0
|
|
{
|
|
var count := 0;
|
|
var i := 0;
|
|
while i < |s|
|
|
invariant 0 <= i <= |s|
|
|
invariant count == GC(s, i)
|
|
{
|
|
if s[i] == 'G' || s[i] == 'C' { count := count + 1; }
|
|
i := i + 1;
|
|
}
|
|
GCAtMost(s, |s|);
|
|
f := (count as real) / (|s| as real);
|
|
}
|