如何证明欧几里德算法的伪代码？ [英] How to prove this pseudo code of Euclids' algorithm?

问题描述

A(n,m):
{
 if n==m, return(n)
 else
{
 t = 1;
 while {n and m are divisible by 2}
 { t=2t, n = n/2, m=m/2 };
 while {n is divisible by 2} n = n/2;
 while {m is divisible by 2} m=m/2;
 if n==m, return( t * n)
 else
 {
 k = m - n;
 while {k is divisible by 2} k=k/2;
 return( t * A( min(n,m), |k| ) )
 }
 }
}

推荐答案

通过形式验证证明代码确实是一项复杂的任务。

接受代码的常用方法因为'足够好'在一组已知输入上运行它，然后将其输出与预期输出进行比较。您可以通过将伪代码转换为实际程序来轻松实现。

Proving code by formal verification is really a complex task.
A common way to accept code as 'good enough' is running it on a known set of inputs and then comparing its outputs with the expected ones. You might easily do that by translating the pseudo code into an actual program.

这篇关于如何证明欧几里德算法的伪代码？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！