Bitcoin

总是看到有一些暴力破解的程序在不停的尝试比特币钱包的密钥，还声称已经很幸运的试到了几个钱包的密钥，并且移走了里面的几万美金。

下面的文字是抄于 rssdao.eth 的朋友圈。

抛256次硬币，你就拥有一个比特币私钥：人类算力难以企及的加密奇迹

破解比特币需要40亿个银河系？普通人根本无法想象的数学深渊。

当你抛硬币正面朝上为1，反面朝上为0，连续抛256次，并把结果转换成一个16进制数，就是下一个比特币的密钥，那么换句话来说，比特币私钥的本质就是256位二进制数，听起来普普通通有没有，感觉用普通的计算机随便就能破解了？

能这么想的一般数学老师已经哭在了厕所，2的256次方，相当于8个2的32次方相乘，二的32次方约等于40亿，现在有概念了吗？就是40亿×40亿×40亿×40亿×40亿×40亿×40亿再除以40亿。量化一下吧，第一个40亿是现代电脑的GPU每秒可以计算10亿个哈希值，40亿就相当于一台非常好的电脑，每秒计算的哈希值。

第二个40亿用世界第一搜索引擎，谷歌公司作为例子，虽然谷歌没有对外公布服务器的数量，但有人估算大约在几百万个，是世界上最多服务器的企业之一，代表着地表最高算力，大部分谷歌服务器的算力都不如我们这些满载GPU的电脑强，那么40亿台电脑姑且约等于1000个谷歌算力。

第三个40亿全世界约有73亿人，我们假设地球一半以上的人每个人都有1000个谷歌的算力。再来看看第4个40亿，想象一下40亿个这样的地球像极了银河系有没有？姑且称为银河系算力。第5个40亿，我们把40亿个这样的银河系打包，算力之和每秒能计算出2的160次方。第6第7个40亿，我们从时间维度考量，40亿秒约等于126.8年，乘以40亿倍，就是5070亿年，差不多是目前我们已知的宇宙年龄的37倍。

最后我们得出了结论，以人类现在的文明程度要解开比特币的密钥，大约需要40亿个银河系的算力，计算37倍于宇宙的年龄一样长的时间，才有1/(40亿^8)可以算出密钥的可能。所以现阶段人类科技而言，要通过技术手段破解密钥，简直就是痴人说梦了，这种体量的计算连量子计算机串联也望尘莫及。

2021年2月旧文，再思考一下比特币的伟大发明。

今天一个大饼的价格是9.2万美金。

Crypto Prices for BTC, ETH, TRX at 2025-04-24

比特币/大饼 BTC/Bitcoin

• 比特币私钥的数学本质与人类算力的极限
• 比特币最近波动有点大: 一天牛市一天熊
• 一万个比特币买披萨的男人: Laszlo Hanyecz 的传奇故事
• 比特币密钥/助记词值存储方法(2025年美国加州大火: 150万枚比特币丢失)
• 比特币创世区块 Genesis Block (大饼/BTC)
• 简单的投资策略: 美元成本平均法: 定投大饼/比特币/BTC
• 剑桥理发店可以用比特币支付
• 牛市2025! 比特币 All Time High 上了10万美金
• 下一次比特币减半是什么时候? When is Next Bitcoin Halving?
• 怎么样通过程序来获得比特币钱包余额? (NodeJs/Python)
• 比特币/BTC的ETF是什么?
• 问了ChatGPT比特币2023年年底多少钱(ChatGPT能预测或者估计将来?)
• 比特币转帐API中的找零参数
• 在亚马逊上买了一个实体比特币
• 世界上总有些人不信比特币
• 贪心算法玩比特币玩的就是心跳
• 把比特币变现的几种方法
• 公司今天上市, 我用比特币买了午餐 - Wirex 银行卡超级好用!
• Coinbase 支持 比特币现金 BCH 的交易了!
• 比特币下车了, 真的就很难于再上车了
• 说说STEEMIT机器人, 比特币和永动机
• 小白教程 - 如何把 SBD或者STEEM转出到比特币钱包?
• 一次有惊无险的误操作 - 通过 blocktrades 转出 SBD 到比特币钱包把MEMO填错了
• 比特币钱包线上和线下有啥区别?
• 我的比特币钱包
• 深度体验: OneKey虚拟货币出金卡(美元黑卡)
• Bittrex Global交易所即将关门大吉-请把币都转走-把价值不到7美元的BTC提现全过程
• 小白教程: 怎么领取 BCC (Bitcoin Cash) ?

英文：Toss a Coin 256 Times: The Math Behind an Unbreakable Bitcoin Private Key

相关文章：

1. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
2. 诈骗者正在利用多重签名钱包(Tron/波场): 保持警惕! 我经常收到类似这样的消息，有人请求协助转移资金，并提供钱包的种子短语或密码。 虽然看起来很诱人，但这实在是好得令人难以置信。不要上当，钱包里的币实际上是无法转出的。 他们实际上只是想骗你将资金（如TRX）转到他们的钱包，并以帮助解锁余额为借口。一旦你将资金转出，就再也拿不回来了。 请记住，任何声称可以“免费”提供带余额的钱包访问权限的人，很可能是在实施诈骗。务必保持警惕，保护好自己的资产！ 多签名授权 这些钱包通常需要多签名授权才能访问资金。这意味着即使你拥有种子短语或密码，也无法转移余额，因为还需要其他签名，这一点骗子通常不会提及。 相反，他们会以解锁钱包为借口，诱骗你转移自己的资金（如TRX）。不要上当——保持警惕，保护自己免受此类诈骗！ 保持谨慎，远离诈骗！ 英文：Scammers Are Exploiting Multi-Signature Wallets (Tron): Stay...
3. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
4. SteemIt 高级定制微信文章列表 RSS/API/阅读器 v2.0 The Advanced Wechat Group Posts Feed/API/Reader v2.0 Abstract: I have added five parameters to the...
5. 面向猫猫编程 Cat Oriented Programming (Chessly/Pyro这一生持续更新) 家里有两只猫 Chessly/Pyro，想着找个地方记录它们的生活，最后决定还是写在这里的博客。猫的一生很短，差不多也就二十年。 Chessly（黑白猫）是我加入微软剑桥研究院MSRC第一个月带回家的，过了两三个月，又把Pyro（橘猫）也接回了家。两只猫的名字是孩子们取的：Chessly因为黑白的像棋盘，加上“ly”听起来像个女孩的名字；而Pyro的意思是一团火（烟火），充满活力。 刚开始的时候，Chessly特别喜欢待在我的工作区域。她有时候趴在键盘上或旁边，有时候藏在显示器后面。偶尔还会绕到我身边“咕咕”地撒娇，等着我去摸她。有时更干脆跑到我腿上，舒舒服服地躺着。 不过，现在它们俩的体型都大了很多，躺在桌上就会挡住屏幕，真是“面向猫猫编程”（Cat Oriented Programming）的极致体验。 记录生活的点滴，也是一种珍惜，毕竟这二十年，我们会一起走过。 2024年 2025年 Ring视频：两猫日常就是打闹，Chessly追上Pyro想舔他，在猫的世界里，地位高的才能舔地位低的。 我家猫现在越来越胖，很喜欢在我工作的时候躺在显示器钱，很影响我的工作，不过这时候我就是会休息一下摸摸她，就当放松一下了。 Pyro在窗边喝水，这是个小的煮饭锅，现在不用了，就给猫当喝水的碗。Pyro很胆小，经常看到我就跑。没法跑就咕咕叫。 Chessly很喜欢陪我工作，然后她很好厅的盯着屏幕上的鼠标光标，真怕她把屏幕抓坏了。 哥哥弹琴，弟弟唱歌，Chessly午睡，真是幸福啊，下辈子做只猫吧。...
6. 个人网站Adsense广告申请通过: 需要最少15篇文章 我的个人网站 zhihua-lai.com 本月通过了 Adsense 审核，终于可以再次放置广告，赚些零花钱了。 其实，最初 Adsense 账户通过审核后就能直接放广告，但后来规则变得严格了。如果一个网站长时间没有放置任何 Adsense 广告代码，账户资格会被撤销。重新启用时，需要进行单独审核。如今，在 Google Adsense 中新增一个域名，也必须通过审核后才能投放广告。 为了让我的网站通过审核，我尝试了几次，但总是被拒，原因之一是必须要有足够的内容支持。例如，以前我做的工具网站 SlowAPI.com...
7. 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. 1 2...
8. 比特币最近波动有点大: 一天牛市一天熊 比特币10万美金以内都是最后上车的机会！ 比特币近期的价格波动可以归因于多个关键因素，包括地缘政治动态、监管变化以及加密行业内的重大安全事件。其中一个主要影响因素是美国前总统唐纳德·特朗普对乌克兰和加密货币监管的立场变化。据报道，特朗普再次当选，他可能会推动减少美国对乌克兰的支持，这可能会影响全球金融市场和风险偏好。同时，特朗普正在将自己塑造为亲加密货币的候选人，表示有意让美国成为一个更加友好的加密货币环境。这一立场引发了市场对监管政策可能发生变化的猜测，导致市场情绪在乐观和不确定性之间波动。 特朗普对俄乌战争的态度 美国第43届总统唐纳德·特朗普已经在2025年1月当选并正式上任（第二次），那么他的政策可能会对比特币价格的波动产生更加直接和显著的影响。他政府对乌克兰和加密货币监管的立场已经不再是猜测，而是正在实际塑造市场的关键力量。 特朗普（Donald Trump）减少美国对乌克兰的支持，全球投资者可能会预期地缘政治稳定性发生变化，从而增加对比特币作为避险资产的需求。同时，他的亲加密货币立场可能正在推动市场的乐观情绪。如果他的政府推出有利于加密行业的监管政策，例如明确的合规指南或减少监管审查，可能会吸引更多机构投资者进入市场，并促进更广泛的加密货币采用。然而，政策的快速变化也可能导致短期市场剧烈波动，因为市场需要时间来消化新的政策动向。 朝鲜黑客盗取Bybit交易所15亿美元的ETH 另一个显著影响比特币价格的事件是近期涉及朝鲜黑客组织“Lazarus”的15亿美元以太坊被盗案件。据报道，Bybit交易所（全球第二）这些被盗的ETH已经被清洗，此次大规模黑客攻击引发了人们对加密行业安全性的担忧。此类安全事件不仅会削弱投资者信心，还可能引发更严格的监管审查，导致短期市场动荡。此外，被盗资金的大规模流动和出售可能对市场流动性造成冲击，进一步加大价格波动。随着这些事件的持续发酵，比特币价格正受到政治决策、监管预期以及安全挑战等多重因素的影响。 与此同时，与朝鲜黑客组织 Lazarus 相关的 15 亿美元以太坊被盗事件仍在影响加密市场。由于这些被盗 ETH 已被清洗，人们对加密行业安全漏洞的担忧持续存在，同时也可能引发更严格的监管审查。政治、监管和安全等多重因素交织在一起，共同导致了比特币近期的剧烈价格波动。...

弟弟说，他想像我一样长大后成为一名程序员。然而，随着 人工智能/AI（比如ChatGPT） 的飞速进化，未来或许程序员这个职业都会被取代。这一两年，互联网大厂的招聘也明显减少了。

不过，我依然认为学习编程是一件好事。写程序不一定是为了当码农，刷题可以锻炼思维。之前教了他 700 天编程，但从未让他真正写代码，大概已经忘得差不多了。现在每天带着他刷题，也算是一次复习与再学习的过程。

对我来说，每天陪着他一起刷题，其实也相当于我自己做了一题。大部分时间里，我不亲自敲代码，而是我讲解，孩子来动手，这样能让他更熟悉代码，学得更快。

微博：我娃又在淘气了. 一身反骨: 我娃说他是想看看多添加几个if 会不会slow it down

我娃又在淘气了. 一身反骨: 我娃说他是想看看多添加几个if 会不会slow it down

相比之下，哥哥对金融更感兴趣，未来想从事相关行业，所以我没有强求他一起刷题，但有时候他也会在一旁听着。

乔布斯曾说：“这个国家的每个人都应该学习编程，因为编程能教会你如何思考。”（It teaches people how to think.）

乔布斯的名言：这个国家的每个人都应该学编程，它教会里如何思考。Every person in this country should learn how to program, as it teaches you how to think.

21 天可以养成习惯

我的儿子现在每天都在刷题，他说想成为一名软件工程师。但他还不知道，ChatGPT 正在统治世界，未来可能不再需要那么多程序员，尤其是初级工程师。

自己这辈子也就这样了，看不到希望，所以鸡个娃。每天带着娃刷力扣，等于自己也刷了一道。

每天弟弟都在刷力扣 希望他能坚持下来

视频：油管/Youtube | B站/小破站 | 微博视频 | 西瓜视频 | 微信视频号 | X/推特 | 小红书

Leetcode/力扣 多人协作代码房间

娃经常会在Google Talk上给我发力扣房间链接，邀请我看他实时敲代码，这个功能挺好，多人协作编辑文档。N年前QQ聊天对话框也有一个这种即时模型，可以实时看到对方敲的文字。

力扣的这个房间功能挺好，娃开了房间，我就能同步看到他敲代码，也能同时指点帮助他进步！

教娃编程

• 娃开始每天都在刷力扣, 他长大以后想当软件工程师
• 当了UP主四年多: 油管/Youtube上传了700多期视频, 2000个粉丝
• 写在教娃编程700天, what's next?
• 写在教娃编程视频300天

刷题：程序员的基本技能

• 力扣刷题打卡2209天竟然断了, 哎
• 娃开始每天都在刷力扣, 他长大以后想当软件工程师
• 力扣 Leetcode 的刷题利器: 在线调试器和自动代码提示完成
• 在LG的OLED智能电视下刷题/力扣
• 面试刷题更像是一种服从性测试
• 力扣刷题2000天
• 力扣刷题获得一件衣服奖励(Leetcode DCC Winner)
• 和媳妇约会影响我刷题的速度
• 第一次在动车上刷题: 国内的火车又快又舒服又便宜
• C++ 刷题坑: 二分查找也没有那么容易写出来
• 周末刷刷题找回ACM-er 的感觉
• 找一个 IPAD 9.7能刷题的蓝牙键盘不容易
• 程序员能刷题的网站和资源(我的刷题经验之谈)
• 时间碎片用来刷题是再好不过的了
• 熟能生巧 - 刷题的一些技巧的经验之谈
• 体验 Google Kickstart 刷题

英文：My 10-yr old son starts to do leetcode every day
英文：Leetcode’s Coding Room – Real time Coding Collaboration (Coding Interview)
英文：My son wants to know if “too many if-s” would slow the code down

弟弟刷题 vlog – 刷题要从娃娃卷起

2025-04-07：Ryan 每天都在练 LeetCode。他正在厨房里用苹果平板 iPad Pro 11 英寸（妙控键盘 Magic Keyboard）解决二叉树问题/Evaluate Binary Tree。

视频：油管/Youtube | B站/小破站 | 微博视频 | 西瓜视频 | 微信视频号 | X/推特 | 小红书 | Facebook

相关文章：

1. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
2. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
3. 编程: NodeJs/Javascript 函数检查Tron/波场区块链上的交易是否已确认(TronGrid API) 我们想知道给定的交易是否已经在 Tron/波场 区块链上确认，这可以通过 TronGrid API 轻松实现。 为了确保交易在Tron/波场区块链上被确认，验证逻辑应关注交易的状态，这表明交易是否已被 Tron 虚拟机（TVM）成功处理。以下是正确的验证方法： 检查 receipt.result 验证交易成功的主要标志是 receipt.result 字段。值为 “SUCCESS”...
4. 在英国给孩子换学校的经历: 孩子离开了村里的小学 由于搬了家, 孩子上学得提前半小时出门了, 因为早上堵, 也得开车半小时才能到. 之前在 Fen Drayton 村庄上小学, 早上8:45学校门开, 9点敲钟孩子排队依次进入教室, 我们由于在村里, 只需要提前5分钟出门和孩子一起走路就可以了. 现在一下子早上变得很匆忙, 得叫孩子起床, 做早饭,...
5. 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. 1 2...
6. 公司请的专业摄影师 公司来了新的CEO管理之后,很多事情都不一样了, 特别是一些公司对外形象的事情就特别的在意, 比如公司网站用上SSL.现在公司还有空闲的位置,请速来(钱多人不傻). 一月份出差回LUTON,刚好公司请来摄影师给高层管理照像放网站上的,于是我也凑了凑热闹(但是却还不够资格被放在公司网站上),不过没关系,放这里也差不多. 人到中年, 沧桑感强了些. 更新更新: 同事用他NB的单反给谢菲尔得办公室的人也拍了一组这样的照片.看起来很不错, 很专业,灯光,道具应有尽有.我已经用在了LINKEDIN页面上,立马高大上. 本文一共 230 个汉字, 你数一下对不对. 公司请的专业摄影师. (AMP...
7. 力扣 Leetcode 的刷题利器: 在线调试器和自动代码提示完成 力扣代码调试器 Debugger 最近 leetcode 刷题网站出了一个在线调试器. 个人感觉非常好用. 因为我平时是用 IPAD+蓝牙键盘来刷题, 而在 ipad 上是没有集成的IDE的, 对于调试来说, 只能很原始的让函数退出一个值, 然后尝试不同的输入来发现问题. leetcode在线调试器的好处...
8. 35岁生日: 媳妇和孩子就是最好的礼物 35岁生日, 感觉是一道坎. 之前20多岁的时候得过且过, 总是对自己说, 反正还没30, 过了30岁生日, 总是会对自己说, 反正还没35, 还年轻. 但是该来的总是要来的. 35岁, 不再年轻, 这个月感冒2次, 很不正常, 年轻的时候身体几乎不生病,...

我时不时会收到一些诈骗邮件，大多数情况下，Gmail 会自动将它们归类为垃圾邮件。不过，我经常会去翻一翻垃圾邮件夹，以免错过一些正常的邮件。现在谷歌的算法非常先进，其 AI 模型（基于贝叶斯邮件分类算法 Naive Bayes）的准确率已经超过了 99%。

OpenSea 的钓鱼邮件，声称有人愿意花 0.55 个 ETH 购买我的 NFT

像上面这样的邮件一看就很假，这其中一个很大的原因是，邮件被归到垃圾邮件夹后，图片不会自动加载，看起来就更加可疑。当然，也不能排除有些人的邮箱过滤能力没这么强，因此更容易上当受骗。更何况，我根本不记得自己在 OpenSea 上卖过东西。我记得 OpenSea 确实可以上传图片，但如果想把它们铸造成 NFT，是需要支付 Gas 费用的（以太网ETH上的）。而我肯定没有付过费，所以这封邮件一定是假的。

希望大家都能多加小心，现在的骗子无孔不入。他们广撒网，用的是最简单却有效的策略：只要数量足够大，即使成功的概率很低，抓住一个就是赚到了。这种小概率事件在样本基数足够大的情况下，总会发生。虽然有些邮件看起来明显是假消息，但这也是骗子的一种筛选方式，用来过滤掉更加谨慎的人，专挑那些容易上当的目标下手。

查了一下GMAIL的垃圾邮件箱，发现不止一封，每次的金额都不一样。

小心诈骗/骗局

• OpenSea一眼假的钓鱼邮件(NFT)
• 在币圈第一次被骗1355 USDT(1000英镑)的惨痛经历(Wirex)
• 96100海外骗局-差点就被骗了
• 警惕区块链上的小额诈骗转帐
• 诈骗者正在利用多重签名钱包(Tron/波场): 保持警惕!
• Linkedin 竟然也有杀猪盘SCAM

英文：A blatantly fake phishing email from OpenSea (NFT)

相关文章：

1. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
2. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
3. 英国驾照过期后更新的经验 英国驾照(除学车L驾照)是可以做为正式的ID的. 上个月去银行办点事才发现我的英国驾照已经过期2年了. 英国驾照卡上的4b是有效期, 银行柜员无意发现过期了, 所以当时只能回家取护照再折回. 回家后立马去邮局拿了 D1 表格, 填了资料, 需要最新的一张照片, 然后还需要支付17英镑费用(可以是支票 日期必须不能是将来, 或者是 邮局买的 Postal...
4. 在英国给孩子换学校的经历: 孩子离开了村里的小学 由于搬了家, 孩子上学得提前半小时出门了, 因为早上堵, 也得开车半小时才能到. 之前在 Fen Drayton 村庄上小学, 早上8:45学校门开, 9点敲钟孩子排队依次进入教室, 我们由于在村里, 只需要提前5分钟出门和孩子一起走路就可以了. 现在一下子早上变得很匆忙, 得叫孩子起床, 做早饭,...
5. SteemIt 高级定制微信文章列表 RSS/API/阅读器 v2.0 The Advanced Wechat Group Posts Feed/API/Reader v2.0 Abstract: I have added five parameters to the...
6. 英国房子的EPC节能报告(Energe/Efficiency Performance Certificate) EPC (Energe/Efficiency Performance Certificate) 是英国房子的节能报告, 法律上规定, 每个房子都必须要有一个EPC报告, 报告的有效期为十年. 房东在把房子出租或者想卖房的时候, 这个EPC就必须有效, 在一些情况下 比如出租房子的时候, 这个EPC报告还必须符合一些最低标准, 比如房子必须满足 F档(类似及格线)...
7. 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. 1 2...
8. 在英国带孩子去露营全攻略 之前就做了一些露营的准备工作, 因为大儿子Eric 很兴奋说是要去 Camping Holiday 估计是在 Papa Pig 里看到的. 英国有很多可以露营的地方, 最后面选了一个离家开车1个多小时. 看了评论还不错. 地址为: New Road,...

币圈的P站是Poloniex，前几年被孙宇晨收购了，它是一个交易所。我很久之前用过Poloniex，当时对其印象并不是很好。

不过，现在我对其好感增加，因为币安买下的coinmarketcap免费的接口就很多限制。

官方文档），这个接口的频率限制是一秒200次，很慷慨了。

https://api.poloniex.com/markets/price

能返回所有交易配对，比如这样的：

[
    {
        "symbol": "BTS_BTC",
        "price": "0.0000000186",
        "time": 1731852313035,
        "dailyChange": "-0.0462",
        "ts": 1731852313054
    },
    {
        "symbol": "DASH_BTC",
        "price": "0.000317",
        "time": 1731848096481,
        "dailyChange": "0.0063",
        "ts": 1731848096489
    },
    ... ...
]

这个JSON返回的结构是一个数组，每个元素是个结构体，也就是一个币价的具体配对信息，我们可以看成是一条边Edge两个顶点Vertice，这样就是一个图结构（带权图 Weighted Graph，权值就是兑换价格），虽然给的是单边，但其实是个双向的，比如USD_BTC得值可以反过来推得BTC到USD的价格。我们可以设计一个算法，从币价A到币价B，可以通过BFS广度优先搜索算法来获取价格。比如有配对A_B、B_C、C_D我们就可以获得A_D的值。

深度优先搜索算法DFS也可以，不过这个算法会返回找到的第一条路径，并不能保证是最短的，最短的确实是最准确的，因为链也长，转换精度就会下降。

当然，可能存在多条路径，最理想的状态是把这些路径都求出来，取个平均啥的，不过这样就得暴力搜索所有的路径了，算法时间复杂度就会比较高。

以下是BFS广度优先算法的代码，Javascript的，可以用于网页前端或者NodeJs后端，甚至是CloudFlare Serverless Worker或者是其它无服务框架：Azure Function、AWS Lambda等。

const fetch = require('node-fetch');

async function getTicker(a, b) {
  try {
    const response = await fetch('https://api.poloniex.com/markets/price');
    const data = await response.json();

    // 创建一个哈希表来存储代币对及其价格
    const pairMap = new Map();

    // 使用直接对及其反向对填充哈希表
    for (const { symbol, price } of data) {
      const [base, quote] = symbol.split('_').map(token => token.toLowerCase());
      if (!pairMap.has(base)) pairMap.set(base, new Map());
      if (!pairMap.has(quote)) pairMap.set(quote, new Map());
      
      pairMap.get(base).set(quote, parseFloat(price));
      pairMap.get(quote).set(base, 1 / parseFloat(price)); // 添加反向边
    }

    // 将 token 转换为小写
    a = a.toLowerCase();
    b = b.toLowerCase();

    // BFS 查找从 a 到 b 的转换率
    const queue = [[a, 1]]; // 从初始代币和兑换率 1 开始
    const visited = new Set([a]);

    while (queue.length > 0) {
      const [currentToken, currentRate] = queue.shift();

      if (currentToken === b) return currentRate;

      // Check connected tokens
      for (const [nextToken, rate] of (pairMap.get(currentToken) || new Map())) {
        if (!visited.has(nextToken)) {
          visited.add(nextToken);
          queue.push([nextToken, currentRate * rate]);
        }
      }
    }

    // 如果未找到路径，则返回 null
    return null;
  } catch (error) {
    console.error("获取或处理数据时出错:", error);
    return null;
  }
}

// Example usage:
(async () => {
  const rate = await getTicker('btc', 'trx');
  console.log('BTC 到 TRX 的兑换率:', rate);
})();

代码的一些简单说明：

• API 数据提取：从 P站 API 提取数据并将响应解析为 JSON。
• 映射对：以每个代币作为键创建一个映射，其中值是它可以直接转换为的另一个代币映射，以及兑换率。
• 双向映射：通过反转反向转换的价格来存储直接对和反向对。
• 广度优先搜索：使用队列遍历从 a 到 b 的路径。对于每个代币，都会检查其邻居（可转换代币）。如果找到 b，该函数将返回累积率；如果没有，则继续，直到所有选项都用尽。
• 处理无路径：如果未找到转换路径，则函数返回 null。

如果有多组兑换，我们可以改成传入一个数组，这样就不用多次调用P站的API了。

const fetch = require('node-fetch');

async function getToken(pairs) {
  try {
    const response = await fetch('https://api.poloniex.com/markets/price');
    const data = await response.json();

    // 创建一个哈希表来存储代币对及其价格
    const pairMap = new Map();

    // 使用直接对及其反向对填充哈希表
    for (const { symbol, price } of data) {
      const [base, quote] = symbol.split('_').map(token => token.toLowerCase());
      if (!pairMap.has(base)) pairMap.set(base, new Map());
      if (!pairMap.has(quote)) pairMap.set(quote, new Map());
      
      pairMap.get(base).set(quote, parseFloat(price));
      pairMap.get(quote).set(base, 1 / parseFloat(price)); // 添加一条反向边
    }

    // 使用 BFS 查找单个对的转换率的辅助函数
    const findConversionRate = (a, b) => {
      a = a.toLowerCase();
      b = b.toLowerCase();
      
      if (a === b) return 1; // 直接转换

      const queue = [[a, 1]];
      const visited = new Set([a]);

      while (queue.length > 0) {
        const [currentToken, currentRate] = queue.shift(); // 出队列

        if (currentToken === b) return currentRate;

        for (const [nextToken, rate] of (pairMap.get(currentToken) || new Map())) {
          if (!visited.has(nextToken)) {
            visited.add(nextToken);
            queue.push([nextToken, currentRate * rate]);
          }
        }
      }

      return null; // 路径没找到
    };

    // 迭代列表并查找转换率
    const results = pairs.map(([a, b]) => findConversionRate(a, b));
    return results;
  } catch (error) {
    console.error("Error fetching or processing data:", error);
    return pairs.map(() => null); // 如果有错误，则返回每对的 null
  }
}

// Example usage:
(async () => {
  const conversionRates = await getToken([['btc', 'trx'], ['usd', 'steem']]);
  console.log('兑换结果：', conversionRates);
})();

简单的代码说明：

• 参数更新：getToken 现在接受成对的元组数组，其中每个元组代表一对 [a, b]。
• 辅助函数：findConversionRate 处理每对的转换，实现与以前相同的 BFS 方法。
• 映射每对：函数迭代数组里的每个配对币，应用 findConversionRate 计算转换率，并将结果存储在数组中。
• 错误处理：如果出现 API 或处理错误，则返回一个空值数组，与输入数组的长度匹配。

这个修改后的函数现在可以接受一个数组，并在一次Poloniex API调用中返回数组里每个配对的兑换率。

英文：Crypto Token Exchange Rate Computation Based on Breadth First Search Algorithm on Poloniex API

区块链技术

• 波场TRX和火币HTX可能是下一个百倍币
• 诈骗者正在利用多重签名钱包(Tron/波场): 保持警惕!
• 简介: 区块链DeFi交易中的无常损失/Impermanent Loss
• 基于P站(Poloniex)的广度优先搜索算法来获得任意两种币的兑换价格
• 加密货币只是区块链的冰山一角
• 警惕区块链上的小额诈骗转帐
• 区块链: 硬分叉与软分叉
• 区块链中Layer 1和Layer 2协议的简介
• 孙老板/师卖在区块链上卖沙子 (营销/沙币/孙哥/ICO)
• 和媳妇聊聊 区块链 (Web3.0, 还有共识算法 PoW, PoS, DPoS)
• 我玩区块链虚拟货币的原则
• SteemIt 就可以把图片也存在区块链上了
• Steem转波场U的信任问题(Steem/SBD to USDT TRC-20)

Crypto虚拟货币交易所

• 交易所退币: 为啥要原路退回, 不能直接充到交易所帐号上么?
• 浅谈虚拟货币交易所三角套利的算法
• 通过程序来减少到交易所转帐出错的可能
• 帐号被Wirex解封的经历
• Steem转波场U的信任问题(Steem/SBD to USDT TRC-20)
• 通过在Wirex X 账户上质押代币(USDT 等)赚取被动收入
• 订单簿简介(Order Book)+最简单的高频交易策略HFT(低买高卖)
• Coinbase 支持 比特币现金 BCH的交易了!
• 基于P站(Poloniex)的广度优先搜索算法来获得任意两种币的兑换价格

交易所跑路啦

• 交易所Ionomy跑路, 又丢了好多币, 哎
• Bittrex Global交易所即将关门大吉-请把币都转走-把价值不到7美元的BTC提现全过程
• 币放在 BitAsset 交易所里拿不出来

相关文章：

1. HPZ800服务器主板太老不支持超过2TB的大硬盘 我家里一直用的是HPZ800服务器, 很吵, 很老, 虽然这台服务器已经有十年之久(我在EBAY上买来用了五年多了), 但是即使放到今天, 这服务器速度依旧很快, 很稳定. 由于服务器用的是ECC较验内存, 所以基本上不重启关机. HPZ800主机有两个硬核CPU – 因特志强 X5650 – 每个CPU是12核....
2. 给孩子零花钱培养孩子正确的金钱观价值观 两个娃已经不知不觉7岁8岁了. 媳妇和我商量一下决定给孩子每人每周5英镑的零花钱(Pocket Money). 这样他们慢慢的就有自己的小积蓄备将来不时之需: 比如朋友聚会生日啥的需要准备礼物. 同时, 我们决定不再给孩子买零食(薯片啥的). 孩子一天好几餐, 晚上睡觉前还得吃零食, 我们就多买了很多水果面包, 健康的食物多吃一些总不是啥坏事. 孩子可以用这些零钱买自己想要的东西, 我们也不再过问. 孩子有自己的决定权. 第一周的时候,...
3. 测测你的幸运 – Linux Fortune-Teller LINUX 下有很好很好玩的命令,之前已经介绍过: figlet, rig, curl. 现在推荐另一个 命令 fortune 是用来随机显示一段(句)话的.fortune 在英文里就是幸运的意思. 这个命令可以不需要 参数 如果没有 可以通过 apt-get...
4. 负电价活久见: 安装Octopus智能电表省电费甚至赚钱 前几周我的电气公司 Octopus 终于来装智能电表了（Smart Meter），虽然是免费安装的，但是排队排了有两三年了吧。因为之前一直写邮件催的时候就老是说 Not Ready。 收到邮件说可以安装智能电表我还是相当开心和期待的，因为已经听说这玩意好，但是还是得亲身体验一下。工程师来安装大概不到2小时，其中需要停电闸一会儿，重新接下线。装好后，给了个小册子，自动切换到了 Agile 的电价，也就是每半小时的电价都不一样，提前一天可以在手机App和网站上查得。 正好在原来的电价计费合同快要结束前2天换到了智能电表计价 Octopus Agile方式，但是系统还是扣了我75英镑 Exit Fee （提前合同结束得交违约费），不过我一个电话打过去，公司很爽快就给我退了。...
5. ChatGPT-4 使用 Math Wolfram 插件解决数学脑筋急转弯问题 这篇文章, 我们看一个简单的数学问题(脑筋急转弯), 并用 Python 解决它. 我们看一下LLM(大型语言模型): ChatGPT3.5和ChatGPT4. 通过 ChatGPT-Plus 订阅(目前每月 20 美元 + VAT增值税), 我们可以启用...
6. 微软面试题: 三角形的面积是多少? 据说是一个印度人杀入微软最后的面试, 面试官给了这么一道小学数学几何题: 这哥门也有疑问 可是最后还是坚持 答案 30 (底 X 高 / 2) 不存在 这是个陷井: 这个直角三角形是不存在的. 两个小直角三角形的勾股定理:...
7. 给STEEM中文微信群加了个机器人 之前说到我的公众号 justyyuk 可以查询几种虚拟货币的实时价钱, 但是有点不方便, 因为很多朋友在群里聊天得切换到公众号, 这下好了, 今天往STEEM中文微信群(还有编程群)加了个机器人, 在聊天的时候想了解价钱就直接输入货币代号即可, 如: 既方便自己, 又能方便别人(省事, 价格信息会同时显示给其它成员). 注: 这机器人不是我做的, 只是我拉进来的,...
8. Javascript 中 sleep 函数实现 Javascript 中并没有 built-in 的 sleep 函数支持, 在 async/await/Promise 的支持之前, 我们可以用 busy-waiting 的方式来模拟: 1 2 3...

人工智能AI

几天前中午和同事一起吃饭，聊到了AI（人工智能），特别是过去两三年间非常火热的ChatGPT大语言模型。他提到，有一次他在火车站打算去机场，结果火车停运了，于是他用手机查询了一下Uber去机场的费用，大概是80英镑。碰巧旁边有一位女士也要去机场，他便询问能否拼车以平摊车费。神奇的是，那位女士也查了一下Uber的价格，结果她的报价是50英镑。

同事不明白为什么仅相隔几分钟，价格会有这么大的差异。我解释道，这可能是因为Uber知道你在微软工作，觉得你有支付能力。

其实一些公司早就有算法（甚至不用AI）来实施差别定价。如果判断你是老客户，可能认为你更有可能会下单，于是就提高价格。甚至公司还会根据用户所在地区显示不同的价格，因此有时使用VPN更换地区，可能会获得更便宜的报价。

随着AI技术的引入，AI对你的了解也在增加（如性别、年龄、兴趣爱好等），模型会预测你能接受的最高价格，从而为公司带来最大化利润。当然，最简单的避免入坑的方法就是多比价（货比三家）。

英文：人工智能和动态定价如何影响我们的日常成本: How AI and Dynamic Pricing Shape Our Everyday Costs

相关文章：

1. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
2. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
3. SteemIt 高级定制微信文章列表 RSS/API/阅读器 v2.0 The Advanced Wechat Group Posts Feed/API/Reader v2.0 Abstract: I have added five parameters to the...
4. 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. 1 2...
5. 在英国带孩子去露营全攻略 之前就做了一些露营的准备工作, 因为大儿子Eric 很兴奋说是要去 Camping Holiday 估计是在 Papa Pig 里看到的. 英国有很多可以露营的地方, 最后面选了一个离家开车1个多小时. 看了评论还不错. 地址为: New Road,...
6. LOGO 海龟作画 系列三 递归画一个国际象棋棋盘 今天我们要来讲一讲递归. 递归就是函数自己调用自己, 我们可以定义一个过程, 然后这只海龟不停的画, 结束的时候再调用自身再继续画. 再次调用的时候参数变化了, 至到参数满足一定的条件则停止. 比如 下面定义的这个过程可以用来画一个实现的正方形. TO FK :B IF :B>15 ;...
7. ACM题解系列之 – 最小堆栈 (Min Stack) 没事刷刷题能防止老年痴呆, 而且也能让你随时处于最佳状态, 随时都可以炒老板鱿鱼另谋高就. 题目: 设计一个堆栈(Stack)使 push, pop, 和取最小 min 操作时间复杂度都是 O(1). 这题的难点就是在于怎么样用O(1)常数时间复杂度来取得堆栈里的最小值. class MinStack {...
8. 在英国开车的简单介绍/英国开车上路需要准备什么? 在英国合法上路需要有: 有效的驾照; MOT 车的年检; 路税 (Road Tax);还有最重要的汽车保险; 四者缺一不可. 千万不要有侥幸心理, 因为警察现在都高科技, 都能扫描车牌就能知道你合不合法. 不合法直接拦下来轻则罚款, 重则扣车上述法庭. 驾照 在英国可以用欧盟的大部分驾照,...

数学中的迭代幂运算/重幂是什么？

迭代幂运算（重幂）是数学中的一种运算，涉及到反复进行幂次运算。它是超运算序列的一部分，该序列延伸了加法、乘法和幂运算。在迭代幂运算中，一个数自乘多次，直到达到指定的次数。

一个数a迭代幂的高度n通常表示为：，也就是把n写在a的左上角，（也可以记作：a↑↑n）这表示a被迭代n次。

例如：

• （简单恒等式）
• （a自乘一次）
• （a的幂次为a自乘）
• ，依此类推。

在迭代幂运算的上下文中， 通常未定义或没有普遍共识。然而，一些数学惯例建议对于任何 ，，类似于在幂运算中对任何非零的 有 的情况。

迭代幂运算示例

让我们评估 （读作“2迭代到高度3”）：

因此

迭代幂/重幂运算的通用性质

• 非交换性：迭代幂运算不是交换的，这意味着
• 增长速度非常快：迭代幂运算增长非常快。即使是小数也会因为幂运算的快速增长而导致非常大的结果。

迭代幂运算/重幂在基础数学中较少见，但在某些高级数学领域中发挥作用，特别是在涉及极大数的领域，如大数理论和计算机科学中。

用 Python 计算迭代幂运算

以下是两个计算迭代幂运算的Python函数。第一个使用递归，第二个使用迭代。

在两个函数中，我们在开始时添加了对 n = 0 的检查。如果 n 为 0，则函数返回 1，否则继续处理。这种方式使函数能够按照任意数的迭代幂高为0时为1的惯例处理 n=0 的情况。

递归函数计算迭代幂

递归函数：此函数将自己调用，n 的高度递减1，直到达到1，此时返回基数a。这就实现了从上到下构建指数链的效果。

@lru.cache(None)  ## 缓存函数
def tetration_recursive(a, n):
    if n == 0:
        return 1
    if n == 1:
        return a
    return a ** tetration_recursive(a, n - 1)

递归计算迭代幂的函数理论上可以进行尾优化。在尾递归中，递归调用是函数中的最后一个操作，这样某些编译器或解释器可以通过重用相同的堆栈帧来优化调用堆栈的使用。这可以通过消除每个递归调用的额外堆栈帧需求来将空间复杂度降到 O(1)。

然而，当前的递归实现并不是尾递归的，因为递归调用嵌套在一个幂运算中：

return a ** tetration_recursive(a, n - 1)

这里，幂运算依赖于递归调用的结果，所以在完成当前调用之前必须计算出结果，从而阻止了尾递归优化。

迭代函数计算迭代幂

迭代函数：此函数使用 for 循环遍历高度 n，通过在每次迭代中更新幂运算的结果，来从下至上计算结果。

def tetration_iterative(a, n):
    if n == 0:
        return 1
    result = a
    for _ in range(1, n):
        result = a ** result
    return result

迭代幂算法的时间/空间复杂度

Python函数计算迭代幂的时间和空间复杂度取决于其递归或迭代实现。让我们分析两种实现。

递归函数的复杂度

时间复杂度：

• 每次递归调用都会与之前的调用结果进行一次幂运算。
• 总共有n-1次递归调用，所以该函数被调用了O(n)次。
• 然而，像 的幂运算需要 的时间。
• 因此，对于较大的 n 值，由于幂次的增长，其时间复杂度会呈指数增长。
• 这导致总的时间复杂度大约为 ，有n层，这意味着增长速度非常快

空间复杂度：

• 由于这是一个递归函数，每次调用都需要堆栈空间。
• 递归的最大深度为 n，所以空间复杂度为 O(n)。

迭代函数的复杂度

时间复杂度：

• 与递归版本一样，该函数迭代 n – 1 次
• 每次迭代涉及计算 的幂次，这个结果会呈指数增长。
• 因此，时间复杂度也成为 ，有n层，因为每一步都是指数级增长。

空间复杂度：

• 此迭代版本仅需要少量额外空间用于 result 变量等，因此它的额外空间复杂度为 O(1)。
• 然而，结果本身可能会变得非常大，如果 a 和 n 很大，可能需要大量内存来存储。

由于反复幂次的快速增长，这两种实现的时间复杂度都非常高，对于较大的值变得不可行。递归版本由于调用堆栈的使用空间复杂度为 O(n)，而迭代版本的辅助空间复杂度为 O(1)，但仍然需要处理极大数，这可能会间接影响内存使用。

英文：Tetration Operator in Math Simply Explained with Python Algorithms

相关文章：

1. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
2. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
3. 英国房子的EPC节能报告(Energe/Efficiency Performance Certificate) EPC (Energe/Efficiency Performance Certificate) 是英国房子的节能报告, 法律上规定, 每个房子都必须要有一个EPC报告, 报告的有效期为十年. 房东在把房子出租或者想卖房的时候, 这个EPC就必须有效, 在一些情况下 比如出租房子的时候, 这个EPC报告还必须符合一些最低标准, 比如房子必须满足 F档(类似及格线)...
4. 给孩子零花钱培养孩子正确的金钱观价值观 两个娃已经不知不觉7岁8岁了. 媳妇和我商量一下决定给孩子每人每周5英镑的零花钱(Pocket Money). 这样他们慢慢的就有自己的小积蓄备将来不时之需: 比如朋友聚会生日啥的需要准备礼物. 同时, 我们决定不再给孩子买零食(薯片啥的). 孩子一天好几餐, 晚上睡觉前还得吃零食, 我们就多买了很多水果面包, 健康的食物多吃一些总不是啥坏事. 孩子可以用这些零钱买自己想要的东西, 我们也不再过问. 孩子有自己的决定权. 第一周的时候,...
5. 拔牙后的注意事项(图, 慎入) Care of Mouth after Extraction 昨天又拔了两颗牙, 初步定在5月4号装牙套. 这是牙医诊所给的术后注意事项: 拔完后需要等3-4小时麻醉失效后才能吃喝. 稍微流点血是很正常的. 但是请不要漱口吐出, 因为这会加速流血. 你只要轻轻的含着口水并咽下即可. 如果一直流血, 请拿着纱布(并不是纸巾)放在拔牙处20分钟. 24小时内请不要运动, 术后几小时内回家静静坐着. 12小时内不要吸烟, 喝酒或者喝热饮, 因为这会让伤口流血....
6. 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. 1 2...
7. ChatGPT-4 使用 Math Wolfram 插件解决数学脑筋急转弯问题 这篇文章, 我们看一个简单的数学问题(脑筋急转弯), 并用 Python 解决它. 我们看一下LLM(大型语言模型): ChatGPT3.5和ChatGPT4. 通过 ChatGPT-Plus 订阅(目前每月 20 美元 + VAT增值税), 我们可以启用...
8. HPZ800服务器主板太老不支持超过2TB的大硬盘 我家里一直用的是HPZ800服务器, 很吵, 很老, 虽然这台服务器已经有十年之久(我在EBAY上买来用了五年多了), 但是即使放到今天, 这服务器速度依旧很快, 很稳定. 由于服务器用的是ECC较验内存, 所以基本上不重启关机. HPZ800主机有两个硬核CPU – 因特志强 X5650 – 每个CPU是12核....

计算机算法理论复杂度分析：P和NP问题

P、NP、NP-hard 和 NP-complete 是计算复杂性理论中的关键概念，用于描述不同类型的计算问题以及它们的求解难度。

P 类问题

P 类问题是指多项式时间内可以通过确定性算法解决的问题。这意味着，给定一个输入，问题可以在有限的步骤内得到解决，且步骤的数量是输入大小的多项式函数。换句话说，P 类问题的求解效率较高。例如，最短路径问题和排序问题都是 P 类问题。

NP 类问题

NP（Non-deterministic Polynomial time）类问题是指能够在多项式时间内验证解是否正确的问题。换句话说，虽然找到问题的解可能比较难，但一旦给出了解，我们可以在多项式时间内验证它是否正确。一个典型的 NP 问题是旅行商问题：找出某个城市之间的最短旅行路径可能很复杂，但给定一条路径，我们可以快速验证它是否满足要求。

NP-complete 问题

NP-complete 问题是 NP 类问题中的一种特殊类型。这类问题满足以下两个条件：

• 它是 NP 类问题，意味着给定解后可以在多项式时间内验证其正确性。
• 它是 NP 类问题中最难的问题，也就是说，如果我们能够找到某个 NP-complete 问题的多项式时间求解算法，那么所有 NP 问题都可以通过多项式时间内解决。

经典的 NP-complete 问题包括布尔可满足性问题（SAT）和哈密顿路径问题。

NP-hard 问题

NP-hard 问题是比 NP 类问题更难的一类问题。这类问题不一定属于 NP 类，即它们的解不一定能够在多项式时间内验证。例如，NP-hard 问题可以是一些更为广泛的问题（如优化问题），或者一些根本无法在多项式时间内验证解的准确性的问题。如果一个 NP-hard 问题有多项式时间的解法，那么所有 NP 问题都可以在多项式时间内解决。

P = NP 问题

计算机科学中最大的未解问题之一是P 是否等于 NP。如果 P = NP，那就意味着所有 NP 类问题实际上都可以在多项式时间内解决。然而，目前还没有证明这个命题是否成立。

O(N!)/O(2^N)算法是P还是NP？

如果一个算法的时间复杂度是 O(N!) 或 O(2^N)，它不属于 P（多项式时间）算法。以下是原因：

P（多项式时间）P 类问题可以在多项式时间内解决，即它们的时间复杂度是输入规模的某个多项式函数，例如 O(N)、O(N^2) 等。与非多项式函数相比，这些增长相对较慢。

O(N!)（阶乘时间）和 O(2^N)（指数时间）的增长速度远远快于任何多项式函数。O(N!) 增长非常快，其中 N! 是 N 的阶乘。

O(2^N) 是指数增长，随着 N 的增加，它也会变得不可计算。

由于这些复杂度比任何多项式函数的增长速度要快得多，具有这些时间复杂度的算法不属于 P 类。

它是 NP 吗？

要判断这样的算法是否属于 NP，重要的是要理解 NP 并不指问题的求解时间，而是指一旦给出解后，验证解是否正确的时间。

如果某个问题的时间复杂度为 O(N!) 或 O(2^N)，它可能属于 NP，也可能不属于，这取决于给出解后能否在多项式时间内验证。如果可以在多项式时间内验证解，那么这个问题可能属于 NP 类，尽管求解非常困难。

O(N!) 或 O(2^N) 不属于 P 类，因为求解该问题所需的时间增长速度太快，无法视为“高效”。

它是否属于 NP 取决于解能否在多项式时间内验证。如果验证过程是多项式时间的，那么该问题属于 NP 类，但并不是所有 O(N!) 或 O(2^N) 问题都在 NP 中。

总结

• P 类问题：可以在多项式时间内求解的问题。
• NP 类问题：解可以在多项式时间内验证的问题。
• NP-complete 问题：最难的 NP 问题，能够解决它就能解决所有 NP 问题。
• NP-hard 问题：不一定属于 NP 类，但至少和 NP-complete 问题一样难。

这个分类系统帮助我们理解各种问题的计算复杂性以及它们之间的关系。

英文：P versus NP problem (NP Complete, NP Hard)

相关文章：

1. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
2. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
3. SteemIt 高级定制微信文章列表 RSS/API/阅读器 v2.0 The Advanced Wechat Group Posts Feed/API/Reader v2.0 Abstract: I have added five parameters to the...
4. 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. 1 2...
5. 在英国带孩子去露营全攻略 之前就做了一些露营的准备工作, 因为大儿子Eric 很兴奋说是要去 Camping Holiday 估计是在 Papa Pig 里看到的. 英国有很多可以露营的地方, 最后面选了一个离家开车1个多小时. 看了评论还不错. 地址为: New Road,...
6. 在英国开车的简单介绍/英国开车上路需要准备什么? 在英国合法上路需要有: 有效的驾照; MOT 车的年检; 路税 (Road Tax);还有最重要的汽车保险; 四者缺一不可. 千万不要有侥幸心理, 因为警察现在都高科技, 都能扫描车牌就能知道你合不合法. 不合法直接拦下来轻则罚款, 重则扣车上述法庭. 驾照 在英国可以用欧盟的大部分驾照,...
7. LOGO 海龟作画 系列三 递归画一个国际象棋棋盘 今天我们要来讲一讲递归. 递归就是函数自己调用自己, 我们可以定义一个过程, 然后这只海龟不停的画, 结束的时候再调用自身再继续画. 再次调用的时候参数变化了, 至到参数满足一定的条件则停止. 比如 下面定义的这个过程可以用来画一个实现的正方形. TO FK :B IF :B>15 ;...
8. 老婆的配偶签证被拒 郁闷死了, 601镑签证费打水漂,一去不回!费钱费力. 去年12月份我请了律师拿到了永居.老婆是T1G签证的陪工签 (DEPENDENT VISA) 2016年4月份到期. 然后我就想说得趁早把她的签证转成配偶签(SPOUSE)这样她就可以尽快走五年永居的路线. 今天收到拒签信,原因是我没有提供 有工资进帐的那份银行帐单,我提供了我和我老婆的联名帐户, 但是工资并不是直接打到这个帐单上的.所以就这一点被拒了.完全不给解释,不给补材料的机会.601镑就这样再见了. 英国的签证寄出之后是先由另一个部门先收费, 收完费才正式审理,而且不管结果如何是不退钱的.后悔没让律师弄,也不至于到现在浪费这么多时间和金钱,签证还没过.由于原签证还没到期,所以还不能上述.估计只能等搬完家后年底请律师搞定这事. 真是郁闷, 600镑, 我可以再买一个IPHONE6,或者给我的新买的车换四个轮胎....

在面试流程（例如筛选）的早期阶段，一位 Google 招聘人员曾向我问过这个问题。

在C++中，当你使用std::map访问一个不存在的键时，行为取决于你是如何访问它的。

使用下标操作符 [] 访问时

如果键不存在，std::map 会默认插入一个该键的元素，并为其赋值为类型的默认值。比如，如果 map 的值类型是 int，那么它会插入该键并赋值为 0。

例子：

std::map<int, int> myMap;
int value = myMap[10]; // 如果键10不存在，会插入myMap[10] = 0

使用 at() 方法访问时

如果键不存在，at() 会抛出 std::out_of_range 异常。

例子：

std::map<int, int> myMap;
try {
    int value = myMap.at(10); // 如果键10不存在，会抛出异常
} catch (const std::out_of_range& e) {
    std::cout << "Key not found!" << std::endl;
}

使用 find() 方法

find() 方法不会修改 map，它返回一个迭代器。如果键不存在，它会返回 map.end()。

例子：

std::map<int, int> myMap;
auto it = myMap.find(10);
if (it == myMap.end()) {
    std::cout << "Key not found!" << std::endl;
} else {
    std::cout << "Value: " << it->second << std::endl;
}

C++ std::map 和 std::unordered_map的比较

std::unordered_map 处理不存在的键与 std::map 类似，但有一些差异，主要是因为它们内部的数据结构不同。

map 和 unordered_map 的区别：

• 顺序：std::map 是有序的（内部实现为平衡树），所以元素会按键的顺序排列。而 std::unordered_map 是无序的，使用哈希表存储元素，因此没有特定的顺序。
• 性能：std::unordered_map 通常有更快的平均访问时间（由于哈希结构，平均时间复杂度为 O(1)），而 std::map 的访问时间复杂度为 O(log n)，因为其内部实现为树结构。然而，如果发生大量哈希冲突，unordered_map 在最坏情况下的时间复杂度可能是 O(n)。

总的来说，std::unordered_map 和 std::map 在处理不存在的键时，对于 []、at() 和 find() 的行为相似，但它们在顺序和性能方面存在差异。

总结

• 使用 [] 访问时，如果键不存在，map 会插入一个新元素并赋予默认值。
• 使用 at() 访问时，如果键不存在，会抛出异常。
• 使用 find() 可以检查键是否存在，而不会修改 map。

英文：C++: Access a Non-existent Key in std::map or std::unordered_map

面试经历

• 记两次伦敦抖音面试经历(Tiktok)
• 我的面试谷哥GOOGLE伦敦SRE的经验和教训
• 记Facebook的第一轮技术面试(伦敦脸书)
• 记微软Principal SE的第一轮面试
• 我的AMAZON面试经历与经验之谈(亚麻伦敦面经)
• 离伦敦脸书最近的一次 - 记FACEBOOK伦敦终面经历

面试题

• 软件工程师面试: TCP/IP协议是什么?
• 软件工程师经典面试题: 当你在浏览器的地址栏敲入google.com并按回车后发生了什么?
• 谷歌面试题: 迷宫随机生成算法
• 软件工程师数据库面试技巧之 SQL中的第二名记录
• 软件工程师面试技巧之 动态规化 - 整数拆分
• 软件工程师面试技巧之 如何检查数独的有效性
• 去年 Google 的面试题 - 打印消息
• 软件工程师面试技巧之 使用哈希表降复杂度
• 微软面试题: 三角形的面积是多少?
• 英国 IT公司 电话面试的一些技巧 (程序员)
• C/C++ 中的内存管理器(堆与栈)
• C++的 map 当键(Key)不存在的时候会发生什么?
• 随机数独游戏的算法设计 (Sudoku)
• 经典二叉树的镜像的递归算法
• 谷歌的扔鸡蛋问题
• 面经: Python 的 List 和 Dictionary 有啥区别?
• 逻辑测试系列 - 一种只有4种语句的编程语言 - (1)
• 逻辑测试系列之二 - DECR
• 逻辑测试系列之三 - SUBT

面试技巧

• 面试后你不应该做的五件事
• 即使你不打算换工作, 你每年也得去面试

面试其它

• 产品设计和系统设计面的区别(Product Design vs System Design)
• 45 分钟模拟面试(编程、系统设计)+职业发展建议
• 英国和美国IT公司面试的主要区别
• 拒了甲骨文(Oracle)的 Offer

相关文章：

1. 步步高学生电脑上 Basic 编程语言 peek 用法示例 步步高学生电脑 是8位FC机的经典之作.它上面的BASIC有三个版本 1.0, 2.0 和 2.1 2.1 版本有个在线帮助,实际上是 help.cmd 1.0 是用 Esc 键退回到 DOS 的,...
2. 你给SteemIt中文微信群拖后腿了么? 这年头不缺算法, 就缺数据. 这两天花了很多时间在整API上, 整完之后自己用了一下还觉得真是挺方便的. 今天就突然想看一看自己是否给大家拖后腿了, 于是调用每日中文区微信群排行榜单的API, 刷刷拿着 NodeJs 练手: 1 2 3 4 5 6...
3. Javascript 中 sleep 函数实现 Javascript 中并没有 built-in 的 sleep 函数支持, 在 async/await/Promise 的支持之前, 我们可以用 busy-waiting 的方式来模拟: 1 2 3...
4. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
5. 《Steem 指南》之 justyy 在线工具与 API 系列 – 同时给多个帐号发送SBD或者STEEM 同时给多个帐号发送SBD或者STEEM STEEMIT 和 BUSY 的前端都有一个内置的钱包工具, 您可以一次给一个帐号发送 SBD 或者 STEEM. 当我们要给很多很多人发送钱的时候, 就显得有些不方便了. 这时候可以用这个在线工具: https://steemyy.com/wallet-tool/ 填写表单 只需要填上你的ID,...
6. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
7. 试用 Linkedin (领英) 高级帐号 (Premium) Linkedin (领英) 算是比较靠谱的职业社交网站, 在上面有很多猎头, 很多知名公司的HR 无时无刻在招人. 特别领英在被微软收购之后, 名气就变得大了许多. 领英是免费使用的, 但也有付费用户, 有给猎头的, 也有给想找工作的. 价格并不便宜, 对于想找工作的 Job...
8. 最简单有效的过滤WordPress垃圾评论的方法 当你的Wordpress博客流量大的时候, 不免会收到很多垃圾评论. 本文介绍一种特别简单而且免费的过滤Wordpress垃圾评论的方法. 这种方法不需要你安装任何插件, 也不需要拥有修改Wordpress主题模板函数的能力, 只需要1分钟就可以搞定. 把这个列表拷贝下来 打开 WordPress 的控制面版, 到设置-讨论 拷贝上面的列表到 “评论审核” 或者 “评论黑名单”...

“回溯 = DFS + 剪枝” 是一个对回溯算法简明且直观的描述。要理解这一点，我们可以先拆解这个等式中的几个关键概念。

深度优先搜索 (DFS)

DFS（Depth-First Search）是一种图或树的遍历算法，它从根节点开始，沿着一个分支深入到尽可能远的节点，直到达到叶子节点或无可拓展的节点，然后回溯到上一个节点继续搜索其他分支。这种搜索策略自然地适合解决需要遍历所有可能状态的问题，如组合、排列问题等。

剪枝/Pruning

剪枝（Pruning）是指在搜索过程中，提前排除不符合条件的分支，以减少计算量。剪枝的主要作用是在搜索的过程中，避免无谓的计算。通过某些条件判断，可以在尚未完全展开某些分支时就停止搜索，从而减少时间复杂度。例如，当我们知道一个分支肯定不会产生有效解时，可以提前终止该分支的搜索过程。

回溯算法/Backtracking

回溯算法可以看作是深度优先搜索DFS的一种特例或具体应用。它采用DFS的思想，在搜索的过程中尝试每一种可能的选择（通常是通过递归实现），并在发现某个选择不符合条件或已经无法产生有效解时，及时回退（即“回溯”），然后继续尝试其他选择。这种“试探—回溯”的过程就构成了回溯算法。

结合三者的理解

DFS 为回溯算法提供了基本的搜索框架，即从起点开始沿着一个分支深入探索；

剪枝 则是在DFS基础上增加的优化步骤，目的是减少无效状态的探索。

因此，“回溯 = DFS + 剪枝” 是对回溯算法的一种总结。它表明回溯算法不仅仅是简单的深度优先搜索，还通过剪枝来提升效率。剪枝使得回溯算法在解决很多问题时比单纯的DFS更加高效，尤其是在解空间很大的情况下，剪枝能够大幅减少计算量，从而使得问题求解变得可行。

例子：Alpha-beta 算法剪枝

Alpha-beta 剪枝可以看作是一种回溯算法，它通过剪枝技术增强了深度优先搜索算法。

alpha-beta-pruning

Alpha-beta 剪枝：这是用于减少博弈论中极小极大算法中评估节点数量的一种技术。

回溯算法：Alpha-beta 剪枝确实可以被视为回溯的一种形式，因为它系统地探索潜在解决方案（在本例中为游戏动作）并修剪保证不会影响最终决策的路径。

深度优先搜索 (DFS)：Alpha-beta 剪枝通常使用 DFS 对树结构进行操作，在回溯之前深入探索节点。

剪枝技术：Alpha-beta 剪枝的主要特征是“剪枝”部分，其中跳过不可能影响最终决策的树的分支。

英文：Backtracking Algorithm = Depth First Search + Pruning

相关文章：

1. 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
2. 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
3. 软件工程师面试技巧之: 使用哈希表降复杂度 最近在刷题, 倒不是为了找工作, 主要是为了练练脑子, 日子过得太舒服, 人脑不动容易变笨. 程序员应该都了解并能熟悉使用 Hash 哈希表, 哈希表的插入和查找时间复杂度是O(1), 空间复杂度是O(N). 我们来看一道简单的面试题: 给定一个数组,找出相差为2的数对,比如: {1, 3, 5,...
4. 升级到 Delphi 10 西雅图 公司前不久买了DELPHI XE8 (花了1400多英镑 一套). 并且买一送一, 我选择了 Delphi 2007. 因为D2007是 ANSI版本中最好的WIN32开发利器. 由于当时选了一年的升级服务 所以昨天发布的 Delphi 10 Seattle...
5. 英国房子的EPC节能报告(Energe/Efficiency Performance Certificate) EPC (Energe/Efficiency Performance Certificate) 是英国房子的节能报告, 法律上规定, 每个房子都必须要有一个EPC报告, 报告的有效期为十年. 房东在把房子出租或者想卖房的时候, 这个EPC就必须有效, 在一些情况下 比如出租房子的时候, 这个EPC报告还必须符合一些最低标准, 比如房子必须满足 F档(类似及格线)...
6. 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. 1 2...
7. Javascript 中 sleep 函数实现 Javascript 中并没有 built-in 的 sleep 函数支持, 在 async/await/Promise 的支持之前, 我们可以用 busy-waiting 的方式来模拟: 1 2 3...
8. 在英国开车走公交通道 Bus Lane 被罚款的经历 昨天才发现有一封信没有打开, 打开后心凉了一下, 原来是媳妇开车不小心走 Bus Lane (公交通道)被摄像头拍到, 需要交罚款. 走公交通道 Bus Lane可以申诉么? 信上说, 如果有足够的理由, 可以在28天内提交相关的证据来申诉抗议, 会有人来审核, 当然不一定能保证通过....

目录

从做过的工作说起

再谈这个职位

参考

目录

堆排序概述

堆排序实现

 1: def parent(heap, node):
 2:     if node > 0:
 3:         return (node - 1) / 2
 4:     else:
 5:         return 0
 6: 
 7: def lchild(node):
 8:     return 2 * node + 1
 9: 
10: def rchild(node):
11:     return 2 * node + 2

 1: def heapify(heap, root, size):
 2:     max_index = root
 3:     l = lchild(root)
 4:     r = rchild(root)
 5:     if  l < size and heap[l] > heap[max_index]:
 6:         max_index = l
 7:     elif r < size and heap[r] > heap[max_index]:
 8:         max_index = r
 9: 
10:     if root != max_index:
11:         heap[root], heap[max_index] = heap[max_index], heap[root]
12:         heapify(heap, max_index)
13: 
14:     return None

1: def build_heap(heap):
2:     size = len(heap)
3:     last = size / 2 - 1
4:     for cur in range(last, -1, -1):
5:         heapify(heap, cur, size)

 1: def hsort(arr):
 2:     size = len(arr)
 3:     last = size - 1
 4:     build_heap(arr)
 5: 
 6:     while size > 1:
 7:         arr[0], arr[last] = arr[last], arr[0]
 8:         last = last - 1
 9:         size = size - 1
10:         heapify(arr, 0, size)
11: 
12:     return None

发散：TOP K问题

目录

归并排序

算法思想

1: def msort(array):
2:     length = len(array)
3:     if length == 1:
4:         return array
5:     else:
6:         mid = length / 2
7:         left = msort(array[0: mid])
8:         right = msort(array[mid: length])
9:         return merge(left, right)

 1: def msort(array):
 2:     length = len(array)
 3:     step = 1
 4:     while step < length:
 5:         for left in range(0, length - step, 2 * step):
 6:             result = merge(array[left:left + step],
 7:                            array[left + step: min(left + 2 * step,
 8:                                                   length)])
 9:             array = array[0:left] + result + array[min(left + 2 *
10:                                                        step, length)]
11:         step = step * 2
12:     return array

 1: def merge(left, right):
 2:     llen = len(left)
 3:     lcur = 0
 4:     rlen = len(right)
 5:     rcur = 0
 6:     result = []
 7:     while lcur < llen and rcur < rlen:
 8:         lone = left[lcur]
 9:         rone = right[rcur]
10:         result.append(min(lone, rone))
11:         if lone < rone:
12:             lcur += 1
13:         else:
14:             rcur += 1
15:     result += left[lcur:]
16:     result += right[rcur:]
17:     return result

完整实现

 1: # -*- coding: utf-8 -*-
 2: def merge(left, right):
 3:     llen = len(left)
 4:     lcur = 0
 5:     rlen = len(right)
 6:     rcur = 0
 7:     result = []
 8:     while lcur < llen and rcur < rlen:
 9:         lone = left[lcur]
10:         rone = right[rcur]
11:         result.append(min(lone, rone))
12:         if lone < rone:
13:             lcur += 1
14:         else:
15:             rcur += 1
16:     result += left[lcur:]
17:     result += right[rcur:]
18:     return result
19: 
20: def msort_rec(array):
21:     length = len(array)
22:     if length == 1:
23:         return array
24:     else:
25:         mid = length / 2
26:         left = msort_rec(array[0: mid])
27:         right = msort_rec(array[mid: length])
28:         return merge(left, right)
29: 
30: def msort_iter(array):
31:     length = len(array)
32:     step = 1
33:     while step < length:
34:         for left in range(0, length - step, 2 * step):
35:             result = merge(array[left:left + step],
36:                            array[left + step: min(left + 2 * step,
37:                                                   length)])
38:             array = array[0:left] + result + array[min(left + 2 *
39:                                                        step, length):]
40:         step = step * 2
41:     return array
42: 
43: if __name__ == '__main__':
44:     L = [1, 4, 2, 6, 3, 5, 8, 7]
45:     print "排序前: %r" %(L)
46:     R = msort_rec(L)
47:     print "排序后(递归): %r" %(R)
48:     I = msort_iter(L)
49:     print "排序后(非递归): %r" %(I)

排序前: [1, 4, 2, 6, 3, 5, 8, 7]
排序后(递归): [1, 2, 3, 4, 5, 6, 7, 8]
排序后(非递归): [1, 2, 3, 4, 5, 6, 7, 8]

发散：外排序应用

 1: #include <stdio.h>
 2: #include <stdlib.h>
 3: #include <time.h>
 4: 
 5: int rand_file(char *file, int num)
 6: {
 7:     int i = 0;
 8:     int now;
 9:     FILE *f = fopen(file, "w");
10: 
11:     if (f == NULL) {
12:         perror("fopen");
13:         return 0;
14:     }
15: 
16:     for (; i < num; ++i) {
17:         srand((int)time(0));
18:         now = rand();
19:         fprintf(f, "%d ", now);
20:     }
21: 
22:     fclose(f);
23:     return num;
24: }

 1: #include <stdio.h>
 2: #include <stdlib.h>
 3: 
 4: int read_to_mem(FILE *file, int *arr, int len)
 5: {
 6:     int i = 0;
 7:     if (file != NULL) {
 8:         for (; !feof(file) && i < len; ++i) {
 9:             fscanf(file, "%d", arr + i);
10:         }
11:         return i;
12:     }
13:     else
14:         return 0;
15: }
16: 
17: int write_from_mem(FILE *file, int *arr, int len)
18: {
19:     int i = 0;
20:     if (file != NULL) {
21:         for ( ; i < len; ++i) {
22:             fprintf(file, "%d ", arr[i]);
23:         }
24: 
25:         return i;
26:     }
27: 
28:     else
29:         return 0;
30: }

 1: #include <stdlib.h>
 2: 
 3: void merge(File *out, File **flist, int fnum)
 4: {
 5:     int i = 0;
 6:     int now = 0;                /* 用于保存当前最小的值 */
 7:     int *fstaus = (int *)calloc(fnum, sizeof(int)); /* 记录文件状态 */
 8:     int *farr =(int *)calloc(fnum, sizeof(int));    /* 记录从各个文件中取出的数 */
 9:     int min = 0;                /* 记录当前值最小的文件索引 */
10: 
11:     for (; i < fnum; ++i) {     /* 检查各个文件指针的状态 */
12:         if (feof(fscanf(flist[i], "%d", farr + i))) {
13:             fstatus[i] = 0;
14:         }
15:         else {
16:             fstatus[i] = 1;
17:         }
18:     }
19: 
20:     while (1) {
21:         now = 0;
22:         for (i = 0; i < fnum && !fstatus[i]; ++i) {}
23:         if (i >= fnum) {     /* 如无可用文件，则退出 */
24:             break;
25:         }
26: 
27:         for (; i < fnum; ++i) { /* 从第一个可用的文件开始读 */
28:             if (fstatus[i] && farr[i] < now) {
29:                 now = farr[i];
30:                 min = i;
31:             }
32:         }
33: 
34:         fprintf(out, "%d ", now); /* 将最小值写入输出文件 */
35: 
36:         /* 读取该文件下一个数，并检查是否读完 */
37:         if (feof(fscanf(flist[min], "%d", farr + min))) {
38:             fstatus[min] = 0;
39:         }
40:     }
41: 
42:     free(farr);                 /* 释放内存 */
43:     free(fstatus);
44: }

References

目录

快速排序

原理

1: def qsort(array, low, high):
2:     if low < high:
3:         mid = partition(array, low, high)
4:         qsort(array, low, mid - 1)
5:         qsort(array, mid + 1, high)
6:     return array

 1: def partition(array, low, high):
 2:     cur = low - 1
 3:     key = array[high]
 4: 
 5:     for index in range(low, high):
 6:         elem = array[index]
 7:         if elem < key:
 8:             cur = cur + 1;
 9:             array[index], array[cur] = array[cur], array[index]
10: 
11:     cur = cur + 1;
12:     array[cur], array[high] = array[high], array[cur]
13: 
14:     return cur;

 1: # -*- coding: utf-8 -*-
 2: def partition(array, low, high):
 3:     cur = low - 1
 4:     key = array[high]
 5: 
 6:     for index in range(low, high):
 7:         elem = array[index]
 8:         if elem < key:
 9:             cur = cur + 1
10:             array[index], array[cur] = array[cur], array[index]
11: 
12:     cur = cur + 1;
13:     array[cur], array[high] = array[high], array[cur]
14: 
15:     return cur;
16: 
17: def qsort(array, low, high):
18:     if low < high:
19:         mid = partition(array, low, high)
20:         qsort(array, low, mid - 1)
21:         qsort(array, mid + 1, high)
22: 
23:     return array
24: 
25: L = [5, 2, 7, 6, 3, 1, 8, 4]
26: print "排序前: %r" %(L)
27: qsort(L, 0, 7)
28: print "排序后: %r" %(L)

排序前: [5, 2, 7, 6, 3, 1, 8, 4]
排序后: [1, 2, 3, 4, 5, 6, 7, 8]

发散