https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%9D%D0%B5%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE_%D0%BE_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8._%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2%2F%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8%2Fex-fast-power 2026-04-24T12:41:46Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%9D%D0%B5%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE_%D0%BE_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8._%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/ex-fast-power&diff=25793&oldid=prev 2023-05-04T06:50:52Z

<p>Массовая правка: добавление <a href="/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8" title="Категория:Теоретические задачи">Категория:Теоретические задачи</a></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 06:50, 4 мая 2023</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l8" >Строка 8:</td> <td colspan="2" class="diff-lineno">Строка 8:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:Решенные задачи]]</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:Решенные задачи]]</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Категория:Теоретические задачи]]</ins></div></td></tr> </table>

StasFomin https://discopal.ispras.ru/index.php?title=%D0%9D%D0%B5%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE_%D0%BE_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8._%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/ex-fast-power&diff=12267&oldid=prev 2020-10-04T12:10:44Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 12:10, 4 октября 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l7" >Строка 7:</td> <td colspan="2" class="diff-lineno">Строка 7:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[<del class="diffchange diffchange-inline">Category</del>:<del class="diffchange diffchange-inline">Решения</del>]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[<ins class="diffchange diffchange-inline">Категория</ins>:<ins class="diffchange diffchange-inline">Решенные задачи</ins>]]</div></td></tr> <!-- diff cache key discopal:diff:version:1.11a:oldid:3983:newid:12267 --> </table>

StasFomin https://discopal.ispras.ru/index.php?title=%D0%9D%D0%B5%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE_%D0%BE_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8._%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/ex-fast-power&diff=3983&oldid=prev 2015-05-19T15:40:39Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 15:40, 19 мая 2015</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l7" >Строка 7:</td> <td colspan="2" class="diff-lineno">Строка 7:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Category:<del class="diffchange diffchange-inline">Нерешенные задачи</del>]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:<ins class="diffchange diffchange-inline">Решения</ins>]]</div></td></tr> <!-- diff cache key discopal:diff:version:1.11a:oldid:3664:newid:3983 --> </table>

StasFomin https://discopal.ispras.ru/index.php?title=%D0%9D%D0%B5%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE_%D0%BE_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8._%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/ex-fast-power&diff=3664&oldid=prev 2015-02-26T09:53:11Z

<p>Массовая правка: замена <a href="/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%A0%D0%B5%D1%88%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8" title="Категория:Решенные задачи">Category:Решенные задачи</a> на <a href="/%D0%9A%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D1%8F:%D0%9D%D0%B5%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%BD%D1%8B%D0%B5_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8" title="Категория:Нерешенные задачи">Category:Нерешенные задачи</a></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 09:53, 26 февраля 2015</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l7" >Строка 7:</td> <td colspan="2" class="diff-lineno">Строка 7:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Category:<del class="diffchange diffchange-inline">Решенные </del>задачи]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:<ins class="diffchange diffchange-inline">Нерешенные </ins>задачи]]</div></td></tr> <!-- diff cache key discopal:diff:version:1.11a:oldid:3446:newid:3664 --> </table>

StasFomin https://discopal.ispras.ru/index.php?title=%D0%9D%D0%B5%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE_%D0%BE_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8._%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/ex-fast-power&diff=3446&oldid=prev 2014-12-26T00:13:20Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 00:13, 26 декабря 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td> <td colspan="2" class="diff-lineno">Строка 1:</td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Преобразуем n к такому виду:</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&lt;<ins class="diffchange diffchange-inline">latex</ins>&gt;</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&lt;<del class="diffchange diffchange-inline">math</del>&gt;<del class="diffchange diffchange-inline">n=</del>2<del class="diffchange diffchange-inline">^{k-t}*</del>(<del class="diffchange diffchange-inline">2^t</del>+<del class="diffchange diffchange-inline">2^{t-</del>1<del class="diffchange diffchange-inline">}+</del>.<del class="diffchange diffchange-inline">..+2+1)</del>=2^{<del class="diffchange diffchange-inline">k-t</del>}<del class="diffchange diffchange-inline">*((</del>1<del class="diffchange diffchange-inline">-1*2^</del>{<del class="diffchange diffchange-inline">t+1</del>}<del class="diffchange diffchange-inline">)/(1-2))</del>=2^{k<del class="diffchange diffchange-inline">+</del>1}<del class="diffchange diffchange-inline">-</del>2^{k-<del class="diffchange diffchange-inline">t</del>}<del class="diffchange diffchange-inline">&lt;/math&gt;</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Более внимательно взглянув на алгоритм быстрого возведения в~степень, видно, что достаточно $</ins>2(<ins class="diffchange diffchange-inline">\log_2 n </ins>+1<ins class="diffchange diffchange-inline">)$ умножений</ins>.</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Получается аналог поставленной задачи &lt;math&gt;2^n&lt;/math&gt;. Единственным отличием будет то, что необходимо будет запоминать значение для &lt;math&gt;</del>2^{k-t}<del class="diffchange diffchange-inline">&lt;/math&gt;. Таким образом мы получили указанную оуенку.</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">На самом деле, как видно из изложенного, для чисел вида $n</ins>=2^<ins class="diffchange diffchange-inline">k$&#160; достаточно $k=\log </ins>{<ins class="diffchange diffchange-inline">_2</ins>} <ins class="diffchange diffchange-inline">n+</ins>1<ins class="diffchange diffchange-inline">$ умножений. </ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Можно ли получить такую же асимптотическую оценку $\sim \log </ins>{<ins class="diffchange diffchange-inline">_2</ins>} <ins class="diffchange diffchange-inline">n$ для чисел вида $n</ins>=<ins class="diffchange diffchange-inline">2^k+</ins>2^{k<ins class="diffchange diffchange-inline">-</ins>1}<ins class="diffchange diffchange-inline">+</ins>2^{k-<ins class="diffchange diffchange-inline">2</ins>}<ins class="diffchange diffchange-inline">+\ldots+</ins>2^{k-t}<ins class="diffchange diffchange-inline">$?</ins></div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[<del class="diffchange diffchange-inline">Категория</del>:<del class="diffchange diffchange-inline">На проверку</del>]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Для произвольных чисел?</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">&lt;/latex&gt;</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#160;</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[<ins class="diffchange diffchange-inline">Category</ins>:<ins class="diffchange diffchange-inline">Решенные задачи</ins>]]</div></td></tr> <!-- diff cache key discopal:diff:version:1.11a:oldid:3127:newid:3446 --> </table>

StasFomin https://discopal.ispras.ru/index.php?title=%D0%9D%D0%B5%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE_%D0%BE_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8._%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/ex-fast-power&diff=3127&oldid=prev 2014-10-07T08:11:55Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 08:11, 7 октября 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td> <td colspan="2" class="diff-lineno">Строка 1:</td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&lt;<del class="diffchange diffchange-inline">latex</del>&gt;</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Преобразуем n к такому виду:</ins></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Более внимательно взглянув на алгоритм быстрого возведения в~степень, видно, что достаточно $</del>2(<del class="diffchange diffchange-inline">\log_2 n </del>+1<del class="diffchange diffchange-inline">)$ умножений</del>.</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&lt;<ins class="diffchange diffchange-inline">math</ins>&gt;<ins class="diffchange diffchange-inline">n=</ins>2<ins class="diffchange diffchange-inline">^{k-t}*</ins>(<ins class="diffchange diffchange-inline">2^t</ins>+<ins class="diffchange diffchange-inline">2^{t-</ins>1<ins class="diffchange diffchange-inline">}+</ins>.<ins class="diffchange diffchange-inline">..+2+1)</ins>=2^{<ins class="diffchange diffchange-inline">k-t</ins>}<ins class="diffchange diffchange-inline">*((</ins>1<ins class="diffchange diffchange-inline">-1*2^</ins>{<ins class="diffchange diffchange-inline">t+1</ins>}<ins class="diffchange diffchange-inline">)/(1-2))</ins>=2^{k<ins class="diffchange diffchange-inline">+</ins>1}<ins class="diffchange diffchange-inline">-</ins>2^{k-<ins class="diffchange diffchange-inline">t</ins>}<ins class="diffchange diffchange-inline">&lt;/math&gt;</ins></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">На самом деле, как видно из изложенного, для чисел вида $n</del>=2^<del class="diffchange diffchange-inline">k$&#160; достаточно $k=\log </del>{<del class="diffchange diffchange-inline">_2</del>} <del class="diffchange diffchange-inline">n+</del>1<del class="diffchange diffchange-inline">$ умножений. </del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">Получается аналог поставленной задачи &lt;math&gt;2^n&lt;/math&gt;. Единственным отличием будет то, что необходимо будет запоминать значение для &lt;math&gt;</ins>2^{k-t}<ins class="diffchange diffchange-inline">&lt;/math&gt;. Таким образом мы получили указанную оуенку.</ins></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Можно ли получить такую же асимптотическую оценку $\sim \log </del>{<del class="diffchange diffchange-inline">_2</del>} <del class="diffchange diffchange-inline">n$ для чисел вида $n</del>=<del class="diffchange diffchange-inline">2^k+</del>2^{k<del class="diffchange diffchange-inline">-</del>1}<del class="diffchange diffchange-inline">+</del>2^{k-<del class="diffchange diffchange-inline">2</del>}<del class="diffchange diffchange-inline">+\ldots+</del>2^{k-t}<del class="diffchange diffchange-inline">$?</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">Для произвольных чисел?</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[<ins class="diffchange diffchange-inline">Категория</ins>:<ins class="diffchange diffchange-inline">На проверку</ins>]]</div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">&lt;/latex&gt;</del></div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>&#160;</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[<del class="diffchange diffchange-inline">Category</del>:<del class="diffchange diffchange-inline">Нерешенные задачи</del>]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div></div></td></tr> <!-- diff cache key discopal:diff:version:1.11a:oldid:2919:newid:3127 --> </table>

Abondar https://discopal.ispras.ru/index.php?title=%D0%9D%D0%B5%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE_%D0%BE_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8._%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/ex-fast-power&diff=2919&oldid=prev 2014-04-24T07:49:41Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 07:49, 24 апреля 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l7" >Строка 7:</td> <td colspan="2" class="diff-lineno">Строка 7:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Category:<del class="diffchange diffchange-inline">Решенные </del>задачи]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:<ins class="diffchange diffchange-inline">Нерешенные </ins>задачи]]</div></td></tr> <!-- diff cache key discopal:diff:version:1.11a:oldid:2596:newid:2919 --> </table>

StasFomin https://discopal.ispras.ru/index.php?title=%D0%9D%D0%B5%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE_%D0%BE_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8._%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/ex-fast-power&diff=2596&oldid=prev 2013-12-19T13:08:22Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 13:08, 19 декабря 2013</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l7" >Строка 7:</td> <td colspan="2" class="diff-lineno">Строка 7:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Category:<del class="diffchange diffchange-inline">Нерешенные </del>задачи]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:<ins class="diffchange diffchange-inline">Решенные </ins>задачи]]</div></td></tr> <!-- diff cache key discopal:diff:version:1.11a:oldid:1627:newid:2596 --> </table>

StasFomin https://discopal.ispras.ru/index.php?title=%D0%9D%D0%B5%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE_%D0%BE_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8._%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/ex-fast-power&diff=1627&oldid=prev 2013-04-18T07:42:11Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 07:42, 18 апреля 2013</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l7" >Строка 7:</td> <td colspan="2" class="diff-lineno">Строка 7:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Category:<del class="diffchange diffchange-inline">Решенные </del>задачи]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Category:<ins class="diffchange diffchange-inline">Нерешенные </ins>задачи]]</div></td></tr> <!-- diff cache key discopal:diff:version:1.11a:oldid:1161:newid:1627 --> </table>

StasFomin https://discopal.ispras.ru/index.php?title=%D0%9D%D0%B5%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE_%D0%BE_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8._%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B8/ex-fast-power&diff=1161&oldid=prev 2012-12-20T17:37:06Z

<p></p> <p><b>Новая страница</b></p><div>&lt;latex&gt;<br /> Более внимательно взглянув на алгоритм быстрого возведения в~степень, видно, что достаточно $2(\log_2 n +1)$ умножений.<br /> На самом деле, как видно из изложенного, для чисел вида $n=2^k$ достаточно $k=\log {_2} n+1$ умножений. <br /> Можно ли получить такую же асимптотическую оценку $\sim \log {_2} n$ для чисел вида $n=2^k+2^{k-1}+2^{k-2}+\ldots+2^{k-t}$?<br /> <br /> Для произвольных чисел?<br /> &lt;/latex&gt;<br /> <br /> [[Category:Решенные задачи]]</div>

StasFomin