社区讨论

辗转相除法_一道数学题

2024/03/31 16:35灌水区参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

证明或否定:

定义计算次数

C(gcd(a,b))

为以下递归函数的调用次数:（例如

C(gcd(10,4))=3,C(gcd(25,7))=5

,要求

a\geqslant b

)

CPP

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

再定义正整数

n

的位数

W(n)=\lfloor log_{10}{n} \rfloor+1

最后定义一次辗转相除法运算的优越度

N(a,b)=\frac{C(gcd(a,b))}{W(a)+W(b)}

那么在数组

(x,y)\in U=\left\{(x,y)|x\geqslant y,x,y\in N\right\}

中，

(5,3)

使得

N(x,y)

最大。

共 0 条回复，欢迎继续交流。

正在加载回复...