算法篇————入门级算法 - th是个小屁�?/title> <link rel="shortcut icon" href="/blog/favicon.ico">  <link rel="stylesheet" href="//cdn.bootcss.com/font-awesome/4.5.0/css/font-awesome.min.css"> <link rel="stylesheet" href="/blog/css/thplayer.css">  <link rel="stylesheet" href="/blog/css/style.css"> <script src="js/jquery.js"></script> </head> <body>  <header class="site-header"> <div class="header-inside"> <div class="logo"> <a href="http://www.tianhao.site" rel="home"> <img src="img/timg.jpg" alt="th是个小屁�? height="60"> </a> </div> <a class="header-name" href="/blog/"> <span>th是个小屁�?/span> 的部落宅 </a>  <nav class="navbar">  <div class="collapse"> <ul class="navbar-nav"> <li> <a href="/blog/."> <i class="fa fa-home "></i> 首页 </a> </li> <li> <a href="/blog/archives"> <i class="fa fa-archive "></i> 归档 </a> </li> <li> <a href="/blog/about"> <i class="fa fa-user "></i> 关于 </a> </li> <li> <a href="/blog/project"> <i class="fa fa-folder-open "></i> 项目 </a> </li> <li> <a href="/blog/photo"> <i class="fa fa-photo "></i> 相册 </a> </li> <li> <a href="/blog/guestbook"> <i class="fa fa-edit "></i> 留言 </a> </li> <li> <a href="/blog/one"> <i class="fa fa-bicycle "></i> one </a> </li> <li> <a href="/blog/atom.xml"> <i class="fa fa-send "></i> RSS </a> </li> </ul> </div>  </nav> <div class="button-wrap"> <button class="menu-toggle">Primary Menu</button> </div> </div> </header>  <div class="content-area"> <div class="post">  <div class="container"> <article>  <div class="post-header"> <h1 class="entry-title"> 算法篇————入门级算法 </h1> </div> 　　　　　　　　<p class="a-posted-on">2016-09-14</p>  <div class="entry-content"> <p> 从今天开始，复习各种算法，每天都会去理解一种算法，争取贴出自己对每种算法的理解，今天介绍的是最基础的入门算法，最大公约数，最小公倍数，快速幂（后面会重点介绍），简单并查集（后面会重点介绍），还有排列组合（后面会重点介绍）的算法�?br> <a id="more"></a></p> <h2 id="最大公约数和最小公倍数的算法原�?><a href="#最大公约数和最小公倍数的算法原�? class="headerlink" title="最大公约数和最小公倍数的算法原�?></a>最大公约数和最小公倍数的算法原�?/h2><ol> <li><p>最大公约数gcd的实现原理：</p> <p> 欧几里德定理<br>�?a=b×r+q 则gcd(a, b) = gcd(b, q).</p> <p>欧几里德定理的证�?br>a = b × r + q<br>设c = gcd(a, b), a = m×c, b= n×c<br>q = a - b× r = (m - n × r)×c<br>下面证明 m-n×r与n互质�?br>假设不互质，则存在k使得 m-n×r = x×k, n = y×k.<br>�?<br>a = m×c = (n×r + x×k)×c = (y×r + x×k)×c×k<br>b = n×c = y×c×k<br>�?c=gcd(a, b) 矛盾�?br>辗转相除法的算法实现<br>a = b × r_1 + q_1<br>if q_1 = 0<br> then return b<br>else<br>b = q_1 × r_2 + q_2<br>if q_2 = 0<br> then return q_1<br>else<br>…�?br>直到找到GCD为止�?/p> </li> <li><p>最小公倍数的实现原�?/p> <p>lcm=a*b/gcd (公式)</p> </li> </ol> <h2 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h2><figure class="highlight plain"><table><tr><td class="gutter"><pre><div class="line">1</div><div class="line">2</div><div class="line">3</div><div class="line">4</div><div class="line">5</div><div class="line">6</div><div class="line">7</div><div class="line">8</div><div class="line">9</div><div class="line">10</div><div class="line">11</div><div class="line">12</div><div class="line">13</div><div class="line">14</div><div class="line">15</div><div class="line">16</div><div class="line">17</div><div class="line">18</div><div class="line">19</div><div class="line">20</div><div class="line">21</div><div class="line">22</div><div class="line">23</div><div class="line">24</div><div class="line">25</div><div class="line">26</div><div class="line">27</div><div class="line">28</div><div class="line">29</div><div class="line">30</div><div class="line">31</div><div class="line">32</div><div class="line">33</div><div class="line">34</div><div class="line">35</div><div class="line">36</div><div class="line">37</div><div class="line">38</div><div class="line">39</div><div class="line">40</div><div class="line">41</div><div class="line">42</div><div class="line">43</div><div class="line">44</div><div class="line">45</div><div class="line">46</div><div class="line">47</div><div class="line">48</div><div class="line">49</div><div class="line">50</div><div class="line">51</div><div class="line">52</div><div class="line">53</div><div class="line">54</div><div class="line">55</div><div class="line">56</div><div class="line">57</div><div class="line">58</div><div class="line">59</div><div class="line">60</div><div class="line">61</div><div class="line">62</div><div class="line">63</div><div class="line">64</div></pre></td><td class="code"><pre><div class="line">#include <iostream></div><div class="line">#include <cstdio></div><div class="line">#include <cstring></div><div class="line">#include <cmath></div><div class="line">using namespace std;</div><div class="line">#define N 1009</div><div class="line">#define inf 0x0f0f0f0f</div><div class="line">//最大公约数</div><div class="line">int gcd(int a,int b){</div><div class="line"> if(b==0) return a;</div><div class="line"> else return gcd(b,a%b);</div><div class="line">}</div><div class="line">//最小公倍数</div><div class="line">int lcm(int a,int b){</div><div class="line"> return a/gcd(a,b)*b;</div><div class="line">}</div><div class="line">//快速幂</div><div class="line">int Fast(int x,int n){</div><div class="line"> int tem = x,ans = 1;</div><div class="line"> while(n){</div><div class="line"> if(n%2==1) ans*=tem;</div><div class="line"> tem *= tem;</div><div class="line"> n >>= 1;</div><div class="line"> }</div><div class="line"> return ans;</div><div class="line">}</div><div class="line">//简单并查集</div><div class="line">int f[N];</div><div class="line">int ans;</div><div class="line">void init(int n){</div><div class="line"> for(int i = 1;i<=n;i++)</div><div class="line"> f[i] = i;</div><div class="line"> ans = 0;</div><div class="line">}</div><div class="line">int find(int x){</div><div class="line"> if(f[x]==x) return x;</div><div class="line"> else return f[x] = find(f[x]);</div><div class="line">}</div><div class="line">void Union(int a,int b){</div><div class="line"> int f1 = find(a);</div><div class="line"> int f2 = find(b);</div><div class="line"> if(f1!=f2){</div><div class="line"> f[f1] = f2;</div><div class="line"> ans++;</div><div class="line"> }</div><div class="line">}</div><div class="line">//计算排列组合</div><div class="line">int c[N][N];</div><div class="line">void Com(){</div><div class="line"> memset(c,0,sizeof(c));</div><div class="line"> for(int i = 1;i<N;i++){</div><div class="line"> c[i][0] = c[i][i] = 1;</div><div class="line"> for(int j = 1;j<i;j++){</div><div class="line"> c[i][j] = c[i-1][j] + c[i-1][j-1];</div><div class="line"> }</div><div class="line"> }</div><div class="line">}</div><div class="line">void Test1(){</div><div class="line"> Com();</div><div class="line"> printf("gcd==%d\n",gcd(12,3));</div><div class="line"> printf("lcm==%d\n",lcm(4,3));</div><div class="line"> printf("fast===%d\n",Fast(2,3));</div><div class="line"> printf("Com===%d\n",c[12][3]);</div><div class="line">}</div></pre></td></tr></table></figure> </div> </article> </div>  <div class="container" > <ul class="pager"> <li class="previous"> <a href="/blog/2016/09/13/2016-9-13随记/" rel="prev">下一�?/a> </li> <li class="next"> <a href="/blog/2016/09/15/算法篇————快速幂/" rel="prev">上一�?/a> </li> </ul> </div> 　　　　 <div id="cloud-tie-wrapper" class="cloud-tie-wrapper"></div> <script src="https://img1.cache.netease.com/f2e/tie/yun/sdk/loader.js"></script> <script> var cloudTieConfig = { url: document.location.href, sourceId: "", productKey: "df8ef703a5a1404fb862cb96bfb8272c", target: "cloud-tie-wrapper" }; var yunManualLoad = true; Tie.loader("aHR0cHM6Ly9hcGkuZ2VudGllLjE2My5jb20vcGMvbGl2ZXNjcmlwdC5odG1s", true); </script> 　　　　 </div> </div> 　　 <div id="rocket-to-top"> <div class="level-2"></div> <div class="level-3"></div> </div> <script src="js/top.js"></script> <script type="text/javascript" src="js/jquery.js"></script>   <footer class="site-info"> <p> <span>th是个小屁�?© 2017</span> <span class="split">|</span> <span>th是个小屁孩的技术小�?/span> </p> <script async src="//dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script> 本站总访问量<span id="busuanzi_value_site_pv"></span>�? 本站访客�?span id="busuanzi_value_site_uv"></span>人次 </footer>   <script src="/blog/js/app.js"></script>  <script type="text/javascript"> var duoshuoQuery = {short_name:'th720309'}; (function() { var ds = document.createElement('script'); ds.type = 'text/javascript';ds.async = true; ds.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//static.duoshuo.com/embed.js'; ds.charset = 'UTF-8'; (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(ds); })(); </script>  </body> </html>