辗转相除法_一道数学题
  • 板块灌水区
  • 楼主jason20250630
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/31 16:35
  • 上次更新2024/3/31 16:44:14
查看原帖
辗转相除法_一道数学题
591412
jason20250630楼主2024/3/31 16:35

证明或否定:

定义计算次数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))=5,要求a⩾ba\geqslant b)

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

再定义正整数nn的位数W(n)=⌊log10n⌋+1W(n)=\lfloor log_{10}{n} \rfloor+1

最后定义一次辗转相除法运算的优越度N(a,b)=C(gcd(a,b))W(a)+W(b)N(a,b)=\frac{C(gcd(a,b))}{W(a)+W(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\}中,(5,3)(5,3)使得N(x,y)N(x,y)最大。

2024/3/31 16:35
加载中...