证明或否定:
定义计算次数C(gcd(a,b))C(gcd(a,b))C(gcd(a,b))为以下递归函数的调用次数:(例如C(gcd(10,4))=3,C(gcd(25,7))=5C(gcd(10,4))=3,C(gcd(25,7))=5C(gcd(10,4))=3,C(gcd(25,7))=5,要求a⩾ba\geqslant ba⩾b)
int gcd(int a,int b){ return b?gcd(b,a%b):a; }
再定义正整数nnn的位数W(n)=⌊log10n⌋+1W(n)=\lfloor log_{10}{n} \rfloor+1W(n)=⌊log10n⌋+1
最后定义一次辗转相除法运算的优越度N(a,b)=C(gcd(a,b))W(a)+W(b)N(a,b)=\frac{C(gcd(a,b))}{W(a)+W(b)}N(a,b)=W(a)+W(b)C(gcd(a,b))
那么在数组(x,y)∈U={(x,y)∣x⩾y,x,y∈N}(x,y)\in U=\left\{(x,y)|x\geqslant y,x,y\in N\right\}(x,y)∈U={(x,y)∣x⩾y,x,y∈N}中,(5,3)(5,3)(5,3)使得N(x,y)N(x,y)N(x,y)最大。