关于辗转相除法的一道数学题(Upgraded)
  • 板块灌水区
  • 楼主jason20250630
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/3/31 16:52
  • 上次更新2024/3/31 19:40:56
查看原帖
关于辗转相除法的一道数学题(Upgraded)
591412
jason20250630楼主2024/3/31 16:52

证明或否定:

定义计算次数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\}中(8,5)(8,5)使得N(a,b)N(a,b)最大

P.S.经验证对于(x,y)∈U={(x,y)∣1⩽x⩽2×104,1⩽y⩽2×104,x⩾y,x,y∈Z}(x,y)\in U=\left\{(x,y)|1\leqslant x\leqslant 2\times10^{4},1\leqslant y\leqslant 2\times10^{4},x\geqslant y,x,y\in Z\right\}

N(8,5)=2.50N(8,5)=2.50是最大的(存在相同的值)

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