Linux迷+Python粉https://blog.pythonwood.com/2018-04-27T19:00:00+08:00XUbuntu18.04(Bionic河狸)正式发布,系统安装升级记录2018-04-27T19:00:00+08:002018-04-27T19:00:00+08:00pythonwoodtag:blog.pythonwood.com,2018-04-27:/2018/04/XUbuntu18.04(Bionic河狸)正式发布,系统安装升级记录/<p>Ubuntu&nbsp;18.04发布时间是(美国)4月26号,彼时的中国已经是27号,就是今天。我花了一天时间折腾升级旧Ubuntu系统到刚发布的最新版。</p> <p>多年使用linux经验已经使得这个过程驾轻就熟,闲庭信步:)。为了不忘记,将有沉淀价值的部分,简要记录一下。</p> <h2 id="linuxubuntu">偶然得知Linux,成为Ubuntu多年用户<a class="headerlink" href="#linuxubuntu" title="Permanent link">&para;</a></h2> <h3 id="ubuntults">建议:只使用Ubuntu的<span class="caps">LTS</span>版本(长期维护 …</h3><p>Ubuntu&nbsp;18.04发布时间是(美国)4月26号,彼时的中国已经是27号,就是今天。我花了一天时间折腾升级旧Ubuntu系统到刚发布的最新版。</p> <p>多年使用linux经验已经使得这个过程驾轻就熟,闲庭信步:)。为了不忘记,将有沉淀价值的部分,简要记录一下。</p> <h2 id="linuxubuntu">偶然得知Linux,成为Ubuntu多年用户<a class="headerlink" href="#linuxubuntu" title="Permanent link">&para;</a></h2> <h3 id="ubuntults">建议:只使用Ubuntu的<span class="caps">LTS</span>版本(长期维护)<a class="headerlink" href="#ubuntults" title="Permanent link">&para;</a></h3> <p>我的Ubuntu升级之路是10.04 -&gt; 14.04 -&gt; 18.0,中间的<span class="caps">LTS</span>版本12.04和16.04因在升级后不满意而没用,回滚恢复降版本。如果升级前没有备份,就没法恢复。系统升级前备份旧系统的准备很重要,让你可以安心折腾走得更远。这次也是花了很长时间全备份的。如果失败需要恢复系统可参考<a href="https://blog.pythonwood.com/2017/11/树莓派SD卡Linux系统盘复制,10分钟克隆新机/" title="树莓派SD卡Linux系统盘复制,10分钟克隆新机">关于linux系统备份与恢复的随笔</a></p> <h3 id="xubuntu1804bionic">期待已久的XUbuntu18.04(Bionic河狸)正式发布<a class="headerlink" href="#xubuntu1804bionic" title="Permanent link">&para;</a></h3> <p>新系统意味着更好的驱动,更好的软件版本,比如ubuntu14.04驱动<span class="caps">RTL8723BE</span>这种网卡会偶尔掉线。不幸,我的一台笔记本就是<span class="caps">RTL8723BE</span>网卡的。显然大版本升级 14.04 -&gt; 18.04 能巧妙地不折腾而解决很多旧问题(再比如http2支持)。因此,我是带着期待在等待Ubuntu18.04发布的,同时这次升级也没有退路(14.04太老了)。幸好,升级还算满意。已经用上了最新Ubuntu了,并且速度还可以,在换<span class="caps">SSD</span>盘后的酷睿I3老机上运行顺畅。</p> <h4 id="ubuntu-1804-xubutnu">Ubuntu 18.04 桌面截图(XUbutnu)<a class="headerlink" href="#ubuntu-1804-xubutnu" title="Permanent link">&para;</a></h4> <p><img alt="XUbutnu18.04桌面截图" src="https://blog.pythonwood.com/uploads/2018/2018-04-27XUbutnu18.04桌面截图.jpg" title="XUbutnu18.04桌面截图"></p> <h2 id="ubutnu1804-xfce">Ubutnu18.04安装升级过程 (Xfce版本)<a class="headerlink" href="#ubutnu1804-xfce" title="Permanent link">&para;</a></h2> <h3 id="10-ubutnuxubuntu">1.0 选择并下载Ubutnu版本(XUbuntu)<a class="headerlink" href="#10-ubutnuxubuntu" title="Permanent link">&para;</a></h3> <p>旧系统是配搭Xfce桌面的<a href="https://blog.pythonwood.com/2014/07/笔记本系统转换Linux一个半月——xubuntu14.04截图纪念里程碑/" title="xubuntu14.04截图纪念">XUbuntu14.04</a>,Xfce同时也是Linus本人选择<a href="https://linux.cn/article-202-1.html" title="Linus Torvalds 弃 GNOME 3 用 Xfce">Linus Torvalds 弃 <span class="caps">GNOME</span> 3 用 Xfce</a>。XUbuntu里面的好软件有很多,比如文件管理器Thunar,截图软件xfce4-screenshooter,网速提示器xfce4-netload-plugin,<span class="caps">CPU</span>内存提示器xfce4-systemload-plugin等等。同时Ubuntu18的Xfce比原版<span class="caps">ISO</span>文件轻量很多。 <img alt="Ubuntu18的Xfce比原版ISO文件轻量很多" src="https://blog.pythonwood.com/uploads/2018/2018-04-27Ubuntu18的Xfce比原版ISO文件轻量很多.jpg"></p> <h3 id="20">2.0 升级前先备份<a class="headerlink" href="#20" title="Permanent link">&para;</a></h3> <h4 id="21-deb">2.1 备份已安装过的deb包名称列表<a class="headerlink" href="#21-deb" title="Permanent link">&para;</a></h4> <div class="highlight"><pre><span></span><span class="o">(</span> <span class="nt">zcat</span> <span class="o">/</span><span class="nt">var</span><span class="o">/</span><span class="nt">log</span><span class="o">/</span><span class="nt">apt</span><span class="o">/</span><span class="nt">history</span><span class="p">.</span><span class="nc">log</span><span class="o">*</span><span class="p">.</span><span class="nc">gz</span> <span class="o">|</span> <span class="nt">grep</span> <span class="nt">Commandline</span><span class="o">:</span> <span class="o">;</span> <span class="nt">zcat</span> <span class="o">/</span><span class="nt">var</span><span class="o">/</span><span class="nt">log</span><span class="o">/</span><span class="nt">apt</span><span class="o">/</span><span class="nt">history</span><span class="p">.</span><span class="nc">log</span><span class="o">*</span><span class="p">.</span><span class="nc">gz</span> <span class="o">|</span> <span class="nt">grep</span> <span class="nt">Commandline</span><span class="o">:</span> <span class="o">)</span> <span class="o">&gt;</span> <span class="o">~/</span><span class="nt">deb</span><span class="p">.</span><span class="nc">list</span><span class="p">.</span><span class="nc">txt</span> </pre></div> <h4 id="22-pythonrubyperl">2.2 备份已安装过的python包名称列表(无则忽略,ruby,perl等备份操作同理)<a class="headerlink" href="#22-pythonrubyperl" title="Permanent link">&para;</a></h4> <div class="highlight"><pre><span></span>( pip2 list ; pip3 list ) &gt; ~/pip.list.txt </pre></div> <h4 id="23-etcvar-rootetcvar">2.3 /etc,/var一些关键目录备份, root权限执行(/etc是配置文件仓库,/var包含各用户的定时任务)<a class="headerlink" href="#23-etcvar-rootetcvar" title="Permanent link">&para;</a></h4> <div class="highlight"><pre><span></span>cd /; sudo tar czf ~/etc.tar.gz etc var/spool/cron/crontabs </pre></div> <h4 id="24">2.4 繁重但强烈建议的全盘备份<a class="headerlink" href="#24" title="Permanent link">&para;</a></h4> <p>备份方法多种:rsync同步到安全盘备份 或 tar打包放到安全目录下 或&nbsp;dd复制分区为文件保存到安全目录下。</p> <h3 id="30">3.0 分区、格式化、安装<a class="headerlink" href="#30" title="Permanent link">&para;</a></h3> <h4 id="31-ubuntu1804">3.1 方式一:从新硬盘或空白分区安装ubuntu18.04<a class="headerlink" href="#31-ubuntu1804" title="Permanent link">&para;</a></h4> <p>linux分区不是越多越好的,推荐 / + /home 模式, 实用而不折腾,&nbsp;一个分区代表系统,一个分区代表用户数据空间。这样的好处就是为后续升级带来方便。</p> <p>根 / 分区给15G已经完全足够,绰绰有余了。&nbsp;把剩余空间都给/home,因为/分区使用量不会明显增加,/home分区放的东西却会成倍的增加。</p> <p>多年之后我目前用的分区方式,window与linux双系统共存的分区方式。msdos方式只能4主分区,刚好用完: <img alt="Ubuntu安装推荐分区" src="https://blog.pythonwood.com/uploads/2018/2018-04-27Ubuntu安装推荐分区.jpg" title="Ubuntu安装推荐分区"></p> <h4 id="32-linux">3.2 方式二:从旧linux系统升级<a class="headerlink" href="#32-linux" title="Permanent link">&para;</a></h4> <p>告诫:不要尝试从命令<code>sudo apt-get dist-upgrade</code>升级,结局一般都是不能自动处理错误而中止升级,系统可能因此寿终正寝,只留下无辜的你。这和不要尝试用系统升级方法装windows是一样的。</p> <p>参考升级方法:</p> <ol> <li>之前已有linux分区是 / + /home 模式,先把 &ldquo;/&rdquo; 所在分区格式化,然后将整个ubuntu18.04安装 &ldquo;/&rdquo;&nbsp;所在区。</li> <li>系统安装后重启进入ubuntu18.04系统,原 &ldquo;/home&rdquo; 分区不会挂载。&nbsp;总过程已经完成一半了。</li> <li>再挂载并将原 &ldquo;/home&rdquo; 分区清理瘦身一下,删除家目录中.thumbnails,&nbsp;.cache这些可能冲突或不大重要的用户数据。</li> <li>将新/home目录内容rsync同步到旧 &ldquo;/home&rdquo;&nbsp;分区所在目录里。</li> <li>修改/etc/fstab,增加1行让系统重启后挂载原 &ldquo;/home&rdquo;&nbsp;盘。确认无误后重启就完成全部过程。</li> </ol> <p>这样的好处是家目录中的图片、视频、工作文件、工作目录等用户资料依然在那里,变了的只是系统部分,优雅完成升级。</p> <h3 id="40-ubuntu1804">4.0 安装Ubuntu18.04系统之后的优化<a class="headerlink" href="#40-ubuntu1804" title="Permanent link">&para;</a></h3> <h4 id="41-ubuntu1804">4.1 Ubuntu18.04修改源<a class="headerlink" href="#41-ubuntu1804" title="Permanent link">&para;</a></h4> <p>原来的url是cn.archive.ubuntu.com, 速度下载包时有<span class="caps">3MB</span>以上。其实不换也是可以的。</p> <p>如果要换, 以阿里举例, 修改/etc/apt/sources.list文件内容即可(修改前备份),&nbsp;改其他第三方的同理该域名即可。</p> <div class="highlight"><pre><span></span><span class="k">deb</span> <span class="s">http://mirrors.aliyun.com/ubuntu/</span> <span class="kp">bionic</span> <span class="kp">main</span> <span class="kp">restricted</span> <span class="k">deb</span> <span class="s">http://mirrors.aliyun.com/ubuntu/</span> <span class="kp">bionic-updates</span> <span class="kp">main</span> <span class="kp">restricted</span> <span class="k">deb</span> <span class="s">http://mirrors.aliyun.com/ubuntu/</span> <span class="kp">bionic</span> <span class="kp">universe</span> <span class="k">deb</span> <span class="s">http://mirrors.aliyun.com/ubuntu/</span> <span class="kp">bionic-updates</span> <span class="kp">universe</span> <span class="k">deb</span> <span class="s">http://mirrors.aliyun.com/ubuntu/</span> <span class="kp">bionic</span> <span class="kp">multiverse</span> <span class="k">deb</span> <span class="s">http://mirrors.aliyun.com/ubuntu/</span> <span class="kp">bionic-updates</span> <span class="kp">multiverse</span> <span class="k">deb</span> <span class="s">http://mirrors.aliyun.com/ubuntu/</span> <span class="kp">bionic-backports</span> <span class="kp">main</span> <span class="kp">restricted</span> <span class="kp">universe</span> <span class="kp">multiverse</span> <span class="k">deb</span> <span class="s">http://mirrors.aliyun.com/ubuntu</span> <span class="kp">bionic-security</span> <span class="kp">main</span> <span class="kp">restricted</span> <span class="k">deb</span> <span class="s">http://mirrors.aliyun.com/ubuntu</span> <span class="kp">bionic-security</span> <span class="kp">universe</span> <span class="k">deb</span> <span class="s">http://mirrors.aliyun.com/ubuntu</span> <span class="kp">bionic-security</span> <span class="kp">multiverse</span> </pre></div> <h3 id="42-ubuntu1804">4.2 Ubuntu18.04调整用户界面、桌面工具栏、安装字体、重新安装历史包等<a class="headerlink" href="#42-ubuntu1804" title="Permanent link">&para;</a></h3> <h4 id="421-xp">4.2.1 调整桌面工具栏到下面,下重上轻的风格看起来比较稳重。也是xp时代传下的习惯。<a class="headerlink" href="#421-xp" title="Permanent link">&para;</a></h4> <h5 id="xubutnu1804ubuntubionic-beaver"><strong>XUbutnu18.04截图(Ubuntu),这个版本别名&rdquo;Bionic Beaver&rdquo;仿生河狸</strong><a class="headerlink" href="#xubutnu1804ubuntubionic-beaver" title="Permanent link">&para;</a></h5> <p><img alt="XUbutnu18.04程序截图" src="https://blog.pythonwood.com/uploads/2018/2018-04-27XUbutnu18.04程序截图.jpg" title="XUbutnu18.04程序截图"></p> <h4 id="422-cpu">4.2.2 在桌面地板面板工具栏上,添加自定义显示比如网速,<span class="caps">CPU</span>,内存等。<a class="headerlink" href="#422-cpu" title="Permanent link">&para;</a></h4> <p>添加网速提示器xfce4-netload-plugin,<span class="caps">CPU</span>内存提示器xfce4-systemload-plugin后的工具栏随时可获知负载网速这些计算机情况,用户体验比windows更赞! <img alt="XUbuntu已设置显示网速和CPU内存负载的工具栏" src="https://blog.pythonwood.com/uploads/2018/2018-04-27XUbuntu已设置显示网速和CPU内存负载的工具栏.jpg" title="XUbuntu已设置显示网速和CPU内存负载的工具栏"></p> <h4 id="423">4.2.3 安装谷歌拼音,文泉驿字体,调整系统字体大小等<a class="headerlink" href="#423" title="Permanent link">&para;</a></h4> <p>Ubuntu18.04默认安装fcitx-sunpinyin也好用,用起来和googlepinyin差不多。所以……我还是选大款的好了。</p> <div class="highlight"><pre><span></span>sudo apt-get install fcitx-googlepinyin fonts-wqy* </pre></div> <h4 id="424">4.2.4 安装以前安装过的软件<a class="headerlink" href="#424" title="Permanent link">&para;</a></h4> <p>之前记录过旧系统安装的软件,现在按需安装回来。</p> <div class="highlight"><pre><span></span>apt-get install gedit gthumb tmux vim-gtk3 python-pip python3-pip ipython ipython3 iotop iftop sysstat nload iptraf virtualbox virtualbox-ext-pack gparted testdisk fcitx-googlepinyin smplayer vlc gpaint xpaint pinta pelican python-bs4 axel aria2 unzip apt-file gimp remmina retext potool curl geoip-bin phantomjs lynx vim-tiny gnome-disk-utility sqlite3 python-mysqldb python-pymysql kazam pitivi gsound-tools flowblade mp3splt-gtk mp3wrap mtp-tools adb cmake </pre></div> <h3 id="43-qqctrlaltalinuxxfce-screenshooterqq">4.3 实现<span class="caps">QQ</span>截图功能,快捷键Ctrl+Alt+A框选截屏。(linux下用xfce-screenshooter变身<span class="caps">QQ</span>截图神器)<a class="headerlink" href="#43-qqctrlaltalinuxxfce-screenshooterqq" title="Permanent link">&para;</a></h3> <p>不需安装额外软件xfce-screenshooter是XUbuntu自带的,只需操作如下步骤: 打开设置-&gt; 键盘 -&gt; 应用程序快捷键 -&gt; 添加。 然后命令框输入xfce4-screenshooter&nbsp;&ndash;region确认,再按住Ctrl+Alt+A,确认添加即可。</p> <p>xfce4-screenshooter这软件很赞,不需安装<span class="caps">QQ</span>就能有很好的截图体验。某些时候,linux用户体验可以比windows好,需要使用者本身已经对linux比较上手。 <img alt="在Linux下设置QQ截图功能" src="https://blog.pythonwood.com/uploads/2018/2018-04-27在Linux下设置QQ截图功能.jpg" title="在Linux下设置QQ截图功能"></p> <h3 id="50-ubuntu1804">5.0 安装Ubuntu18.04系统之后的问题解决<a class="headerlink" href="#50-ubuntu1804" title="Permanent link">&para;</a></h3> <h4 id="51-ubuntu1804shadowsocks">5.1 Ubuntu18.04启动shadowsocks报错解决<a class="headerlink" href="#51-ubuntu1804shadowsocks" title="Permanent link">&para;</a></h4> <p>原因:openssl升级到1.1.0以上版本,导致shadowsocks启动报undefined symbol:&nbsp;EVP_CIPHER_CTX_cleanup错误</p> <p>解决:&nbsp;将py文件中所有的EVP_CIPHER_CTX_cleanup改为EVP_CIPHER_CTX_reset</p> <div class="highlight"><pre><span></span>sudo vim /usr/local/lib/python2.7/dist-packages/shadowsocks/crypto/openssl.py # 按实际路径改 </pre></div> <h4 id="52-ubuntu1804wpserror-while-loading-shared-libraries-libpng12so0">5.2 Ubuntu18.04安装wps(解决报错error while loading shared libraries: libpng12.so.0)<a class="headerlink" href="#52-ubuntu1804wpserror-while-loading-shared-libraries-libpng12so0" title="Permanent link">&para;</a></h4> <p>第一步下载wps-office_10.1.0.5672~a21_amd64.deb, libpng12-0_1.2.54-1ubuntu1_amd64.deb,&nbsp;wps_symbol_fonts.zip(window字体非必须)文件备用。</p> <p>第二步运行命令安装:</p> <div class="highlight"><pre><span></span>sudo dpkg -i wps-office_10.1.0.5672~a21_amd64.deb libpng12-0_1.2.54-1ubuntu1_amd64.deb </pre></div> <h4 id="53-panel">5.3 底部面板panel出现重复的网络图标解决<a class="headerlink" href="#53-panel" title="Permanent link">&para;</a></h4> <p><img alt="panel面板重复出现network图标" src="https://blog.pythonwood.com/uploads/2018/2018-05-09面板显示重复网络图标.png" title="panel面板重复出现network图标"></p> <p>解决:设置 - 会话与启动 - 程序自启动 - 取消勾选network项。 注销,再登录,重新勾选,注销,再登录。&nbsp;图标恢复只有一个。</p> <h3 id="60-ubuntu1804">6.0 安装Ubuntu18.04总结提升<a class="headerlink" href="#60-ubuntu1804" title="Permanent link">&para;</a></h3> <p>升级过程比较有把握,遇到的问题都是典型缺so文件这些小问题,通过谷歌搜索就能解决。</p> <p>某些时候,linux用户体验可以比windows好,需要使用者本身已经对linux比较上手。</p>实测家庭电器电功率记录——节约用电支持环保2018-04-20T15:16:00+08:002018-04-20T15:16:00+08:00pythonwoodtag:blog.pythonwood.com,2018-04-20:/2018/04/实测家庭电器电功率记录——节约用电支持环保/<p>家用电器经常待机,手机插头不拔,长期旅行不清空冰箱不关总闸,我一直认为浪费电但没有具体量化的认知。最近下决心花36元来记录电器的耗电功率排行。具体就是买了个可以显示耗电快慢的<a href="https://s.click.taobao.com/t?e=m%3D2%26s%3DNYboi0mHsGQcQipKwQzePOeEDrYVVa64K7Vc7tFgwiHjf2vlNIV67rTJ9qRSwRX4jGYPrSmetxGs9V29auOuBOBgn3DwXo5fs9cRaxJdiKw3LnkA3bZiA5IdTsHekIOqQxPkL4fipmEcVFeZKQgm4n%2BucW%2B%2Fygb8cSpj5qSCmbA%3D&amp;pvid=10_120.239.178.83_3183_1524209142036" title="家用电功率计量插座">家用电功率计量插座</a>,然后花了些时间测量数据并记录下来。随用随测出结果,十分好用。</p> <h3 id="_1">实测过程<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p><img alt="电功率插座显示插头纯消耗功率是0.5W" src="https://blog.pythonwood.com/uploads/2018/电功率插座显示插头纯消耗功率是0.5W.jpg" title="电功率插座显示插头纯消耗功率是0.5W"></p> <p>插座本身很小,测试过程非常方便。插上就实时显示电功率,按上下可切换显示电压,频率,时间,功率因素等。</p> <p>孔位不多没有关系,可加一个排插测出总电功率就好 …</p><p>家用电器经常待机,手机插头不拔,长期旅行不清空冰箱不关总闸,我一直认为浪费电但没有具体量化的认知。最近下决心花36元来记录电器的耗电功率排行。具体就是买了个可以显示耗电快慢的<a href="https://s.click.taobao.com/t?e=m%3D2%26s%3DNYboi0mHsGQcQipKwQzePOeEDrYVVa64K7Vc7tFgwiHjf2vlNIV67rTJ9qRSwRX4jGYPrSmetxGs9V29auOuBOBgn3DwXo5fs9cRaxJdiKw3LnkA3bZiA5IdTsHekIOqQxPkL4fipmEcVFeZKQgm4n%2BucW%2B%2Fygb8cSpj5qSCmbA%3D&amp;pvid=10_120.239.178.83_3183_1524209142036" title="家用电功率计量插座">家用电功率计量插座</a>,然后花了些时间测量数据并记录下来。随用随测出结果,十分好用。</p> <h3 id="_1">实测过程<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p><img alt="电功率插座显示插头纯消耗功率是0.5W" src="https://blog.pythonwood.com/uploads/2018/电功率插座显示插头纯消耗功率是0.5W.jpg" title="电功率插座显示插头纯消耗功率是0.5W"></p> <p>插座本身很小,测试过程非常方便。插上就实时显示电功率,按上下可切换显示电压,频率,时间,功率因素等。</p> <p>孔位不多没有关系,可加一个排插测出总电功率就好。</p> <p>但很可惜,最想测试的电热水器因为插孔为非普标的,所以没能测试。</p> <h3 id="_2">电器功耗实测记录表<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h3> <table> <thead> <tr> <th>常用电器元件</th> <th>耗电功率</th> </tr> </thead> <tbody> <tr> <td>树莓派</td> <td>4.5W (开机过程8W)</td> </tr> <tr> <td>笔记本电脑</td> <td>10W (开机过程20W)</td> </tr> <tr> <td>手机充电器</td> <td>0W (充电时2W)</td> </tr> <tr> <td>排插</td> <td>0.5W</td> </tr> <tr> <td>低音音箱</td> <td>15W</td> </tr> <tr> <td>hp打印机</td> <td>1W (A4打印时10W)</td> </tr> <tr> <td>广电机顶盒</td> <td>7W</td> </tr> <tr> <td>tplink路由</td> <td>2.4W</td> </tr> <tr> <td>上网猫</td> <td>3W</td> </tr> <tr> <td>oye路由</td> <td>1.5W</td> </tr> <tr> <td>电风扇待机</td> <td>0W</td> </tr> </tbody> </table> <h3 id="_3">电功率综述<a class="headerlink" href="#_3" title="Permanent link">&para;</a></h3> <ol> <li>插座本身通电下就要浪费0.5W。(和预测相反)</li> <li>手机充电器一直插着是0W,以后再不怕浪费电了。(和预测相反)</li> <li>猜测刷了openwrt的路由可能比很多厂商路由省电。比起功能复杂的路由,我更偏向选择功耗低的。</li> <li>猫、机顶盒确实是耗电大户,电费隐形杀手。(符合预测)</li> <li>笔记本电脑功耗甚至比台式电脑的单个组成部分音箱还低,所以买电脑选择笔记本重要原因之一是省电。按台式机60W估算一年下来,省下的电费是很可观的。</li> </ol> <h3 id="_4">附上原始笔记<a class="headerlink" href="#_4" title="Permanent link">&para;</a></h3> <p><img alt="家用电器功率记录原始笔记" src="https://blog.pythonwood.com/uploads/2018/家用电器功率记录原始笔记.jpg" title="家用电器功率记录原始笔记"></p> <h3 id="_5">总结<a class="headerlink" href="#_5" title="Permanent link">&para;</a></h3> <p>最近物联网、智能家居很火,有很多商家向消费者推销产品只重功能不重功耗。典型例子就是路由器做了很多不应该做的事情,路由器功能越丰富,就越费电。另外一个例子是智能插座,插座变成微型电脑,连接wifi以便于手机远程开断插头电源。本身这个idea就比较有争议,而且耗电大增,我不看好其发展。现在提倡环保,资源越来越紧张,希望在选购商品时,为环境多考虑一分。能节约用电的地方尽量节约。</p> <h3 id="_6">参考<a class="headerlink" href="#_6" title="Permanent link">&para;</a></h3>个案分析:20800元的微信小程序抢注骗局揭秘2017-12-29T15:00:00+08:002017-12-29T15:00:00+08:00pythonwoodtag:blog.pythonwood.com,2017-12-29:/2017/12/个案分析:20800元的微信小程序抢注骗局揭秘/<p>2017年12月份,我身边一位做实体母婴商品店的老板陷入了一场微信小程序“骗局”,以每个小程序20800的价格投资了小程序,我一开始以也没发现很不妥,直到后来老板再次被忽悠买多了几个小程序才醒悟是这样一场骗局。</p> <h3 id="_1">过程<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <ol> <li>骗子以展望小程序未来,小程序像域名那样具有唯一性,有品牌推广功能等等为噱头,诱骗店主购买小程序20800元。</li> <li> <p>半年后,四川一家野技公司加了店主微信,表示他的小程序名字非常唯一,价值高,有家天津科技公司愿意买,然后故意任由店主出价。最后谈到150万转让费。期间制造各种问题拖延时间,店主也认为升值快 …</p></li></ol><p>2017年12月份,我身边一位做实体母婴商品店的老板陷入了一场微信小程序“骗局”,以每个小程序20800的价格投资了小程序,我一开始以也没发现很不妥,直到后来老板再次被忽悠买多了几个小程序才醒悟是这样一场骗局。</p> <h3 id="_1">过程<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <ol> <li>骗子以展望小程序未来,小程序像域名那样具有唯一性,有品牌推广功能等等为噱头,诱骗店主购买小程序20800元。</li> <li> <p>半年后,四川一家野技公司加了店主微信,表示他的小程序名字非常唯一,价值高,有家天津科技公司愿意买,然后故意任由店主出价。最后谈到150万转让费。期间制造各种问题拖延时间,店主也认为升值快,担心卖早了,不想早早答应,“配合”拖延。</p> </li> <li> <p>再有其他2家异地公司谈另一种合作模式,一切成本由科技公司出,有利润后,店主和公司按8:2分成。为增加信任,同时给出了一篇四海皆准的操作方案稿,并且互怼竞争方说自己公司才比较靠谱。</p> </li> <li>我开始介入,发现小程序可登录可运行,前台后台用户体验都极差,并有不能写收货地址等明显bug。但因为反馈后当日下午就修复了问题,就觉得这家公司还是靠谱的。我甚至还觉得店主可能真的捡到金了。毕竟在互联网工作,见过些大起大落的科技浪潮。风口之中,猪也能飞。</li> <li>后来店主被忽悠,再入手2个20800元的小程序,签完文件交了钱才和我说。我终于才想清楚整件事情。——一边虚高价销售抢注和维护小程序的“终身服务”,一边装作有意收购出更离谱的高价造成店主认为小程序极具投资价值的幻觉。然后骗子让店主多买几个来挣更多钱。&nbsp;因没有互联网经验,实体店主在被忽悠下爽口地多买几个。</li> <li>认清这个行骗模式之后劝醒了店主,店主后来收回合约和钱,只损失了2000元。至于之前就有那个小程序,他表示就算了。此事至此结束。</li> </ol> <p><img alt="可疑公司1" height="50%" src="https://blog.pythonwood.com/uploads/2017/可疑公司1.jpg" title="可疑公司1" width="20%"> <img alt="可疑公司2" height="50%" src="https://blog.pythonwood.com/uploads/2017/可疑公司2.jpg" title="可疑公司2" width="20%"> <img alt="可疑公司3" height="50%" src="https://blog.pythonwood.com/uploads/2017/可疑公司3.jpg" title="可疑公司3" width="20%"> <img alt="可疑公司合同" height="50%" src="https://blog.pythonwood.com/uploads/2017/可疑公司合同.jpg" title="可疑公司合同" width="20%"> </p> <h3 id="_2">证据难点<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h3> <p>这个产品是一个能运行,能使用,能交易的空壳,除此之外毫无价值。 虽然明知那些小程序的劣质功能只值两、三千,卖了20800给实体店主,但是骗子可以咬定这个壳程序就值这个价。&nbsp;互联网虚拟产品成本核算难问题。让你无法判定次品高卖这个事实。所以,这是一次高级的骗局,虽然能识破,但维权投诉没有用。</p> <p>最近接触股市,中国股市的本质是不是类似呢? 再比如比特币最近大起大落……&nbsp;大伪若真。假作真时假亦真。</p> <h3 id="_3">参考<a class="headerlink" href="#_3" title="Permanent link">&para;</a></h3> <p>假冒腾讯公司1.98万卖小程序,各大小老板为何纷纷被骗?&nbsp;http://www.newbelink.com/article/31911.html</p> <p>注意微信小程序骗局&nbsp;https://tieba.baidu.com/p/5249331035</p> <p>警惕!北海出现“1.98万抢注小程序”骗局!已有人被骗惨,都要注意…&nbsp;http://www.sohu.com/a/203976441_185101</p>RSA原理:欧几里德算法与奥数内容辗转相除法——挑战PythonTip2017-12-17T23:00:00+08:002017-12-17T23:00:00+08:00pythonwoodtag:blog.pythonwood.com,2017-12-17:/2017/12/RSA原理:欧几里德算法与奥数内容辗转相除法——挑战PythonTip/<p><a href="http://www.pythontip.com" title="PythonTip">PythonTip</a> 里未攻克的题目,如<a href="http://www.pythontip.com/coding/code_oj_case/46" title="RSA密码方程"><span class="caps">RSA</span>密码方程</a>,如今积累工作经验之后从新挑战,仍然失败未成功了。把过程记录分享下。</p> <h3 id="_1">描述:<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>在<span class="caps">RSA</span>密码体系中,欧几里得算法是加密或解密运算的重要组成部分。它的基本运算过程就是解 (x*a) % n = 1 这种方程。 其中 …</p><p><a href="http://www.pythontip.com" title="PythonTip">PythonTip</a> 里未攻克的题目,如<a href="http://www.pythontip.com/coding/code_oj_case/46" title="RSA密码方程"><span class="caps">RSA</span>密码方程</a>,如今积累工作经验之后从新挑战,仍然失败未成功了。把过程记录分享下。</p> <h3 id="_1">描述:<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>在<span class="caps">RSA</span>密码体系中,欧几里得算法是加密或解密运算的重要组成部分。它的基本运算过程就是解 (x*a) % n = 1 这种方程。 其中,x,a,n皆为正整数。现在给你a和n的值(1 &lt; a,n &lt; 140000000),请你求出最小的满足方程的正整数解x(保证有解). 如:a = 1001, n =&nbsp;3837,则输出23。</p> <h3 id="_2">分析:<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h3> <p>没头绪,在讨论里看时恍然,用到小学奥术内容辗转相除法(求最大公约数)了。如果 <code>(x*a) % n = 1</code> 变成 <code>(x*a) % n = 0</code> , 那x*a就是a和n公倍数了。如果这是小学奥数题,就先用辗转相除法得最大公约数,而最小公倍数用两数积除以最大公约数得出来。&nbsp;rsa的原理数学基础欧几里得算法和小学奥数有着这样的联系,发现这点让我觉得不可思议又略有惊叹。看来学小学奥数有用,至少是可以为算法编程做准备的,学到了最朴素的数论。</p> <h4 id="_3">辗转相除法(朴素欧几里得算法,中国余数定理,韩信点兵)<a class="headerlink" href="#_3" title="Permanent link">&para;</a></h4> <p>(引用自 <a href="https://xuanwo.org/2015/03/11/number-theory-gcd/," title="数论——欧几里得算法">数论——欧几里得算法</a>)</p> <p>欧几里得算法,又名辗转相除法,是求最大公约数的算法。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如,252和105的最大公约数是21(252 = 21 × 12;105 = 21 × 5);因为252 − 105 =&nbsp;147,所以147和105的最大公约数也是21。在这个过程中,较大的数缩小了,所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时,所剩下的还没有变成零的数就是两数的最大公约数。 </p> <p><img alt="辗转相除法演示图.gif" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,辗转相除法演示图.gif"></p> <h4 id="_4">题目语义转化<a class="headerlink" href="#_4" title="Permanent link">&para;</a></h4> <p>求这样一个数x*a,能被a整除,被n整除余1。 </p> <p>这就很形似 <em>有一个数除以3余2,除以5余3,除以7余4,除以9余5.这个数至少是?</em> 被称为<a href="https://zh.wikipedia.org/wiki/中国余数定理," title="中国余数定理">中国余数定理</a></p> <h4 id="_5">扩展欧几里德算法<a class="headerlink" href="#_5" title="Permanent link">&para;</a></h4> <p>基本算法:对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x,y ,使得&nbsp;gcd(a,b)=ax+by。</p> <p>证明:设&nbsp;a&gt;b。</p> <p>1,显然当 b=0,gcd(a,b)=a。此时&nbsp;x=1,y=0;</p> <p>2,ab!=0&nbsp;时</p> <p>设&nbsp;ax1+by1=gcd(a,b);</p> <p>bx2+(a mod b)y2=gcd(b,a mod&nbsp;b);</p> <p>根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod&nbsp;b);</p> <p>则:ax1+by1=bx2+(a mod&nbsp;b)y2;</p> <p>即:ax1+by1=bx2+(a-(a/b)<em>b)y2=ay2+bx2-(a/b)</em>by2;</p> <p>根据恒等定理得:x1=y2;&nbsp;y1=x2-(a/b)*y2;</p> <p>这样我们就得到了求解 x1,y1 的方法:x1,y1 的值基于&nbsp;x2,y2.</p> <p>上面的思想是以递归定义的,因为 gcd 不断的递归求解一定会有个时候&nbsp;b=0,所以递归可以结束。</p> <p>&hellip;</p> <p>同余方程 ax≡b (mod n)对于未知数 x 有解,当且仅当 gcd(a,n) | b。且方程有解时,方程有 gcd(a,n)&nbsp;个解。</p> <p>求解方程 ax≡b (mod n) 相当于求解方程 ax+ ny= b, (x,&nbsp;y为整数)</p> <h3 id="_6">我的一个另类编程解法(融合了辗转相除法思想)。<a class="headerlink" href="#_6" title="Permanent link">&para;</a></h3> <h4 id="_7">算法描述<a class="headerlink" href="#_7" title="Permanent link">&para;</a></h4> <p>(x*a) % n = 1 对应 方程 ax - ny = 1&nbsp;的整数解 </p> <p>(a,n必定互质。如不互质可提取公因子,公因子*X=1,与X为整数矛盾)</p> <p>化简降解方程分两情况:</p> <ol> <li>a&gt;=n 时 变形为方程 (a mod n)x - n(y-[a/n]x) = 1&nbsp;有整数解 </li> <li>a&lt;n 时 变形为方程 a(x-[n/a]a) - (n mod a)y = 1&nbsp;有整数解</li> </ol> <p>无论那一种都变回 ax - ny = 1&nbsp;的形式。所以重复化简,因a,n互质,最后会到达a,n其一是1的情况。</p> <h4 id="971">例子说明: 求能被9整除,被7除余1的最小数<a class="headerlink" href="#971" title="Permanent link">&para;</a></h4> <ol> <li>9x=1(mod7) 对应方程 9x - 7y = 1&nbsp;的整数解</li> <li>变形有2x - 7(y-x) = 1 然后令 x_1=x, y_1=y-x 得方程 2x_1 - 7y_1 =&nbsp;1 </li> <li>变形有2(x_1-3y_1) - y_1 = 1 然后令 x_2=x_1-3y_1, y_2=y_1 得方程 2x_2 - y_2 = 1 显然有解 x_2=1&nbsp;y_2=1 </li> <li>好了,往上一步一步回溯得最初的x,y值 (x_2,y_2), (x_1,y_1), (x,y)&nbsp;分别为(1,1),(4,1),(4,5)</li> <li>9x = (9<em>4 mod 9</em>7) = 36&nbsp;答:求能被9整除,被7除余1的数是36</li> </ol> <p>python语言是弱递归化语言,&nbsp;python之父说递归都可以转成循环。所以我用递归后,转循环了。</p> <h3 id="python">Python代码:<a class="headerlink" href="#python" title="Permanent link">&para;</a></h3> <div class="highlight"><pre><span></span><span class="c1">################################################################################</span> <span class="c1"># print &quot;F: 答案错误 循环解法&quot;</span> <span class="c1">################################################################################</span> <span class="s s-Atom">def</span> <span class="nf">gcd</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">)</span><span class="s s-Atom">:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">辗转相除求最大公约数</span> <span class="s s-Atom">if</span> <span class="s s-Atom">a</span> <span class="o">&lt;</span> <span class="nn">n</span><span class="p">:</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span> <span class="o">=</span> <span class="s s-Atom">n</span><span class="p">,</span><span class="s s-Atom">a</span> <span class="s s-Atom">while</span> <span class="s s-Atom">n</span> <span class="p">!</span><span class="o">=</span> <span class="mi">0</span><span class="s s-Atom">:</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span> <span class="o">=</span> <span class="s s-Atom">n</span><span class="p">,</span><span class="s s-Atom">a</span><span class="c1">%n</span> <span class="s s-Atom">return</span> <span class="s s-Atom">a</span> <span class="s s-Atom">def</span> <span class="nf">exgcd</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">)</span><span class="s s-Atom">:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">ax</span><span class="o">=</span><span class="mi">1</span><span class="p">(</span><span class="o">mod</span> <span class="s s-Atom">n</span><span class="p">)</span> <span class="s s-Atom">即</span> <span class="s s-Atom">ax</span><span class="o">-</span><span class="s s-Atom">ny</span><span class="o">=</span><span class="mi">1</span> <span class="s s-Atom">求x</span><span class="p">,</span><span class="s s-Atom">y</span> <span class="s s-Atom">#</span> <span class="s s-Atom">print</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span> <span class="s s-Atom">if</span> <span class="nf">gcd</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">)</span> <span class="p">!</span><span class="o">=</span> <span class="mi">1</span><span class="s s-Atom">:</span> <span class="s s-Atom">raise</span> <span class="nv">Exception</span><span class="p">(</span><span class="s s-Atom">&#39;fei hu zhi&#39;</span><span class="p">)</span> <span class="s s-Atom">#</span> <span class="s s-Atom">先检查是否互质</span> <span class="s s-Atom">l</span> <span class="o">=</span> <span class="p">[]</span> <span class="s s-Atom">while</span> <span class="s s-Atom">a</span><span class="p">!</span><span class="o">=</span><span class="mi">1</span> <span class="s s-Atom">and</span> <span class="s s-Atom">n</span><span class="p">!</span><span class="o">=</span><span class="mi">1</span><span class="s s-Atom">:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n总会有个先到1,触底条件就是1</span> <span class="s s-Atom">l</span><span class="p">.</span><span class="nf">append</span><span class="p">((</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">))</span> <span class="s s-Atom">if</span> <span class="s s-Atom">a</span><span class="o">&gt;</span><span class="nn">n</span><span class="p">:</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span> <span class="o">=</span> <span class="s s-Atom">a</span><span class="c1">%n,n</span> <span class="nn">else</span><span class="p">:</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span> <span class="o">=</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="c1">%a</span> <span class="s s-Atom">if</span> <span class="s s-Atom">a</span><span class="o">==</span><span class="mi">1</span><span class="s s-Atom">:</span> <span class="s s-Atom">p</span> <span class="o">=</span> <span class="p">(</span><span class="s s-Atom">n</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span> <span class="s s-Atom">elif</span> <span class="s s-Atom">n</span><span class="o">==</span><span class="mi">1</span><span class="s s-Atom">:</span> <span class="s s-Atom">p</span> <span class="o">=</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="s s-Atom">a</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="s s-Atom">for</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span> <span class="s s-Atom">in</span> <span class="s s-Atom">l</span><span class="p">[</span><span class="s s-Atom">::-</span><span class="mi">1</span><span class="p">]</span><span class="s s-Atom">:</span> <span class="s s-Atom">if</span> <span class="s s-Atom">a</span><span class="o">&gt;</span><span class="nn">n</span><span class="p">:</span> <span class="s s-Atom">p</span> <span class="o">=</span> <span class="p">(</span><span class="s s-Atom">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="c1">% n, (a//n*p[0]+p[1]) % a) # 这个值也是解,但没有最简:return (p[0], a//n*p[0]+p[1])</span> <span class="nn">else</span><span class="p">:</span> <span class="s s-Atom">p</span> <span class="o">=</span> <span class="p">((</span><span class="s s-Atom">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">+</span><span class="s s-Atom">n</span><span class="o">//</span><span class="s s-Atom">a</span><span class="o">*</span><span class="s s-Atom">p</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> <span class="c1">% n, p[1] % a) # 这个值也是解,但没有最简:return (p[0]+n//a*p[1], p[1])</span> <span class="s s-Atom">return</span> <span class="s s-Atom">p</span> <span class="s s-Atom">print</span> <span class="nf">exgcd</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">)</span> <span class="c1">################################################################################</span> <span class="c1"># print &quot;F: 答案错误 递归解法&quot;</span> <span class="c1">################################################################################</span> <span class="s s-Atom">def</span> <span class="nf">gcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">)</span><span class="s s-Atom">:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">辗转相除求最大公约数</span> <span class="s s-Atom">if</span> <span class="s s-Atom">a</span> <span class="o">*</span> <span class="s s-Atom">n</span> <span class="o">==</span> <span class="mi">0</span><span class="s s-Atom">:</span> <span class="s s-Atom">return</span> <span class="s s-Atom">a</span><span class="o">+</span><span class="s s-Atom">n</span> <span class="s s-Atom">return</span> <span class="nf">gcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="c1">%n,n) if a&gt;=n else gcd_r(a,n%a)</span> <span class="c1"># print gcd(a,n)</span> <span class="s s-Atom">def</span> <span class="nf">exgcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="p">)</span><span class="s s-Atom">:</span> <span class="s s-Atom">#</span> <span class="s s-Atom">ax</span><span class="o">=</span><span class="mi">1</span><span class="p">(</span><span class="o">mod</span> <span class="s s-Atom">n</span><span class="p">)</span> <span class="s s-Atom">即</span> <span class="s s-Atom">ax</span><span class="o">-</span><span class="s s-Atom">ny</span><span class="o">=</span><span class="mi">1</span> <span class="s s-Atom">求x</span><span class="p">,</span><span class="s s-Atom">y</span> <span class="s s-Atom">#</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n总会有个先到1,触底条件就是1</span> <span class="s s-Atom">#</span> <span class="s s-Atom">print</span> <span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span> <span class="s s-Atom">if</span> <span class="nf">gcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">)</span> <span class="p">!</span><span class="o">=</span> <span class="mi">1</span><span class="s s-Atom">:</span> <span class="s s-Atom">raise</span> <span class="nv">Exception</span><span class="p">(</span><span class="s s-Atom">&#39;fei hu zhi&#39;</span><span class="p">)</span> <span class="s s-Atom">#</span> <span class="s s-Atom">先检查是否互质</span> <span class="s s-Atom">if</span> <span class="s s-Atom">a</span><span class="o">==</span><span class="mi">1</span><span class="s s-Atom">:</span> <span class="nf">return</span> <span class="p">(</span><span class="s s-Atom">n</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="mi">1</span><span class="p">)</span> <span class="s s-Atom">if</span> <span class="s s-Atom">n</span><span class="o">==</span><span class="mi">1</span><span class="s s-Atom">:</span> <span class="nf">return</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="s s-Atom">a</span><span class="o">-</span><span class="mi">1</span><span class="p">)</span> <span class="s s-Atom">if</span> <span class="s s-Atom">a</span><span class="o">&gt;</span><span class="nn">n</span><span class="p">:</span> <span class="s s-Atom">p</span> <span class="o">=</span> <span class="nf">exgcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="c1">%n, n)</span> <span class="nf">return</span> <span class="p">(</span><span class="s s-Atom">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span> <span class="c1">% n, (a//n*p[0]+p[1]) % a) # 这个值也是解,但没有最简:return (p[0], a//n*p[0]+p[1])</span> <span class="nn">else</span><span class="p">:</span> <span class="s s-Atom">p</span> <span class="o">=</span> <span class="nf">exgcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span> <span class="s s-Atom">n</span><span class="c1">%a) </span> <span class="nf">return</span> <span class="p">((</span><span class="s s-Atom">p</span><span class="p">[</span><span class="mi">0</span><span class="p">]</span><span class="o">+</span><span class="s s-Atom">n</span><span class="o">//</span><span class="s s-Atom">a</span><span class="o">*</span><span class="s s-Atom">p</span><span class="p">[</span><span class="mi">1</span><span class="p">])</span> <span class="c1">% n, p[1] % a) # 这个值也是解,但没有最简:return (p[0]+n//a*p[1], p[1])</span> <span class="s s-Atom">print</span> <span class="nf">exgcd_r</span><span class="p">(</span><span class="s s-Atom">a</span><span class="p">,</span><span class="s s-Atom">n</span><span class="p">)</span> </pre></div> <p>小学初中就知道数论,数论真有魅力,非常漂亮。</p> <h3 id="_8">参考<a class="headerlink" href="#_8" title="Permanent link">&para;</a></h3> <p>数论——欧几里得算法&nbsp;https://xuanwo.org/2015/03/11/number-theory-gcd/</p> <p>欧几里德与扩展欧几里德算法&nbsp;http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html</p> <p>欧几里得算法(辗转相除法)&nbsp;https://my.oschina.net/u/1780798/blog/646739</p> <p>https://zhidao.baidu.com/question/406531667.html?qbl=relate_question_3</p>威佐夫博弈:取石子游戏算法——挑战PythonTip2017-12-16T16:30:00+08:002017-12-16T16:30:00+08:00pythonwoodtag:blog.pythonwood.com,2017-12-16:/2017/12/威佐夫博弈:取石子游戏算法——挑战PythonTip/<p><a href="http://www.pythontip.com" title="PythonTip">PythonTip</a> 里未攻克的题目,如<a href="http://www.pythontip.com/coding/code_oj_case/46" title="取石子游戏">取石子游戏</a>,如今积累工作经验之后从新挑战,成功了。把过程记录分享下。</p> <h3 id="_1">描述:<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法, 一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。 现在给出初始的两堆石子的数目a和b,如果轮到你先取,假设双方都采取最好的策略 …</p><p><a href="http://www.pythontip.com" title="PythonTip">PythonTip</a> 里未攻克的题目,如<a href="http://www.pythontip.com/coding/code_oj_case/46" title="取石子游戏">取石子游戏</a>,如今积累工作经验之后从新挑战,成功了。把过程记录分享下。</p> <h3 id="_1">描述:<a class="headerlink" href="#_1" title="Permanent link">&para;</a></h3> <p>有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法, 一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。 现在给出初始的两堆石子的数目a和b,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。 如果你是胜者,输出Win,否则输出Loose。 例如,a=3,b=1,&nbsp;则输出Win(你先在a中取一个,此时a=2,b=1,此时无论对方怎么取,你都能将所有石子都拿走).</p> <h3 id="_2">分析(动态规划):<a class="headerlink" href="#_2" title="Permanent link">&para;</a></h3> <p>我的思路是转变成图形化表示,二维表中点(x,y)用W表示会赢,L表示为输。</p> <p>(x,y)的结果显然决定与前面已填好的(m,n) , 其中m,n 分别小于 x,y 。 所以可以用动态规划。&nbsp;根据之前失败坐标的集合推算本行的失败坐标。</p> <p>并且每行至多有一个失败坐标。所以能保证动态规划的时间复杂度不会很高。</p> <p>当我从(0,0)开始,填到(a,b)时就知道结果了。</p> <p>明显(x,y)和(y,x)结果一样,因此我刚开始只填半个表,导致结果不准,看了其他人的奇异坐标才明白到自己的错误。从新填好。</p> <h4 id="_3">错误填表分析过程<a class="headerlink" href="#_3" title="Permanent link">&para;</a></h4> <p><img alt="错误填表图1" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏错误填表图1.png"></p> <p><img alt="错误填表图2" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏错误填表图2.png"></p> <p><img alt="错误填表图3" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏错误填表图3.png"></p> <p>我根据这个过程写出版本一代码。</p> <h4 id="_4">正确填表分析过程<a class="headerlink" href="#_4" title="Permanent link">&para;</a></h4> <p><img alt="正确填表图1" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏正确填表图1.png"></p> <p><img alt="正确填表图2" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏正确填表图2.png"></p> <p><img alt="正确填表图3" src="https://blog.pythonwood.com/uploads/2017/挑战PythonTip,威佐夫博弈:取石子游戏正确填表图3.png"></p> <p>我本来猜测需要推到前面代码从来。幸运的是,运行正常的版本二的代码只在版本一加一行就可以了。</p> <p>下面是我的算法代码,比较简洁。动态规划确实强大,另外还有分治法也强。</p> <h3 id="python">Python代码:<a class="headerlink" href="#python" title="Permanent link">&para;</a></h3> <div class="highlight"><pre><span></span>################################################################################ # print &quot;T: 二维坐标表示法, 每行至多有一个失败坐标。二维表只填半边导致失误,改正&quot; ################################################################################ if a &lt; b: a,b = b,a m = [(0,0)] # 失败的坐标纪录池 for i in range(1,a+1): for j in range(i+1): # if i == j or j == 0: # win # continue for x in m: if (i-x[0]) == (j-x[1]) or i == x[0] or j == x[1]: # win break else: # else 是for的部分,break for的时候也break了else m.append((i,j)) # 版本一:二维表只填半边,所以只有这行代码 m.append((j,i)) # 版本二:二维表两边都填,多加这一行就OK了 #print i,j,m print &quot;Loose&quot; if (a,b) in m else &quot;Win&quot; </pre></div>