上传文件到网站根目录,深圳建站公司优化,整合营销传播的方法包括,绍兴网站制作方案定制令 $mn1$ 为正整数. 一个集合含有 $m$ 个给定的实数. 我们从中选取任意 $n$ 个数, 记作 $a_1$, $a_2$, $\dotsc$, $a_n$, 并提问: 是否 $a_1a_2\dotsb a_n$ 正确? 证明: 我们可以最多问 $n!-n^22n-2m(n-1)(1\lfloor \log_{n} m \rfloor)-m$ 个问题#…令 $mn1$ 为正整数. 一个集合含有 $m$ 个给定的实数. 我们从中选取任意 $n$ 个数, 记作 $a_1$, $a_2$, $\dotsc$, $a_n$, 并提问: 是否 $a_1a_2\dotsb a_n$ 正确? 证明: 我们可以最多问 $n!-n^22n-2m(n-1)(1\lfloor \log_{n} m \rfloor)-m$ 个问题将所有的 $m$ 个数排序. We can find the order of the first $n$ numbers $n!-1$ questions,looking at all possible orderings but one. 我们可通过查看除$1$以外的所有可能的顺序,找出前$n$个数$n!-1$个问题的顺序. Suppose we have found the relative order of the first $k$ numbersand let us find the relative order of first $k1$ numbers. 假设我们已找到前$k$个数的相对顺序,让我们来找出前$k1$个数的相对顺序. Suppose we have $a_1a_2\dotsba_k$and let us find where $a_{k1}$ fits. 假设有$a_1a_2\dotsba_k$,让我们找出$a_{k1}$应该放在哪里. We use the following {\it binary search}:pick $n-1$ numbers among $1,2,\dotsc,k$ that divide the interval $[1,k]$most equally. 利用下面的\textbf{二分法搜索(binary search)}:在$1,2,\dotsc,k$之间选取$n-1$个数等分区间$[1,k]$. (This is achieved by taking the numbers$a_{\left\lfloor \frac{k}{n}\right\rfloor},a_{\left\lfloor \frac{2k}{n}\right\rfloor},\ldots ,a_{\left\lfloor \frac{(n-1)k}{n}\right\rfloor}$). (这可通过取数字$a_{\left\lfloor \frac{k}{n}\right\rfloor},a_{\left\lfloor \frac{2k}{n}\right\rfloor},\ldots ,a_{\left\lfloor \frac{(n-1)k}{n}\right\rfloor}$来实现). We can find the relative order of $a_{k1}$ and these numbers by at most $n-1$ questions. 我们最多可通过$n-1$次提问找出$a_{k1}$和这些数的相对顺序. Indeed, for $1\leqslant j\leqslant n-1$, let $q_i$ be Is it true that$a_{\left\lfloor \frac{k}{n}\right\rfloor}\ldots aa_{\left\lfloor \frac{ik}{n}\right\rfloor}a_{k1}a_{\left\lfloor \frac{(i1)k}{n}\right\rfloor}\ldots a_{\left\lfloor \frac{(n-1)k}{n}\right\rfloor}$? 实际上, 对于$1\leqslant j\leqslant n-1$, 令$q_i$为$a_{\left\lfloor \frac{k}{n}\right\rfloor}\ldots aa_{\left\lfloor \frac{ik}{n}\right\rfloor}a_{k1}a_{\left\lfloor \frac{(i1)k}{n}\right\rfloor}\ldots a_{\left\lfloor \frac{(n-1)k}{n}\right\rfloor}$成立么? Then we find an $i$ such that$a_{\left\lfloor \frac{ik}{n}\right\rfloor}a_{k1}a_{\left\lfloor \frac{(i1)k}{n}\right\rfloor}$. 那么我们找到 $i$使得$a_{\left\lfloor \frac{ik}{n}\right\rfloor}a_{k1}a_{\left\lfloor \frac{(i1)k}{n}\right\rfloor}$. Therefore, by at most $n-1$ questions we reduce the length of the interval of searchingfrom $k$ to at most $\left\lceil \frac{k}{n}\right\rceil$, where $\lceil x\rceil$is the least integer number not less than $x$. 因此,我们最多可通过$n-1$个问题,使搜索的区间长度从$k$减小到最多是$\left\lceil \frac{k}{n}\right\rceil$,其中$\lceil x\rceil$为不小于$x$的最小整数. We repeat this binary search until we find exactly the position of $a_{k1}$(that is, the interval of searching is 1 or 0). 我们重复这个二分法搜索,直到找出$a_{k1}$的确切位置.(即搜索间隔为$1$或$0$). Now if $k\leqslant n^j$, then after $i$ steps the interval will be at most $n^{j-i}$,so we need at most $j\lceil \log _n k\rceil$ steps to insert $a_{k1}$ into the sequence. 现在如果$k\leqslant n^j$,那么在$i$步之后,间隔最多为$n^{j-i}$,因此我们最多需要$j\lceil \log _n k\rceil$步来将$a_{k1}$插入数列中. Therefore, the number of questions needed is at most$n!-1(n-1)(\lceil \log_n(n1)\rceil\ldots \lceil \log_n(m-1)\rceil)$. 因此,所需的提问次数最多为$n!-1(n-1)(\lceil \log_n(n1)\rceil\ldots \lceil \log_n(m-1)\rceil)$. All we need to do is to evaluate this number:suppose that$n^k\leqslant mn^{k1}$.Then there are $n^2-n$ numbers $r$ for which$\lceil \log_n r\rceil2$, $n^3-n^2$ numbers for which$\lceil \log_n r\rceil3$, and so on until we have $m-1-n^k$ numbers $r$ for which$\lceil \log_n r\rceilk1$. 我们需要做的就是计算这个数字:设$n^k\leqslant mn^{k1}$.那么有$n^2-n$个数$r$满足$\lceil \log_n r\rceil2$, 有$n^3-n^2$个数满足$\lceil \log_n r\rceil3$等等,直到我们有$m-1-n^k$个数$r$满足$\lceil \log_n r\rceilk1$. Therefore the sum is\begin{align*} n!-1(n-1)(2(n^2-n)3(n^3-n^2)\dotsb k(n^k-n^{k-1})(k1)(m-1-n^k)) \\ n!-1(n-1)((k1)(m-1)-n^k-n^{k-1}-\dotsb -n^2-2n).\end{align*}Because $n^{k1}m$,\[ n^kn^{k-1}\dotsb n^22n\frac{n^{k1}-1}{n-1}n-1\geqslant \frac{m}{n-1}n-1. \]Hence our sum is at most\begin{align*} n!-1(n-1)\left((k1)(m-1)-\frac{m}{n-1}-n1\right) \\ n!-n^22n-2(n-1)(\lfloor \log_n m\rfloor1)m-m,\end{align*}as desired. 因此和为\begin{align*} n!-1(n-1)(2(n^2-n)3(n^3-n^2)\dotsb k(n^k-n^{k-1})(k1)(m-1-n^k)) \\ n!-1(n-1)((k1)(m-1)-n^k-n^{k-1}-\dotsb -n^2-2n).\end{align*}由于$n^{k1}m$,\[ n^kn^{k-1}\dotsb n^22n\frac{n^{k1}-1}{n-1}n-1\geqslant \frac{m}{n-1}n-1. \]因此我们的和最多为\begin{align*} n!-1(n-1)\left((k1)(m-1)-\frac{m}{n-1}-n1\right) \\ n!-n^22n-2(n-1)(\lfloor \log_n m\rfloor1)m-m,\end{align*}得证.转载于:https://www.cnblogs.com/Eufisky/p/11247759.html
