惠州seo,网站做优化多少钱,网站建设工程师招聘,国际财经新闻目录 设计一个计算的算法#xff0c;n是任意正整数。除了赋值和比较运算#xff0c;该算法只能用到基本的四则运算操作。 答#xff1a; 设计一个算法#xff0c;在已经排序的两个列表中#xff0c;找出所有相同的元素。例如#xff0c;列表2#xff0c;5#xff0c;…目录设计一个计算的算法n是任意正整数。除了赋值和比较运算该算法只能用到基本的四则运算操作。答设计一个算法在已经排序的两个列表中找出所有相同的元素。例如列表255,5和2,2,3,5,5,7,应该输出2,5,5。如果给定的两个列表的长度分别为m和n,你设计的算法的最大比较次数是多少?答a. 用欧几里得算法求 gcd(31415,14142)。代码手算过程b. 用欧几里得算法求 gcd(31415,14142), 速度是检查 min{m,n}和 gcd(m,n)间连续整数的算法的多少倍?请估算一下。答证明等式 gcd(m,n) gcd(n,m mod n)对每一对正整数(m,n)都成立。接下来正式证明 gcd (m,n) gcd (n, m mod n)1若 d 是 m 和 n 的公约数则 d 一定是 n 和 r 的公约数2若 d 是 n 和 r 的公约数则 d 一定是 m 和 n 的公约数对于第一个数小于第二个数的一对数字欧几里得算法将会如何处理?该算法在处理这种输入的过程中上述情况最多会发生几次?答a.对于所有m≥1n≤10的输入欧几里得算法最少要做几次除法?b.对于所有m≥1n≤10的输入欧几里得算法最多要做几次除法?在欧几里得的书里欧几里得算法用的不是整数除法而是减法。请用伪代码描述这个版本的欧几里得算法。欧几里得游戏(参见[Bog])一开始板上写有两个不相等的正整数。两个玩家交替写数字每一次当前玩家都必须在板上写出任意两个板上数字的差而且这个数字必须是新的也就是说不能与板上任何一个已有的数字相同。当玩家再也写不出新数字时他就输了。请问你是选择先行动还是后行动呢答扩展欧几里得算法 不仅能够求出两个正整数m和n的最大公约数d还能求出两个整数x和y(不一定为正)使得 mxnyd。a.在参考资料中查阅扩展欧几里得算法的描述(参见[KnuI])然后任选一种语言实现它。答b.改写上述程序以对丢番图方程 axbyc求解系数abc为任意整数。带锁的门 在走廊上有n个带锁的门从1到n依次编号。最初所有的门都是关着的。我们从门前经过n次每一次都从1号门开始。在第i次经过时(i12…n)我们改变 i的整数倍号锁的状态如果门是关的就打开它如果门是打开的就关上它。在最后一次经过后哪些门是打开的哪些门是关上的有多少打开的门答设计一个计算的算法n是任意正整数。除了赋值和比较运算该算法只能用到基本的四则运算操作。答蛮力法利用 “整数平方根的单调性”暴力遍历找到最大的i满足i2≤n伪代码// 输入正整数n // 输出floor(√n) Algorithm BruteForceSqrt(n): if n 1: // 特殊值处理 return 1 i ← 0 // 循环条件(i1)² ≤n 时继续尝试更大的i while (i 1) * (i 1) ≤ n: i ← i 1 return iC:int BruteForceSqrt(int n){ if(n0||n1) return n; int i 0; for(;(i1)*(i1)n;i){ } return i; }二分// 输入正整数n // 输出floor(√n) Algorithm BinarySearchSqrt(n): if n 0 or n 1: // 特殊值√00√11 return n left ← 0 right ← n res ← 0 // 保存最终结果 while left ≤ right: mid ← (left right) // 2 // 整数除法四则运算 mid_square ← mid * mid if mid_square n: // 恰好是完全平方数 return mid elif mid_square n: // mid可能是候选尝试更大的值 res ← mid // 记录当前符合条件的最大mid left ← mid 1 else: // mid² n尝试更小的值 right ← mid - 1 return resCint BinarySearchSqrt(int n){ if(n0||n1) return n; int left 0; int right n; int res 0; while(leftright){ int mid (leftright)/2; if(mid*mid n){ return mid; }else if(mid*midn){ res mid; left mid1; }else{ rightmid-1; } } return res; }设计一个算法在已经排序的两个列表中找出所有相同的元素。例如列表255,5和2,2,3,5,5,7,应该输出2,5,5。如果给定的两个列表的长度分别为m和n,你设计的算法的最大比较次数是多少?答利用 “列表已排序” 的特性用两个指针分别遍历两个列表通过比较指针指向的元素大小移动指针若 A [i] B [j]A [i] 更小不可能在 B 中出现i 右移若 A [i] B [j]B [j] 更小不可能在 A 中出现j 右移若 A [i] B [j]找到相同元素加入结果i 和 j 都右移处理重复。最坏的比较次数为mn即没有重复的元素。// 输入已排序的列表A长度m、已排序的列表B长度n // 输出两个列表中相同的元素组成的列表 Algorithm FindCommonElements(A, B): i ← 0 // 遍历A的指针 j ← 0 // 遍历B的指针 result ← [] // 存储相同元素 m ← length(A) n ← length(B) // 循环条件两个指针都未越界 while i m and j n: if A[i] B[j]: i ← i 1 // A[i]更小跳过 elif A[i] B[j]: j ← j 1 // B[j]更小跳过 else: // 找到相同元素加入结果 result.append(A[i]) i ← i 1 j ← j 1 return resultC:vectorint FindCommonElements(vectorintA,vectorintB){ int ai0;int bi0; int k0; int an A.size();int bn B.size(); vectorintres(max(an,bn)); for(;aianbibn;){ if(A[ai]B[bi]) { res[k]A[ai]; ai;bi; } else if(A[ai]B[bi]){ bi; }else{ ai; } } return res; }a.用欧几里得算法求 gcd(31415,14142)。代码int gcd(int n,int m){ if(n%m0) return m; else return gcd(m,n%m); }手算过程初始值m31415n14142计算31415 mod 1414214142 × 2 2828431415 - 28284 3131→gcd(31415,14142) gcd(14142, 3131)下一步m14142n3131计算14142 mod 31313131 × 4 1252414142 - 12524 1618→gcd(14142, 3131) gcd(3131, 1618)下一步m3131n1618计算3131 mod 16183131 - 1618 1513→gcd(3131, 1618) gcd(1618, 1513)下一步m1618n1513计算1618 mod 15131618 - 1513 105→gcd(1618, 1513) gcd(1513, 105)下一步m1513n105计算1513 mod 105105 × 14 14701513 - 1470 43→gcd(1513, 105) gcd(105, 43)下一步m105n43计算105 mod 4343 × 2 86105 - 86 19→gcd(105, 43) gcd(43, 19)下一步m43n19计算43 mod 1919 × 2 3843 - 38 5→gcd(43, 19) gcd(19, 5)下一步m19n5计算19 mod 55 × 3 1519 - 15 4→gcd(19, 5) gcd(5, 4)下一步m5n4计算5 mod 4 1→gcd(5, 4) gcd(4, 1)下一步m4n1计算4 mod 1 0→ 余数为 0此时非零数1即为最大公约数。b.用欧几里得算法求 gcd(31415,14142), 速度是检查 min{m,n}和 gcd(m,n)间连续整数的算法的多少倍?请估算一下。答连续整数检查算法的逻辑是取k min(m, n)此处min(31415,14142)14142从k开始向下遍历依次检查k是否能同时整除m和n第一个满足条件的k即为gcd本题中gcd1因此需要遍历14142 次从 14142 到 1每次遍历需执行 2 次除法取余判断。而a题中总共计算了10次英文版的答案这里给出的是11次因为会最后再算一遍gcd(1,0)本质上是代码实现不同所以倍数 ≈ 14142 / 11 1414.2 倍如果每次都进行两次除法一次n一次m那倍数≈ 2*14142 / 11 2828.4 倍证明等式 gcd(m,n) gcd(n,m mod n)对每一对正整数(m,n)都成立。结合律如果整数 d 同时整除 u 和 v那么 d 也一定整除 uv 和 u−v。根据整除的定义如果 d | u 且 d | v那么存在整数 s、t使得u s・d v t・d。于是u ± v s・d ± t・d (s ± t)・d这说明 d 也整除 u ± v。另外再证明如果 d 整除 u那么 d 也整除 u 的任意整数倍 k・u。因为 d | u所以存在整数 s使得 u s・d。于是k・u k・(s・d) (k・s)・d即 d 整除 k・u。接下来正式证明 gcd (m,n) gcd (n, m mod n)r m mod n根据取模的定义r 可以写成r m − q・n其中 q 是某个整数商。我们要证明(m, n) 和 (n, r) 拥有完全相同的公约数集合。1若 d 是 m 和 n 的公约数则 d 一定是 n 和 r 的公约数设 d | m 且 d | n。由前面的引理d | nd | q・nd 整除 n 的倍数d | m − q・nd 整除 m 和 qn 的差而 r m − q・n所以d | r因此 d 是 n 和 r 的公约数。2若 d 是 n 和 r 的公约数则 d 一定是 m 和 n 的公约数设 d | n 且 d | r。因为m r q・n由引理d | n ⇒ d | q·nd | r 且 d | q・n ⇒ d | r q・n即d | m因此 d 是 m 和 n 的公约数。由1和2可知m 和 n 的所有公约数 n 和 r 的所有公约数既然公约数完全一样它们的最大公约数自然也相等gcd(m, n) gcd(n, m mod n)对于第一个数小于第二个数的一对数字欧几里得算法将会如何处理?该算法在处理这种输入的过程中上述情况最多会发生几次?答我们拿前面510来举例子也就是m5,n10;第一轮r 5%105; mn10,nr5;此时便已经调换完毕后续的每一步都不会再有mn的情况因此上述情况最多发生一次a.对于所有m≥1n≤10的输入欧几里得算法最少要做几次除法?答最少的情况则是mn1时且m是n的倍数此时仅做一次除法b.对于所有m≥1n≤10的输入欧几里得算法最多要做几次除法?答我们直接蛮力搜索一遍得到当m5n8的时候最多要做5次除法在欧几里得的书里欧几里得算法用的不是整数除法而是减法。请用伪代码描述这个版本的欧几里得算法。Algorithm EuclideanAlgorithm_Subtraction_Opt(m, n): while m ≠ 0 and n ≠ 0: if m n: m m - n * (m // n) // 批量减等价于 m m mod n else: n n - m * (n // m) // 批量减等价于 n n mod m return max(m, n)欧几里得游戏(参见[Bog])一开始板上写有两个不相等的正整数。两个玩家交替写数字每一次当前玩家都必须在板上写出任意两个板上数字的差而且这个数字必须是新的也就是说不能与板上任何一个已有的数字相同。当玩家再也写不出新数字时他就输了。请问你是选择先行动还是后行动呢答dgcd(a,b),Mmax(a,b)最终能出现在板上的所有数d, 2d, 3d, …, M总个数KdM​一开始已经有2 个数所以还能写的步数 总可写数 - 2 K−2当k为偶数时最后一步会被后手走完所以后手胜反之先手必胜扩展欧几里得算法 不仅能够求出两个正整数m和n的最大公约数d还能求出两个整数x和y(不一定为正)使得 mxnyd。a.在参考资料中查阅扩展欧几里得算法的描述(参见[KnuI])然后任选一种语言实现它。答扩展欧几里得算法基于普通欧几里得算法的递归逻辑在求gcd(a, b)的同时反向推导满足ax by gcd(a, b)的整数x和y。递归关系若b 0则gcd(a, 0) a此时x1y0因为a*1 0*0 a若b ≠ 0先求gcd(b, a%b) d且有b*x (a%b)*y d由于a%b a - (a//b)*b代入得a*y b*(x - (a//b)*y) d因此x yy x - (a//b)*y。// 扩展欧几里得算法返回 (d, x, y)d gcd(a,b)且 a*x b*y d tuplelong long, long long, long long extended_gcd(long long a, long long b) { // 基线条件b0时gcd(a,0)ax1y0 if (b 0) { return {a, 1, 0}; } // 递归求解 gcd(b, a%b)得到 (d, x, y) auto [d, x_prime, y_prime] extended_gcd(b, a % b); // 反向推导当前层的 x 和 y long long x y_prime; long long y x_prime - (a / b) * y_prime; return {d, x, y}; }b.改写上述程序以对丢番图方程 axbyc求解系数abc为任意整数。不会直接跳了。带锁的门 在走廊上有n个带锁的门从1到n依次编号。最初所有的门都是关着的。我们从门前经过n次每一次都从1号门开始。在第i次经过时(i12…n)我们改变 i的整数倍号锁的状态如果门是关的就打开它如果门是打开的就关上它。在最后一次经过后哪些门是打开的哪些门是关上的有多少打开的门答当第 i 次经过时只改变 “i 的倍数” 号门的状态对于编号为 k 的门它的状态会被所有 k 的约数对应的 i 值改变比如 k4约数是 1、2、4所以会在 i1、2、4 时各改变 1 次初始状态是 “关”改变偶数次→ 回到 “关”改变奇数次→ 变成 “开”。此时我们只需要知道哪些数会改变奇数次即可而完全平方数正好满足这个条件即能被1、它的开方、它本身改变三次因此编号为完全平方数的门约数个数奇数 → 状态改变奇数次 → 最终打开所以打开的门数量 不大于 n 的最大完全平方数的平方根